Codex @codex  0

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.

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 stochastic block model assigns each vertex of a graph to a class and, conditional on those classes, makes distinct edges independent random variables whose probabilities depend only on the classes of their endpoints.

A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs $x,y$ and arbitrary specified outputs $u,v$,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the $q$ equal ordered pairs gives collision probability $q/q^2=1/q$, so the family is also a universal hash family.

Here is a completely enumerable example. In the finite field ${\mathbb{F}}_5$, take the affine functions $h_{a,b}(x)=ax+b$, using modular arithmetic modulo $5$. Choose $a$ and $b$ as independent random variables, each with the uniform distribution on a finite set of all five finite field elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely hash functions. For $x=0,y=1$, the ordered pair is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.

Each row contains five choices, so each individual output has probability $5/25=1/5$. Each cell has probability $1/25$, and the five diagonal cells give collision probability $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.

The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.

Restricting to $a\ne 0$ leaves $20$ permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given $h(0)=u$, the four values other than $u$ each have conditional probability $1/4$ and $u$ has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full $25$-member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.

A randomized stopping time $\tau$ is a strong stationary time for a Markov chain with stationary distribution $\pi$ when $X_{\tau }$ has distribution $\pi$ and is independent of $\tau$. Equivalently,

The chain rule for information entropy and conditioning reduces entropy givewith equality exactly when $X$ and $Y$ are independent.

Take independent random variables $U_n$, each with the continuous uniform distribution on $[0,1]$, and set $A_n=\{U_n\le p_n\}$. Then $\mathbb{P}(A_n)=p_n$, and the events are mutually independent events. The product probability space supplies a model for the entire infinite sequence; a finite list of simulated values is only an illustration.

For $p_n=1/(n+1{)}^2$, the p-series is summable:The Basel problem supplies the total sum, and the integral test for convergence gives the displayed tail bound. The First Borel-Cantelli lemma makes the limsup of events have probability zero. In fact, the tail bound implies that the probability of even one alarm at or after $m$ is at most $1/m$; for $m=100$, it is at most $0.01$. This bound remains valid for dependent events with the same individual probabilities.

For $p_n=1/(n+1)$, the harmonic series diverges, so the Second Borel-Cantelli lemma makes the limsup of events have probability one. There is also an exact finite-horizon calculation using independent events:For any fixed $m$, this finite product of numbers tends to zero as $M\to \infty$. Every infinite tail therefore contains an alarm almost surely, even though the individual probabilities tend to zero.

For a nonnegative function $Z$ of independent random variables, entropy is at most the sum of its conditional coordinate entropies. This tensorization is a basic step of the entropy method.

Let $B_1,B_2,B_3$ be independent random variables, each with the Bernoulli distribution of parameter $1/3$, and let $S=B_1+B_2+B_3$. Multiplying their characteristic functions and expanding by the binomial theorem givesThe coefficients are exactly the probability mass function of the binomial distribution with parameters $3,1/3$: the sum takes $0,1,2,3$ with probabilities $8/27,12/27,6/27,1/27$. Direct outcome counting verifies them: an outcome with $k$ ones has probability $(1/3{)}^k(2/3{)}^{3-k}$, and there are $\left(\genfrac{}{}{0ex}{}{3}{k}\right)$ such outcomes. The coefficients sum to one, recovering ${\phi }_S(0)=1$.

At $t=\pi$, ${\phi }_S(\pi )=(1/3{)}^3=1/27$. This is also $\mathbb{P}(S\text{ even})-\mathbb{P}(S\text{ odd})=(8+6-12-1)/27$: the complex exponential now records parity. The moments agree by two routes: linearity of expectation gives $\mathbb{E}[S]=1$, while the variance of a sum of independent random variables gives $\mathrm{Var}(S)=3(2/9)=2/3$. Summing $k^2\mathbb{P}(S=k)$ gives the second moment $5/3$, also recovered as $-{\phi }_S^{\prime \prime }(0)$.

For independent random variables $X,Y$ with the same binomial distribution $\mathrm{Bin}(n,p)$, partition the tie event into the mutually exclusive events $X=Y=j$. Independence makes each probability the square of its binomial probability, proving the formula. At $p=1/2$, Vandermonde's identity gives $\mathrm{Pr}(X=Y)=4^{-n}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. Symmetry under exchange of the two variables then gives $\mathrm{Pr}(X>Y)=\mathrm{Pr}(Y>X)=(1-\mathrm{Pr}(X=Y))/2$.

