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 [tex]\bar a=(a_1,\dots, a_n)[/tex] where [tex]a_i[/tex] can be either 1 or -1 with equal probability. That is, at each step we either go right (+1) or left (-1); [tex]a_1[/tex] is the first step, [tex]a_2[/tex] the second and so on. Suppose a fellow stands at some natural number [tex]k[/tex] 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 [tex](-1,-1,1,1,1,-1,-1)[/tex], 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 [tex]R_k[/tex] the number of all random walks of length *n* that start at *k* and end at *k*. Denote by [tex]R_k(0)[/tex] 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

[tex]\displaystyle 1-\frac{R_k(0)}{R_k}[/tex]

It is easily seen that

[tex]R_k=\left({n}\atop {n/2}\right)[/tex]

is just the number of subsets of *n* of size [tex]n/2[/tex] (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 [tex]n/2[/tex] steps are suitable. Hence it is enough to calculate the number of subsets of [tex]\{1,\dots n\}[/tex] of size [tex]n/2[/tex]. Recall that *n* is even). So now we are left with calculating [tex]R_k(0)[/tex].

Further, denote by [tex]S_k[/tex] the set of all random walks that start at –*k* and end at *k*.

**Theorem** (André’s Method.) [tex]R_k(0)=S_k[/tex].

**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 [tex](a_1,\dots,a_n)[/tex] is a random walk in *R*. Let *i* be the first number such that [tex]\sum_{j=1}^i a_j=0[/tex]; 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 [tex]b_j=a_j[/tex], if [tex]j\gneq i[/tex] and [tex]b_j=-a_j[/tex] if [tex]j\le i[/tex] and define

[tex]f((a_1,\dots, a_n))=(b_1,\dots, b_n).[/tex]

Why is it a bijection? It is easily seen to be injection: the walks [tex]\bar a=(a_1,\dots,a_n)[/tex] and [tex]f(\bar a)[/tex] meet zero first time at the same step and so if [tex]f(\bar a)=f(\bar b)[/tex], then [tex]\bar a[/tex] and [tex]\bar b[/tex] 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 [tex](b_1,\dots,b_n)[/tex] from –*k* to *k*. Applying the obvious inverse map [tex]a_j=b_j[/tex] if [tex]j\gneq i[/tex] and [tex]a_j=-b_j[/tex] if [tex]j\le i[/tex], where i is the first step, [tex]\bar b[/tex] meets zero, we get [tex]\bar a[/tex] such that [tex]f(\bar a)=\bar b[/tex]. [tex]\square[/tex]

Now we have just to calculate [tex]S_k[/tex]. The idea is the same as calculating [tex]R_k[/tex] above. [tex]S_k[/tex] is a walk of length *n* that gets from –*k* to *k*. So there are 2*k* more 1’s than -1’s. So we have to calculate in what possible orders can [tex](n/2+k)[/tex] 1’s and [tex](n/2-k)[/tex] -1’s occure in a row. This equals

[tex]\displaystyle \left(n\atop{n/2-k}\right)[/tex].

Thus the final answer is

[tex]1-\displaystyle \frac{\left(n\atop{n/2-k}\right)}{\left(n\atop{n/2}\right)},\text{ which equals }\frac{1}{n+1}\text{ when }k=1.[/tex]

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

Pingback: Walks On Math » The Drunken Finn