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₀

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

n t k²

If we choose k such that n t k² = s² t, and let n®¥, then S is the continuous equivalent to the assets of A, where s is the 'intensity' of coin throwing.

In derivative notation, this is equivalent to writing

dS=sdZ

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+dt we hold a portfolio of C and aS, with a value of

V=C+aS

How does this evolve from t to t+dt? Well

dV=(¶C/¶t)dt+(¶C/¶S)dS+(¶² C/¶ S²)dS² +adS

But, from ito's lemma,

dS² = s² dt

so

dV=(¶C/¶t)dt+(¶C/¶S)dS+(¶² C/¶ S²)s² dt +adS

Now, we are at liberty to choose a at will. So we choose

a = -(¶C/¶S)

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

dV=(¶C/¶t)dt+ (¶² C/¶S²)s² dt

Now 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 dV=0 and therefore:

(¶C/¶t)+s² (¶² C/¶S²)=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 "t and C(H_h,t)=1 "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₁) and C(S,t₂) [provided that neither barrier has been breached]. Therefore C(S,t)=C(S)! So C must satisfy:

(d² C/dS² )s² = 0

And therefore C(S)=a S+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.