| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
46 |
|
Paper 2, Section II, H |
2014 |
Let $\left(X_{n}: n \geqslant 0\right)$ be a homogeneous Markov chain with state space $\mathrm{S}$ and transition matrix $P=\left(p_{i, j}: i, j \in S\right)$. For $A \subseteq S$, let
$$H^{A}=\inf \left{n \geqslant 0: X_{n} \in A\right} \text { and } h_{i}^{A}=\mathbb{P}\left(H^{A}<\infty \mid X_{0}=i\right), i \in S$$
Prove that $h^{A}=\left(h_{i}^{A}: i \in S\right)$ is the minimal non-negative solution to the equations
$$h_{i}^{A}= \begin{cases}1 & \text { for } i \in A \ \sum_{j \in S} p_{i, j} h_{j}^{A} & \text { otherwise. }\end{cases}$$
Three people $A, B$ and $C$ play a series of two-player games. In the first game, two people play and the third person sits out. Any subsequent game is played between the winner of the previous game and the person sitting out the previous game. The overall winner of the series is the first person to win two consecutive games. The players are evenly matched so that in any game each of the two players has probability $\frac{1}{2}$ of winning the game, independently of all other games. For $n=1,2, \ldots$, let $X_{n}$ be the ordered pair consisting of the winners of games $n$ and $n+1$. Thus the state space is ${A A, A B, A C, B A, B B, B C, C A, C B, C C}$, and, for example, $X_{1}=A C$ if $A$ wins the first game and $C$ wins the second.
The first game is between $A$ and $B$. Treating $A A, B B$ and $C C$ as absorbing states, or otherwise, find the probability of winning the series for each of the three players.