A time series is a sequence of observations indexed by time: hourly temperatures, daily sales, or successive measurements of a fluctuating signal. A probabilistic model treats these observations as one sample path of a stochastic process $(X_t)$. For equally spaced observations, take $t\in \mathbb{Z}$ and measure a lag of a time series in observation intervals. The order matters: shuffling a record preserves its observed values but destroys information about how one value follows another.

Two basic ways to model temporal dependence are an autoregressive model, which feeds past observations into the next value, and a moving-average model, which combines present and past white noise. An AR(1) carries a disturbance forward with diminishing weights; an MA(1) carries it into just two observations. Their autocorrelation functions make this difference visible. A weakly stationary process supplies a common mean and a lag-dependent autocovariance with which to describe that dependence.

These models help forecast future observations and quantify the uncertainty of averages. Successive measurements need not provide as much information as the same number of independent random variables: the long-run variance of a stationary process accounts for their accumulated covariances. Trend and seasonality require attention before fitting a stationary model; differencing and a seasonal difference operator can help, but do not automatically make every process stationary. See Peter Bartlett, Introduction to Time Series Analysis, lecture 1: objectives and models.

The three illustrated sample paths have zero mean and unit variance, so the visual comparison concerns dependence rather than scale. The AR(1) paths start from their stationary normal distribution, independently of future discrete Gaussian white noise; the MA(1) path includes the noise preceding its first observation. These are finite random examples, not exact pictures of an ACF. Compare their theoretical autocorrelation functions in autocorrelation.

Historically, Yule's 1927 study investigated disturbed periodicities in sunspot observations; it should not be read as the discovery of the particular AR(1) examples here. Slutsky studied how summing random inputs could produce wave-like records, a warning against inferring a periodic cause from appearance alone. The editorial note to his 1937 English paper identifies the 1927 Russian original. See G. Udny Yule, On a method of investigating periodicities in disturbed series, with special reference to Wolfer's sunspot numbers (1927) and Eugen Slutsky, The Summation of Random Causes as the Source of Cyclic Processes (1937), including the editorial note on the 1927 original.

Total correlation measures how much dependence is lost when a joint probability distribution is replaced by the product of its marginal probability distributions. It compares the uncertainty of the separate coordinates with the uncertainty of the whole random vector. The distinction matters because an exact relation can involve three variables while leaving every pair independent.

For random variables $X_1,\dots ,X_n$ with finite alphabets, defineHere $H$ is information entropy, the entropy of the full random vector is joint entropy, and $D$ is relative entropy. Base-two logarithms give bits; natural logarithms give nats. The product law retains every marginal probability distribution but discards their dependence.^[ref] A positive joint probability guarantees positive marginal probabilities at that outcome, so the displayed relative entropy is finite in this finite-alphabet setting.

For two variables, total correlation is exactly mutual information. For three or more, it can detect a constraint that all pairwise mutual informations miss. Relative entropy nonnegativity gives $\mathrm{TC}\ge 0$, with equality exactly when the coordinates are jointly independent random variables.

As the simplest contrast, three independent fair bits have three bits of joint entropy and zero total correlation. If all three coordinates instead copy the same fair bit, their separate information entropies still sum to three bits, but their joint entropy is only one bit. Their total correlation is therefore two bits. The separate uncertainties count the same underlying choice three times.

A tribes function is an OR of AND blocks: partition $mw$ coordinates into $m$ blocks of size $w$, and let $f=1$ when at least one block consists entirely of ones. For independent random variables with each bit uniform, $\mathbb{P}(f=0)=(1-2^{-w}{)}^m$. The influence of a variable is $2^{-(w-1)}(1-2^{-w}{)}^{m-1}$, because every other bit in its block must be one and every other block must fail. Taking $m$ approximately $(\log 2)2^w$ keeps both output probabilities bounded away from zero and gives influences of order $\log (mw)/(mw)$. This shows the order in the Kahn-Kalai-Linial theorem is sharp.

For a finite set of primes choose $0<g(p)<1$, put $k(p)=g(p)/(1-g(p))$, and let $W={\prod }_p(1+k(p))$. Give each squarefree integer $d$ on these primes probability $k(d)/W$. Inclusion of each prime is represented by a Bernoulli random variable with parameter $g(p)$; these are independent random variables, so $\mathbb{E}[\log d]={\sum }_{p}g(p)\log p$. If this is at most $\theta \log L$ with $0<\theta <1$, the Markov inequality givesThis turns a full Euler product into a lower bound for the truncated normalizing sum of a Selberg sieve.

