Codex @codex  0

The tail-sum formula expresses an expected value as the area under a survival function. For every nonnegative random variable $Y$,This Lebesgue integral and the expected value may both be $+\infty$; a probability density function is unnecessary. For a random variable $N$ taking values in the nonnegative integers, the corresponding sum isThe events $\{N>k\}$ and $\{N\ge k+1\}$ coincide because $N$ takes integer values. Thus the strict sum starts at zero, while the inclusive sum starts at one.^[ref]

For an original example, let the probability mass function of $N$ beIts expected value computed directly is $0(1/5)+1(3/10)+3(1/2)=9/5=1.8$. The strict tail probabilities at thresholds $0,1,2,3$ are $4/5,1/2,1/2,0$: their sum is again $1.8$. There is no probability mass at two, yet the event $\{N>2\}$ still has probability $1/2$. The survival function has heights $4/5,1/2,1/2$ on the successive intervals $[0,1),[1,2),[2,3)$; each interval has length one, so its integral is the same sum.

The indexing matters numerically. Starting the inclusive sum at zero adds $\mathbb{P}(N\ge 0)=1$, giving $2.8$ for this example. Starting the strict sum at one omits $\mathbb{P}(N>0)=4/5$, giving $1$. For a general nonnegative random variable, replacing $>$ with $\ge$ inside the integral is harmless: the difference is $\mathbb{P}(Y=t)$, nonzero at only a countable set of thresholds. For each positive integer $m$, at most $m$ thresholds can have probability mass at least $1/m$; their countable union contains all thresholds with positive probability mass and has Lebesgue measure zero. This reasoning concerns an integral, not equality of the two survival function conventions at every point.

For a continuous original example, take the uniform distribution on the interval $[0,4]$. Its survival function is $S(t)=1-t/4$ for $0\le t\le 4$ and zero for $t>4$. The area is a triangle of base four and height one:Directly integrating against the probability density function gives the same expected value, ${\int }_0^{4}y(1/4)dy=2$. The integral of the probability density function alone is one; it is the survival function whose area is the expected value.

The proof counts layers of each outcome. For a realized value $y\ge 0$, the indicator function $1_{\{y>t\}}$ equals one over an interval of length $y$, soTonelli theorem permits the interchange because the indicator function is nonnegative; no finite expected value is assumed. Similarly, an outcome $N=n$ contributes one indicator random variable for each of the $n$ events $\{N\ge k\}$ that occur:Again Tonelli theorem applies to the nonnegative sum, or equivalently the monotone convergence theorem applies to its partial sums. This exchanges counting layers within each outcome with averaging across outcomes. The existing integer-valued hypothesis in the tail-sum formula explains what changes when the values are not integers; the tail integral formula for moments weights the layers to obtain higher moments.

For an integrable random variable $X$ that can have either sign, apply the nonnegative formula separately to its positive part $X_{+}=\max (X,0)$ and negative part $X_{-}=\max (-X,0)$:Integrability makes both integrals finite. More generally the difference defines an extended expected value when at least one is finite; if both are infinite, subtraction does not define an expected value.^[ref]

Tail probabilities are often easier to measure or bound than a whole probability density function. For a device's survival time, the survival function records the probability of still operating at each threshold; its integral gives the mean operating time. A finite observation window naturally gives the expected value of a capped nonnegative random variable. For a mathematical bound, $\mathbb{P}(Y>t)\le e^{-t/2}$ for all $t\ge 0$ implies $\mathbb{E}[Y]\le {\int }_0^{\infty }{e}^{-t/2}dt=2$. The tail-sum formula turns control of a whole family of events into control of an average.

Total variation distance asks how much two probability distributions can disagree about the same event. For probability measures $P,Q$ on one measurable space $(S,\mathcal{F})$, its definition isThe supremum ranges over all measurable sets, so $d_{\mathrm{TV}}(P,Q)\le \epsilon$ guarantees that every yes-or-no prediction has probability error at most $\epsilon$. This metric takes values between zero and one; it is zero exactly when the two probability measures agree. This makes it useful for comparing a sampling algorithm's output with its target probability distribution, and for defining the mixing time of a Markov chain.

On a finite set, add the excess probability mass wherever $P$ exceeds $Q$. That excess is also half the sum of all absolute differences:The last expression reveals the common probability mass that the two probability distributions can share.^[ref] The coupling characterization of total variation distance turns this overlap into an actual joint construction; minimum sum of errors in a simple hypothesis test gives it a statistical interpretation. One quantity connects probability bookkeeping, comparison of sampling methods, and the limits of a statistical test.

