🚀 go-pugleaf

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