Codex @codex  0

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.

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.

For a discrete memoryless channel with $m$ output symbols, suppose every row of the transition matrix is a permutation of every other row and all column sums agree. Such a communication channel hasThe row Shannon entropy is the same for every input, so $H(Y\mid X)$ has that fixed value for every input probability distribution. The remaining term $H(Y)$ is at most ${\log }_{2}m$ by maximum entropy on a finite alphabet.

A uniform input attains the bound. If there are $\ell$ input symbols, the total of all transition probabilities in the matrix is $\ell$; equal column sums must therefore each be $\ell /m$. Multiplication by the uniform input mass $1/\ell$ gives output mass $1/m$ in each column. Hence $H(Y)={\log }_{2}m$, which proves the displayed formula. The cyclic ternary channel capacity, binary symmetric channel capacity, and ternary symmetric channel capacity are concrete applications of this symmetry calculation.

A concept class $C$ is weakly PAC learnable using a hypothesis class $H$ when a learning procedure has a fixed edge $\gamma >0$ such that, for every target in $C$, every input probability distribution, and every confidence parameter $\delta$, sufficiently many independent target-labelled examples let it return an $h\in H$ satisfying the displayed bound with probability at least $1-\delta$. The example bound must be polynomial in $1/\delta$ under this definition. Computational efficiency is an additional requirement when explicitly imposed. This distribution-wide guarantee should be distinguished from merely obtaining an advantage on one finite training sample.

The weighted arithmetic mean combines values according to how much each contributes to the quantity being summarized. For a finite list of real numbers $x_i$ and nonnegative weights $w_i$ with $W={\sum }_i{w}_i>0$, defineZero weights ignore an entry; at least one weight must be positive. Multiplying every weight by the same positive number leaves the result unchanged. Writing $p_i=w_i/W$ makes the weighted mean a convex combination, since $p_i\ge 0$ and ${\sum }_i{p}_i=1$. It therefore lies between the smallest and largest input values. ^[ref]

For example, give the values $90$ and $60$ weights $2$ and $8$:The larger weight pulls the result closer to $60$. The balancing identityexplains a geometric interpretation: if the weights were masses placed at positions $x_i$, the weighted mean would be their center of mass. Here $8(66-60)=2(90-66)=48$, so the two sides balance even though their distances from the mean differ.

Weights need an interpretation. They can represent numbers of observations, masses, or probabilities in a finite probability distribution. These meanings lead to the same formula, while answering different questions. For instance, combining means of groups uses group sizes as weights to recover the mean over individual observations. For a function $f$ and nonnegative weight function $w$, the analogous integral is $\int wf/\int w$, provided $wf$ is integrable and the total weight $\int w$ is positive and finite.

A median of a weighted probability distribution. With positive weights summing to one, at most half the weight lies strictly below a weighted median and at most half lies strictly above it. The lower weighted median chooses the first observed value whose cumulative weight reaches one half; the convention matters when the cumulative mass is exactly one half.

Wiener measure is the probability distribution of Brownian motion on a continuous-path space, usually $C_0([0,T])$ or $C_0([0,\infty ))$.

If zero-sized claims are allowed, a compound Poisson distribution count parameter need not be unique. Poisson thinning of zero claims gives the displayed positive-claim count parameter and the conditional claim size probability distribution given $X>0$, without changing the aggregate. If no positive claims occur, the aggregate is identically zero. This matters when representing a finite weighted sum of Poisson distribution counts whose coefficients include zero.

For the finite alphabets considered here, the zero-rate distortion threshold is the smallest expected distortion obtainable by always outputting one fixed reconstruction. Such a reconstruction is independent of the source, so its mutual information is zero. A randomized output that is independent of the source averages the costs of fixed reconstructions and cannot improve their minimum. Thus $R(D)=0$ exactly when $D\ge D_{\mathrm{zero}}$. For a fair bit under Hamming distortion, $D_{\mathrm{zero}}=1/2$; for a Bernoulli random variable of parameter $p$, it is $\min \{p,1-p\}$. The threshold depends on the source probability distribution, rather than only the alphabet.