Assouad's lemma ($R^{\ast }\ge k(1-\eta )/2$)

Assouad's lemma turns many neighbouring testing problems into a lower bound for minimax risk. One direct form estimates an unknown bit vector $\omega \in \{0,1{\}}^k$ from data with law $P_{\omega }$, using Hamming distance as loss. If every neighbouring pair satisfies $\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }})\le \eta$, where $\omega ,{\omega }^{\prime }$ differ in one bit, thenTo prove it, average the risk over all vertices. For a fixed coordinate, pair vertices differing only in that bit. The sum of the two bit-error probabilities of any hypothesis test is at least $1-\mathrm{TV}$, so the averaged error in that coordinate is at least $(1-\eta )/2$. Sum over coordinates and use that a maximum dominates an average.

An Assouad hypercube embeds this construction in a larger estimation problem. The embedding must also relate the original loss to bit errors; it is that geometric separation which transfers the testing difficulty into a numerical estimation lower bound.

An Assouad hypercube is a family $(P_{\omega },{\theta }_{\omega }{)}_{\omega \in \{0,1{\}}^k}$ in which loss separates proportionally to Hamming distance while distributions at neighboring vertices remain close in total variation.