TITLE: Alternating Markov process
QUESTION [1 upvotes]: Given the situation:

When Bob enters the room and the light is off, he turns it on with $P = 1/2$
when it is on, he does nothing.
When Alice enters the room with light on, she turns it off with $P =1/2$ and when the light is off, she turns it on with $P= 1/4$
Bob and Alice alternatively enter and leave the room after each other many times

Find the P the light is on just after
- Alice enters
- Bob enters
I've retrieved the long run probabilities of both and know that the state $t+n$ is $Mb^n * Ma^n * state(t)$  where $Ma$ = Alice's Markov matrix - although I don't know how to define how many or how to equalize the long run probabilities when alternating?
Is it (for just after Alice enters) - the Ma* Bob's long run probabilities $(pi1,pi2)$?

REPLY [2 votes]: In order to make the entire process be Markov, you can raise the dimension, and consider a four state chain: the states are $(A,1),(A,0),(B,1),(B,0)$. (This is a common theme: you can increase the dimension to take away memory effects, or reduce the dimension at the cost of adding memory effects.) The first component represents "Alice will come in next/Bob will come in next". The second component represents "the light is on/the light is off". So for instance $(A,1)$ is "Alice is coming in next and the light is on". Then your transition matrix for this chain is
$$P=\begin{bmatrix}
0 & 0 & 1/2 & 1/2 \\
0 & 0 & 1/4 & 3/4 \\
1 & 0 & 0 & 0 \\
1/2 & 1/2 & 0 & 0 \end{bmatrix}$$
For instance the second row reads "if Alice is about to come in and the light is off, then at the next step, with probability 1/4, Bob is about to come in and the light is on, and with probability 3/4, Bob is about to come in and the light is off."
Here I am using the convention that $P_{ij}$ is the probability to go from $i$ to $j$, so that if the distribution is currently the row vector $q$ then at the next step it is $qP$.
Now a full step where Alice goes in and Bob goes in evolves the distribution according to $P^2$. So given an initial distribution $q$ which is confined to $\{ (A,1),(A,0) \}$ (meaning that Alice will always come in first), calculate $q_A=\lim_{n \to \infty} q P^{2n}$. This will be the limiting distribution that Alice sees. Then calculate $q_B=q_A P$; this will be the limiting distribution that Bob sees.
Importantly, the fact that the first component of this process is a "deterministic oscillator" (always flipping back and forth between $A$ and $B$) causes $P$ to have an eigenvalue of $-1$. This causes $q_A$ and $q_B$ to not simply be the same. If Alice came in twice in a row even one in every million visits, $q_A$ and $q_B$ would be equal (but the convergence would be very slow).
{"set_name": "stack_exchange", "score": 1, "question_id": 1283660}