🚀 go-pugleaf

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