# Reflection principle for simple random walk

Let $(X_n)$ be a sequence of independent random variables, such that $P(X_i=1) = P(X_i=-1) = 1/2$. Then, the reflection principle states that for all $a > 0$,

$$P(\max_{1\leq k\leq n} S_k \geq a) = P(S_n \geq a) + P(S_n \geq a + 1).$$

I have looked at many places but I have rarely found a full proof for the simple random walk case (I have found lots of document that state it for stochastic process / brownian motion, etc. ). So just to be sure to understand, I wrote the following proof. Is it correct?

Proof : We have, for $a \in \mathbb N$,

\begin{align*}P\Big(\max_{k\leq n} S_k \geq a\Big) &= \sum_{k=-n}^n P(\max_{k\leq n} S_k \geq a \cap S_n = k) \\ &= \sum_{k=-n}^{a - 1} P(\max_{k\leq n} S_k \geq a \cap S_n = k) + \sum_{k=a}^n P(\max_{1\leq k\leq n} S_k \geq a \cap S_n = k) \\ &= \sum_{k=-n}^{a - 1} P(\max_{k\leq n} S_k \geq a \cap S_n = 2 a - k) + \sum_{k=a}^n P(\max_{1\leq k\leq n} S_k \geq a \cap S_n = k) \\ &= \sum_{k=-n}^{a - 1} P(S_n = 2 a - k) + \sum_{k=a}^n P(S_n = k) \\ &= \sum_{j=a+1}^{2 a + n} P(S_n = j) + \sum_{k=a}^n P(S_n = k) = P(S_n \geq a + 1) + P(S_n \geq a). \end{align*}

When $a$ is not an integer, the same argument works by replacing $a$ by $\lceil a \rceil$, and we can verify that the equality $P(\max_{1\leq k\leq n} S_k \geq a) = P(S_n \geq a) + P(S_n \geq a + 1)$ still holds.

• "I have looked at many places but I have rarely found a full proof for the simple random walk case" Hmmm... Two seconds on gg yield this: cgm.cs.mcgill.ca/~breed/MATH671/lecture2corrected.pdf (page 4). – Did Feb 5 '16 at 11:23
• Oops, it seems that maybe I did not look far enough in this document, you're right! Well, anyway, I learned something by trying to do the proof myself! – Basj Feb 5 '16 at 11:27
• @Did I'm trying to adapt this proof for $X_i \sim \mathcal N(0,1)$ (not brownian, but still discrete random walk with $X_i$ normal). What would be equivalent of $P(\max_{k\leq n} S_k \geq a) = \sum_{k=-n}^n P(\max_{k\leq n} S_k \geq a \cap S_n = k)$ ? Is something like $P(\max_{k\leq n} S_k \geq a) = \int_{-\infty}^{+\infty} P(\max_{k\leq n} S_k \cap S_n = t) d t$ the correct equivalent? – Basj Feb 5 '16 at 11:59