### Probability Puzzle Time!

Writing about web page http://www.gchq.gov.uk/recruitment/careers/math_apply.html

This puzzle from the GCHQ recruitment website has completely flummouxed me. I suspect there is some sort of general method to dealing with stuff like this, but I have no idea what it is.

2. Alice and Bob play coin toss: Alice pays Bob £1 for each head and Bob pays Alice £1 for each tail they throw. They continue playing until one player loses (runs out of money). Initially Alice has £6 and Bob has £14.

a. Determine, with proof, the probability that Alice loses.

b. Determine the probability that Alice loses but also has at some time previously been within £1 of winning.

## 9 comments by 2 or more people

[Skip to the latest comment]## Amit Sood

This can't be done using elementary probability methods, since there are possible endless loops of alternate heads and tails with no net effect on the situation. This is an example of what statisticians call a stochastic process. The problem is solveable, but it essentially requires matrix methods to determine the answer.

13 Jun 2005, 18:50

## Jason Hu

Hey Zhou, finally found out where you disappeared to. Hope you still remember me.

To solve this question doesn't necessarily require matrix methods it can be done quite easily with difference equations.

Let p = chance of heads, q = chance of tails

Let Un = chance of winning at position n

Thus

Un = qUn-1 + pUn+1

where Un-1 = chance of winning at position n-1, similarly for PUn+1

Assume Un = Ae^(w*n)

Solve as per any normal difference equation

and then you have the chance of winning at position n (starting position).

If you want the complete solution e-mail me and I'll do it and type it up for you.

The only difference between part a.) and part b.) are the starting conditions (i.e which n they start on and the total number of positions they can be at)

omg I beat Zhou at Maths

~~.~~hasn't happened since…er….ever.17 Jun 2005, 13:32

Oh hi, Jason. (Looks like you got into Cambridge too, you little

…)Anyway.

Well, I didn't think particularly hard about it. But I don't get your method. Specifically, where did:

Un = qUn-1 + pUn+1

Come from?

17 Jun 2005, 16:09

Ah wait, you're studying computer science. Ok, I can still retain a shred of dignity.

Erm..

17 Jun 2005, 16:10

Wait, wait, thinking again, your solution

can'tbe correct. For example one of the distinguishing marks of this question is that probability of anyone winning at a certain point in time is zero up to the sixth turn, and Alice can only have won after the 14th turn. Secondly, the probability that anyone has won at a certain point in time must tend to 1 as we continue to play the game. (We can prove this by the Drunken Walker theorems, I think) There is no way you can get this by an assumption of an exponential function.17 Jun 2005, 16:16

## Jason Hu

You misunderstand.

Firstly

Imagine the following number line

0,1,2,3,4,4,5,6,7,9,10,11,12,13,14,15,16,17,19,20

U(0) = 0 as she's lost

U(20) = 1 as at that point she's got all the money and has won

U(n) = the probability of winning starting from point n.

Thus U(n) = qU(n-1) + pU(n+1)

means that in this case the probably of winning from having 6 pounds is equal to the probability of losing one pound multiplied by the probability of winning after losing one pound, added to the probability of winning one pound multiplied by the probability of winning after winning one pound (phew try saying that 10 times in quick succession).

You are working out the probability

overallof winning from the position n, not the probability of winning in one turn from the position n so the exponential can be safely assumed.p.s. Trust me I just had an exam on this

p.p.s I aced that exam

p.p.p.s Compsci sucks I might be changing to maths for next year but who knows.

17 Jun 2005, 20:17

## Jason Hu

Ignore the repeated 4 in the numberline

If you wish to know more about this question it's called the "Gambler's Ruin" problem and is possible the most famous example of a stochastic process in probability.

I'll give you the answer (if only to remove the satisfaction of getting it yourself)

If it is a biased coin (p != q)

U(n) = A(1

^{n) + B((q/p)}n)Given the boundary conditions U(0) = 0, and U(20) = 1

Let X = (q/p) (cba writing it out lots of times)

U(n) = ((X

^{n)-1)/((X}20)-1)Thus

U(6) = ((X

^{6)-1)/((X}20)-1)In the fair case

U(n) = n/20

U(n) = 6/20 = 3/10 = 0.3

It works out that in the fair case it's possible the most boring game ever as the probability is linear with how much money you have.

You can do the same with the expected length of a game by having

D(n) = 1+ pD(n+1) + qD(n-1)

(I'll leave this as an exercise to the reader)

17 Jun 2005, 20:26

## Jason Hu

Your stupid blog leaves out power signs.

General solution =

U(n) = A * (1 to the power of n) + B* ((q/p) to the power of n)

With boundary conditions…

U(n) = (((q/p) to the power of n)-1)/(((q/p) to the power of 6) – 1)

17 Jun 2005, 20:29

Ah, I see.

(Goes off to slam head against wall.)

18 Jun 2005, 15:13

## Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.