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.

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 alpha;, there is a uniquely define walk alpha;' 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

• Arithmetic in Disguise
• Construction of Pascal's Triangle
• Dot Patterns, Pascal Triangle and Lucas Theorem
• Integer Iterations on a Circle
• Leibniz and Pascal Triangles
• Lucas' Theorem
• Patterns in Pascal's Triangle
• Random Walks
  • The Ballot Lemma
  • The Reflection Lemma
• Sierpinski Gasket and Tower of Hanoi
• Treatise on Arithmetical Triangle
• Ways To Count

|Activities| |Contact| |Front page| |Contents| |Algebra| |Up| |Store|

Copyright © 1996-2012 Alexander Bogomolny