The Gambler's Ruin Problem
📂Probability TheoryThe Gambler's Ruin Problem
Problem
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 p and the probability of losing is (1−p). State 0 is when you go bankrupt, and state N 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 0 and N being 1. i can be seen as your initial money when starting the game.
Basically, if p=21 or i=2N, 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 i 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 i and the winning probability is p ‘, which is Pi. For convenience, let’s call the situation ‘of bankrupting the opponent and taking all the money’ a ‘win’.
Solution
Based on the definition of Pi, we have P0=0 and PN=1.
Part 1.
Pi can be seen as the probability of winning the first game with the probability of p and then starting anew from (i+1) to win, plus the probability of losing the first game with the probability of (1−p) and then starting anew from (i−1) to win. Mathematically, this is represented as Pi=pPi+1+(1−p)Pi−1. If we split the left-hand side into p and (1−p), then
Pi=(p+1−p)Pi=pPi+(1−p)Pi
thus,
⟹⟹⟹Pi=pPi+(1−p)Pip(Pi+1−Pi)=(Pi+1−Pi)=pPi+1+(1−p)Pi−1=pPi+1+(1−p)Pi−1(1−p)(Pi−Pi−1)p1−p(Pi−Pi−1)
Recursive solving leads to Pi−Pi−1=(p1−p)i−1(P1−P0), but since P0=0,
Pi−Pi−1=(p1−p)i−1P1
Part 2.
P1−P0=(p1−p)0P1P2−P1=(p1−p)1P1P3−P2=(p1−p)2P1Pi−Pi−1=(p1−p)i−1P1
Adding the equations side by side, the left-hand side becomes
(P1−P0)+(P2−P1)+⋯+(Pi−Pi−1)=Pi−P0=Pi
and the right-hand side becomes
k=1∑i(p1−p)k−1P1=1−(p1−p)1−(p1−p)iP1
Simplifying,
Pi=1−(p1−p)1−(p1−p)iP1
Part 3.
Since PN=1,
1=PN=1−(p1−p)1−(p1−p)NP1
Therefore,
P1=1−(p1−p)N1−(p1−p)
By substituting P1 into the equation obtained in Part 2.,
Pi=1−(p1−p)1−(p1−p)i⋅1−(p1−p)N1−(p1−p)=1−(p1−p)N1−(p1−p)i
is obtained.
■