By Jochen Voss, on
Recently I learned how to compute the distribution of the number N of visits in zero of a one-dimensional, symmetric, simple random walk (Xn), conditioned on X2n=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 2k 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:
This is an excerpt from Jochen's blog.
Newer entry: What every Programmer should know about memory
Older entry: Shiny New Shelf
Copyright © 2007, Jochen Voss. All content on this website (including text, pictures, and any other original works), unless otherwise noted, is licensed under a Creative Commons Attribution-Share Alike 3.0 License.