Random walk
One-dimensional random walk

An elementary example of a random walk is the random walk on the integer number line, Z {\displaystyle \mathbb {Z} }, which starts at 0 and at each step moves +1 or −1 with equal probability.

This walk can be illustrated as follows. A marker is placed at zero on the number line, and a fair coin is flipped. If it lands on heads, the marker is moved one unit to the right. If it lands on tails, the marker is moved one unit to the left. After five flips, the marker could now be on -5, -3, -1, 1, 3, 5. With five flips, three heads and two tails, in any order, it will land on 1. There are 10 ways of landing on 1 (by flipping three heads and two tails), 10 ways of landing on −1 (by flipping three tails and two heads), 5 ways of landing on 3 (by flipping four heads and one tail), 5 ways of landing on −3 (by flipping four tails and one head), 1 way of landing on 5 (by flipping five heads), and 1 way of landing on −5 (by flipping five tails). See the figure below for an illustration of the possible outcomes of 5 flips.

To define this walk formally, take independent random variables Z 1, Z 2, … {\displaystyle Z_{1},Z_{2},\dots }, where each variable is either 1 or −1, with a 50% probability for either value, and set S 0 = 0 {\displaystyle S_{0}=0} and S n = ∑ j = 1 n Z j. {\textstyle S_{n}=\sum _{j=1}^{n}Z_{j}.} The series { S n } {\displaystyle \{S_{n}\}} is called the simple random walk on Z {\displaystyle \mathbb {Z} }. This series (the sum of the sequence of −1s and 1s) gives the net distance walked, if each part of the walk is of length one.The expectation E (S n) {\displaystyle E(S_{n})} of S n {\displaystyle S_{n}} is zero. That is, the mean of all coin flips approaches zero as the number of flips increases. This follows by the finite additivity property of expectation: E (S n) = ∑ j = 1 n E (Z j) = 0. {\displaystyle E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.}

A similar calculation, using the independence of the random variables and the fact that E (Z n 2) = 1 {\displaystyle E(Z_{n}^{2})=1}, shows that: E (S n 2) = ∑ i = 1 n E (Z i 2) + 2 ∑ 1 ≤ i < j ≤ n E (Z i Z j) = n. {\displaystyle E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j\leq n}E(Z_{i}Z_{j})=n.}

This hints that E (| S n |) {\displaystyle E(|S_{n}|)\,\!}, the expected translation distance after n steps, should be of the order of n {\displaystyle {\sqrt {n}}}. In fact, lim n → ∞ E (| S n |) n = 2 π. {\displaystyle \lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.}

To answer the question of how many times will a random walk cross a boundary line if permitted to continue walking forever, a simple random walk on Z {\displaystyle \mathbb {Z} } will cross every point an infinite number of times. This result has many names: the level-crossing phenomenon, recurrence or the gambler's ruin. The reason for the last name is as follows: a gambler with a finite amount of money will eventually lose when playing a fair game against a bank with an infinite amount of money. The gambler's money will perform a random walk, and it will reach zero at some point, and the game will be over.

If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or − a is ab. The probability that this walk will hit b before − a is a / (a + b) {\displaystyle a/(a+b)}, which can be derived from the fact that simple random walk is a martingale. And these expectations and hitting probabilities can be computed in O (a + b) {\displaystyle O(a+b)} in the general one-dimensional random walk Markov chain.

Some of the results mentioned above can be derived from properties of Pascal's triangle. The number of different walks of n steps where each step is +1 or −1 is 2. For the simple random walk, each of these walks is equally likely. In order for S to be equal to a number k it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 by k. It follows +1 must appear (n + k)/2 times among n steps of a walk, hence the number of walks which satisfy S n = k {\displaystyle S_{n}=k} equals the number of ways of choosing (n + k)/2 elements from an n element set, denoted (n (n + k) / 2) {\textstyle n \choose (n+k)/2}. For this to have meaning, it is necessary that n + k be an even number, which implies n and k are either both even or both odd. Therefore, the probability that S n = k {\displaystyle S_{n}=k} is equal to 2 − n (n (n + k) / 2) {\textstyle 2^{-n}{n \choose (n+k)/2}}. By representing entries of Pascal's triangle in terms of factorials and using Stirling's formula, one can obtain good estimates for these probabilities for large values of n {\displaystyle n}.

If space is confined to Z {\displaystyle \mathbb {Z} } + for brevity, the number of ways in which a random walk will land on any given number having five flips can be shown as {0,5,0,4,0,1}.

This relation with Pascal's triangle is demonstrated for small values of n. At zero turns, the only possibility will be to remain at zero. However, at one turn, there is one chance of landing on −1 or one chance of landing on 1. At two turns, a marker at 1 could move to 2 or back to zero. A marker at −1, could move to −2 or back to zero. Therefore, there is one chance of landing on −2, two chances of landing on zero, and one chance of landing on 2.

The central limit theorem and the law of the iterated logarithm describe important aspects of the behavior of simple random walks on Z {\displaystyle \mathbb {Z} }. In particular, the former entails that as n increases, the probabilities (proportional to the numbers in each row) approach a normal distribution.

To be precise, knowing that P (X n = k) = 2 − n (n (n + k) / 2) {\textstyle \mathbb {P} (X_{n}=k)=2^{-n}{\binom {n}{(n+k)/2}}},and using Stirling's formula one has

log P (X n = k) = n + log 2 π + o (1). {\displaystyle {\log \mathbb {P} (X_{n}=k)}=n\left+\log {\frac {\sqrt {2}}{\sqrt {\pi }}}+o(1).}

Fixing the scaling k = ⌊ n x ⌋ {\textstyle k=\lfloor {\sqrt {n}}x\rfloor }, for x {\textstyle x} fixed, and using the expansion log (1 + k / n) = k / n − k 2 / 2 n 2 + … {\textstyle \log(1+{k}/{n})=k/n-k^{2}/2n^{2}+\dots } when k / n {\textstyle k/n} vanishes, it follows

P (X n n = ⌊ n x ⌋ n) = 1 n 1 2 π e − x 2 (1 + o (1)). {\displaystyle {\mathbb {P} \left({\frac {X_{n}}{n}}={\frac {\lfloor {\sqrt {n}}x\rfloor }{\sqrt {n}}}\right)}={\frac {1}{\sqrt {n}}}{\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}(1+o(1)).}

taking the limit (and observing that 1 / n {\textstyle {1}/{\sqrt {n}}} corresponds to the spacing of the scaling grid) one finds the gaussian density f (x) = 1 2 π e − x 2 {\textstyle f(x)={\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}}. Indeed, for a absolutely continuous random variable X {\textstyle X} with density f X {\textstyle f_{X}} it holds P (X ∈ [ x, x + d x)) = f X (x) d x {\textstyle \mathbb {P} \left(X\in [x,x+dx)\right)=f_{X}(x)dx}, with d x {\textstyle dx} corresponding to an infinitesimal spacing.

As a direct generalization, one can consider random walks on crystal lattices (infinite-fold abelian covering graphs over finite graphs). Actually it is possible to establish the central limit theorem and large deviation theorem in this setting.
detectable_content:postscript