Ties in Matching Pennies

Question

Players A and B match pennies N times. They keep a tally of their gains and losses. After the first toss, what is the chance that at no time during the game will they be even?

I have seen a solution for this problem summing a series of choose functions for an expectation, but I wanted to solve it with a simple random walk in one dimension.

my logic is thus; suppose a random walk in 1 dimension. half chance for a step to the left or to the right. and one coin toss has gone (say A) so suppose we start at position 1 and go right for A and left for B, how likely is it we reach 0 in N steps or less.

So call $p_N$ the probability for doing it in N steps. Then it seems to me we have $$p_N = \frac{1}{2} + \frac{1}{2}p_{N-2}\frac{1}{2}= \frac{1}{2} + \frac{1}{4}p_{N-2}$$ since if he goes right on the first step he has N-2 steps or less to get back to 1 and then a half chance of hitting 0.

Solving the recurrence on noticing that $p_2$ = $\frac{1}{2}$ gives $$ p_{2n} = p_{2n+1} = \frac{1 + 4 + 4^2 ... + 4^{n-1}}{4^{n-1}.2}$$

Now this agrees with the correct answer for the first couple of cases but then slowly differs as N gets bigger.

Could someone please explain my mistake and perhaps give a correct solution to this problem using random walks?

Answer 1

I don’t see a random walk solution of the very simple kind that you had in mind, but there’s a walk-counting solution that’s not too bad.

Suppose that a walk starts to the right and first returns to $0$ in $2n$ steps. Represent it as a sequence of R’s and L’s, for Right and Left steps; it must be of the form LWR, where W is a Dyck word of length $2(n-1)$, and every Dyck word of length $2(n-1)$ gives rise to such a walk. It’s well known that there are $C_{n-1}$ Dyck words of length $2(n-1)$, where $C_k$ is the $k$-th Catalan number, and that

$$C_k=\frac1{k+1}\binom{2k}k\;,$$

so that

$$C_{n-1}=\frac1n\binom{2n-2}{n-1}=\frac1n\binom{2n-2}{n-1}\cdot\frac{2n(2n-1)}{2n(2n-1)}=\frac1{2(2n-1)}\binom{2n}n\;.$$

There are the same number of walks that start to the left and first return to $0$ in $2n$ steps. Thus, the probability of a first return to $0$ in $2n$ steps is

$$\frac{2C_{n-1}}{2^{2n}}=\frac1{(2n-1)2^{2n}}\binom{2n}n\;.$$

Answer 2

When you write $p_N=\frac 12 +\frac 12p_{N-2}\frac12$ you are assuming the only ways to get back to zero are either to go immediately (the first $\frac 12$) or to take one step away (the leading $\frac 12$ in the next term) and then come back towards zero immediately (the second $\frac 12$ in the second term). This is consistent with your use of $p_{N-2}$ as you have defined this as the probability of hitting zero in $N-2$ steps starting at $1$. But you can also have the first step go to $2$, the third to $3$, and then return to zero. You have missed this chance.