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.

On a finite undirected graph, stationary mass is proportional to vertex degree.

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.

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.

Chronological loop erasure removes each loop from a finite or transient infinite path as soon as the loop is formed, producing a self-avoiding path.

A locally finite connected graph is transient when its simple random walk visits every vertex only finitely often almost surely.

A bishop random walk moves uniformly among the current square and all chessboard squares sharing a diagonal with it.

A weighted graph assigns a symmetric nonnegative conductance ${\mu }_{xy}$ to each edge. With killing weights ${\kappa }_x$, the associated discrete-time walk moves from $x$ to $y$ with probability ${\mu }_{xy}/{\mu }_x$ and is killed with probability ${\kappa }_x/{\mu }_x$, where ${\mu }_x={\kappa }_x+{\sum }_y{\mu }_{xy}$.

A finite extension of local fields is totally ramified when its residue-field degree is one, equivalently when its ramification index equals its field degree.

The residue-field degree of a finite extension of local fields is $f(L/K)=[k_L:k_K]$, and $[L:K]=e(L/K)f(L/K)$.

The innermost stable circular orbit is the smallest stable circular timelike orbit around a black hole. Its radius and orbital energy depend on black-hole spin and on whether the orbit is prograde or retrograde.

With an intercept present, a categorical predictor having $m$ represented levels adds $m-1$ linearly independent indicator columns and therefore $m-1$ model degrees of freedom.

For $w=-2/3$, a quintessence-dominated scale factor grows quadratically and $tH$ approaches two.

For $w=-2/3$, zero cosmological constant, and negative curvature, $a(t)=\sqrt{\beta }t+\gamma t^2/4$ with density and curvature parameters $\gamma ,\beta >0$.

In a Gromov-hyperbolic geodesic metric space, every quasigeodesic segment stays within a uniformly bounded Hausdorff distance of a geodesic segment with the same endpoints. The bound depends only on the hyperbolicity and quasigeodesic constants.

The bounded-distance conclusion is a property of a Gromov-hyperbolic metric space, under the geodesic and quasigeodesic hypotheses stated here.

When the shared resource is $|{\Psi }^{+}⟩$, Bell outcomes ${\Phi }^{+},{\Phi }^{-},{\Psi }^{+},{\Psi }^{-}$ leave the receiver with $X|\alpha ⟩,XZ|\alpha ⟩,|\alpha ⟩,Z|\alpha ⟩$, respectively, up to global phases.

A deterministic finite-dimensional universal programmable quantum gate cannot implement every unitary exactly: programs for physically distinct unitaries would have to be mutually orthogonal, but a finite-dimensional program register contains only finitely many mutually orthogonal states.

This is a restriction on programmable quantum circuits and their unitary operators, rather than a statement about the existence of classical program descriptions.

The quantum conditional entropy has the relative-entropy representationwhere the minimum ranges over density operators on $B$.

For every state on ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$,The upper bound follows from Subadditivity of Von Neumann entropy and the lower bound from the Araki–Lieb inequality.

If $\epsilon =\Vert {\rho }_{AB}-{\sigma }_{AB}{\Vert }_1/2$ and $d_A=\dim {\mathcal{H}}_A$, thenThe proof couples the two states through their positive and negative differences, then combines concavity of quantum conditional entropy with the entropy bound for a binary mixture.