Assouad Bounds for Product Bernoulli Models

Why Product Bernoulli Models Are Useful

A common lower-bound construction uses many binary choices, one for each coordinate of a parameter. Each choice changes the distribution of the data only slightly. Although any one change may be difficult to detect, estimating the whole vector requires getting many such choices right. Assouad’s method makes that accumulation precise: it relates the difficulty of testing neighboring models to the expected number of incorrectly estimated coordinates.

For product Bernoulli experiments, the key calculation is especially transparent. Neighboring models differ in one coordinate block, so their Kullback–Leibler divergence is the divergence for one Bernoulli observation multiplied by the number of replicates in that block. A bound on the resulting total variation distance then yields a lower bound on aggregate Hamming error.

Product Bernoulli Hypercube

There are \(n\) observations for each coordinate, and the \(d\) coordinate blocks are independent. If \(\omega\) and \(\omega^{(j)}\) differ only at coordinate \(j\), the corresponding data distributions differ only in the \(j\)th block. For distributions \(P,Q\), write \(D(P\|Q)\) for Kullback–Leibler divergence and \(\operatorname{TV}(P,Q)=\sup_A|P(A)-Q(A)|\) for total variation distance.

Neighboring-Model Divergence

For Bernoulli probabilities \(p,q\in(0,1)\), the Kullback–Leibler divergence is \(\operatorname{kl}(p,q)=p\log(p/q)+(1-p)\log((1-p)/(1-q))\). Product distributions have additive Kullback–Leibler divergence. In this setting, that fact can be checked directly using the log-likelihood ratio.

To verify the calculation, the likelihood ratio for the full data cancels in every coordinate other than \(j\). In coordinate \(j\), it is the product of the \(n\) Bernoulli likelihood ratios. Taking its logarithm gives a sum; taking expectation under \(P_\omega\) gives \(n\) copies of the one-observation divergence:

The expectation in the second line uses \(E_{p_0}[X_{ij}]=p_0\) and \(E_{p_0}[1-X_{ij}]=1-p_0\). No factor of \(d\) appears: a neighboring pair differs in only one coordinate block.

From Neighboring Tests to Hamming Error

For each coordinate, deciding whether \(\omega_j=0\) or \(1\) is a binary testing problem. Pair each hypercube point with its neighbor in coordinate \(j\), holding the other \(d-1\) bits fixed. The binary testing bound says that the sum of the two error probabilities for any test is at least one minus the total variation distance between the two distributions. Applying that bound to every pair gives the following aggregate result.

Here is the full aggregation argument. Fix coordinate \(j\), and index the \(2^{d-1}\) pairs by \(\eta\in\{0,1\}^{d-1}\), the common values of the other coordinates. Let \(P_{\eta,0}\) and \(P_{\eta,1}\) denote the corresponding data distributions. The decoder’s \(j\)th bit is a test between this pair. By the binary testing error bound,

Average the error probability for coordinate \(j\) over all \(2^d\) indices. Each pair contributes the two probabilities on the left, and there are \(2^{d-1}\) pairs. Therefore,

Summing this inequality over all \(d\) coordinates shows that the average expected Hamming error over the hypercube is at least \(d(1-v)/2\). A maximum is at least an average, giving the theorem’s first inequality. In the product Bernoulli model, every neighboring pair has divergence \(n\operatorname{kl}(p_0,p_1)\). Pinsker’s inequality bounds its total variation by the square root in the theorem, which proves the stated consequence. \(\square\)

Explicit Divergences Near One Half

A useful special case sets \(p_0=1/2\) and \(p_1=1/2+\delta\), where \(0<\delta<1/2\). The one-observation divergence in the direction from \(p_0\) to \(p_1\) simplifies to

The direction matters: this expression is specifically \(\operatorname{kl}(p_0,p_1)\), not a claim that Bernoulli divergence is symmetric. The neighboring-model divergence is \(n\) times this quantity, and the Hamming bound follows by substituting it into the theorem.

Using the Bound Carefully

The method is useful when a parameter can be encoded by many binary choices and changing one choice at a time produces nearby data distributions. The divergence calculation quantifies how nearby each pair remains; the Hamming aggregation then converts that local indistinguishability into a global estimation obstruction. The resulting lower bound is most informative when the neighboring total variation distance is bounded away from one.

If \(p_0\) and \(p_1\) are fixed and \(n\) grows, the neighboring divergence grows linearly with \(n\), so the Pinsker expression may eventually exceed one. That does not contradict the theorem: the displayed Hamming lower bound then becomes negative and provides no useful information. In applications, the two probabilities may be chosen close enough that the neighboring experiments remain difficult to distinguish at the sample size under study.

Common Pitfall

• Multiplying by the wrong dimension. A pair differing in one bit has divergence \(n\operatorname{kl}(p_0,p_1)\), not \(nd\operatorname{kl}(p_0,p_1)\). Only one coordinate block changes between neighbors.
• Confusing a maximum with an average. Pairwise testing bounds first yield a lower bound on the average expected Hamming error over the hypercube. The maximum is at least that average; the argument does not establish the same lower bound separately for every \(\omega\).
• Using the wrong parameter values in a loss calculation. If the target is the probability vector, its entries are \(p_0\) and \(p_1\). If the target is the offset vector, its entries are \(0\) and \(p_1-p_0\). The action space and the loss calculation must match the target actually defined.

The practical sequence is: calculate the divergence for a single changed coordinate block, bound the corresponding total variation distance, aggregate the coordinate testing errors, and only then translate Hamming error into the loss for the stated parameter and action spaces.