I'm having trouble with the following problem:
Three players, $A, B, C$ are taking turns playing chess. The winner will always go on to play the third player. Suppose that $A$ beats $B$ with probability $1/2$, $B$ beats $C$ with probability $1/2$ and $C$ beats $A$ with probability $1/4$. Let $p_n$ denote the probability that $A$ is playing in the $n^{th}$ match. Find $p_n$ given that $A$ and $B$ are playing the first match.
I'm trying to set up a recurrence equation for $p_n$. We are given that $p_1 = 1$. Let $A_n$ denote the event that $A$ is playing in the $n^{th}$ match. Then,
$$ p_n = P(A_n | A_{n-1})P(A_{n-1}) + P(A_n | A_{n-1}^c)P(A_{n-1}^c) = P(A_n | A_{n-1})p_{n-1} + 1- p_{n-1}$$
where the second equality comes from the fact that $A$ will always play the next match if he/she didn't play in the previous one.
My difficulty lies in the computation of $P(A_n | A_{n-1})$. Am I right to condition on $A_{n-1}$, or is there some other event that would make things simpler? I know that $P(A_2 | A_1) = 1/2$ and $P(A_3 | A_2) = 3/4$. But things become rather complicated from here.
Apologies in advance for the sort of clunky notation. Let $A_n$ be the event that player A is in the $n^{th}$ round, $AB_n$ be the event that players $A$ and $B$ are in round $n$, $AC_n$ be the event that players $A$ and $C$ are in round $n$ and $BC_n$ be the event that players $B$ and $C$ are in round $n$. Also, let $p_{IJ}$ be the probability that player $I$ beats player $J$. As specified in the problem $p_{AB}=p_{BA}=p_{BC}=p_{CB}=1/2$, $p_{CA}=1/4$ and $p_{AC}=3/4$.
Now, to start setting up the necessary recursive equations, it would be a good idea to draw out the event tree: i.e., $A, B$ are in round $1$, which branches out to $A, C$ and $B, C$ in round 2, $\ldots$. The probability we desire is $P(A_n|AB_1)$, so I start by writing out a recursive equation with the law of total probability:
\begin{align*} P(A_n|AB_1) & = P(A_n|AB_1, AC_2)p_{AB}+P(A_n|AB_1, BC_2, AB_3)p_{BA}p_{BC}+P(A_n|AB_1, BC_2, AC_3)p_{BA}p_{CB} \\ &=P(A_{n-1}|AC_1)p_{AB}+P(A_{n-2}|AB_1)p_{BA}p_{BC}+P(A_{n-2}|AC_1)p_{BA}p_{CB}, \end{align*} where in the last line I have used the typical recursive strategy.
We now see that we will need another equation to solve for $P(A_{n}|AC_1)$. I suggest that you draw another event tree with $A, C$ in the first round so you can see how to write this equation. The proper equation is: \begin{align*} P(A_n|AC_1) & = P(A_n|AC_1, AB_2)p_{AC}+P(A_n|AC_1, BC_2, AC_3)p_{CA}p_{CB}+P(A_n|AC_1, BC_2, AB_3)p_{CA}p_{BC} \\ &=P(A_{n-1}|AB_1)p_{AC}+P(A_{n-2}|AC_1)p_{CA}p_{CB}+P(A_{n-2}|AB_1)p_{CA}p_{BC}. \end{align*}
We therefore have 2 coupled recursive equations, which, for clarity, I write in somewhat easier to read notation: \begin{equation*} \begin{cases} p_n^{AB}=p_{n-1}^{AC}p_{AB}+p_{n-2}^{AB}p_{BA}p_{BC}+p_{n-2}^{AC}p_{BA}p_{CB} \\ p_n^{AC}=p_{n-1}^{AB}p_{AC}+p_{n-2}^{AC}p_{CA}p_{CB}+p_{n-2}^{AB}p_{CA}p_{BC}, \end{cases} \end{equation*} with the following boundary conditions: $p_1^{AB}=1$, $p_2^{AB}=p_{AB}$, $p_1^{AC}=1$, $p_2^{AC}=p_{AC}$.
I solve the recursive equations numerically and have the following for the first few values of $p_n^{AB}$: \begin{equation*} 1,~0.5,~0.875,~0.625,~0.78125,~0.6875, \ldots. \end{equation*} I have verified that these values are correct up until $n=4$ by calculating $p_n^{AB}$ by hand by multiplying/adding the probabilities from the event tree starting with $A, B$ in the first round.
If you plot out the solution, you'll see that $p_n^{AB}$ oscillates with decaying amplitude about $\sim 0.722$ (this value could probably be computed exactly by taking limits), and converges pretty well to this value by around the 12$^{th}$ round.
Hope this made sense!