A gambler repeatedly plays a game where in each round, he wins a dollar with probability 1/3 and loses a dollar with probability 2/3. His strategy is “quit when he is ahead by 2 dollars”, though some suspect he is a gambling addict anyway. Suppose that he starts with a million dollars. Show that the probability that he’ll ever be ahead by $2 is less than 1/4.

Is it possible to solve it without Markov chain and with a very basic reasoning.

  • $\begingroup$ Asking to use "basic reasoning" instead of some kind of theory is really asking the wrong thing. The whole point of theories like that of the Markov Chain is that it collects together a whole variety of individual arguments, and puts them into a framework where it's clear that all the arguments have a common structure, only with certain parameters tweaked. If you want to use more elementary reasoning, you need simply read the proofs of the theorems about Markov chains. Conversely, I suspect any "basic reasoning" that will give you your answer can also be adapted into a proof of Markov chains $\endgroup$ – oxeimon Aug 2 '15 at 18:12
  • $\begingroup$ It is interesting to note the following "paradox": the fellow is better off hazarding twice the amount (\$2 for a win, -\$2 for a loss). That gives him a $\frac 13$ shot of getting the \$2 on the first pass. Unfair games are like that...it's better to wager higher stakes than to let the house bleed away assets. $\endgroup$ – lulu Aug 2 '15 at 18:38

Let $P(i)$ denote the probability he'll get to $\$1,000,002$ if he starts from $\$i$. We know that $$P(0)=0\;\;\;P(1,000,002)=1$$ You are asked to find $P(1,000,000)$. Imagine he has $\$i$ and places a bet. He either gets to state $(i+1)$ or to state $(i-1)$ and we have: $$P(i) = \frac 13 P(i+1)+\frac 23 P(i-1)$$ It is easier to start near the "ruin state". We see, for example, that $$P(1) = \frac 13 P(2)+\frac 23 P(0)=\frac 13 P(2)\;\;\;\Rightarrow\;\;\;P(2)=3P(1).$$ In a similar way we see that $$P(3) = 7P(1)\;\;\mbox{and}\;\;\;P(4)=15P(1)$$ We are lead to conjecture that $$P(n) = \left(2^{n}-1\right)P(1)$$ And this is easily confirmed by induction.
To finish, we compute $P(1)$ from the other boundary value: $$P(1,000,002)=1=(2^{1,000,002}-1)P(1)$$ Whence $$P(1) = \frac {1}{(2^{1,000,002}-1)}$$ We now see the answer: $$P(1,000,000)= \frac{2^{1,000,000}-1}{2^{1,000,002}-1}$$ From which the desired inequality follows at once.

We note that $4$ times the numerator is $2^{1,000,002}-4$ so $4P(1,000,000)=1-\frac{3}{2^{1,000,002}-1}$. We may be below $\frac 14$ here, but not by much.

  • $\begingroup$ @ByronSchmuland Thanks for the edits. As soon as there are dollar amounts involved in the text my formatting invariable collapses. I generally just avoid them. $\endgroup$ – lulu Aug 2 '15 at 18:45
  • $\begingroup$ Hi lulu, Is it possible to solve following problem in gambler's ruin framework -: Calvin and Hobbes play a match consisting of a series of games, where Calvin has probability p of winning each game (independently). They play with a “win by two” rule: the first player to win two games more than his opponent wins the match. Find the probability that Calvin wins the match (in terms of p) $\endgroup$ – Rahul Aug 9 '15 at 21:08
  • 2
    $\begingroup$ @Rahul. Sure. $5$ states labeled by "#games Calvin is ahead by", thus $<i>$ for $i\in{-2,-1,0,1,2}$. Of course $<-2>$ is a Loss and $<2>$ is a Win. Let $P[i]$ be the probability that Calvin wins from state $<i>$. Then, $P[i]=p*P[i+1]+(1-p)*P[i-1]$. Easy backwards induction from there. $\endgroup$ – lulu Aug 9 '15 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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