Simple random walk

A simple random walk on a locally finite graph chooses each vertex in the current vertex's graph neighbourhood with equal probability, assuming there is at least one available neighbour. On the integer line there are two choices, one unit left or right, so each has probability $1/2$. This is the one-dimensional simple symmetric random walk. Terminology varies: a simple random walk on the integer line is also often allowed unequal step probabilities, with “symmetric” specifying the fair case.

For a simple symmetric random walk starting at $S_0=0$, each increment has the Rademacher distribution, with expected value zero and variance one. Thus linearity of expectation and the variance of a sum of independent random variables giveFor example, after $80$ steps the expected value is zero, the variance is $80$, and the standard deviation is $\sqrt{80}\approx 8.944$. Doubling the typical distance scale takes four times as many steps. This square-root growth explains why a random walk can wander far even when there is no preferred direction.

The colored curves are illustrative sample paths, not averages over all possible walks. The dashed curves show the expected values; the shaded bands show the expected value plus or minus one standard deviation at each time. These bands are a scale of spread, not confidence intervals, and give no guarantee that an entire sample path stays inside them.

Zero expected value does not make this a stationary process: its one-time probability distribution changes with $n$, as the increasing variance already proves. It does have stationary increments and independent increments, because blocks of fresh steps have the same probability distribution at any starting time and disjoint blocks use independent random variables. This separation of position from increment is one reason the random walk is such a useful first example of a stochastic process.

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

On the $n$-dimensional hypercube graph, simple random walk flips one uniformly chosen coordinate at each step. Its stationary distribution is uniform on the $2^n$ vertices, so its mean return time is $2^n$.

For random walk on $\{-1,1{\}}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the Walsh characters $f_J(x)={\prod }_{j\in J}{x}_j$ form an orthonormal eigenbasis under the uniform distribution on a finite set. Flipping a coordinate in $J$ negates $f_J$, so $P{f}_J=(1-|J|/n)f_J$. Hence $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the ordinary and absolute spectral gaps both equal $1/n$.

A simple random walk on ${\mathbb{Z}}^2$ visits its starting point infinitely often almost surely and hits every fixed vertex almost surely.