Simple symmetric random walk

A simple symmetric random walk starting from $S_0$ haswhere the increments ${\xi }_k$ are independent and satisfy

For a simple symmetric random walk starting from zero, its first hitting time of $1$ is almost surely finite but has infinite expectation. Stopping at exit from $[-m,1]$, the optional stopping theorem for $S_n$ gives upper-exit probability $m/(m+1)$, while stopping $S_n^2-n$ gives mean exit time $m$. The first probabilities tend to one, and the exit times are bounded above by the first passage to $1$, proving both conclusions. Finite-time stopping and bounded stopped positions justify passage to the exit time.

Suppose two independent planar simple symmetric random walks are compared while one stays at its $j$th position throughout a deterministic time block. If each block has an unconditional probability bounded below by a positive constant that the other walk visits the origin, simultaneous origin visits occur infinitely often almost surely. Markov-chain recurrence gives infinitely many origin blocks for the sleepy walk. The block bound yields positive probability of infinitely many coincidences; eventual coupling of planar symmetric random walks then makes this future event have probability zero or one. Conditional block bounds or independence of capture attempts are not required.

For a simple symmetric random walk, the estimate $\mathbb{E}{e}^{\theta S_n}\le e^{n{\theta }^2/2}$ and the exponential maximal inequality give $\mathbb{P}({\max }_{k\le n}{S}_k\ge t\sqrt{n})\le e^{-t^2/2}$ for $t\ge 0$.

For the simple symmetric random walk on $\mathbb{Z}$, the renewal equation relates first-return and return probability generating functions. The central-binomial return series is $U(s)=(1-s^2{)}^{-1/2}$, giving $F(s)=1-U(s{)}^{-1}$. Its value tends to one at $s=1$, but its derivative diverges there: the walk has null recurrent states.

For a simple symmetric random walk on the integers, let $T_k$ be the first time that $k$ distinct vertices have been visited. The visited set is an interval, and at $T_k$ the walk is at an endpoint. The Strong Markov property turns the time to add one vertex into gambler's ruin between the two immediately exterior vertices, starting one step from a boundary. The expected duration of symmetric gambler's ruin is therefore $k$. This also holds at $k=1$.

For a simple symmetric random walk, $S_n^2-n$ is a martingale because the next increment has conditional mean zero and conditional square one.

If $T$ is a stopping time with finite mean, thenStopping first at $T\wedge n$ and using the $L^2$ martingale convergence theorem justifies passage to an unbounded $T$.

For a walk with increments $+1$ with probability $p$ and $-1$ with probability $1-p$, putThen $\exp (\theta S_n-n\psi (\theta ))$ is a martingale. Optional stopping at the first linear-boundary crossing and optimization over $\theta$ gives exponential maximal-deviation bounds governed by the Legendre transform of a cumulant-generating function.