A gambler has 0 dollars. He tosses a fair coin that gives him 1 dollar on heads and he loses 1 dollar (goes into debt) on tails. What is the probability he'll reach 2 dollars before he goes 1 dollar in debt? I have other means of answering this, but wanted people to look at one particular solution which is returning a nonsense answer.
Let's call $P_{i,j}$ the probability that the gambler will hit $i$ dollars before going $j$ dollars in debt. Now, what happens when he tosses the coin once? With $\frac 1 2$ probability he'll make a single dollar and now he has to hit $i-1$ dollars before going $j+1$ dollars in debt. Similarly for if he gets tails he now has to hit $i+1$ dollars before going $j-1$ dollars in debt. So we get the recurrence:
$$P_{i,j} = \frac{1}{2} P_{i+1,j-1} + \frac{1}{2} P_{i-1,j+1}$$
Now plug in $i=2$ and $j=1$. We get:
$$P_{2,1} = \frac{1}{2} P_{3,0} + \frac{1}{2} P_{1,2} \tag{1}$$
Now we should have $P_{3,0}=0$ (which is another way of saying that if he gets tails he's already lost). Also, by symmetry we should have: $P_{1,2}=P_{2,1}$. But combining these two facts gives us:
$$P_{2,1}=0$$
What went wrong here?
Best Answer
You're right there is a symmetry, but it should be $P_{1,2}=1-P_{2,1}$.
This is because those are the only two stopping conditions. He either reaches $2$ dollars before reaching $1$ dollar and if not, he must have reached $1$ dollar before he reached $2$ dollars.