Random walk bridges

By Jochen Voss, on 2007-10-17

Recently I learned how to compute the distribution of the number N of visits in zero of a one-dimensional, symmetric, simple random walk (X_n), conditioned on X_2n=0. There are two ways to compute this.

Plan A. Using the nice equality

which I learned long ago as a student, we can see that there is a bijection between all bridge paths and all paths which don't hit zero. (The equality is proved by constructing a bijection between the complements of these sets, using the reflection principle.) We can apply this to bridge paths with at least k zeros, mapping the path segment starting at the kth zero to a path which does not hit zero. This results in a bijection between all bridge paths having at least k zeros and all paths having exactly k zeros. If you happen to know this number, you are done. Otherwise you can use

Plan B. Consider the following map: for each bridge path with at least k zeros, flip the last k excusions so that they are all positive and then remove the last step of each of these excursions. This procedure defines a map from paths of length 2n with at least k zeros which end at zero to paths of length 2n-k (we removed k steps) which end at level k (all removed steps where downwards). It transpires that this map is surjective and every image has exactly 2^k pre-images. Thus the number of bridge paths with at least k zeros is

and dividing by the total number of bridge paths gives the required probability: