Random walk bridges

By , on [atom feed]

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

P(X1≠0, …, X2n≠0) = P(X2n=0)

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

/ 2n-k \ 2k | | \ k /

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

P(Nk | X2n=0) / 2n-k \ 2k | | \ k / = --------------- . / 2n \ | | \ n /

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.