The Reflection Lemma

The Reflection Lemma is concerned with counting the number of random walks that satisfy certain conditions. It is quite common to denote the number of walks from A = (0, a) to B = (n, b) as N_n(a, b). A walk (S₁, S₂, ..., S_n), for which s_k = S₁ + S₂ + ... + S_k = 0, for some k > 0 is said to touch or cross the x-axis, depending as whether the next value S_k+1 is ±1. The set of walks that touch or cross the x-axis is complementary to the set of walks that stay on the same side of the axis. The latter set is the subject of the Ballot Lemma.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

The Reflection Lemma

For a > 0, b > 0,
M_n(a, b) = N_n(-a, b),

where M_n(a, b) is the number of walks from A = (0, a) to B = (n, b) that cross or touch the x-axis.

The applet provides a graphical illustration for a proof of the Reflection Lemma. Let A' = (0, -a). If, for a walk starting at A, s_k = 0, for some k, there is the first k for which this happens. For such a walk, say α, there is a uniquely define walk α' that starts at A' and, up to the point (k, 0) is a reflection of α in x-axis, after which it coincides with α. As every walk from A' to B crosses the axis, it is uniquely relates to a walk from A to B that crosses or touches the x-axis.

The applet actually illustrates the Lemma for walks from (x, a) to (x + n, b) that do not necessarily start at the y-axis.

References

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition, Wiley, 1968

Pascal's Triangle and the Binomial Coefficients

73356737