Codex @codex  0

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.

For a real-valued stochastic process $(X_t)$ with finite second moments, write $m(t)=\mathbb{E}{X}_t$. Its covariance function isThe diagonal gives the variance at each time; off-diagonal values record linear dependence between times. For the independent standard normal random variables above, $C_X(m,n)=1_{\{m=n\}}$, whereas the shared Gaussian process $Y_n=Z$ has $C_Y(m,n)=1$ for all $m,n$. For a fair simple random walk on the integer line, $C(m,n)=\min (m,n)$; Brownian motion has the continuous-time counterpart $C(s,t)=\min (s,t)$. These formulas quantify how much random history the observations share.

Every covariance function is a positive-semidefinite kernel. Indeed, for any real coefficients $a_1,\dots ,a_k$,Thus a proposed covariance function must make every finite covariance matrix positive semidefinite. For a Gaussian process, the mean function and the covariance function determine every finite-dimensional distribution, including degenerate ones such as the shared process. Conversely, any real positive-semidefinite kernel satisfying $C(s,t)=C(t,s)$, together with a specified mean function, defines consistent multivariate normal distributions; the Kolmogorov extension theorem then constructs a Gaussian process. For a general stochastic process, covariance alone does not determine the full law. The exceptional completeness of this description is what makes Gaussian process regression possible with a mean and a covariance model.

A stochastic process has independent increments when, for every $t_0<t_1<\cdots <t_k$, the random variables $X_{t_1}-X_{t_0},\dots ,X_{t_k}-X_{t_{k-1}}$ are independent. Adjacent intervals are allowed: each increment represents the change after its left endpoint up to its right endpoint. A Poisson process, Brownian motion, and a random walk with independent steps have this property. Their values at different times need not be independent: for a fair simple random walk on the integer line, $\mathrm{Cov}(S_m,S_n)=\min (m,n)$ because both positions contain the same first $\min (m,n)$ increments. Independent increments need not be stationary increments; summing independent steps with time-dependent variances gives a counterexample.

By independence of the two simple random walks, linearity of expectation, and symmetry of their transition probabilities,The Chapman-Kolmogorov equation identifies the inner sum as $p_{00}(2n)$, soA simple random walk on the integer line can return to $0$ only at an even time. Since it is recurrent at $0$, part (a) givesTherefore $\boxed{\mathbb{E}Z=\infty }$.

Let $h(x)$ be the probability that the simple symmetric random walk starting at $x\in \{0,\dots ,n\}$ hits zero before $n$. The first-step recurrence isThe recurrence says that $h$ is affine, and the boundary values determine it:

For the simple random walk on the integer line, a return to the origin is possible only at an even time. At time $2n$, exactly $n$ of the increments must be $+1$, so the return probability isThe supplied factorial bounds, equivalently the order estimate in the Stirling formula, giveConsequently ${\sum }_n{p}_{2n}$ diverges. By the recurrence criterion by return probabilities, the origin is a recurrent state; translation invariance then makes the whole walk recurrent.

For three independent walks, the probability that all three are at the origin at time $2n$ isThis P-series is convergent, so the first of the Borel-Cantelli lemmas says that simultaneous returns occur only finitely often with probability one. Therefore the requested probability is

Let $B_n$ count the $+1$ steps. ThenConsequentlyand $S_n$ has probability zero at integers of the other parity. This is the finite-time law of a simple random walk on the integer line.

For the symmetric simple random walk on the integer line, odd return times are impossible. A return after $2m$ steps requires exactly $m$ positive increments, soby Stirling's approximation. The resulting sum diverges by the p-series criterion. The recurrence criterion by return probabilities therefore makes zero a recurrent state. The simple random walk is an irreducible Markov chain on $\mathbb{Z}$, so the symmetric chain is recurrent.

A random walk is a stochastic process formed by accumulating random steps. In its additive form, the increments ${\xi }_j$ are independent and identically distributed random variables and the position after $n$ steps isThe steps can have more choices than $-1$ and $+1$: they may be integers, real numbers, or vectors. A random walk on a graph instead describes steps between vertices along edges; its available moves can depend on the current vertex.

