The Gambler's Ruin Problem 賭徒破產

Example (The Gambler's Ruin)
Two gamblers, A and B, bet on the outcomes of successive flips of a coin. On each flip, if the coin comes up heads, A collects 1 unit from B, whereas, if it comes up tails, A pays 1 unit to B. They continue to de this until one of them runs out of money. If it is assumed that the successive flips of the coin are independent and each flip results in a head with probability p, what is the probability that A ends up with all the money if he starts with i units and B starts with N-i units?
Solution:
Let E denote the event that A ends up with all the money when he starts with i and B with N-i, and to make clear the dependence on the initial fortune of A, let Pi=P(E). We shall obtain an expression for P(E) by conditioning on the outcome of the first flip as follows: Let H denote the event that the first flip lands heads; then
$\begin{array}{rcl} P_i=P(E)&=&P(E\vert H)P(H)+P(E\vert H^c)P(H^c) \\ &=&pP(E\vert H)+(1-p)P(E\vert H^c) \\ \end{array}$
Now, given that the first flip lands heads, the situation after the first bet is that A has i+1 units and B has N-(i+1). Since the successive flips are assumed to be independent with a common probability p of heads, it follows that, from that point on, A's probability of winning all the money is exactly the same as if the game were just starting with A having an initial fortune of i+1 and B having an initial fortune of N-(i+1). Therefore, P(E|H)=Pi+1 and similarly, P(E|Hc)=Pi-1
Hence, letting q=1-p, we obtain
$P_i=pP_{i+1}+qP_{i-1}\qquad i=1,2,\ldots ,N-1 \qquad (4.2)$
By making use of the obvious boundary conditions P0=0 and PN=1, we shall now solve Equation (4.2). Since p+q=1, these equations are equivalent to
$\begin{array}{rcl} pP_i+qP_i&=&pP_{i+1}+qP_{i-1}\qquad \mbox{or} \\ P_{i+1}-P_... ...aystyle\frac{q}{p}(P_i-P_{i-1})\qquad i=1,2,\ldots ,N-1\qquad (4.3) \end{array}$
Hence, since P0=0, we obtain from Equation (4.3):
$\begin{array}{rcl} P_2-P_1&=&\displaystyle\frac{q}{p}(P_1-P_0)=\frac{q}{p}P_1 \... ...1}-P_{N-2})= \left (\frac{q}{p}\right )^{N-1}P_1 \qquad (4.4)\\ \\ \end{array}$
Adding the first i-1 of Equation (4.4) yields
$P_i=\left\{\begin{array}{rl} \displaystyle\frac{1-(q/p)^i}{1-(q/p)}P_1&\display... ...{p}\neq 1 \\ \\ iP_1&\displaystyle\mbox{ if }\frac{q}{p}=1 \end{array}\right .$
Now, using the fact that PN=1, we obtain
$P_1=\left\{\begin{array}{rl} \displaystyle\frac{1-(q/p)}{1-(q/p)^N}&\displaysty... ...splaystyle\frac{1}{N}&\displaystyle\mbox{ if }p=\frac{1}{2} \end{array}\right .$
and hence
$P_i=\left\{\begin{array}{rl} \displaystyle\frac{1-(q/p)^i}{1-(q/p)^N}&\displays... ...ac{i}{N}&\displaystyle\mbox{ if }p=\frac{1}{2} \qquad (4.5) \end{array}\right .$
Let Qi denote the probability that B winds up with all the money when A starts with i and B with N-i. Then, by symmetry with the situation described and on replacing p by q and i by N-i, we see that
$Q_i=\left\{\begin{array}{rl} \displaystyle\frac{1-(q/p)^{N-i}}{1-(q/p)^N}&\disp... ...{N-i}{N}&\displaystyle\mbox{ if }q=\frac{1}{2} \qquad (4.5) \end{array}\right .$
Moreover, since $\displaystyle q=\frac{1}{2}$ is equivalent to $\displaystyle p=\frac{1}{2}$, we have when $\displaystyle q\neq\frac{1}{2}$,
$\begin{array}{rcl} P_i+Q_i&=&\displaystyle\frac{1-(q/p)^i}{1-(q/p)^N}+\frac{1-(... ...isplaystyle\frac{p^Np^{N-i}q^i-q^N+q^ip^{N-i}}{p^N-q^N} \\ \\ &=&1 \end{array}$
As this result also holds when $\displaystyle p=q=\frac{1}{2}$, we see that Pi+Qi=1
In words this equation states that with probability 1 either A or B will wind up with all of the money; or, in other words, the probability that the game continues indefinitely with A's fortune always being between 1 and N-1 is zero. (The reader must be careful because, a priori, there are three possible outcomes of this gambling game, not two. Either A wins or B wins or it goes on forever with nobody winning. We have just shown that this last event has probability 0.)
As a numerical illustration of the above result, if A were to start with 5 units and B with 10, then the probability of A's winning would be $\displaystyle\frac{1}{3}$if p were $\displaystyle\frac{1}{2}$, whereas it would jump to
$\displaystyle\frac{\displaystyle1-\left (\frac{2}{3}\right )^5} {\displaystyle1-\left (\frac{2}{3}\right )^{15}}\approx .87$
if p were .6.          $\rule[0.02em]{1.0mm}{1.5mm}$