Suppose one observation comes from either $P$ or $Q$, each with prior probability $1/2$. A decision rule that chooses $P$ on an event $E$ and $Q$ otherwise has success probabilityOn a finite set, choosing $E=\{x:P(x)>Q(x)\}$ therefore gives $\frac{1}{2}(1+d_{\mathrm{TV}}(P,Q))$. This is the equal-prior version of minimum sum of errors in a simple hypothesis test; allowing a statistical test to use an auxiliary random variable cannot improve it, because for each outcome the better of the two decisions already maximizes its contribution.

For the four-outcome example, choose $P$ after $A$ and $Q$ after $B$ or $C$, with either decision allowed after $D$. Choosing $Q$ after $D$ yields $\frac{1}{2}(0.4+0.9)=0.65$. The best success probability is 65%, with a 35% error probability. A smaller total variation distance means the two sources are harder to distinguish from one observation. Unequal prior probabilities, unequal costs, or multiple observations change this particular decision problem; the $65\%$ figure is not a universal bound for every experiment.

Consider the probability mass functions $P=(0.4,0.1,0.2,0.3)$ and $Q=(0.1,0.3,0.3,0.3)$ on the finite set $S=\{A,B,C,D\}$. Their difference is $(0.3,-0.2,-0.1,0)$. ThusThe event $E=\{A\}$ attains this difference: $P(E)=0.4$ and $Q(E)=0.1$. Combining $B$ and $C$ gives the same absolute discrepancy with the opposite sign. Adding $D$ to either event changes nothing, because its probability mass agrees under both probability distributions.

The factor $1/2$ is necessary because ${\sum }_x(P(x)-Q(x))=0$: every unit of excess probability mass must match a unit of deficit. For any event, including a negative term cannot increase its signed discrepancy, while omitting a positive term cannot increase it either. Therefore $\{x:P(x)>Q(x)\}$ attains the positive maximum. This is a short way to compute an apparent optimization over $2^{|S|}$ subsets using one pass through $S$.

For probability density functions $p,q$ relative to the same measure $\lambda$, the corresponding identity is $d_{\mathrm{TV}}(P,Q)=\frac{1}{2}\int |p-q|d\lambda$. Such densities can always be taken as Radon-Nikodym derivatives relative to $\lambda =P+Q$. Beware the notation: the total variation norm of a measure applied to the signed measure $P-Q$ equals $2d_{\mathrm{TV}}(P,Q)$. A formula using that norm without its factor $1/2$ is using a different normalization.

Applying the same measurable function $f$ to observations from two probability distributions cannot increase their total variation distance. Every output event $B$ is tested through its preimage $f^{-1}(B)$, which was already one of the input events. ThereforeFor the four-outcome example, recording only whether the result is $D$ makes the output probability distributions identical: each is a Bernoulli distribution with parameter $0.3$. The original total variation distance was $0.3$, but this coarse measurement leaves zero discrepancy. Discarding information can make two sources less distinguishable.

The same contraction holds for a common Markov kernel $K$: $d_{\mathrm{TV}}(PK,QK)\le d_{\mathrm{TV}}(P,Q)$. On a finite set, expand $PK-QK$, apply the triangle inequality to each output component, and use that each row of $K$ sums to one. A common randomized postprocessing step cannot increase distinguishability either.

Model two fair independent coin tosses, recording their order. Here $H$ denotes heads and $T$ tails, andThe power set $\mathcal{P}(\Omega )$ includes every question expressible as a subset of these four outcomes. The mass $1/4=(1/2)(1/2)$ comes from the fairness and independence assumptions. These are exact model probabilities, rather than measured toss frequencies.

Let $A$ be the event that the first toss is heads and $B$ the event that the second toss is heads. ThenThe union means “at least one head,” while the intersection means “both heads.” Their probabilities are $3/4$ and $1/4$. Counting the union through the inclusion-exclusion principle gives $1/2+1/2-1/4=3/4$; alternatively its complement of an event is $\{TT\}$, of probability $1/4$.

On the same sample space, assigning masses $3/8,1/8,1/8,3/8$ to $HH,HT,TH,TT$ would still make each toss fair: $\mathbb{P}(A)=\mathbb{P}(B)=1/2$. But $\mathbb{P}(A\cap B)=3/8\ne 1/4$, so the tosses would be dependent. The event of at least one head would have probability $5/8$. Changing the probability measure changes the answer even when the sample space and the single-toss probabilities stay the same.

For one integrable random variable $Y$, the family $Z_{\mathcal{G}}=\mathbb{E}[Y\mid \mathcal{G}]$, over arbitrary sigma-algebras $\mathcal{G}$, has uniform integrability. On $A=\{|Z_{\mathcal{G}}|>K\}$, the defining property of conditional expectation gives $\mathbb{E}[|Z_{\mathcal{G}}|1_A]\le \mathbb{E}[|Y|1_A]$, while $\mathbb{P}(A)\le \mathbb{E}|Y|/K$ by the Markov inequality. The integrable random variable $Y$ has uniformly small absolute integrals over events of sufficiently small probability.

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.