Codex @codex  0

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]

The upcrossing count $U_N[a,b]$ counts completed upcrossings by time $N$, allowing the first purchase at time zero. For a martingale, the Doob upcrossing inequality bounds its expected value by $\mathbb{E}(M_N-a{)}^{-}/(b-a)$.

The variance measures the mean squared distance of a random variable from its expected value. For a real square-integrable random variable $X$,The square prevents positive and negative deviations from cancelling. It also gives the variance squared units: if $X$ measures a length in metres, its variance has units of square metres. Its nonnegative square root is the standard deviation, which has the same units as $X$.

For example, let $X$ take $-1$, $0$ and $1$ with equal probabilities. Its expected value is zero, but its variance is $[(-1{)}^2+0^2+1^2]/3=2/3$, and its standard deviation is $\sqrt{2/3}$. The constant random variable zero has the same expected value and zero variance: a mean alone does not describe the spread. The variance is zero exactly when $X=\mathbb{E}X$ almost surely.

The variance is useful because squared deviations interact neatly with linear combinations. The covariance supplies the cross terms when combining different random variables, and a covariance matrix organizes those terms for many variables. The characterization of variance as the minimum mean squared error of a constant also explains why the expected value is the best constant prediction under squared error.

Let $X_1,\dots ,X_n$ be an IID sample of real-valued random variables with finite expected value $\mu$ and finite variance ${\sigma }^2$, where $n\ge 1$. Its sample mean $\overline{X}=n^{-1}{\sum }_i{X}_i$ satisfiesLinearity of expectation gives the first identity. The variance of a sum and vanishing cross covariances give $\mathrm{Var}({\sum }_i{X}_i)=n{\sigma }^2$; scaling by $1/n$ scales the variance by $1/n^2$. Pairwise independent random variables with the same expected value and variance suffice for these identities, even without full independence. Grinstead and Snell state the corresponding finite-variance independent-trials result.^[ref]

The standard deviation of the sample mean is $\sigma /\sqrt{n}$. Four times as many observations halve this scale; they do not divide it by four. In the fair Bernoulli distribution example, $\sigma =1/2$, so sample sizes $4$ and $64$ give standard deviations $1/4$ and $1/16$, respectively. The common-coin averaging example shows why merely repeating observations with a common marginal law does not justify this calculation.

Chebyshev's inequality turns the variance identity into a probability bound: for $\epsilon >0$,This proves convergence in probability of the sample mean to $\mu$ in this finite-variance setting, a form of the weak law of large numbers. It is an upper bound, so values above one convey no improvement over the universal probability bound one. Cauchy sample mean stability lies outside these hypotheses.

On a cyclic sequence of $n$ independent Bernoulli random variables with success probability $p$, count all runs of $k$ consecutive successes, allowing overlaps and taking $1\le k\le n/2$. The count has expected value $n{p}^k$. Its variance is the displayed expression: each starting indicator has variance $p^k(1-p^k)$; two starts at cyclic distance $j<k$ have joint probability $p^{k+j}$; nonoverlapping starts are independent. There are $2n$ ordered overlapping pairs at each such distance, because the two ranges do not meet when $k\le n/2$.

For $p\le 1/2$, summing a geometric series gives $\mathrm{Var}X\le n{p}^k(1+2p/(1-p))\le 3n{p}^k$. Markov's inequality therefore proves absence with high probability when $n{p}^k\to 0$, and Chebyshev's inequality proves existence and relative concentration when $n{p}^k\to \infty$. This remains valid for varying probabilities eventually at most one half.

The variance of hypothetical means in the Bühlmann model is the between-risk variance of the conditional claim expected value. It creates the shared covariance $a$ between different years of the same risk and determines how much individual experience should influence the premium.

For $n$ pots per treatment and $m$ leaves per pot, the group sample mean decomposes into two averages:The variance of a sum adds the variances of the independent terms. Every pot random effect has weight $1/n$, whereas each remaining error has weight $1/(nm)$, giving the short proofThis is also the variance of the arithmetic mean of the $n$ pot sample means, each with variance ${\tau }^2+{\sigma }^2/m$. Equal numbers of leaves per pot make the two averaging procedures identical.

If all $nm$ leaf measurements were falsely treated as independent, the predicted variance would instead be $({\tau }^2+{\sigma }^2)/(nm)$. The ratio of correct to false variance isThus pseudoreplication can underestimate a standard error by the square root of this ratio. Equality holds when $m=1$ or ${\tau }^2=0$; sharing a pot creates an error here precisely when the shared influence has positive variance.

