Author |
Topic: Gambler's Ruin (Read 1629 times) |
|
Jigga Wha?
Guest
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Gambler's Ruin
« Reply #1 on: Oct 23rd, 2005, 7:35am » |
 Quote  Modify
|
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.
| hidden: |
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. |
But the gambler will still loose with probability 1.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Gambler's Ruin
« Reply #2 on: Oct 23rd, 2005, 11:22am » |
Quote Modify
|
Except it's a weighted coin... so S(1) = 1 + p S(2) = 1 + 2p S(1).
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 x/(1-2p).
These results are shown here.
|
|
IP Logged |
|
|
|
Jigga Wha?
Guest
|
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?
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 p3 chance of having 4 coins, a 2 p2 q chance of having 2 coins, and a p q2 chance of losing. Thus, if {q + p q2 >= 1/2, p>1/2} , we have E(N) = 3. Continue.
What is the proper way to phrase my question?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Gambler's Ruin
« Reply #5 on: Oct 24th, 2005, 4:21am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Jigga Wha?
Guest
|
So here is the most general answer that I've gotten.
The probability P(x,n), that starting with x coins, the Gambler will fail on round n+x is given by:
P(x,n) = qx-1 Sumover n C(x,n) * (p q)n
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.
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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove