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.
Best Answer
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.