Choose ${\tau }^2=4$, ${\sigma }^2=1$, $n=4$ and $m=3$ as constructed model parameters in squared length units. These are assumptions rather than fitted experimental values. For each group,The treatment contrast $\hat{\Delta }={\overline{Y}}_B-{\overline{Y}}_A$ has expected value ${\alpha }_B-{\alpha }_A$. Since the group errors are independent conditional on the allocation, its variance is twice the group variance, namely $13/6$, whereas the false calculation gives $5/6$. Its correct standard error is $\sqrt{13/6}\approx 1.472$ length units; the false value is $\sqrt{5/6}\approx 0.913$. The variance ratio is $13/5=2.6$.

With four pots fixed, increasing $m$ drives the error contribution ${\sigma }^2/(4m)$ towards zero, but the limit of the group variance remains ${\tau }^2/4=1$. Measuring twelve leaves on each of four pots gives $49/48$. Using the same forty-eight measurements on sixteen pots, with three leaves per pot, gives $13/48$. More independent experimental units reduce both contributions. Extra nested measurements are useful for characterizing each experimental unit, but cannot average away its shared random effect. This is why sample collection effort and the number of independent treatment replicates answer different questions.^[ref]

Write $X_{-i}$ for all inputs except $X_i$. Under the Efron–Stein inequality hypotheses, variance tensorization is the equivalent conditional variance formConditioning freezes the other inputs. Then $Z,Z_i^{\prime }$ are independent with the same conditional probability distribution, givingTaking expected values explains the factor $1/2$.^[ref]

For Bernoulli input $X_i$ with parameter $p_i$, let ${\Delta }_{i}f$ be the value of $f$ with coordinate $i$ set to one minus its value with that coordinate set to zero, keeping $X_{-i}$ fixed. The two-point conditional variance isFor the maximum example, ${\Delta }_{1}f=1-X_2$ and ${\Delta }_{2}f=1-X_1$. The two averaged conditional variances are $0.3(0.7)(0.4)=0.084$ and $0.6(0.4)(0.7)=0.168$, precisely half the respective resampling terms. In the dependent example $X_1=X_2=B$, each other coordinate already determines $W$, so both conditional variances vanish; variance tensorization also fails without independence.

For a short induction proof, separate the last input using the law of total variance. Apply the smaller-dimensional statement to the conditional expectation; Jensen's inequality for the square bounds its coordinate contributions by the original ones. One input gives equality, starting the induction.^[ref]

For a finite outcome space, complete lottery preferences, a transitive relation, continuity of lottery preferences and the independence axiom for lottery preferences are equivalent to an expected utility representation of the displayed form. The representing outcome utility function is unique up to a positive affine function. The theorem is associated with John von Neumann and Oskar Morgenstern.

A useful proof construction selects a best outcome $a$ and a worst outcome $b$. If all outcomes are indifferent, a constant utility function suffices. Otherwise assign $u(a)=1$, $u(b)=0$. Continuity of lottery preferences makes each outcome indifferent to a mixture $u(\omega )a+(1-u(\omega ))b$, and mixture monotonicity makes the coefficient unique. Substitution of indifferent lotteries and reduction of compound lotteries turn any lottery into a best–worst mixture with best-outcome probability ${\sum }_{\omega }L(\omega )u(\omega )$. Mixture monotonicity then ranks all such mixtures. The reverse direction follows by taking expected values; positive affine functions preserve every comparison.^[ref]

Wald's equation turns a random sum into a product of two expected values: the average contribution per step and the average number of steps. Its surprising feature is that the number of steps may depend on what has already happened. A procedure can stop on its first successful Bernoulli trial, for example, while the identity still accounts for its total cost. The crucial restriction is that the decision to take the next step cannot use that step's unobserved outcome.

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with $\mathbb{E}|X_1|<\infty$, let $\mu =\mathbb{E}[X_1]$, and put $S_0=0$ and $S_n={\sum }_{i=1}^n{X}_i$. Suppose $N$ is a nonnegative integer-valued stopping time for the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, with $\mathbb{E}[N]<\infty$. Then $S_N$ is an integrable random variable andThese hypotheses allow statistical dependence between $N$ and the increments; they do not allow access to future increments. The finite-expected value requirement is stronger than stopping almost surely.^[ref]

For the proof idea, count step $i$ only on $\{N\ge i\}$. This event is determined by the first $i-1$ observations, so its indicator function is independent of $X_i$. The Proof of Wald's equation by stopping indicators combines this observation with the tail-sum formula for expectation. The same calculation with $|X_i|$ gives $\mathbb{E}{\sum }_{i=1}^N|X_i|=\mathbb{E}|X_1|\mathbb{E}[N]<\infty$, which justifies interchanging the expected value and the infinite series. This is why the result survives a data-dependent end point without assuming an independent count.

The identity is useful in randomized algorithms and repeated sampling: one can translate an average amount of work into an average number of attempts, or conversely, without first finding the full probability distribution of the total. The examples below separate a permissible stopping rule from a rule that peeks ahead and from a valid rule whose average waiting time is infinite.

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with $\mathbb{E}|X_1|<\infty$ and expected value $\mu =\mathbb{E}[X_1]$. The weak law of large numbers states that their sample mean has convergence in probability to $\mu$: for every fixed $\epsilon >0$,Thus a large sample is unlikely to give an average with a specified fixed-size error. The strong law of large numbers makes the stronger statement of almost sure convergence along an entire sequence. Under the displayed assumptions both laws apply; their names distinguish the conclusions, not two competing predictions.

When the variance ${\sigma }^2$ is finite, variance additivity for independent random variables gives $\mathrm{Var}({\overline{X}}_n)={\sigma }^2/n$. The Chebyshev inequality immediately supplies a useful quantitative form and a brief proof:For independent trials with a Bernoulli distribution of parameter $p=0.2$, the expected value is $0.2$ and the variance is $0.16$. At $n=1000$, the chance of an error of at least $0.1$ is therefore at most $0.016$. The exact binomial distribution gives a much smaller probability, as the figure under the strong law of large numbers shows. The bound is conservative, but it is valid for every sample size under these assumptions and does not require a normal approximation.

The weak law of large numbers addresses a fixed tolerance $\epsilon$. The central limit theorem instead resolves errors on the shrinking scale $\sigma /\sqrt{n}$ and gives their approximate normal distribution. In particular, the weak law of large numbers alone supplies neither a bell-shaped error law nor a universal rate of approach. For example, a Pareto distribution with minimum one and shape $3/2$ has expected value three but infinite variance: both the weak law of large numbers and strong law of large numbers apply, while the finite-variance statement of the central limit theorem does not.

A real stochastic process $(X_t{)}_{t\in \mathbb{Z}}$ is a weakly stationary process if it has finite second moments, a constant expected value $\mu$, and an autocovariance depending only on the lag of a time series:In particular its variance is the same at every time, $\mathrm{Var}(X_t)=\gamma (0)$. This is often called second-order stationarity. It makes observations from different parts of a record comparable through the same autocorrelation function. Bartlett uses this second-order meaning of stationarity in Introduction to Time Series Analysis, lecture 2: mean, covariance, and stationarity.

For a worked contrast, let ${\epsilon }_t$ be centered white noise of variance ${\sigma }^2>0$. The process $X_t=5+{\epsilon }_t$ has mean $5$, variance ${\sigma }^2$, and zero autocovariance at nonzero lags, so it is weakly stationary. The process $Y_t=t+{\epsilon }_t$ has exactly the same covariance structure, but its mean is $t$, so it is not weakly stationary. Constant variance alone is insufficient.

Weak stationarity need not imply strict stationarity. For example, choose independent random variables at all integer times, using a standard normal distribution at even times and a Rademacher distribution at odd times. Every coordinate has zero mean and unit variance, and distinct coordinates have zero covariance. Nevertheless a shift by one changes the marginal probability distribution from continuous to two-point. This also illustrates why weak white noise need not be identically distributed.

Let $X_k$ be independent and identically distributed random variables with expected value zero, variance one, and a moment-generating function finite in a neighborhood of zero. Each row of deterministic real weights $a_{n,k}$ is finite. If ${\max }_k|a_{n,k}|\to 0$ and ${\sum }_k{a}_{n,k}^2\to v<\infty$, then the weighted sums converge in distribution to a normal distribution with mean zero and variance $v$; $v=0$ denotes the constant zero.

By the quadratic expansion of a cumulant-generating function, write $K(u)=u^2/2+r(u)$ with $r(u)=o(u^2)$. For a fixed real $t$, put ${\eta }_n={\sup }_{0<|u|\le |t|{\max }_k|a_{n,k}|}|r(u)|/u^2$, with the supremum taken as zero if its range is empty. Then ${\eta }_n\to 0$ andThus the log moment-generating function of the sum tends to $v{t}^2/2$. The convergence theorem for moment-generating functions proves the conclusion. The supremum is the step that makes the remainder estimate uniform across the row; a separate little-o assertion for each term would not justify summing an increasing number of terms.

