Andre’s Reflection Method

I promised to post something about random walks. I learned the content of this post while listening to Vilppu Tarvainen’s bachelor’s degree talk and I consider it is quite cute.

Let us consider a one dimensional random walk: formally it is a sequence where can be either 1 or -1 with equal probability. That is, at each step we either go right (+1) or left (-1); is the first step, the second and so on. Suppose a fellow stands at some natural number and then executes such a random walk: an n-step walk, and at each step goes left or right by one:

For example, if the starting position is the picture above and the walk is given by , then you end up at 4.

Question: Suppose a fellow stands at the positive natural number k and makes a random walk of length n which ends up back at k. What is the probability that the fellow never visited zero? (n is assumed to be even, or otherwise it is impossible to get back to k)

This problem seems to be originated as the so-called Ballot Problem: Suppose A and B are candidates for office and there are 2n voters, n voting for A and n for B. In how many ways can the ballots be counted so that B is never ahead of A? To formulate this in the previous setting, let a vote for A be +1 and a vote for B -1. The random walk is now determined by the order of counting the votes and the starting point is 1. If you visit zero during the counting, then B is necessarily ahead of A at this step. Note that since the voters voted equally for A and B, the walk ends up at 1.

More generally one can of course ask: if 1 occurs with probability p and -1 with probability 1-p in the walk and we know that the walk starts at k>0 and ends at m>0, what is the probability that the walk does not visit zero? The answer below generalizes easily to this extend.

Answer: André’s Reflection Method. Désiré André (1840-1917)

A brute force counting might be possible; but if brute force were the solution I am going to present, I wouldn’t bother to write this post at all.

So in the following k>0 is a natural number and n>0 is an even natural number.

Denote by the number of all random walks of length n that start at k and end at k. Denote by the number of all random walks of length n that start at k, end at k and visit 0. Clearly now the Question asks for the value of

It is easily seen that

is just the number of subsets of n of size (The walk will get back to k from k iff the number of -1′s and 1′s in the walk is the same; so all walks with 1′s everywhere except for steps are suitable. Hence it is enough to calculate the number of subsets of of size . Recall that n is even). So now we are left with calculating .

Further, denote by the set of all random walks that start at -k and end at k.

Theorem (André’s Method.) .
Proof. Sets are of the same size if there is a bijection between them. We shall define a bijection f between the sets R={walks from k to k that do visit zero} and S={walks from -k to k}. Suppose that is a random walk in R. Let i be the first number such that ; in other words i is the first step after which the walk visits zero. We know that it will happen since the walk is in R. Then put , if and if and define

Why is it a bijection? It is easily seen to be injection: the walks and meet zero first time at the same step and so if , then and must meet zero first time at the same step. Further by definition of f they must agree before that zero and also after that zero. In order to see that it is a surjection, fix a walk from -k to k. Applying the obvious inverse map if and if , where i is the first step, meets zero, we get such that .

Now we have just to calculate . The idea is the same as calculating above. is a walk of length n that gets from -k to k. So there are 2k more 1′s than -1′s. So we have to calculate in what possible orders can 1′s and -1′s occure in a row. This equals

.

Thus the final answer is

What a nice illustration of how a mathematical theorem can simplify a calculation!