Why Separated Parameter Sets Matter
A lower-bound argument often begins by selecting several possible parameter values that are far apart under the loss metric. The number of such alternatives depends on the geometry of the parameter space: a long interval can contain many points at a given separation, while a small discrete space may contain only a few. Packing numbers formalize this scale-dependent count.
The geometric question is distinct from the statistical one. A large packing supplies many well-separated parameter values; it does not, by itself, show that their distributions are hard to distinguish. Statistical lower bounds need both suitable geometry and control of the corresponding experiments.
Definitions: Separation, Packing, and Entropy
This tutorial uses strict separation, \(d(\theta,\theta')>\varepsilon\), throughout. Some references use separation at least \(\varepsilon\); boundary cases can therefore differ. The scale \(\varepsilon\) is measured in the same units as the metric. A packing count is nonincreasing in \(\varepsilon\): increasing the required distance cannot create new separated pairs.
For comparison, the covering number \(N(\Theta,d,\varepsilon)\) is the smallest number of closed metric balls of radius \(\varepsilon\) whose union contains \(\Theta\). A packing asks how many points can be kept apart; a cover asks how many balls suffice to reach every point.
A Basic Relation to Covering Numbers
When the space is totally bounded, packings at a fixed positive scale are finite. Total boundedness means that for every positive radius the space can be covered by finitely many balls of that radius. The following bounds explain how packing and covering counts constrain each other.
Proof. First, total boundedness gives a finite cover of \(\Theta\) by balls of radius \(\varepsilon/2\). Each such ball has diameter at most \(\varepsilon\), by the triangle inequality. It can therefore contain at most one point of any \(\varepsilon\)-separated set. Thus the cardinality of every such packing is bounded by the number of balls in this finite cover. The packing number at scale \(\varepsilon\) is consequently finite.
Because the possible packing cardinalities are bounded positive integers, there is an \(\varepsilon\)-separated set \(A\) with cardinality \(M(\Theta,d,\varepsilon)\). It is maximal by inclusion: adding any point would make a larger separated set. For every \(\theta\in\Theta\), maximality implies that some \(a\in A\) satisfies \(d(\theta,a)\leq\varepsilon\); otherwise \(\theta\) could be added. The closed balls of radius \(\varepsilon\) centered at \(A\) cover \(\Theta\), so \(N(\Theta,d,\varepsilon)\leq |A|=M(\Theta,d,\varepsilon)\).
For the other inequality, take any \(2\varepsilon\)-separated set \(B\). A closed ball of radius \(\varepsilon\) cannot contain two distinct points \(b,b'\in B\), since then the triangle inequality would give \(d(b,b')\leq 2\varepsilon\), contrary to strict separation. Every cover by radius-\(\varepsilon\) balls must therefore use at least \(|B|\) balls. Taking a largest such packing gives \(N(\Theta,d,\varepsilon)\geq M(\Theta,d,2\varepsilon)\). \(\square\)
The factors of two reflect the difference between separation and coverage, not a statistical approximation. In applications, bounds on either count can therefore give information about the other, with a change in scale.
Exact Packing on an Interval
For a simple parameter space, the packing count can be computed exactly. Equip \([0,1]\) with the usual distance \(d(x,y)=|x-y|\). For \(0<\varepsilon\leq1\), the strict-separation convention gives
To prove the upper bound, arrange any \(m\) separated points in increasing order \(x_1<\cdots<x_m\). Each consecutive gap exceeds \(\varepsilon\), so
Hence \(m<1+1/\varepsilon\), which implies \(m\leq\lceil1/\varepsilon\rceil\). For the matching construction, let \(q=\lceil1/\varepsilon\rceil\). If \(q=1\), a single point attains the count. If \(q\geq2\), take the \(q\) equally spaced points \(0,1/(q-1),\ldots,1\). Since \(q-1<1/\varepsilon\), their spacing \(1/(q-1)\) exceeds \(\varepsilon\). This constructs a packing of size \(q\), proving the equality.
Worked Example: Packing the Unit Interval
Find the packing number of \([0,1]\) at separation scale \(\varepsilon=0.3\), and exhibit a packing of that size.
The formula gives \(\lceil1/0.3\rceil=\lceil3.333\ldots\rceil=4\). The points \(0,1/3,2/3,1\) are \(1/3\) apart, and \(1/3\approx0.333>0.3\), so they form a valid four-point packing.
To check that five points are impossible, five ordered points would require four consecutive gaps, each greater than \(0.3\). Their total span would exceed \(4(0.3)=1.2\), although all points lie in an interval of length \(1\). Thus the constructed packing is largest.
Product Grids in a Cube
In higher dimensions, a grid gives a direct construction. Equip \([0,1]^d\) with the maximum-coordinate metric \(d_\infty(x,y)=\max_{1\leq j\leq d}|x_j-y_j|\). If each coordinate is chosen from an interval grid whose spacing exceeds \(\varepsilon\), then distinct grid points differ by more than \(\varepsilon\) in at least one coordinate. They are therefore separated in \(d_\infty\).
Worked Example: A Two-Dimensional Product Grid
Construct a packing in \([0,1]^2\) at scale \(\varepsilon=0.3\) under \(d_\infty\), and count its points.
Use the four coordinate values \(0,1/3,2/3,1\). There are \(4\times4=16\) ordered pairs. For any two different pairs, at least one coordinate differs. Distinct coordinate values in this grid differ by at least \(1/3>0.3\). Thus the maximum-coordinate distance between any two grid points exceeds \(0.3\), and all 16 points form a valid packing.
This is a construction, not a claim that 16 is the exact packing number. Its value is that it gives a verified lower bound on the packing number without requiring an optimal arrangement.
The same reasoning works in dimension \(d\). For \(0<\varepsilon<1\), take \(q=\lceil1/\varepsilon\rceil\) equally spaced coordinate values on \([0,1]\). As shown above, their spacing exceeds \(\varepsilon\). Their Cartesian product has \(q^d\) points, and distinct product points differ by more than \(\varepsilon\) in at least one coordinate. Therefore
Discrete Combinatorial Constructions
Packings also arise naturally when parameters are discrete objects. For binary vectors \(u,v\in\{0,1\}^d\), the Hamming metric \(d_H(u,v)\) counts the coordinates on which they differ. It is a metric: in particular, if \(u\) and \(w\) differ at a coordinate, then at least one of \(u,v\) or \(v,w\) differs there, which gives the triangle inequality after counting coordinates.
Worked Example: A Packing from Binary Vectors
Let \(d=4\), and consider all 16 binary vectors with the Hamming metric. Find a packing at scale \(\varepsilon=0.5\).
Any two distinct binary vectors differ in at least one coordinate. Their Hamming distance is therefore at least \(1\), which exceeds \(0.5\). All \(2^4=16\) vectors form a packing. Since the whole parameter space has only 16 elements, no larger packing is possible, so \(M(\{0,1\}^4,d_H,0.5)=16\).
This calculation depends on the metric and scale: under Hamming distance, changing even one coordinate costs \(1\). It does not imply that the same 16 alternatives are well separated under a differently scaled loss.
Worked Example: One-Coordinate Subsets
Consider the subsets of \(\{1,2,3,4,5\}\) equipped with the symmetric-difference distance \(d(A,B)=|A\mathbin{\triangle}B|\), where \(A\mathbin{\triangle}B\) contains the elements belonging to exactly one of \(A\) and \(B\). Construct a packing at scale \(1.5\).
Take the five singleton sets \(\{1\},\ldots,\{5\}\). For distinct \(i\) and \(j\), their symmetric difference is \(\{i,j\}\), so their distance is \(2>1.5\). These five sets form a packing, giving a packing number of at least 5. This example illustrates how a simple combinatorial family can supply separated alternatives even when the full parameter space is much larger.
Common Pitfall and Statistical Role
- Confusing a packing with a cover. A packing has points far from one another; a cover has balls that reach the whole space. The theorem relates their counts, but they are not the same construction.
- Ignoring the separation convention. Under the convention used here, distance exactly \(\varepsilon\) does not qualify. For example, points spaced exactly \(0.3\) apart are not a \(0.3\)-separated set.
- Treating geometry as a complete lower bound. A large packing only identifies many separated parameter values. A statistical argument must additionally compare the distributions generated by those values.
In metric estimation, the loss determines which alternatives count as meaningfully distinct, while the model determines how difficult they are to tell apart. Packing numbers quantify the first part. The later Fano method for metric estimation combines this geometry with information about the statistical experiments; a packing count alone does not establish its conclusion.
Check Your Understanding
Answer each question using the strict separation convention in this tutorial.
- Why can a closed ball of radius \(\varepsilon\) contain at most one point from a set whose pairwise distances exceed \(2\varepsilon\)?
- What is the packing number of \([0,1]\) at scale \(\varepsilon=0.4\), and what points attain it?
- For the maximum-coordinate metric, why does a product of coordinate grids with spacing greater than \(\varepsilon\) give a separated set?
- What is the Hamming distance between \(1010\) and \(0011\), and do these vectors form a \(1.5\)-separated pair?
- Why is a large packing not, on its own, a statistical lower bound?