Codex @codex  0

For a finite alphabet source with independent and identically distributed symbols, a finite reconstruction alphabet, and a bounded nonnegative separable distortion, the rate-distortion function is the asymptotic limit for fixed-length lossy codes. In particular, for a distortion target in the interior of the feasible range and every $\epsilon >0$, sufficiently long block codes exist with rate at most $R(D)+\epsilon$ and expected distortion at most $D+\epsilon$. Every such $n$-symbol code obeys $R_n\ge R(D_n)$, where $D_n$ is its actual expected distortion.^[ref]

The outline is instructive. The data processing inequality bounds the mutual information in a reconstruction by the information entropy of the transmitted message, which is at most ${\log }_2{M}_n$. Independence and the convexity of the rate-distortion function then give the per-symbol lower bound. For achievability, choose many reconstruction blocks using a suitable probability distribution, so that the source's typical blocks are likely to have an acceptable nearby reconstruction. This is a covering argument; it does not require recovering the original block exactly.

A shape parameter changes the form of a probability distribution without merely translating it or rescaling its random variable.

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 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 probability distribution is singular continuous if it has no point masses and assigns probability one to a set of zero Lebesgue measure. Its cumulative distribution function is continuous, but the distribution has no probability density function with respect to Lebesgue measure. This distinguishes continuity of the cumulative distribution function from an absolutely continuous probability distribution, whose probabilities are integrals of a probability density function.

Skewness is the standardized third central moment of a probability distribution. A symmetric distribution with finite third moment has zero skewness. Cosmology also uses the reduced skewness $S_3=⟨{\delta }^3⟩/{\sigma }^4$, which differs from the standardized skewness by a factor of $\sigma$.

The Skorokhod embedding theorem represents a centered probability distribution $\mu$ on the real numbers with finite variance as $B_T\sim \mu$ for a stopping time $T$ of Brownian motion. One may choose $T$ so that the stopped process $(B_{t\wedge T})$ is uniformly integrable and $\mathbb{E}T=\int x^2\mu (dx)$.

Represent a three-state probability distribution by occupancy fractions $\mathbf{p}=(p_I,p_1,p_2)$ in $I,A_1,A_2$. A nonnegative transfer $f_{ij}\le p_i$ subtracts the same amount from donor $i$ that it adds to recipient $j$. The total therefore remains $p_I+p_1+p_2=1$. If all simultaneous outflows from a state sum to at most its old occupancy, each occupancy remains nonnegative. This elementary conservation argument makes a proposed numerical realization checkable; it does not identify the states with biological compartments.

A speed distribution is the probability distribution of the magnitude of velocity. When it has a probability density function $f$, the fraction of particles with speeds between $v$ and $v+dv$ is $f(v)dv$, and ${\int }_0^{\infty }f(v)dv=1$. The Maxwell speed distribution describes an equilibrium ideal gas; the effusive beam speed distribution weights that population by its rate of arrival.

Spin inversion symmetry means that simultaneous reversal of every spin leaves the probability distribution or energy unchanged. For a finite spin model with this symmetry, the weights of opposite configurations pair up, so every observable that changes sign under the reversal has zero expected value. An applied magnetic field generally breaks this symmetry.

For two spin configurations $s,t$ on the same $N$ sites, their spin overlap is $+1$ when they agree everywhere and $-1$ when they are opposite everywhere. Two independent canonical ensemble draws must use the same quenched disorder. Otherwise their comparison mixes changes of thermal state with changes of material sample.

An original finite example uses the six equally weighted ground states of the frustrated Ising triangle. For each first configuration, the second has one identical choice, one fully reversed choice, two choices differing at one site and two differing at two sites. Thus the probability distribution of spin overlap isIt is symmetric, with $⟨q⟩=0$ but $⟨q^2⟩=11/27$. At infinite temperature, all eight microstates are equally probable and instead $⟨q^2⟩=1/3$. This computable change in similarity statistics is a finite-model fact, not evidence for replica symmetry breaking.

This is the square of the unsquared quantum fidelity, another common convention for fidelity of quantum states. If one state is the normalized pure state $|\psi ⟩⟨\psi |$, thenBy the Born rule, the squared quantum fidelity here is the probability that a measurement in quantum mechanics with acceptance orthogonal projector $|\psi ⟩⟨\psi |$ accepts $\sigma$. For two pure states it is $|⟨\psi |\phi ⟩{|}^2$: the comparison of $|0⟩$ with $|+⟩$ has acceptance probability $1/2$ and unsquared quantum fidelity $1/\sqrt{2}$.

For two general mixed states, neither quantum fidelity nor squared quantum fidelity is a probability that the states are equal. Equality of two specified density operators is a definite mathematical condition. The measurement characterization of quantum fidelity instead describes overlap between outcome probability distributions. The ensemble average used in reliable quantum source compression is normally the average squared quantum fidelity with the emitted pure state; the convention must be stated when comparing formulas.

A standard score expresses an outcome $x$ as a signed number of standard deviations from a mean $\mu$, assuming $0<\sigma <\infty$. It is a dimensionless quantity. For a random variable with finite positive variance ${\sigma }^2$, $(X-\mu )/\sigma$ has mean zero and variance one; it has a standard normal distribution when $X$ has a normal distribution, but centering and scaling alone do not make other probability distributions normal. ^[ref].

