A probability game

This type problem on random walk is usually solved with the Reflection Principle, with the walk visualized as a lattice path. Strangely, I can't find an online reference to the solution but it is given in Feller's book on probability theory, volume 1.

Here, measuring the money in units of 0.5 dollars, the walk, drawn in the $(x,y)$ plane, starts at (2,0), moves by $(+1,\pm 1)$ at each step, and the question is what is the probability that over $n$ moves the walk is always $\geq 1$.

As Issac pointed out, this is known as the Gamler's ruin problem. I recently wrote a couple of blog posts (this and the post linked from there) explaining how to calculate the ruin probability. I'll repeat part of one of the proofs here.

Problem Formulation

A gambler enters a casino with $n$ dollars in cash and starts playing a game where he wins with probability $p$ and looses with probability $q = 1-p$ The gampler plays the game repeatedly, betting $1$ dollar in each round. He leaves the gave it his total fortune reaches $N$ or he runs out of money (he is ruined), whichever happens first. What is the probability that the gambler is ruined.

A gambler's ruin can be modeled as a one-dimensional random walk in which we are interested in the hitting probability of the absorbing states. Calculating these probabilities is fairly straightforward. Let $P_N(n)$ denote the probability that the gambler's fortune reaches $N$ dollars before he is ruined on the condition that his current fortune is $n$. Then,

$P_N(n) = p P_N(n+1) + q P_N(n-1)$

which can be rewritten as

$\displaystyle [P_N(n+1) - P_N(n)] = \left(\frac q p \right)[ P_N(n) - P_N(n-1)]$

Since $P_N(0) = 0$, we have that

$\displaystyle P_N(2) - P_N(1) = \left(\frac qp \right) P_N(1)$

and similarly

$\displaystyle P_N(3) - P_N(2) = \left(\frac qp \right) [P_N(2) - P_N(1)] = \left( \frac qp \right)^2 P_N(1)$

Continuing this way, we get that

$\displaystyle P_N(n) - P_N(n-1) = \left( \frac qp \right)^{n-1} P_N(1) $.

and therefore, by adding the first $n$ such terms, we get

$\displaystyle P_N(n) = \sum_{k=0}^{n-1} \left( \frac qp \right)^k P_N(1)$.

Moreover, we know that

$\displaystyle P_N(N) = \sum_{k=0}^{N-1} \left( \frac qp \right)^k P_N(1) = 1$.

Thus,

$\displaystyle P_N(1) = \frac 1{\sum_{k=0}^{N-1} \left( \frac qp \right)^k} = \frac { 1 - (q/p)}{\strut 1 - (q/p)^N}, \quad p \neq q $

$P_N(1) = \frac 1N, \quad p = q $.

Combining with the previous expression for $P_N(n)$ we get,

$\displaystyle P_N(n) = \begin{cases} \frac{ 1 - (q/p)^n} {\strut 1 - (q/p)^N}, & p \neq 1/2 \ \frac{n}{N}, & p = 1/2 \end{cases}$.

For ease of representation let $\lambda = q/p$. Then, the probability of winning are

$\displaystyle P_N(n) = \frac{ 1 - \lambda^n} {\strut 1 - \lambda^N}, \quad \lambda \neq 1 $

$P_N(n) = \frac{n}{N}, \quad \lambda = 1 $.