Simple symmetric random walk

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

Let $a<i<b$ and $a<j<b$ be integers. A simple symmetric random walk started at $i$ exits the integer interval at $\tau =\inf \{n\ge 0:S_n\in \{a,b\}\}$. Its expected occupation of $j$ before exit, including its initial state, isA block of $b-a$ consecutive positive steps forces exit, so the geometric tail bound from a uniform escape probability proves $\tau <\infty$ almost surely. Optional stopping at the bounded stopping time $n\wedge \tau$, followed by the bounded convergence theorem for $S_{n\wedge \tau }\in [a,b]$, gives the gambler's ruin probabilitiesTranslate the absolute value martingale of a simple symmetric random walk from zero to $j$. Bounded-time optional stopping yieldsUse monotone convergence on the increasing visit count and the bounded convergence theorem on the right. Substituting the exit probabilities giveswhich simplifies to the displayed expression by considering $i\le j$ and $i\ge j$. In particular, $G_{a,b}(0,0)=-2ab/(b-a)$ when $a<0<b$.

The proof establishes finite expected value of the visit count. Therefore each translated stopped absolute-value martingale is dominated in absolute value by a constant plus that total count, an integrable random variable; its family of values is uniformly integrable. This supplies the limit justification without assuming uniform integrability in advance.

For the nearest-neighbor symmetric walk on ${\mathbb{Z}}^3$, a return at time $2n$ uses $i,j,k$ positive and the same numbers of negative steps along each axis, with $i+j+k=n$. Counting arrangements gives the displayed identity. The sum of squares of the three-category multinomial distribution probabilities is at most their maximum. This maximum occurs at balanced counts and is $O(n^{-1})$ by Stirling's formula; the central binomial factor is $O(n^{-1/2})$. The total return probability is therefore summable. The expected number of visits is finite, so the probability of returning after time zero is strictly below one, proving that the origin is a transient state.

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$.