# Finding a clever solution to a game of chance

This question may smell like my older question http://math.stackexchange.com/questions/1778/a-probability-game, but this time my intentions are different.

The above problem came from my friend. Or so I thought, it really came from me incorrectly remembering his problem. The problem he actually gave me was:

Suppose you start with 1 dollar and flip a weighted coin. With probability 3/4 (call this heads) you win a dollar and with probability 1/4 (call this tails) you lose a dollar. What is the probability you eventually run out of money? (Suppose the house has as many dollar bills as needed).

I know how to solve this problem in the following way: First observe the number of tails must equal the number of heads plus one. If a string of Hs and Ts satisfy this property, call it Good. Now we want to count the number of Good strings that don't have Good proper prefixes. For a string of length 2n-1 this is just the nth Catalan number. Now we just take the appropriate summation and we arrive at the probability we eventually run out of money which turns out to be 1/3.

Now when my friend told me this problem, he said he was able to apply a clever trick and solve it almost instantly. The thing is, he doesn't remember how he did it. He says he vaguely remembers using a recurrence relation and then telescoping a sum. (Which sounds very plausible)

So can you come up with a short and sweet solution?

On a side note, I am aware my title is poor at best. If you can think of a better one, please let me know.

-
I don't really know probability that well so I'll just comment. Can't you reason that at trial 1, probability of loss is (1/4). Then if you win trial 1, probability of then losing is (1/4)(1/4) since you need to lose 2 in a row. As this continues, we get the probability of loss to be (1/4)+(1/16)+(1/64)+...=(1/4)(1-(1/4))=1/3. –  WWright Sep 5 '10 at 3:27
@WWright: That argument doesn't work because a) there should be a factor of $3/4$ for each time you win, and b) you're only considering sequences consisting of a streak of wins followed by a streak of losses, whereas the wins and losses can occur in any order. –  joriki Jan 6 '12 at 22:20

If $p$ is the probability that you eventually lose a dollar then we must have that

$$p = \frac{1}{4} + \frac{3}{4}p^{2}$$

(We lose a dollar, or win one and lose two eventually).

Solving gives $p=1$ or $p=\frac{1}{3}$. I suppose we can eliminate $p=1$ somehow and get $p=\frac{1}{3}$ as the required answer.

-
I think saying p is the probability that your net loss is eventually one dollar is clearer than saying you eventually lose a dollar. But nonetheless, this is a great solution. –  yjj Sep 5 '10 at 6:56
Can someone clarify as to the "somehow" eliminate p = 1? –  Sev Sep 5 '10 at 8:12
$p=1$ means you surely lose a dollar (zero chance of gaining a dollar), which is implausible. –  Ｊ. Ｍ. Sep 5 '10 at 17:09
@J. M.: I'm not so sure--p=1 means that you surely lose the dollar eventually (which is true if the coin were fair), not that there is zero chance of gaining the dollar right now. –  Isaac Sep 6 '10 at 6:44
@Isaac: I agree. The relationship between this answer and the value $p=1$ for a fair coin is illuminated in ronaf's answer: The two solutions of the quadratic equation cross at $\alpha=1/2$, $p=1$. We want the lower one, $p=\alpha/(1-\alpha)$, for $\alpha\le1/2$ and the upper one, $p=1$, for $\alpha\ge1/2$. –  joriki Jan 6 '12 at 22:38

Here is a more formal way to derive the answer: Define $q_n$ to be the probability that you eventually go broke when you start with $n$ dollars. Then $q_0 = 1$, $\lim_{n \to \infty} q_n = 0$, and $q_n = \frac{1}{4} q_{n-1} + \frac{3}{4} q_{n+1}$.

The last equation defines a recursive sequence with constant coefficients, whose general solution is $q_n = c_1 + c_2 3^{- n}$ (the factors $1$ and $\frac{1}{3}$ come from solving the quadratic equation of Moron's answer, which is the fundamental equation of the recursion). To satisfy the other two conditions on $q_n$, we see that $c_1 = 0$ and $c_2 = 1$ i.e. $q_n = 3^{-n}$.

In particular, the probability to go broke starting with one dollar is $q_1 = \frac{1}{3}$.

-
This is a good method, but $\lim_{n \to \infty} q_n = 0$, right? –  Michael Lugo Sep 5 '10 at 17:27
Lugo: Good catch, thanks. Corrected. –  Michael Ulm Sep 5 '10 at 18:19

the assertion $q_n \to 0$ as $n \to \infty$ in michael ulm's response is perhaps not entirely obvious - and is related to the remark in moron's response: "I suppose we can eliminate $p=1$ somehow..".

i'll elaborate a bit more on this:

suppose $\alpha$ is the probability of winning $\$1$and$\beta = 1-\alpha$is the chance of losing$\$1$. two facts are clear:

$$(1)\kern{15pt} q_0=1\kern{10pt} {\rm and\ for}\kern{10pt} n\ge 1,\kern{10pt} q_n = \alpha q_{n+1} + \beta q_{n-1},$$

$$\kern{-1.2in}(2) \kern{1.5in} q_n = q_1^n,\qquad n\ge 1.$$

taking $n = 1$ in (1) and writing $q_1 = q$ gives

$$\kern{-1.7in}(3) \kern{1.5in} q = \alpha q^2 + \beta,$$

which means $q = 1$ or $q = {\beta\over\alpha}$.

so if $\alpha \le \frac{1}{2},\ q = 1$ [because one root is $\ge 1$], while if $\alpha > \frac{1}{2}$, both roots are admissible answers.
[this is what moron also concluded.]

to rule out the case $q = 1$, we can argue as follows:

suppose $q = 1$ and let $S_n$ be the player's fortune at time $n$. then

$T = T_1 = in\kern{-1pt}f \{ n \ge 1 : S_n = 0\}$ is finite ($wp1$).

now consider just the random walk $\{S_n : n \ge 1\}$ [forgetting about the gambling context]. we can recursively define $T_{k+1} = in\kern{-1pt}f \{n > T_k : S_n = -k\}$. then $T_k$ is finite ($wp1$) for all $k\ge 1$.

then $\{S_{T_k} = 1-k : k \ge 1\}$ is a nonpositive subsequence of $\{S_n\}_1^\infty$.

but this contradicts the SLLN which $\mathit inter\ alia$ implies that $S_n\to \infty$ when $\alpha > \frac{1}{2}$.

so the case $q = 1$ is ruled out, and therefore $q = \frac{\beta}{\alpha} = \frac{1}{3}$ when $\alpha = \frac{3}{4}$.

-