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.

Let's consider this simple dice game: A coin is faked so it has p chance to land on heads, and 1-p chance to land on tails. Every round costs $1, and gives you $2 if you win (for a total of +$1).

Assume you're starting with $n. What are your odds to "go infinite" - be able to play the game forever? This sounds like Markov Chains 101, it's just been ages since I read anything about Markov Chains.

Also - given any constant m, what are the odds of ever reaching $m in this game?

share|improve this question
    
I can answer the second question: if $m < n$ then the probability is between $0$ and $1$, if $m \geq n$ then the probability is $1$. –  Yuval Filmus Feb 4 '11 at 7:26
    
@Yuval: The probability is most certainly not 1. Imagine you start out with $1 and lose the first round... –  BlueRaja - Danny Pflughoeft Jun 24 '11 at 23:23
add comment

1 Answer

up vote 5 down vote accepted

Define $f(n)$ as the probability of playing forever when starting out with n coins. Also, assume that the probability p of winning a round is bigger than $\frac{1}{2}$ (otherwise, the probability of playing forever is 0). Then, we get the recurrence relation $$ f(n) = p f(n + 1) + (1-p) f(n-1) $$ with the boundary conditions $f(0) = 0$ and $\lim_{n \to \infty} f(n) = 1$.

The general solution of the recurrence relation is $$ f(n) = a + b \left( \frac{1-p}{p} \right)^n $$ and from the boundary conditions we get $a = -b = 1$. So, the probability to play infinitely is $$ f(n) = 1 - \left( \frac{1-p}{p} \right)^n . $$

The second question can be answered just as the first one, but with different boundary conditions: $f(0) = 0$ and $f(m) = 1$. This leads to the probability of reaching m as $$ \frac{1 - \left( \frac{1-p}{p} \right)^n}{1 - \left( \frac{1-p}{p} \right)^m} . $$

By the way, the keyword for this kind of problems is 'Random Walk'.

share|improve this answer
add comment

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.