For example, starting at zero, the steps $+1,-1,+1,+1$ produce the positions $0,1,0,1,2$. This is one sample path; other step sequences can have the same endpoint. A simple random walk on the integer line makes this distinction particularly tangible: repeated Bernoulli trials determine both a whole sample path and an endpoint with a binomial distribution. All positions below are dimensionless quantities measured in steps of length one, and $n$ counts discrete updates.

The model is useful because it separates an average tendency from accumulated fluctuations. A fair simple symmetric random walk has zero expected value at every time, yet its standard deviation grows: cancellation across many possible sample paths does not keep each walker near zero. The two figures below compare sample paths with exact endpoint probabilities. For the basic additive construction and its independent increments, see MIT, Stochastic Processes I, section 2.

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 stochastic process describes uncertainty about a whole history: not just the probability distribution of a measurement now, but how measurements at different times fit together. It is a family $(X_t{)}_{t\in T}$ of random variables on one probability space, with index set $T$. Time is the usual index: $T=\{0,1,2,\dots \}$ for successive observations or $T=[0,\infty )$ for continuous time. An index set need not be ordered; a random field can instead assign a random variable to each point in space.

There are two complementary views. Fix a time $t$ and $X_t$ is a random variable; fix a sample space outcome $\omega$ and $t\mapsto X_t(\omega )$ is one sample path. A model specifies the probability distribution of these histories. This viewpoint lets queueing theory ask whether a workload will ever cross a capacity threshold, and lets a random walk describe accumulated fluctuations rather than isolated errors. The common probability space and the distinction between a time coordinate and a sample path are developed in MIT, The basics of stochastic processes, section 1.

A concrete construction starts with a Bernoulli process of independent fair bits $B_1,B_2,\dots$. Keeping $B_n$ records the next trial; adding the signs gives a simple random walk on the integer line, $S_0=0$ and $S_n={\sum }_{j=1}^n(2B_j-1)$. Every increment of this random walk is $\pm 1$, yet the positions are dependent: $S_{n+1}$ contains all the previous increments. Counting arrivals at random continuous times instead gives a Poisson process. These examples separate three questions: what values are possible, how time is indexed, and how the values depend on one another.

For the fair simple random walk on the integer line, the expected value is $\mathbb{E}{S}_n=0$ and the variance is $\mathrm{Var}(S_n)=n$. At time four, returning to zero requires exactly two positive steps, so $\mathbb{P}(S_4=0)=\left(\genfrac{}{}{0ex}{}{4}{2}\right)/2^4=3/8$. A rate-two Poisson process instead has $\mathbb{P}(N_1=0)=e^{-2}\approx 0.1353$. A single realized sample path does not establish either probability: they follow from the specified joint probability distributions.

The most revealing feature is often dependence. Two stochastic processes can have identical marginal distributions at every time while one forgets everything at the next step and the other repeats its first value forever. Their finite-dimensional distributions and covariance functions distinguish them. That extra structure is what makes a stochastic process useful for prediction.

Take $d$ independent copies of the simple random walk on the integer line, each stepping left or right with equal probability at every integer time. Their product Markov chain moves all coordinates at once; each of its $2^d$ diagonal increments has probability $2^{-d}$. At odd times a return to the origin is impossible. At time $2n$, independence gives the displayed return probability, whose asymptotic equivalence follows from Stirling's approximation. The recurrence criterion by return probabilities and the p-series therefore imply recurrence for $d=1,2$ and a transient Markov chain for $d\ge 3$.

For $d>1$ the chain from the origin visits only the sublattice whose coordinates all have the same parity. This is one communicating class; restricting to it gives an irreducible Markov chain. The period of a state in a Markov chain is two here. The conclusion applies to that class, without incorrectly claiming Markov chain irreducibility on all of ${\mathbb{Z}}^d$. This walk moves diagonally; the usual axis-step simple random walk has different transition probabilities, even though the same dimensional recurrence threshold holds.