Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 36 ยท Random Walks and Brownian Motion

The Reflection Principle and the Maximum of a Walk

Use the reflection principle to count random walk paths that touch a level. Derive P(max โ‰ฅ a) for the symmetric walk and verify it with exact counting.

How high does a random walk climb before time n? Does it ever touch a level a? These questions about the running maximum Mโ‚™ = max(Sโ‚€, Sโ‚, โ€ฆ, Sโ‚™) have a surprisingly clean answer for the symmetric walk, found by a geometric trick called the reflection principle. The same idea reappears for Brownian motion, where it gives the distribution of the maximum and of hitting times.

Throughout, Sโ‚™ is the symmetric simple random walk started at 0.

The reflection principle

Fix a level a > 0 and let ฯ„ be the first time the walk reaches a. Take any path that touches a at some time before n but ends below a, at position b < a. After time ฯ„, reflect the rest of the path across the horizontal line at height a: every up-step becomes a down-step and vice versa. The new path ends at 2a - b > a.

This is a one-to-one correspondence between

  • paths that hit a and end at b < a, and
  • paths that end at 2a - b (any path ending above a must hit a).

Because every path of length n has the same probability 2^(-n), we get

Text
P(M_n โ‰ฅ a, S_n = b) = P(S_n = 2a - b)        for b < a
flowchart LR
  A["Path touches level a, ends at b below a"] -->|"reflect after first hit"| B["Path ends at 2a - b above a"]
  B -->|"same probability 2^-n"| A

Reflection pairs paths that hit and end low with paths that end high.

Distribution of the maximum

Split the event {Mโ‚™ โ‰ฅ a} by the final position:

  • If Sโ‚™ โ‰ฅ a, the walk certainly touched a.
  • If Sโ‚™ < a, use reflection.

Summing over b < a, the reflected endpoints 2a - b cover all values above a. The result:

Text
P(M_n โ‰ฅ a) = P(S_n โ‰ฅ a) + P(S_n > a) = 2 P(S_n > a) + P(S_n = a)

In words, the maximum is about twice as likely to reach a as the end of the walk is to be above a. Example: for n = 100 the standard deviation of Sโ‚โ‚€โ‚€ is 10. The chance of ending above 10 is about 16%, so the maximum exceeds 10 with probability about 32%. (This is the normal approximation of the formula; exact values are computed below.)

Another consequence: P(M_n = k) = P(S_n = k) + P(S_n = k + 1). Only one of Sโ‚™ = k and Sโ‚™ = k + 1 has the right parity, so the maximum is as spread out as |Sโ‚™|: the running maximum "looks like" the absolute value of the endpoint, and in the limit the two have exactly the same law.

Exact counting versus the formula

The next program calculates the distribution of the maximum by a dynamic program that tracks both the position and the highest point reached, then compares with the reflection formula.

Python Exact distribution of the maximum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dynamic program (which never uses reflection) and the formulas agree to every printed digit.

Simulation and the arcsine surprise

Reflection answers questions about hitting levels. A related, more surprising question: what fraction of the time does a symmetric walk spend positive? Intuition says about half. In fact the fraction follows the arcsine law, which puts the most weight near 0 and 1, so a walk is most likely to spend almost all of its time on one side.

Python Maximum and the arcsine law by simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first block checks the reflection formula. In the histogram the outer bins hold more probability than the middle one, which is the arcsine law at work.

The reflection trick needs symmetry. For an unfair walk the reflected path has a different probability from the original, and the clean formula fails.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the reflection principle say about paths that hit level a and end at b < a?

    Reflecting the path after the first hit of a maps them to paths ending at 2a - b.
  2. 2. Which formula gives P(M_n โ‰ฅ a) for a symmetric walk and a > 0?

    P(M_n โ‰ฅ a) = P(S_n โ‰ฅ a) + P(S_n > a) = 2P(S_n > a) + P(S_n = a).
  3. 3. Roughly, what is P(M_100 โ‰ฅ 10) for the symmetric walk using the normal approximation (SD of S_100 is 10)?

    P(S > 10) is about 0.16, so twice that is about 0.32.
  4. 4. The arcsine law says the fraction of time a symmetric walk spends positive is most likely...

    The arcsine density piles up near the ends of [0, 1].

Summary

  • Reflecting a path after its first hit of a pairs hitting paths ending low with paths ending high.
  • For the symmetric walk: P(Mโ‚™ โ‰ฅ a) = 2P(Sโ‚™ > a) + P(Sโ‚™ = a).
  • The distribution of the maximum mirrors that of |Sโ‚™|.
  • The time a walk spends positive follows the arcsine law: a walk tends to stay on one side.

Next: Brownian Motion Basics