Probability, Concentration & Confidence Amplification

Why Random Answers Can Still Be Reliable

Imagine estimating the fraction of red marbles in a huge, well-mixed jar by drawing a few marbles. One draw can mislead, but repeated independent draws make a large error less likely. Streaming sketches use a related idea: controlled randomness saves space, while a probability statement limits how often the answer can be far from its target. The statement needs a target, an error threshold, a failure probability, and assumptions about how randomness enters.

For a tiny example, let $X$ be $1$ for red and $0$ otherwise. If red marbles make up half the jar, $\mathbb E[X]=1/2$. Three draws $1,0,1$ give sample average $2/3$; that is a possible observation, not a contradiction of the expected value. Expectation is the average over possible repetitions, variance measures spread around that average, and a tail probability asks how often a deviation crosses a stated threshold. Confidence amplification combines several independent attempts to reduce the chance of a bad final answer. A bound on expectation alone never says every run is close. This chapter builds on the preceding page's fixed-input randomized guarantee: we now ask which mathematical tools justify its $\varepsilon$ and $\delta$.

Expectation, Variance and Indicator Variables

Let $X$ be a real-valued random variable with finite expectation $\mu=\mathbb E[X]$. Its variance, when finite, is $\sigma^2=\mathbb E[(X-\mu)^2]$. For any event $A$, the indicator $I_A$ equals $1$ on $A$ and $0$ otherwise, so $\mathbb E[I_A]=\Pr(A)$. Linearity gives $\mathbb E[\sum_i X_i]=\sum_i\mathbb E[X_i]$ even for dependent variables. Variances add as $\operatorname{Var}(\sum_i X_i)=\sum_i\operatorname{Var}(X_i)$ when variables are pairwise uncorrelated; independence is a sufficient, stronger condition. Without it, covariance terms remain.

An estimator $\widehat\theta$ is unbiased for a target $\theta$ if $\mathbb E[\widehat\theta]=\theta$. Its bias is $b=\mathbb E[\widehat\theta]-\theta$. The identity $\mathbb E[(\widehat\theta-\theta)^2]=\operatorname{Var}(\widehat\theta)+b^2$ separates spread from systematic error whenever the second moment exists. For $n$ independent Bernoulli draws with mean $p$, $\bar X=\sum_i X_i/n$ has mean $p$ and variance $p(1-p)/n\le1/(4n)$. If the draws share one random outcome, the sample average remains unbiased but its variance does not shrink with $n$.

A moment assumption is a statement such as finite mean, finite variance, or a bound on exponential moments. Higher-quality tails need stronger structure: a nonnegative random variable permits Markov's inequality; finite variance permits Chebyshev's; independent bounded summands permit Hoeffding's. Independent Bernoulli indicators permit a familiar Chernoff bound, and independent bounded summands plus their variance permit Bernstein's. Dependence can be treated with martingale differences, but only after specifying a filtration and conditional assumptions. The probability is over the estimator's randomness for a fixed input; a guarantee against an adaptive stream needs its own theorem.

flowchart TD
    I["Indicator events"] --> E["Expectation by linearity"]
    E --> B["Bias and target"]
    E --> V["Variance with covariance accounted for"]
    V --> C{"Available assumptions"}
    C -->|Finite variance| W["Chebyshev: polynomial tail"]
    C -->|Independent bounded terms| H["Hoeffding: exponential tail"]
    C -->|Martingale differences| M["Conditional tail theorem"]
    W --> A["Repetition plus median"]
    H --> A
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class I,E,B navy; class V,C purple; class W,H,A teal; class M crimson;

From Weak Moment Bounds to Exponential Tails

Start with little information. If $Y\ge0$ and $a>0$, then $Y\ge aI_{\{Y\ge a\}}$, hence $\mathbb E[Y]\ge a\Pr(Y\ge a)$. Thus Markov gives $\Pr(Y\ge a)\le\mathbb E[Y]/a$. Apply it to $Y=(X-\mu)^2$: if $X$ has finite variance, Chebyshev gives $\Pr(\lvert X-\mu\rvert\ge t)\le\sigma^2/t^2$. For an average of $n$ independent variables with common variance $\sigma^2$, this becomes at most $\sigma^2/(nt^2)$. Each step exposes an assumption: nonnegativity for Markov's chosen $Y$, finite second moment for Chebyshev, and variance addition for the average.

