Expected outcome of a random game Suppose we play a game where each time we take a turn, one of two possible outcomes occurs ($A$ or $B$). And suppose we know the following conditional probabilities:
If $A$ occurs, then $p(A \mbox{ occurs in the next turn}) = 0.7$ and $p(B \mbox{ occurs in the next turn}) = 0.3$.
If $B$ occurs, then $p(A \mbox{ occurs in the next turn}) = 1.0$ and $p(B \mbox{ occurs in the next turn}) = 0.0$.
Is it possible to determine, after an infinite number of turns, the expected proportion of the time that events $A$ and $B$ occur?
I have managed to simulate $1$ million turns of this game using a simple program and I get the following:
$p(A) = 0.7699$
$p(B) = 0.2301$
which seems to be intuitively correct.
However, I have no way of figuring out an exact solution to this. Any help would be greatly appreciated.
 A: What you've got here is a Markov chain with transition matrix
$$
M=
\begin{pmatrix}
0.7 & 0.3 \\
1 & 0
\end{pmatrix}
$$
and what you want is the limiting distribution of this chain.  That means you seek a matrix
$$
A = \begin{pmatrix}
a & b \\
a & b\\
\end{pmatrix}
$$
with $a+b=1$ such that
$$AM=A.$$
Thus, you want $0.7a+b=a$, and together with $a+b=1$, we find
$$
a= \frac{10}{13}, b = \frac{3}{13}
$$
which are the expected proportions of the time that $A$ and $B$ will occur, respectively.
A: The way to set up problems like these is to write it as a matrix. Say $p_n$ is the probability that $A$ happens on turn $n$, and that $q_n$ is the probability for $B$. What you gave us is the matrix equation $\begin{pmatrix}p_{n+1}\\ q_{n+1}\end{pmatrix}=\begin{pmatrix}0.7&1\\0.3&0\end{pmatrix}\begin{pmatrix}p_n\\ q_n\end{pmatrix}$. Right?
Now what are the eigenvectors of this matrix? You can check that the eigenvalues are $1$ and $-0.3$ with eigenvectors $\begin{pmatrix}\frac{10}{13}\\ \frac{3}{13}\end{pmatrix}$ and $\begin{pmatrix}1\\ -1\end{pmatrix}$. As you look higher and higher turns, whatever comes from the $-0.3$ will disappear, so the stabilizing probability vector is $A$ having probability $\frac{10}{13}$ and $B$ having probability $\frac{3}{13}$.
A: The probabilities can be denoted as vectors.
\begin{bmatrix}
           P(A)\\
           P(B)\\
\end{bmatrix}
If $P(A)$ is 1 on turn $n$, then $P(A) = 0.7, P(B) = 0.3$ on turn $n+1$. If P(B) is 1 on turn $n$, then $P(A) = 1.0, P(B) = 0$ on turn $n+1$. Hence if $T$ represents a "turn" in the game, \begin{align*} T & \begin{bmatrix} 1.0\\ 0.0\\ \end{bmatrix} = \begin{bmatrix} 0.7\\ 0.3\\ \end{bmatrix} \end{align*} Similarly, \begin{align*} T & \begin{bmatrix} 0.0\\ 1.0\\ \end{bmatrix} = \begin{bmatrix} 1.0\\ 0.0\\ \end{bmatrix} \end{align*} What if we start with a mixed probability? Suppose the initial condition at turn $n$ is \begin{bmatrix} p\\ 1-p\\ \end{bmatrix} Then there's a $p$ chance that the next turn will have $P(A) = 0.7, P(B) = 0.3$ and a $1-p$ chance that $P(A) = 1.0, P(B) = 0.0$. Hence the probabilities for the next turn are:
$P(A) = 0.7p + 1.0(1-p),\ P(B) = 0.3p + 0.0(1-p)$
If you haven't realised yet, this corresponds to \begin{align*} \begin{bmatrix} 0.7 & 1.0 \\ 0.3 & 0.0 \end{bmatrix} \begin{bmatrix} p \\ 1-p \end{bmatrix} = T & \begin{bmatrix} p\\ 1-p\\ \end{bmatrix}\end{align*}
The matrix $T$ is called a "stochastic matrix", because it evaluates probabilities and gives you new probabilities for a new moment in time. To find the probabilities of being in states $A$ or $B$ after infinitely many turns, you want to evaluate your probability vector by this matrix infinitely many times, that is,
\begin{align*} T^\infty & \begin{bmatrix} p\\ 1-p\\ \end{bmatrix} = \begin{bmatrix} 0.7 & 1.0 \\ 0.3 & 0.0 \end{bmatrix} \cdot \cdot \cdot \begin{bmatrix} 0.7 & 1.0 \\ 0.3 & 0.0 \end{bmatrix} \begin{bmatrix} p\\ 1-p\\ \end{bmatrix}\end{align*}
Of course, this is difficult to do, so you want to find the decomposition of the stochastic matrix. In this case, we find the two eigenvalues of the matrix are 1 and -0.3. The corresponding eigenvectors are $(10/13, 3/13)$ and $(1/2, 1/2)$ Suppose the initial condition is $(1, 0)$. (It can be shown that the initial condition is irrelevant but I'm using it here to make it more intuitive.) Then by solving for
\begin{align*}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = a_1 \begin{bmatrix} 10/13 \\ 3/13 \end{bmatrix}+ a_2 \begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}\end{align*} we can write the state in terms of eigenvectors. The solution is: \begin{align*}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \frac{13}{7} \begin{bmatrix} 10/13 \\ 3/13 \end{bmatrix}+ \frac{-6}{7} \begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}\end{align*} By the definition of eigenvectors and eigenvalues, it follows that for any number of turns $n$ starting in position A,
\begin{align*}\begin{bmatrix} 0.7 & 1.0 \\ 0.3 & 0.0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}= 1^n \frac{13}{7} \begin{bmatrix} 10/13 \\ 3/13 \end{bmatrix}+ (-0.3)^n \frac{-6}{7} \begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}\end{align*}
By taking the limit as n tends to infinity, the second term vanishes, and you are left with \begin{align*}\begin{bmatrix} 0.7 & 1.0 \\ 0.3 & 0.0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}= 1^n \frac{13}{7} \begin{bmatrix} 10/13 \\ 3/13 \end{bmatrix}\end{align*} This is a multiple of a single vector, so by scaling it ensure the entries add to 1, you see that:
\begin{align*}\begin{bmatrix} P(A) \\ P(B) \end{bmatrix}=\begin{bmatrix} 10/13 \\ 3/13 \end{bmatrix} = \begin{bmatrix} 0.7692 \\ 0.2308 \end{bmatrix}\end{align*} Just like your simulation showed!
You can also see how the "initial condition" simply affected the coefficients in front of the two eigenvectors, but the final state is scaled so the probabilities add to 1, meaning the initial conditions had no effect on the final "infinite turns" state.
