Play forever and never go broke

80 Views Asked by At

In this note (MIT Course: Mathematics for Computer Science), which you can see the pdf link, there is the following term on page 9:

In this case (probability is more than 0.5) there is a non-zero chance that you can play forever and never go broke.

The text is finished here and no further explanation is given. How can that probability be calculated and proven?

1

There are 1 best solutions below

0
On

One can use a sort of inductive argument. I assume that "probability is more than $\tfrac12$" means that you are more likely to go up than down. For simplicity, let's suppose you go up with probability $\tfrac23$ and down with probability $\tfrac13$.

Let $p_{i \to j}$ denote the probability that at some point you ever hit $i$ starting from $j$ with $i,j \in \{0, 1, 2, ...\}$ and $i \ge j$. Note that $p_{k \to k} = 1$ for all $k$.

Start from $1$. Consider what happens in a single step: either you go down (probability $\tfrac13$) to $0$ and end or go up (probability $\tfrac23$) to $2$ and continue. We thus have $$ p_{1\to0} = \tfrac13 \cdot p_{0\to0} + \tfrac23 \cdot p_{2\to0} = \tfrac13 + \tfrac23 p_{2\to0}.$$

Now, how do we evaluate $p_{2\to0}$? Well, to go from $2$ to $0$ you have to pass via $1$, so $p_{2\to0} = p_{2\to1\to0}$. But by the Strong Markov Property applied at the time at which you hit $1$ (if you ever do), the evolution of the chain before hitting $1$ and after is independent! So $p_{2\to0} = p_{2\to1} p_{1\to0}$. By symmetry of the chain, $p_{2\to1} = p_{1\to0}$. Thus $p_{2\to0} = p_{1\to0}^2$.

Plugging this in and abbreviating $p := p_{1\to0}$ gives $$p = \tfrac13 + \tfrac23 p^2, \quad\text{or equivalently}\quad 2 p^2 - 3 p + 1 = 0.$$ But $2 p^2 - 3 p + 1 = (2 p - 1)(p - 1),$ and so the solutions to this are $1$ and $\tfrac12$.

In a Markov chains course, you should've had proved a theorem about this stuff which says that the correct solution is the minimal one. Thus $p = \tfrac12$.

In words, the chance $p_{1\to0}$ that you "go broke" at some point is non-zero.