# A probability game

Motivation: A friend asked me this question.

The Problem: Suppose you start off with a dollar. You flip a fair coin, if it lands on heads you win $50$ cents otherwise you lose $50$ cents. If after $n$ flips you have a nonzero amount of money, you win. What's the probability you win? What about the limiting case as $n$ tends to infinity?

edit: In this game you are not allowed to have negative money. Thanks, Jonathan Fischoff, the linked helped greatly.

-
You might find this interesting math.stackexchange.com/questions/607/… – Jonathan Fischoff Aug 7 '10 at 3:25
Are you allowed to have a negative amount of money or does the game end when you lose all your money? In either case I think the keyword you want is "one-dimensional random walk." – Qiaochu Yuan Aug 7 '10 at 4:31
Can the 'house' (the person betting against the player) ever run out of money? – Larry Wang Aug 7 '10 at 15:55
I want Qiaochu's question answered a little more explicitly. If I get 60 flips and I get 2 tails on my first 2 flips, is that considered a loss automatically? If my first 59 flips come up tails, but I then flip again and get heads, do I finish the game with 50 cents and thus a nonzero amount of money? Or have I already lost? – Carter Pape Jul 27 at 21:25

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$.

-
this wikipedia page is somewhat relevant (some time ago I too tried to find some online reference for reflection principle) – Grigory M Aug 7 '10 at 9:59

As n goes to infinity, you run out of money with probability 1. This is known as gambler's ruin or the drunk walk--if you are winning/losing money or walking side to side such that you win/lose/go left/go right with probability 1/2 (a 1-d simple symmetric random walk), and there is a boundary like going broke or ending up in the gutter, as the number of games/steps goes to infinity, the probability of hitting that boundary goes to 1.

I don't know how to prove it, but per Joshua Zucker's comment on A001405 in the OEIS, and agreeing with T..'s answer, the probability of ending up with a positive amount of money after n flips if you started with no money would be $\frac{1}{2^n}{n\choose \left\lfloor\frac{n}{2}\right\rfloor}$. Because you start with one dollar instead of no money, this is offset so that the probability of having money after n flips is $\frac{1}{2^{n-1}}{n-1\choose \left\lfloor\frac{n-1}{2}\right\rfloor}$ for n≥1.

-

Here is a completely probabilistic proof inspired by Moron in http://math.stackexchange.com/questions/4044/finding-a-clever-solution-to-a-game-of-chance.

Let p be the probability that I end up with a net loss of 50 cents, then $p = \frac{1}{2} + \frac{1}{2} p^3$. That is to say, I either lose 50 cents, or gain a dollar and lose a dollar and 50 cents eventually. Solving for p I get 1, $(-1-\sqrt{5})/2$, and $(1-\sqrt{5})/2$ and it is not hard to see that we can dismiss the first two. Now the probability I end up with a net loss of one dollar is $p^2 = (3-\sqrt{5})/2$.

-

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$.

-
That's a different problem. Gambler's ruin asks about the probability of reaching one of two absorbing barriers (0 and N) starting from a given point. The number of steps is unlimited so one can just just compute probabilities of reaching various states. In the problem posted by yjj, the number of steps is given and there is one absorbing barrier at 0. The solution is by the reflection principle, and I don't know if there is a closed form in the asymmetrical case $p \neq 1/2$. – T.. Aug 8 '10 at 20:20
Sorry. I didn't realize the difference. – Aditya Aug 8 '10 at 20:38