logo

The Gambler's Ruin Problem 📂Probability Theory

The Gambler's Ruin Problem

Problem

20190213\_101451.png

The gambler’s ruin problem is a type of random walk where two players bet a finite amount of money and the game is repeated until one of them goes bankrupt.

If you are one of the players, then according to the diagram above, the probability of you winning is pp and the probability of losing is (1p)(1-p). State 00 is when you go bankrupt, and state NN is when you win all the money from your opponent, meaning the game does not continue. This is represented by the probability of moving to oneself in 00 and NN being 11. ii can be seen as your initial money when starting the game.

Basically, if p12\displaystyle p \ne {{1} \over {2}} or iN2\displaystyle i \ne {{N} \over {2}}, the game is not fair. The game doesn’t end until one person goes bankrupt. A question of mathematical interest might be “what are the chances of you bankrupting your opponent and winning when you start with ii amount of money?”. However, one might first ask “why play such an unfair and extreme game?”.

But this is only a question one might pose when viewing the gambler’s ruin problem strictly as a game, whereas in reality, fair fights are even harder to come by. This could be seen as the struggle between large corporations with significant capital and protected small businesses, or as total warfare between nations that produce similar resources. There are times when one must engage in an unfavorable fight, and naturally, one would be curious about their chances of winning.

Returning to mathematics, our interest lies in calculating the probability ‘of bankrupting the opponent and taking all the money when the initial capital is ii and the winning probability is pp ‘, which is PiP_{i}. For convenience, let’s call the situation ‘of bankrupting the opponent and taking all the money’ a ‘win’.

Solution

Based on the definition of PiP_{i}, we have P0=0P_{0} = 0 and PN=1P_{N} = 1.

Part 1.

PiP_{ i } can be seen as the probability of winning the first game with the probability of pp and then starting anew from (i+1)( i+1 ) to win, plus the probability of losing the first game with the probability of (1p)(1-p) and then starting anew from (i1)( i-1 ) to win. Mathematically, this is represented as Pi=pPi+1+(1p)Pi1P_{ i } = p P_{ i + 1 } + (1 - p ) P_{ i - 1 }. If we split the left-hand side into pp and (1p)(1-p), then Pi=(p+1p)Pi=pPi+(1p)PiP_{ i } = (p + 1 - p ) P_{i} = p P_{i} + (1 - p) P_{i} thus, Pi=pPi+1+(1p)Pi1    pPi+(1p)Pi=pPi+1+(1p)Pi1    p(Pi+1Pi)=(1p)(PiPi1)    (Pi+1Pi)=1pp(PiPi1) \begin{align*} & P_{ i } =& p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p P_{i} + (1 - p) P_{i} &= p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p \left( P_{i+1} - P_{i} \right) =& (1 - p) \left( P_{i} - P_{i-1} \right) \\ \implies& \left( P_{i+1} - P_{i} \right) =& {{1-p} \over {p}} \left( P_{i} - P_{i-1} \right) \end{align*}

Recursive solving leads to PiPi1=(1pp)i1(P1P0)\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} \left( P_{1} - P_{0} \right), but since P0=0P_{0} = 0, PiPi1=(1pp)i1P1\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}


Part 2.

P1P0=(1pp)0P1P2P1=(1pp)1P1P3P2=(1pp)2P1PiPi1=(1pp)i1P1P_{1} - P_{0} = \left( {{1-p} \over {p}} \right)^{0} P_{1} \\ P_{2} - P_{1} = \left( {{1-p} \over {p}} \right)^{1} P_{1} \\ P_{3} - P_{2} = \left( {{1-p} \over {p}} \right)^{2} P_{1} \\ P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}

Adding the equations side by side, the left-hand side becomes (P1P0)+(P2P1)++(PiPi1)=PiP0=Pi( P_{1} - P_{0} ) + ( P_{2} - P_{1} ) + \cdots + ( P_{i} - P_{i-1} ) = P_{i} - P_{0} = P_{i} and the right-hand side becomes k=1i(1pp)k1P1=1(1pp)i1(1pp)P1\displaystyle \sum_{k=1}^{i} \left( {{1-p} \over {p}} \right)^{k-1} P_{1} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} Simplifying, Pi=1(1pp)i1(1pp)P1\displaystyle P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}


Part 3.

Since PN=1P_{N} = 1, 1=PN=1(1pp)N1(1pp)P1 1 = P_{N} = {{ 1 - \left( {{1-p} \over {p}} \right)^{N} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} Therefore, P1=1(1pp)1(1pp)N P_{1} = {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} By substituting P1P_{1} into the equation obtained in Part 2., Pi=1(1pp)i1(1pp)1(1pp)1(1pp)N=1(1pp)i1(1pp)N P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} \cdot {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right)^{N} }} is obtained.