Simple random walk on the integer line ($S_n=2B_n-n$)

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.

For the symmetric walk and $V_{2n}=|\{0\le j\le 2n:S_j=0\}|$,Since the central binomial coefficient satisfies $\left(\genfrac{}{}{0ex}{}{2k}{k}\right)/4^k\asymp k^{-1/2}$, this expectation is of order $\sqrt{n}$.

For $d$ independent symmetric walks on $\mathbb{Z}$, the probability that all are at the origin at time $2n$ isThe Borel-Cantelli lemmas therefore show that simultaneous returns occur only finitely often almost surely when $d\ge 3$.

A biased random walk on the integer line takes unit steps right and left with unequal probabilities $p$ and $1-p$, using independent and identically distributed random variables as increments. For $S_0=0$, the expected value is $n(2p-1)$: positive for $p>1/2$ and negative for $p<1/2$. Changing $p$ to $1-p$ reverses the preferred direction. The exact endpoint probability mass function is given under simple random walk on the integer line.

For example, with $p=0.65$ each step has expected value $0.30$ and variance $0.91$. After $80$ steps,The displacement of the expected value from zero is about $24/8.532\approx 2.813$ standard deviations, yet individual sample paths still move left as well as right, as the figure under simple random walk illustrates. Bias lets this elementary stochastic process model an average directional tendency while retaining fluctuations. Boundary and return questions have their own treatments under gambler's ruin and the specialized children below.

Let $S_0=0$ and let the independent and identically distributed random variables $S_n-S_{n-1}$ be $+1$ with probability $p>1/2$ and $-1$ with probability $q=1-p>0$. The strong law of large numbers gives $S_n\to +\infty$ almost surely, so the global minimum $W$ is finite and attained. For each nonnegative integer $m$, the unit-step property and translation of the starting point giveby the biased random walk hitting probability. Subtracting consecutive tails gives the displayed zero-based geometric distribution, with success parameter $1-q/p$. Inclusion of time zero is important: it ensures $-W\ge 0$. Reflecting the sign of the path yields the corresponding maximum of a downward-biased random walk.

For a biased random walk on the nonnegative integers with upward probability $p>q=1-p>0$, the hitting probability of zero from $i$ is $(q/p{)}^i$. Indeed, first-step analysis gives $h_i=p{h}_{i+1}+q{h}_{i-1}$ for $i\ge 1$, with $h_0=1$. Its characteristic roots are $1$ and $\beta =q/p$, so any solution is $A+(1-A){\beta }^i$. Nonnegativity as $i\to \infty$ forces $A\ge 0$ and hence a value at least ${\beta }^i$. This candidate itself satisfies the recurrence. The theorem on the minimal nonnegative solution for hitting probabilities therefore identifies it with $h_i$. A walk on all of $\mathbb{Z}$ has the same probability until it first reaches zero.

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.

On $\{0,\dots ,N\}$, stop at zero, move left with probability $q>1/2$ and right with probability $p=1-q$ at interior states, and move deterministically from $N$ to $N-1$. For $m_i={\mathbb{E}}_i{T}_0$, the first-step analysis gives $m_0=0$, $m_i=1+q{m}_{i-1}+p{m}_{i+1}$ and $m_N=1+m_{N-1}$. Setting $D_i=m_i-m_{i-1}$ gives $q{D}_i-p{D}_{i+1}=1$, $D_N=1$, hence $D_i=[1-2p(p/q{)}^{N-i}]/(q-p)$. Summing these differences proves the displayed formula, and more generally $m_i=i/(q-p)-2pq(p/q{)}^{N-i}[1-(p/q{)}^i]/(q-p{)}^2$. A downward block has a uniformly positive probability of reaching zero, which supplies a geometric tail bound and justifies finiteness of these expectations.

For independent lattice steps of length $a$ at intervals $\tau$, with probabilities $\alpha +\beta =1$, the diffusive scaling $a^2/\tau \to 2D$ and $(\alpha -\beta )a/\tau \to V$ requires a bias of order $a$. Expanding the master equation gives the advection-diffusion equation $p_t+V{p}_x=D{p}_{xx}$. The finite-step variance coefficient is $2a^2\alpha \beta /\tau$; it has the same limit because the squared bias vanishes. Fixed nonzero bias does not give finite drift under this diffusive scaling.

For a nearest-neighbour random walk with upward probability $0<p<q=1-p$, start at $S_0=0$ and put $M={\sup }_{n\ge 0}{S}_n$. Its probability distribution is geometric on the nonnegative integers, with the displayed mass and expected value $p/(q-p)$. To prove this, the exponential martingale of a biased simple random walk $Z_n=(q/p{)}^{S_n}$ has expectation one. Stop at the first hit $H_k$ of $k$. Before that hit, $Z_{n\wedge H_k}\le (q/p{)}^k$; the strong law of large numbers gives $S_n\to -\infty$ on paths without a hit. Dominated convergence theorem therefore gives $1=(q/p{)}^k\mathbb{P}(H_k<\infty )$. Taking differences of $\mathbb{P}(M\ge k)=(p/q{)}^k$ yields the mass. If time zero is excluded, the maximum can equal $-1$ with probability $q-p$ and does not have this nonnegative geometric distribution.

Let a discrete-time chain move up with probability $q$ and down with probability $p=1-q$ away from zero, while at zero it moves up with probability $q$ and stays with probability $p$. It is transient for $q>p$, null recurrent for $q=p$, and positive recurrent for $q<p$. In the positive-recurrent case its invariant distribution isand aperiodicity from the self-loop at zero implies convergence to this distribution.