A and B bet on successive flips of a coin. On each flip, A collects 1 unit from B if the coin comes up heads (this has probability p), otherwise A pays B 1 unit. This continues until either of them runs out of money. What's the probability A wins all the money if A starts with i units and B starts with N - i units?

This is a great puzzle! When I first saw it, it reminded me of a similar problem [essentially the continuous-time equivalent of coin flipping, where B has unlimited amounts of money, and A gets shot if his wealth ever falls below H1 or rises above H2. What it the probability that A is still alive after time t?] I have come across in finance. That is a rather involved problem.

Yours though, is much easier -just a handful of lines. For equal probabilities of head/tail, the probability of A winning is linear on how much they have (relatively) start with.

I don't want to spoil your fun by giving you the 'trick'. My hint to you is giving you the answer. Instead, can I show you how I got there? It was only after going through the agony below that I found the answer, and realised what the trick must be. The techniques below are quite advanced (it's basically 'financial calculus'), so please don't be put off if they are unfamiliar. I repeat, your problem can be solved with 'O' level maths.

So here goes. I first assumed that the probability of head/tails were equal. Then I decided to attack the continuous time equivalent of your problem. Define an asset, $S(t)$ such that

$S(0)=S_0$

Suppose there are $n$ tosses per unit time, each increasing/decreasing $S$ by $k$. The variance of $S$ after time $t$ is

$nt{k}^2$

If we choose $k$ such that $nt{k}^2={\sigma }^{2}t$, and let $n\to \infty$, then $S$ is the continuous equivalent to the assets of $A$, where $\sigma$ is the 'intensity' of coin throwing.

In derivative notation, this is equivalent to writing

$\mathrm{dS}=\sigma \mathrm{dZ}$

Where, in this stochastic differential equation, $Z$ is a Weiner process - $Z(t+1)-Z(t)$ being normally distributed with zero mean and unit variance.

Next define $C$ to be a claim on $S$. $C$ is an asset/liability whose value depends upon $t$ and the history of $S$ up to and including time $t$. We will define (later) $C$ to have a value of 1 when $S$ crosses the upper threshold ( $H_h$) for the first time, 0 when $S$ crosses the lower threshold ( $H_l$) for the first time.

Assume interest rates are zero.

Imagine $S$ were tradeable, i.e. we could invest in $S$ and would experience its gains and losses over time. Or, we could put money on deposit and earn nothing.

Now $C=C(S,t)$, but suppose, between $t$ and $t+\delta t$ we hold a portfolio of $C$ and $\alpha S$, with a value of

$V=C+\alpha S$

How does this evolve from $t$ to $t+\delta t$? Well

$\mathrm{dV}=(\partial C/\partial t)\mathrm{dt}+(\partial C/\partial S)\mathrm{dS}+({\partial }^{2}C/\partial S^2){\mathrm{dS}}^2+\alpha \mathrm{dS}$

But, from ito's lemma,

${\mathrm{dS}}^2={\sigma }^2\mathrm{dt}$

so

$\mathrm{dV}=(\partial C/\partial t)\mathrm{dt}+(\partial C/\partial S)\mathrm{dS}+({\partial }^{2}C/\partial S^2){\sigma }^2\mathrm{dt}+\alpha \mathrm{dS}$

Now, we are at liberty to choose $\alpha$ at will. So we choose

$\alpha =-(\partial C/\partial S)$

(the delta hedge of the claim, $C$). Which simplifies the equation to

$\mathrm{dV}=(\partial C/\partial t)\mathrm{dt}+({\partial }^{2}C/\partial S^2){\sigma }^2\mathrm{dt}$

Now $\mathrm{dV}$ is no longer a function of $S$. It is non stochastic. It must simply grow at the riskless rate of interest. Which we assumed to be zero. So $\mathrm{dV}=0$ and therefore:

$(\partial C/\partial t)+{\sigma }^2({\partial }^{2}C/\partial S^2)=0$

This is a stripped down version of the contingent claims equation. Now we are on familiar territory. The boundary conditions are $C(H_l,t)=0$ $\forall t$ and $C(H_h,t)=1$ $\forall t$.

Now if we had an additional boundary condition at some time in the future (as a function of $S$) this equation is pretty awful to solve. But our problem runs indefinitely. Therefore we can't distinguish between $C(S,t_1)$ and $C(S,t_2)$ [provided that neither barrier has been breached]. Therefore $C(S,t)=C(S)$! So $C$ must satisfy:

$(d^{2}C/{\mathrm{dS}}^2){\sigma }^2=0$

And therefore $C(S)=aS+b$.

i.e., it is linear, having value 0 at $H_l$ and 1 at $H_h$
Andre

I tried allowing both players to go into debt, then computing the probability that B has 0 money (A wins) just after the (k+1)th flip AND neither player had 0 money at any flip < = k (ie P(A wins at the (k+1)th flip).
Summing those probabilities has so far produced calculations too complex for me to believe I won't make an algebraic mistake.

There is a total amount of cash of N. Denote A holding an amount x of cash after the nth roll by (x,n).

Assume the probability of heads/tails are equal. This means that the state (x,n) can evolve to (x+1,n+1) and (x-1,n+1) each with 50% probability.

Denote P(x,n) as being the probability that A will win contingent on not having won/lost to date. So P(N,t)=1 ; P(0,t)=0. Given that there are just 2 possible states at n+1 (given (x,n)),

P(x,n)=1/2.[P(x+1,n+1)+P(x-1,n+1)]

Repeating the argument for one more step:

P(x,n)=1/4.[P(x+2,n+2)+2.P(x,n+2)+ P(x-2,n+2)]

But what is the difference between P(x,n) and P(x,n+2)? Nothing. Dice have no memory and we play the game forever (or until A wins/loses). So

P(x,n+2)=1/4.[P(x+2,n+2)+2.P(x,n+2)+ P(x-2,n+2)]

i.e.

P(x,n+2)=1/2.[P(x+2,n+2) + P(x-2,n+2)]

So these three points are linear, and repeating the argument justifies linearity from x=0..N.

Andre

That is a nice trick! It is unexpected to use the probability values 1 and 0 in such a way.