9 comments by 1 or more people

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

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

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

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

   Erm..

   17 Jun 2005, 16:10

5. Wait, wait, thinking again, your solution can't be 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

6. 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 overall of 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

7. 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)/((X20)-1)
   Thus
   U(6) = ((X^6)-1)/((X20)-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

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

9. Ah, I see.

   (Goes off to slam head against wall.)

   18 Jun 2005, 15:13