Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I realized that an earlier question I'd posted was actually different than what I was actually asking.

My question is: say we have a game where you win 2 dollars, or lose 1 dollar, both with probability 1/2. What is the probability that you end up with exactly the same amount of money that you started with?

Is this equivalent to a ruin problem against an infinitely rich adversary?

share|improve this question
2  
It rather depends on when you decide to end the game. When you run out of money? When you next have what you started with (and what happens if you lose 1 then gain 2)? When you have a million times what you started with? The first of these to happen? –  Henry May 3 '11 at 22:56
    
say it functions exactly as a random walk on the real number line. It ends when you next have what you started with, and you are allowed to go into the negative. –  gentisse May 3 '11 at 23:07
    
Random walks do not usually jump over integer points, but I will take that as "don't stop". –  Henry May 3 '11 at 23:08

1 Answer 1

To stop on your original position you need a multiple of three steps (twice as many $-1$ as $+2$ steps).

The probability of stopping after the first three steps is $\frac{3}{8} = 0.375$: eight possibilities for the steps, of which three end up at a net zero gain. In general the probability of first stopping after $3n$ steps is

$$\frac{{3n \choose n}}{2^{3n-1}(3n-1)}. $$

So the probability of ever stopping, rather than heading off to $+\infty$, is

$$\sum_{n=1}^{\infty} \frac{{3n \choose n}}{2^{3n-1}(3n-1)} =\frac{3}{4} \left(3-\sqrt{5}\right) \approx 0.572949\ldots$$

share|improve this answer
    
Thank you, that is very helpful! So the probabilities do converge. –  gentisse May 4 '11 at 0:00
    
how did you get the denominator in your probability? I'm not really seeing where the 3n-1 comes from –  gentisse May 4 '11 at 0:13
    
It gives the wrong answer otherwise, in the same way the Catalan numbers ${2n \choose n}/(n+1)$ have $n+1$ in the denominator: I arrived at it trying to simplify something ugly. There are $15$ paths which arrive back at zero after six steps but $3\times 3$ first arrived after three, leaving $6$; there are $84$ paths which arrive back at zero after nine steps but $3\times 15$ first arrived after three and $6\times 3$ first arrived after six, leaving $21$; and so on. –  Henry May 4 '11 at 1:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.