Thread View: sci.math.stat
2 messages
2 total messages
Started by Jon Leivent
Thu, 02 Apr 1992 22:02
help needed with Markov flipflop
Author: Jon Leivent
Date: Thu, 02 Apr 1992 22:02
Date: Thu, 02 Apr 1992 22:02
58 lines
2274 bytes
2274 bytes
I need some help finding an analytic solution for a seemingly simple
Markov chain problem. The chain (in discrete time) consists of two
states, A and B, arranged as a flip-flop. The one-step probabilities
are: A to A is q, A to B is 1-q, B to B is r, B to A is 1-r. Here's a
diagram of the chain:
q r
+-+ +-+
| | | |
| V | V
+---+ 1-q +---+
| +----->| |
| A | | B |
| |<-----| |
+---+ 1-r +---+
The initial condition is that we spend the first time step in state A.
I'm trying to find the probability distribution function P(C,S), which
gives the probability that after S steps, the count of the number of
steps spent in state A is C (C is thus the "total sojourn time" in
state A).
The initial condition, expressed in terms of P, is P(1,1)=1.
Obviously, there's also a normalizing condition, that the sum over all
C of P(C,S) is 1 for any S.
I've tried several different techniques. One way, I end up with a
linear partial difference equation for P that has a very complex
non-constant coefficient that prevents me from solving it. Another
way, I end up with a system of 2 linear partial difference equations
that I can solve, but I can't determine the correct linear combination
of the solutions to fit the initial values.
One thing I can find is the probability of being in state A at step S:
(S-1)
(q-1)(q+r-1) + r-1
Z(S) = ----------------------
q+r-2
I would appreciate any help anyone can give (I'd really appreciate a
solution).
Thanks in advance,
-- Jon
--
Jon Leivent
MS A156
The MITRE Corporation
202 Burlington Road
Bedford MA, 01730-1420
email: jil@mitre.org
tel: (617) 271-7648
fax: (617) 271-3816
Re: help needed with Markov flipflop
Author: David desJardins
Date: Thu, 16 Apr 1992 01:24
Date: Thu, 16 Apr 1992 01:24
53 lines
3036 bytes
3036 bytes
In article <JIL.92Apr2170245@mozart.linus.mitre.org> jil@linus.mitre.org (Jon Leivent) writes:
>I need some help finding an analytic solution for a seemingly simple
>Markov chain problem. The chain (in discrete time) consists of two
>states, A and B, arranged as a flip-flop. The one-step probabilities
>are: A to A is q, A to B is 1-q, B to B is r, B to A is 1-r.
>The initial condition is that we spend the first time step in state A.
>I'm trying to find the probability distribution function P(C,S), which
>gives the probability that after S steps, the count of the number of
>steps spent in state A is C (C is thus the "total sojourn time" in
>state A).
Let K be the number of times that we take the transition A->B.
Clearly we take B->A either K or K+1 times. Separate the problem into
these two cases. Let L = C-K be the number of times that we take the
A->A transition. L must be less than or equal to S-2K in the first
case and S-2K-1 in the second case.
Given the number of times each of the four transitions is taken, we
can count the number of ways of dividing the L A->A transitions into K
runs as a binomial coefficient. Similarly for the number of ways of
dividing the B->B transitions. Thus we compute the number of state
sequences and hence the probability of K and L. We sum this over K.
The result:
K C-K K S-C-K
P(C,S) = Sum q (1-q) r (1-r) B(C,K) B(S-C-1,K-1)
K
K+1 C-K K S-C-K-1
+ Sum q (1-q) r (1-r) B(C,K) B(S-C-1,K)
K
where B(N,M) is the binomial coefficient N!/M!(N-M)! and the sums are
over all terms for which the binomial coefficients are defined.
It is standard to express hypergeometric sums such as these in terms
of the hypergeometric function. If I haven't made any mistakes:
C-1 S-C-1 q r
P(C,S) = C q r (1-q) (1-r) F ( 1-C, 1-S+C, 2; ---------- )
2 1 (1-q)(1-r)
C S-C-1 q r
+ q (1-q) (1-r) F ( -C, 1-S+C, 1; ---------- )
2 1 (1-q)(1-r)
For fixed S and C this expression reduces to a polynomial in q and r,
as it surely must from the statement of the problem. If we fix either
C or S-C, the expression reduces to a relatively simple function of q,
r, and S. For general S and C no further simplification is possible.
David desJardins
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads