{%hackmd /@hipp0/Hippotumuxthem %}

# Gambler's ruin

111201508 數學系大二B 鐘仕翔

## Problem state

Two players, A and B, engage in a recurring coin-flipping game. If the coin comes up heads with probability $p$, player A wins one unit from player B; If it comes up tails with probablity $(1-p)$, player B wins one unit from player A. The game continues until one of the players runs out of money. They are ralative between Gamble(A) and Casino(B).

Initail of player A has a money, and player B has b money. The total amount of money for Player A and Player B is N. Therefore when player A has 0 money or N money, the game is ending.

## Research Basis

- Markov chain

## Solve by Markov chain

### State Gambler's ruin Markov chain

In each round, player A has probability $p$ of winning and probability $q = 1-p$ of losing. Let $X_n$ be the wealth of player A at time n.

Then $X_0, X_1,...$ is a Markov chain on the state place ${0,1,...,N}$ design, $X_0=a$ Once the markov chain reaches $0$ or $N$, the diagram of the chain is chown below.


Because it will eventually be absorbed into state $0$ or $N$, never returning to $i$. Therefore states $0$ and $N$ are recurrent, and other state are transient.

We can also state the function $X_n$ with initial $X_0 = a$


we can write $P(X_{n+1} \leq b \mid X_1 = x_1, X_2 = x_2, \ldots, X_n = x_n) = P(X_{n+1} \leq b \mid X_n = x_n)$

### transition matrix

$P(X_{n+1} = j \mid X_n = i) = p_{ij}, \quad \forall n = 1, 2, \ldots$

Markov chain on the state space S = {0, 1, . . . , N}. The transition
probabilities are given by $P_i$,$P_{i+1}$ = p, $P_i , P_{i−1}$ = q, $0 < i < N$, and both 0 and N are absorbing states, $P_{00}$ = $P_{NN}$ = 1

$$
P = \begin{bmatrix}
1 & 0 & 0 & \dots & 0 \\
q & 0 & p & \dots & 0 \\
0 & q & 0 & \dots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & \dots & 0 & q & p \\
0 & \dots & \dots & 0 & 1
\end{bmatrix}$$

example for N = 4

$$
P = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
q & 0 & p & 0 & 0 \\
0 & q & 0 & p & 0 \\
0 & 0 & q & 0 & p \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}$$

### absorbing state

In the Gambler's Ruin problem, absorbing states may represent the gambler reaching the target funds or going bankrupt (losing all funds).

We now simplify the problem to N = 5. Let $x$ = $\{x_0, x_1, x_2, x_3, x_4, x_5\}$ be the probability of player has $i$ money but fininally bankrupt.

$x_i = P(playerAbankrupt \space | playerA \space has \space i \space money)$

With $x_0 = 1, x_5 = 0$

According to the markov chain, we have
$x_2 = px_3 + qx_1$
=> $(p + q)x_2 = px_3 + qx_1$
=> $p(x_2-x_3) = q(x_1-x_3)$
$\therefore x_1 - x_2 = \frac{p}{q}(x_2 - x_3)$

Now let $r = \frac{p}{q}$, use the same method we obtain

$$ \begin{cases}
x_0 - x_1 = r(x_1 - x_2)\\
x_1 - x_2 = r(x_2 - x_3)\\
x_2 - x_3 = r(x_3 - x_4)\\
x_3 - x_4 = r(x_4 - x_5)\\
\end{cases}$$

We have $x_5 = 0$, therefore

$$ \begin{cases}
x_0-x_1 = r(x_1 - x_2)\\
x_1 - x_2 = r(x_2 - x_3)\\
x_2 - x_3 = r(x_3 - x_4)\\
x_3 - x_4 = r(x_4)\\
\end{cases}$$

Simply we can get

$$ \begin{cases}
x_0-x_1 = r(r(r(r(x_4)))) = r^4x_4\\
x_1 - x_2 = r(r(r(x_4))) = r^3x_4\\
x_2 - x_3 = r(r(x_4)) = r^2x_4\\
x_3 - x_4 = r(x_4)\\
x_4 = x_4\\
\end{cases}$$

so
$$x_0 = (1+r+r^2+r^3+r^4)x_4$$

And we have $x_0 = 1$
$$1 = (1+r+r^2+r^3+r^4)x_4$$

Now observe
$$(1-r^5) = (1+r+r^2+r^3+r^4)(1-r)$$

$$\therefore x_4 = \frac{1-r}{1-r^5}$$

Then

$$x_3 = (1+r)x_4 = \frac{1-r^2}{1-r^5}$$

$$x_2 = \frac{1-r^3}{1-r^5}$$

$$x_1 = \frac{1-r^4}{1-r^5}$$

### Solve general problem
Now consider $N\in \mathbb{N}$
$$ \begin{cases}
x_0-x_1 = r(x_1 - x_2)\\
x_1 - x_2 = r(x_2 - x_3)\\
........................\\
x_{N-2} - x_{N-1} = r(x_{N-1} - X_N)\\
\end{cases}$$

With $x_N = 0$

$$ \begin{cases}
x_0 - x_1 = r^{N-1}x_{N-1}\\
x_1 - x_2 = r^{N-2}x_{N-1}\\
......................\\
x_{N-3} - x_{N-2} = r^2x_{N-1}\\
x_{N-2} - x_{N-1} = rx_{N-1}\\
x_{N-1} = x_{N-1}\\
\end{cases}$$

Then

$$ x_0 = (1+r+r^2+...+r^{N-1})x_{N-1}$$

Since $x_0 = 1$ we can conclude
$$ x_a = \frac{1-r^b}{1-r^N} = \frac{1-(\frac{p}{q})^b}{1-(\frac{p}{q})^{a+b}}$$
(because The total amount of money for Player A and Player B is N)

## Discussion

Since
$$ x_a = \frac{1-r^b}{1-r^N} = \frac{1-(\frac{p}{q})^b}{1-(\frac{p}{q})^{a+b}}$$

We can see when $b \to \infty$ then $x_a \to 1$

Under normal circumstances, the casino's funds are significantly larger than those of the gambler. Therefore, based on the outcomes, it is inevitable for the gambler to lose all their money.

## References

1. Joseph K\.Blitzstein (2019) "Introduction to Probabilty", Unit 11 Markov chain
2. Juan Andrés Malaver. (Feb 22, 2021). "The Gambler’s Ruin Problem."