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 (*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 *k*th 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 2*n* with at least *k* zeros which end at zero to paths
of length 2*n*-*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

/ 2*n*-*k* \
2^{k} | |
\ *k* /

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.