Alternating Markov process

Question

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)$?

Answer 1

Let $x_t$ be the probability that the light is on, and $y_t$ be the probability that the light is off, before step $t$.

If Alice enters the room: $$x_{t+1} = \frac 12 x_t + \frac 14 y_t$$ $$y_{t+1} = \frac 12 x_t + \frac 34 y_t$$

If Bob enters the room:

$$x_{t+1} = \frac 12 y_t + x_t$$ $$y_{t+1} = \frac 12 y_t$$

When Alice enters the room, $[x_{t+1} ~~ y_{t+1}] = [x_{t} ~~ y_{t}]A$ for some matrix $A$.

When Bob enters the room, $[x_{t+1} ~~ y_{t+1}] = [x_{t} ~~ y_{t}]B$ for some matrix $B$.

You want to find $A$ and $B$ and use that to find $[x_{\infty} ~~ y_{\infty}]$.

Answer 2

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).