Markov chain game probability

Question

Jane and John are playing a card game. Jane is an expert and, on each game, has probability p = 0.7 of beating John. Suppose that Jane and John each begin with 10 dollars and agree that, on each game, the loser pays the winner $1. They agree to play until one of them is bankrupt. What is the probability that it will be John who goes bankrupt?

My approach to this question is that this seems to be a Dicrete Time Markov Chain. In that case, I let $X_n =$ the amount of money John has at game $n$. In that case, I am trying to find $\pi_0$ My logic is that am I trying to find the long run probability that John is in state 0, i.e. he is bankrupt. Finding this value is very complicated as there are 20 possible states for John to be in. Is my approach correct? Or is there a simpler way to do this?

Answer 1

This is not easy to solve recursively, but may be done using some matrix methods so far as I know. Let $P$ be the transition matrix for the amount of money that John has, with $.3$ being in the 'upper diagonal' and .7 being in the 'lower diagonal'. It will look something like

$\begin{bmatrix} 1 & 0 & \dots & & 0\\ .7 & 0 & .3 & \dots &0 \\ 0 & .7 & 0 & .3 & \dots 0 \\ \vdots \\ 0 &\dots & .7 & 0 & .3 \\ 0 &\dots & & & 1 \end{bmatrix}$

and your initial distribution is $e_{10}$, which is the unit vector with a 1 in the $10th$ place. Now, we are interested in $\sum_{n=1}^\infty P^ne_{10}$, which is a vector element of $\mathbb{R}^{20}$, but we want to know only the probability of John being in the 1st entry, where he loses. Note that the first entry of $P^ne_{10}$ is given by the first row of $P^n\cdot e_{10}$. This will take some matrix diagonalization tools, but your answer will be of the form $S(\sum_{i=1}^{\infty}\Lambda^i) S^{-1}e_{10}$, of which the first element is your answer.

Alternatively, you may evaluate using Wald's equality, with $\zeta$ being an R.V with support 1 with probability $.3$ and $-1$ with probability $.7$. Then, $\mathbb{E}[X_{\tau}] = 10 + \mathbb{E}[\tau]\mathbb{E}[\zeta]$, with $X_n = \sum \zeta_n$ the value of Johns worth, and use something like Chapman-Kologomorov to evaluate $\mathbb{E}[\tau]$, where $\tau$ is stopping time. This however looks like an equally lengthy, if not more lengthy, calculation.

Answer 2

I believe this can be solved using Huygen's result for Unfair Coin flipping in Gambler's Ruin.

It states that a player $P1$ entering a game with a bankroll $n_1$ and a constant probability $p$ of winning each individual game, playing against an opponent with bankroll $n_2$ will go bankrupt with probability:

$$P(\text{P1 bankrupt})=\frac{1-\left( \frac{p}{1-p} \right)^{n_{2}} }{ 1-\left( \frac{p}{1-p} \right)^{n_{1} + n_{2}} }$$

In your case, John has a constant probability of winning each individual game $p=0.3$, and bankroll's are the same for each player $n_{1}=n_{2}=10$, rendering

$$P(\text{John loses})=\frac{1-\left( \frac{0.3}{1-0.3} \right)^{10} }{ 1-\left( \frac{0.3}{1-0.3} \right)^{10 + 10} }$$ $$P(\text{John loses})=0.99979...$$