Information-Theoretic & Statistical Lower Bounds

How Many Worlds Must a Summary Distinguish?

Suppose a museum has one of eight possible floor plans, but a guide may send you only a two-bit note before you enter. Two bits have four possible messages, so at least two plans receive the same note. If your task requires identifying the exact plan, no decoding trick can repair that collision. This is the counting intuition behind an information-theoretic lower bound: a small state cannot reliably distinguish too many possible worlds.

Streaming sketches replace floor plans with streams and the note with memory. If a hidden label $V$ selects one of $M$ carefully separated data-generating worlds, an accurate estimate may reveal which world generated the stream. The sketch state must therefore retain enough information about $V$. An $s$-bit state has entropy at most $s$, while Fano’s inequality says reliable identification among many labels requires mutual information on the order of $\log_2 M$.

For a tiny example, let $V$ be uniform on four labels. Then $H(V)=2$ bits. A one-bit deterministic summary has only two states and cannot identify all four labels exactly. Randomization can redistribute errors, but it cannot create information: if the observation distributions are too similar or the state is too small, a nontrivial error remains unavoidable.

Two kinds of scarcity must be separated. Memory scarcity limits how much an algorithm retains from observations. Sample scarcity limits how distinguishable the underlying distributions are even with unlimited memory. Some lower bounds combine both, but the proof must say which bottleneck is responsible.

Entropy, Encodings and Indistinguishable Streams

For a discrete variable $V$ with mass function $p(v)$,

$$ H(V)=-\sum_v p(v)\log_2 p(v). $$

Conditional entropy $H(V\mid S)$ is the residual uncertainty after observing $S$, and mutual information is $I(V;S)=H(V)-H(V\mid S)$. If $S$ takes at most $2^s$ values, then $H(S)\le s$ and therefore $I(V;S)\le s$. This is the memory bottleneck.

Now let $V$ choose a hard distribution $P_V$ over streams $X$. A randomized streaming algorithm maps $X$ and independent coins $R$ to state $S$. The causal chain is $V\to X\to S\to\widehat V$. Data processing gives

$$ I(V;\widehat V)\le I(V;S)\le I(V;X). $$

The first upper bound can also be capped by $s$. The left side is bounded below when decoding error is small. One common Fano form for uniform $V$ on $M$ labels is

$$ P_e\ge 1-\frac{I(V;S)+1}{\log_2 M}. $$

Equivalently, error $P_e\le\delta$ requires $I(V;S)\ge(1-\delta)\log_2 M-1$. Constants vary with logarithm base and theorem form; the quantifiers and distribution must remain explicit.

Statistical indistinguishability uses distances or divergences between observation laws. Total variation controls the best binary testing advantage. Kullback–Leibler divergence and related inequalities can upper-bound distinguishability, often tensorizing across independent samples. Small KL does not mean pointwise likelihoods are equal, and large parameter distance does not guarantee observable distributions are easy to distinguish.

flowchart TD
    A[Choose hidden label V over M worlds] --> B[World selects stream law P sub V]
    B --> C[Observe stream X]
    C --> D[Compress to s-bit state S]
    D --> E[Estimator or decoder V hat]
    A --> F[Entropy H of V]
    C --> G[Bound I of V and X statistically]
    D --> H[Bound I of V and S by s]
    G --> I[Data processing]
    H --> I
    E --> J[Small error implies large information by Fano]
    F --> J
    I --> K[Contradiction yields sample or memory bound]
    B --> X[Failure if hard worlds are not separated in loss]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C navy;
    class D,E,F purple;
    class G,H,I,J,K teal;
    class X crimson;

Packing, Testing and Information Arguments

A packing converts estimation into decoding. Choose parameters $\theta_1,\ldots,\theta_M$ whose pairwise loss distance exceeds $2\varepsilon$. If an estimator is within $\varepsilon$ of the true parameter, nearest-neighbor decoding recovers its label. Thus an estimator with small risk would induce a successful $M$-way test.

The hard family must balance two competing goals: parameter points must be far apart under the target loss, while their observation distributions remain close under KL, total variation, Hellinger distance, or another divergence. If distributions are too far apart, abundant statistical evidence makes testing easy. If parameters are too close, an inaccurate estimator need not distinguish them.

For memory lower bounds, let the full stream contain ample evidence but force that evidence through an $s$-bit state. For sample lower bounds, bound $I(V;X^n)$ itself. With conditionally independent samples, KL often grows linearly in $n$, so a per-sample information bound becomes an $n$ requirement. For combined bounds, use both $I(V;S)\le s$ and $I(V;S)\le I(V;X^n)$.

Binary testing tools such as Le Cam’s method compare two worlds; Assouad’s lemma embeds many binary coordinates; Fano handles a multiclass packing. Yao’s principle or a Bayes-prior argument can convert distributional hardness into a minimax lower bound, but average risk under a prior is not automatically a worst-case statement without that quantifier step.

flowchart TD
    A[Choose loss and target accuracy epsilon] --> B[Construct M separated parameters]
    B --> C[Put prior on hidden index V]
    C --> D[Generate stream observations X]
    D --> E[Upper-bound KL or mutual information]
    D --> F[Compress into s-bit state S]
    F --> G[Bound I of V and S by s]
    E --> H[Apply data processing]
    G --> H
    B --> I[Accuracy implies nearest-neighbor decoding]
    I --> J[Fano or testing lower bound]
    H --> K[Compare information upper and lower bounds]
    J --> K
    K --> L[Infer sample memory or risk lower bound]
    B --> X[Failure if packing balls overlap]
    E --> Y[Failure if hypotheses are easy to distinguish]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C navy;
    class D,E,F,G purple;
    class H,I,J,K,L teal;
    class X,Y crimson;

Limits of Estimation Under Tiny Memory

In an approachable sensor example, one of many calibrated regimes generates readings. If regimes are well separated in the reported mean but noisy observations are close, samples limit identification. If the readings reveal the regime but a device compresses them to a tiny state before a later query, memory limits identification.

In high-dimensional telemetry, a service may want a sparse histogram, covariance structure, or anomaly direction. A packing can encode exponentially many candidate directions, so $\log M$ scales with dimension. Yet a theorem for Gaussian samples does not automatically apply to heavy-tailed, dependent, or adversarial streams.

In federated learning, each client reveals a privatized or compressed message. Data processing limits information per client, and privacy may further contract distinguishability. But security and privacy are not synonymous with low mutual information under every prior; the channel, adversary knowledge, and composition across rounds must be modeled.

A misleading claim often treats high entropy of raw data as proof that a task needs high memory. That is false when the target is simple: a billion fair coin flips have enormous entropy, but their parity needs one bit and their approximate mean needs little memory. The packing must concern distinctions required by the stated loss.

Prove an Impossibility Without an Algorithm

An information-theoretic proof begins with the task’s loss and quantifiers. Construct a family of parameters separated enough that accuracy identifies a hidden label. Choose a prior, generate observations, and upper-bound the information reaching the estimator through sampling, privacy, communication, or memory. Then lower-bound the information accuracy would require and compare the two.

The final theorem must name its model: input family, distributional assumptions, number of observations, memory or message budget, randomness, side information, loss, success probability, and whether the conclusion is Bayes, average-case, or minimax.