## 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 Nn(a, b). A walk (S1, S2, ..., Sn), for which sk = S1 + S2 + ... + Sk = 0, for some k > 0 is said to touch or cross the x-axis, depending as whether the next value Sk+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,
Mn(a, b) = Nn(-a, b),

where Mn(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, sk = 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

1. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition, Wiley, 1968 ### Pascal's Triangle and the Binomial Coefficients 