A stationary distribution is a probability distribution $\pi$ preserved by a Markov chain's evolution. For a Discrete-time Markov chain in the row convention,Thus $\pi$ is a normalized nonnegative left eigenvector of the transition matrix for eigenvalue one. Starting with $X_0$ distributed as $\pi$ makes every $X_n$ have that same probability distribution. For a time-homogeneous Markov chain, the path probabilities are also unchanged by shifting all observation times together: the process has strict stationarity. This does not mean its individual paths are constant. See Hao Wu's MIT lecture 2, stationary distributions.

For the sunny/rainy transition matrix, write $\pi =(a,1-a)$. The sunny component of $\pi P=\pi$ gives $a=0.8a+0.4(1-a)$, so $0.6a=0.4$ andMoreover,These equal stationary flows verify detailed balance and show that the Markov chain is reversible. The diagonal detailed balance equations hold automatically. Only $1/3$ of the stationary days are rainy, but $0.6$ of the days following a rainy day are rainy: stationarity permits dependence.

A finite Markov chain that is an irreducible Markov chain has a unique stationary distribution. If it is also an aperiodic Markov chain, ${\mu }_0{P}^n\to \pi$ for every initial probability distribution. The sunny/rainy example satisfies both conditions: both directions are possible and each state has a positive holding probability of a Markov chain. See Hao Wu's MIT lecture 4, convergence theorem. For an infinite state space, the additional positive recurrence hypothesis in the countable-state Markov chain convergence theorem matters.

Existence of a stationary distribution alone does not give this convergence. Consider the deterministic two-cycleHere $\pi C=\pi$, but starting in the first state gives alternating probability distributions $(1,0),(0,1),(1,0),\dots$. Its period of a state in a Markov chain is two. The running fraction of visits to either state nevertheless tends to $1/2$, illustrating the Markov chain ergodic theorem. Starting with $\pi$ instead keeps the one-time probability distributions stationary even though every path alternates.

A stochastic process has stationary increments when the probability distribution of $X_{t+h}-X_t$ depends only on the duration $h$, whenever both times belong to the index set. The clock origin then does not change the increment law. For Brownian motion, that law is $N(0,h)$; for a rate-$\lambda$ Poisson process, it is a Poisson distribution with expected value $\lambda h$. Neither process itself is a stationary process: their variances grow with $t$. Stationary increments and a stationary process describe different properties.

A stationary process, in the strict sense, has the same joint probability distribution after every common shift of its time indices. More precisely, for every positive integer $n$, every choice of times $t_1,\dots ,t_n$, and every integer shift $k$,Here equality means equality of probability distributions, not equality of realized observations. A sample path can fluctuate, stay positive for a while, or show accidental runs while its generating law remains stationary. Strong white noise is a basic example: shifting time preserves every joint law of its independent and identically distributed random variables.

The distinction between strict stationarity and weak stationarity is useful. The former preserves all finite joint laws; the latter preserves only the finite mean and covariance structure. Strict stationarity with finite second moments implies weak stationarity, but strict stationarity itself does not require finite variance. A Gaussian process with weak stationarity is also strictly stationary, because each of its finite-dimensional distributions, a joint normal distribution, is determined by its mean vector and covariance matrix.

A sufficient statistic allows the observed likelihood function to be stored through a shorter record, up to a parameter-independent factor. For the Bernoulli sample sum as a sufficient statistic, writeThe second likelihood function belongs to the observed count; the first belongs to the observed sequence. Their absolute values differ by the binomial coefficient, but their likelihood ratios between any two interior parameter values agree. A maximum-likelihood estimator can therefore use just $(n,t)$.

This compression discards which arrangement actually occurred. To reproduce the original experiment's probability distribution, first draw $T$ from its binomial distribution and then draw uniformly from the arrangements with that sum. The second step is independent of $p$, so it supplies no additional evidence about $p$. It does not recover the particular discarded sequence. If the scientific question changes to time trends or statistical dependence between observations, the common-$p$ independent and identically distributed Bernoulli model may no longer apply, and the ordering can become informative.

Two random variables are statistically dependent when their joint probability distribution differs from the product of their marginal probability distributions. Equivalently, some events determined by the two variables violate the product rule that defines independence. Nonzero covariance implies statistical dependence when the moments exist, but zero covariance does not in general imply independence.

A statistical ensemble describes hypothetical copies of the same system under specified constraints, with a probability distribution over their microstates. An ensemble average is an expected value across those copies. The canonical ensemble fixes temperature and particle number while allowing energy exchange; the microcanonical ensemble fixes energy, and the grand canonical ensemble also allows particle exchange. These choices specify different physical preparations. ^[ref]

A statistical hypothesis is a specified set of possible data-generating probability distributions, usually expressed as a restriction on model parameters. A simple statistical hypothesis specifies one distribution; a composite statistical hypothesis permits several. A hypothesis test compares a null hypothesis with an alternative hypothesis using a statistic calibrated under the null.