## 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 _{n}(a, b)._{1}, S_{2}, ..., S_{n}),_{k} = S_{1} + S_{2} + ... + S_{k} = 0,_{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*.

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

The applet provides a graphical illustration for a proof of the Reflection Lemma. Let _{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

The applet actually illustrates the Lemma for walks from

### References

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

### Pascal's Triangle and the Binomial Coefficients

- Binomial Theorem
- 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
- Lucas' Theorem II
- 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
- Another Binomial Identity with Proofs
- Vandermonde's Convolution Formula
- Counting Fat Sets
- e in the Pascal Triangle
- Catalan Numbers in Pascal's Triangle
- Sums of Binomial Reciprocals in Pascal's Triangle
- Squares in Pascal's Triangle
- Cubes in Pascal's Triangle
- Pi in Pascal's Triangle
- Pi in Pascal's Triangle via Triangular Numbers
- Ascending Bases and Exponents in Pascal's Triangle
- Determinants in Pascal's Triangle
- Tony Foster's Integer Powers in Pascal's Triangle

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

Copyright © 1996-2018 Alexander Bogomolny

68859493