Stronger structure yields stronger tails. For independent $X_i\in[0,1]$, Hoeffding bounds the sample mean: $\Pr(\lvert\bar X-\mathbb E\bar X\rvert\ge t)\le2\exp(-2nt^2)$. Unlike Chebyshev's $1/n$ at fixed $t$, its bound decreases exponentially in $n$. For independent Bernoulli variables with sum $S$ and mean $\mu>0$, one Chernoff form for $0<\eta<1$ is $\Pr(S\le(1-\eta)\mu)\le\exp(-\eta^2\mu/2)$; another, for $\eta>0$, is $\Pr(S\ge(1+\eta)\mu)\le\left(e^{\eta}/(1+\eta)^{1+\eta}\right)^\mu$. Bernstein incorporates variance: for independent centered variables $\lvert X_i\rvert\le M$ and $v=\sum_i\mathbb E[X_i^2]$, $\Pr(\sum_iX_i\ge t)\le\exp(-t^2/[2(v+Mt/3)])$. These are different tools with different premises, not interchangeable names for “high probability.” Bounded martingale differences have Azuma–Hoeffding bounds; with a conditional variance process, Freedman's inequality may be useful. Neither permits arbitrary dependence or adversarial choices after seeing secret randomness without further analysis.

Amplify a weak estimator. Suppose one independent run lands within $\varepsilon$ of the target with probability at least $3/4$. Run it $k$ times with independent randomness and take the median. The median is bad only if at least half of the runs are bad. Hoeffding on their failure indicators bounds that event by $\exp(-k/8)$, so $k\ge8\ln(1/\delta)$ suffices for failure at most $\delta$ (round up to an integer). For finite-variance data, the median of means makes this concrete: split independent observations into $k$ disjoint blocks of size $b\ge4\sigma^2/\varepsilon^2$, average each block, then take their median. Chebyshev makes each block fail with probability at most $1/4$, after which the median bound applies. Bias needs separate attention: if every run is centered on the wrong value, repetition concentrates around that wrong value.

flowchart TD
    A["Nonnegative quantity"] --> B["Markov via threshold indicator"]
    B --> C["Square deviation, finite variance"]
    C --> D["Chebyshev: weak single-run bound"]
    D --> E["Independent repetitions"]
    E --> F["Median fails if half fail"]
    F --> G["Exponential failure bound"]
    C --> H{"Independent bounded terms?"}
    H -->|Yes| I["Hoeffding or Chernoff"]
    H -->|No| J["Check covariance or martingale assumptions"]
    I --> G
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class A,B,C navy; class D,E,F,G,I teal; class J crimson; class H purple;

One Alert, Ten Thousand Services

Approachable quality check. A teacher samples independent answers from a large shuffled stack, coding correct as $1$. If $n=50$ of $100$ sampled answers are correct, the estimate is $0.5$; the statement $\Pr(\lvert\bar X-p\rvert\ge0.2)\le2e^{-2(50)(0.2)^2}=2e^{-4}\approx0.0366$ follows under independent sampling with replacement. Without replacement, the draws are dependent; this particular theorem is no longer the direct justification, even though another suitable bound may exist. The model describes repeated randomized selection, not a guarantee that the observed fraction equals the population fraction.

Production telemetry. Suppose a platform monitors $10{,}000$ services, producing one fixed accuracy query per service in a reporting interval. To make the chance of any estimate exceeding tolerance at most $0.01$, the union bound suffices with per-query $\delta=10^{-6}$. If each estimate is a mean of independent bounded observations and needs additive tolerance $0.1$, Hoeffding asks for $n\ge\ln(2/\delta)/(2(0.1)^2)\approx725.43$, so $726$ samples per service suffice under the model. This is a conservative design calculation, not proof that those samples are feasible or that alert thresholds have a 1% false-alarm rate. Selection bias, missing events, and cross-service correlations affect the target or assumptions; the union bound itself requires no independence between services.

Misleading security case. An operator repeatedly inspects noisy dashboard outputs and chooses the next service and time window based on them. A guarantee proved for each fixed query does not automatically cover the selected query: its choice depends on previous randomized answers. Similarly, a sampling gateway that drops overloaded events changes the population represented by the observations. If an attacker sees a sketch's random hash seed, a theorem assuming a fixed stream independent of private coins may fail. The practical conclusion changes from “apply the same $\delta$” to “verify a simultaneous or adaptive guarantee, plus an honest data-collection model.”

Build and Audit a Confidence Budget

Start with the event whose probability you want to limit. Choose a bound whose assumptions fit the estimator, then allocate failure probability across runs, services, and time windows. The exercises progress from identifying a missing premise to reviewing a realistic contract; each answer should say exactly what follows and what still needs evidence.