wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Gambler's Ruin
        
(Message started by: Jigga Wha? on Oct 23^rd, 2005, 3:27am)

Title: Gambler's Ruin
Post by Jigga Wha? on Oct 23^rd, 2005, 3:27am

There is a Gambler, who starts out with x0 quarters, playing a game with the House. Each round he flips one coin (which has probability p of landing heads up). If the coins lands tails up, he loses the coin; if the coin lands heads up, he wins another coin. The House has infinite funds. On average (>50%), how many rounds can he play before going broke?

Note: I've not found a general solution to this myself. When starting with x0 = 1, you get a probability of failing involving a series sum of Catalan Numbers (1,2,5,14,42,132,...). The easiest way of solving this seems to be using Excel, but I'm wholly unsatisfied with that.

Title: Re: Gambler's Ruin
Post by towr on Oct 23^rd, 2005, 7:35am

This is the reasonably well known problem of a random walk. You go backwards or forwards each step with equal probability, and eventually you get back.
You can do it for 2 dimensions or 3 as well.

Anyway, how to solve it.
[hideb]
You have one coin, and you want to know how many round it will take before you have one less.
Let's say it's S(1) round.
If you have two coins, you will have to loose a coin twice, so it must be S(2) = 2 * S(1)
But if you have 1 coin, you will either gain a coin, or loose a coin, and use one round in the progress. So S(1) = 1/2 (0 + S(2)) + 1 = 1/2 S(2) +1
But since S(2) = 2 * S(1) this means S(1) = S(1) + 1 so S(1) must be infinite.[/hideb]

But the gambler will still loose with probability 1.

Title: Re: Gambler's Ruin
Post by Eigenray on Oct 23^rd, 2005, 11:22am

Except it's a weighted coin... so [hide]S(1) = 1 + p S(2) = 1 + 2p S(1)[/hide].

Now, if p>1/2, then the expected time is infinite; moreover, there's a positive probability that the game will run forever. (The probabilitiy of it ending is ((1-p)/p)^x < 1).
If p=1/2, the game will end with probability 1, but the expected time will still be infinite.
But if p<1/2, then the expected time is [hide]x/(1-2p)[/hide].

These results are shown here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1102522052).

Title: Re: Gambler's Ruin
Post by towr on Oct 23^rd, 2005, 12:54pm

on 10/23/05 at 11:22:05, Eigenray wrote:

Except it's a weighted coin...

oops ;D

Title: Re: Gambler's Ruin
Post by Jigga Wha? on Oct 24^th, 2005, 1:09am

I think I'm being an idiot, and asked something else? That is, what is the round at which the probability of failing is equal to or more than 1/2?

[hide]Assuming x0 = 1. For the first round, we have p winning a coin, and q losing. If p <= 1/2, we find E(N) = 1. Let us continue for two more rounds. At this point, we will have a p³ chance of having 4 coins, a 2 p² q chance of having 2 coins, and a p q² chance of losing. Thus, if {q + p q² >= 1/2, p>1/2} , we have E(N) = 3. Continue.[/hide]

What is the proper way to phrase my question?

Title: Re: Gambler's Ruin
Post by towr on Oct 24^th, 2005, 4:21am

Ah, you want to know for which round his chance of not reaching the next is 50% or more, rather than the average number of rounds he'd play..
I'll have to think about that..

Title: Re: Gambler's Ruin
Post by Jigga Wha? on Oct 26^th, 2005, 10:14am

So here is the most general answer that I've gotten.

[hide]The probability P(x,n), that starting with x coins, the Gambler will fail on round n+x is given by:

P(x,n) = q^x-1 Sum_{over n} C(x,n) * (p q)ⁿ

where p is the probability of winning, and q = 1-p the probability of losing a coin. The coefficient C is given by:

C(x,n) = x+1 / (2n - (x-1) ) * Choose( 2n - (x-1) , n+x )

Note that we can check (well, mathematica can) that the chance of ever losing will be given as

P(x,infty) = (q / p)^x

which is what we would expect.

The answer to my original question would involve setting P to 1/2, and then solving for n.
[/hide]

For the life of me, I couldn't get those coefficients right without trial and error. Even now, I'm hard pressed to rationalize everything. Can any of you math whizzes give it a shot?