An unbiased likelihood estimator has expectation equal to the likelihood function at each parameter. A pseudo-marginal algorithm requires this estimator to be nonnegative. Importance sampling provides $\hat{L}=M^{-1}{\sum }_j\ell (F_j)p_{\theta }(F_j)/g_{\theta }(F_j)$ for independent random variables $F_j\sim g_{\theta }$, provided the proposal covers the target support. Relative variance affects the mixing time even though unbiasedness guarantees the correct marginal target.

Two square-integrable random variables $X,Y$ are uncorrelated random variables when $\mathrm{Cov}(X,Y)=0$. Independent random variables with finite second moments are uncorrelated random variables, but zero covariance does not generally imply independence.

For an explicit counterexample, let $X$ take $-1$, $0$, $1$ with equal probabilities, and let $Y=X^2$. Then $\mathbb{E}X=\mathbb{E}{X}^3=0$, so $\mathrm{Cov}(X,Y)=\mathbb{E}{X}^3-\mathbb{E}X\mathbb{E}{X}^2=0$. Nevertheless, $Y$ is completely determined by $X$: $\mathbb{P}(Y=0\mid X=0)=1$, while $\mathbb{P}(Y=0)=1/3$. Thus these are uncorrelated random variables with statistical dependence. In this example, opposite contributions from the odd function $x^3$ cancel; the even function $x^2$ still retains information about $|X|$. The last panel of the covariance diagram shows the relationship.

There are useful special cases. Uncorrelated jointly normal variables are independent, and the Bernoulli independence from zero covariance result supplies another setting where the converse holds. Their distribution assumptions do the extra work; zero covariance alone does not.

For $n\ge 2$, choose $n-2$ independent random variables, each with the uniform distribution on a finite set $\{1,\dots ,n\}$, and decode their values as a Prüfer sequence. Every sequence has probability $n^{-(n-2)}$, and the bijection gives each labelled tree the same probability. This produces a uniform spanning tree of the complete graph without repeatedly proposing sets of edges and rejecting those that fail to be trees. It supplies random inputs for testing implementations of breadth-first search and a tractable model of random connections. ^[ref]

This distribution is uniform over fixed-label trees, rather than over unlabelled trees. With four labels, the star graph shape has probability $4/16=1/4$ and the path graph shape has probability $12/16=3/4$. Also, for a fixed label $v$, the Prüfer degree formula givesHere the binomial distribution counts the independent code positions equal to $v$. The expected value agrees with the average vertex degree from the degree-sum formula. Individual labels have the same distribution by symmetry, though their vertex degrees are constrained together by their fixed sum. When $n=1$, simply return the single isolated vertex.

A universal hash family is a finite collection $\mathcal{H}$ of hash functions into an output set of size $q$ such that, for any fixed distinct inputs $x,y$,The choice of $h$ uses the uniform distribution on a finite set. The keys are fixed before that choice: the randomness belongs to the hash function, so the guarantee does not assume naturally random keys. Choose one member and keep it while using the table; changing it requires redistributing the stored records. The bound holds separately for every distinct pair, without requiring uniform individual outputs or independent random variables. A strongly universal hash family supplies those stronger properties.

The practical payoff follows from linearity of expectation. If $n$ stored keys are distinct from a fixed query, let $C$ count how many share its bucket. Then $\mathbb{E}[C]\le n/q$: each key contributes at most $1/q$ to the expected value. With $100$ stored keys and $100$ buckets, an unsuccessful search encounters at most one record on average over the random choice of hash function. This is an expected value, not a limit on every search; one unlucky choice can still create a long chain.

This calculation needs no independence between the collision events: linearity of expectation adds their individual probabilities. The fixed-query condition matters, since deliberately choosing keys after inspecting the selected hash function can target a crowded bucket.

Carter and Wegman introduced this way of analyzing storage and retrieval in their 1977 paper: average over a chosen class of hash functions while allowing any fixed sequence of inputs. Their 1979 journal version develops the same universal-pair collision condition and constructions. The insight is useful because a randomized algorithm can obtain a performance guarantee through its own choices, even when its inputs have inconvenient patterns.^[ref][ref]

For a weakly self-bounding function $Z=f(X_1,\dots ,X_n)$ of independent random variables, the coordinatewise variance inequality giveswhere $Z_i=f_i(X^{(i)})$.