1

Let $S_n$ be a simple random walk on $\mathbb{Z}$, starting from 0, and let $c>0$ be an integer. Show that $$ \mathbb{P}\left(\underset{1\leq j\leq n}{\max}|S_{j}|\geq c\right)\leq2\mathbb{P}\left(|S_{n}|\geq c\right) $$

I am struggling with this one for a while, still not sure how to start. My first intuition is to use markov inequallity, but I cant see exactly how. Any help would be highly appreciated.

DirichletIsaPartyPooper
  • 609
  • Can you explain the assumptions that go into a "simple random walk"? – Michael Dec 31 '22 at 23:31
  • @Michael $S_n$ is the sum of Rademacher i.i.d random variables. – Andrew Jan 01 '23 at 00:04
  • 1
    The reflection principle applies – jlammy Jan 01 '23 at 00:04
  • This is a standard result and can be found in any book which covers random walks… if you don’t want spoilers, tag me for a hint. – Andrew Jan 01 '23 at 00:06
  • 1
    @AndrewZhang : It is not clear if symmetry applies or not. The OP has not responded. A google search on "simple random walk" gives various definitions, some including symmetry, some not. For your "Rademacher" description it also is not clear if symmetry holds. I believe the result holds regardless but it is easier to prove under symmetry assumptions. – Michael Jan 01 '23 at 00:09
  • @Michael Symmetry applies. – DirichletIsaPartyPooper Jan 01 '23 at 11:33
  • @AndrewZhang can you point me to one? – DirichletIsaPartyPooper Jan 01 '23 at 11:34
  • @DirichletIsaPartyPooper Apparently I have misled you, since I also cannot find a reference covering this identical problem. But as jlammy said, if you google reflection principle simple random walk, you will find a lot of information. – Andrew Jan 01 '23 at 14:15

1 Answers1

1

Hint: Fix $n$ as a positive integer. Just look at the event $\{S_n\geq c\}$ for simplicity (the case $S_n\leq -c$ is similar). Let $M$ be the first time index $i$ such that $S_i\geq c$ (define $M=\infty$ if it never happens). Then $$\cup_{i=1}^n\{M=i, S_n\geq S_i\} \subseteq \{S_n\geq c\}$$ and notice by symmetry that $$P[S_n\geq S_i|M=i]\geq 1/2 \quad \forall i \in \{1, ..., n\} \quad (*)$$ Now you can prove that $$P[\cup_{i=1}^n\{M=i\}] \leq 2P[S_n\geq c]$$

This symmetry argument works whenever we have the following general scenario: $S_0=0$ and $$ S_n = \sum_{i=1}^n X_iV_i \quad \forall n \in \{0, 1, 2, ...\}$$ where $\{X_i\}_{i=1}^{\infty}$ and $\{V_i\}_{i=1}^{\infty}$ are mutually independent processes, $\{X_i\}_{i=1}^{\infty}$ are i.i.d. random variables of any distribution (possibly noninteger), $\{V_i\}_{i=1}^{\infty}$ are i.i.d. with $P[V_i=1]=P[V_i=-1]=1/2$. Then equation (*) applies.

Michael
  • 23,905