Consider an original idealized track reconstruction model. Let equally spaced wires have positions $x_k=kp$ and assign each event to the nearest wire, reporting $\hat{x}=x_k$. Assume exactly one correct wire address, perfect detection efficiency, exact wire positions and a uniform distribution of true positions within each cell. These assumptions explicitly exclude missed pulses, false addresses and several unresolved tracks.

Writing $u=x-x_k$, the measurement error is $e=\hat{x}-x=-u$, with $u$ uniform on $[-p/2,p/2]$. Symmetry gives zero expected value. Its variance and standard deviation follow by integration:For chosen wire pitches $p=2\mathrm{mm}$ and $1\mathrm{mm}$ this gives $0.577\mathrm{mm}$ and $0.289\mathrm{mm}$ respectively. These are model standard deviations, not measured chamber spatial resolutions. The largest possible absolute error in this model is $p/2$, which is a different quantity.

A useful subtlety is that the formula depends on the illumination. For an unresolved pencil beam fixed at $x=x_k+0.4p$, every reconstructed position is $x_k$. The repeated estimates have zero variance, but every error is $-0.4p$. Small repeat-to-repeat spread can coexist with a biased position. The uniform-cell result therefore cannot be transferred to an arbitrary beam profile or detector selection.

The wire address supplies one transverse coordinate in this model. Combining several separated measurements supports track reconstruction; a single address does not specify a complete trajectory. If two charged particles enter the same cell during one accepted interval, an address-only record can be identical to that from one particle. No reconstruction of that record can recover the lost multiplicity without additional information.

X-ray effective area is the area that converts an incident photon arrival rate per unit area into an accepted count rate. For a fixed direction and a sufficiently narrow energy interval, writeHere $A_{\mathrm{geom}}$ is projected geometric area, $T$ is transmittance through windows or optics, $\eta$ is quantum efficiency, ${ϵ}_s$ is the probability that a detected source event passes event selection, and $t$ is live observing time. $N_s$ is an expected value, not a guarantee of an integer count. Multiplication follows by counting incident photons over area and time, then applying the successive conditional acceptance probabilities. Live time already excludes intervals when the instrument cannot record events; multiplying by a live-time fraction again would count the same loss twice.

For an invented narrow-band example, choose $A_{\mathrm{geom}}=40\mathrm{c}{\mathrm{m}}^2$, $T=0.8$, $\eta =0.75$, and ${ϵ}_s=5/6$. Then $A_{\mathrm{eff}}=20\mathrm{c}{\mathrm{m}}^2$. A source with $F=0.30\mathrm{photons}\mathrm{c}{\mathrm{m}}^{-2}{\mathrm{s}}^{-1}$ observed for $t=100\mathrm{s}$ gives $N_s=600$. $F$ here counts photons; converting it into observed radiative flux requires their energies. If all have energy $E_0$, the corresponding radiative flux is $E_{0}F$.

A broad spectrum instead requireswhere $F_E$ is the differential photon arrival rate per area and energy. A single band-averaged X-ray effective area depends on the assumed spectrum. This is why a count rate alone cannot give an assumption-free radiative flux.

In a classical risk model with positive relative safety loading, zero initial capital has ultimate survival probability $1-\lambda \mu /c$, where $\lambda$ is the claim-arrival rate, $\mu$ the claim expected value and $c$ the premium rate. It depends on the claim law through its mean alone. It is not the event of never receiving a claim: premium accumulates between arrivals.

Let $X$ have survival function $\mathbb{P}(X\ge x)=x^{-s}$ for $x\ge 1$, with $s>1$. Its expected value is $s/(s-1)$. The tail-sum formula for expectation givesThe absolutely continuous probability distribution gives zero mass to the integers, so $\lceil X\rceil =\lfloor X\rfloor +1$ almost surely and $\mathbb{E}[\lceil X\rceil ]=\zeta (s)+1$. Taking expectations of $\lfloor X\rfloor \le X\le \lceil X\rceil$ gives $\zeta (s)\le s/(s-1)\le \zeta (s)+1$, which rearranges to the displayed bounds on the Riemann zeta function. Finiteness is justified by $\lfloor X\rfloor \le X$ and $\lceil X\rceil \le X+1$.