Metric Entropy of Finite Classes

Why Metric Entropy Depends on Scale

A finite class has a fixed number of elements, but its effective size can depend strongly on the resolution at which we view it. If many elements are close under a chosen metric, one ball may cover several of them; if distinct elements are well separated, a fine cover must keep them apart. Metric entropy records this scale-dependent covering requirement on a logarithmic scale.

For a finite class, cardinality immediately limits how large its covering number can be. The metric supplies a complementary fact: sufficiently fine covers must distinguish every element, provided distinct elements have positive distance. The precise scale at which this happens is determined by the class's minimum pairwise distance, not by its cardinality alone.

Covering Numbers and Metric Entropy

Let $(\mathcal{X},d)$ be a metric space and let $\mathcal{F}$ be a nonempty finite subset of $\mathcal{X}$. For $\varepsilon\geq 0$, a closed ball of radius $\varepsilon$ centered at $g$ is the set of points $f$ such that $d(f,g)\leq\varepsilon$. In this tutorial, cover centers are required to belong to $\mathcal{F}$. A cover is a collection of such balls whose union contains all of $\mathcal{F}$.

Definition: The covering number $N(\varepsilon,\mathcal{F},d)$ is the smallest number of radius-$\varepsilon$ balls, centered at elements of $\mathcal{F}$, that cover $\mathcal{F}$. The metric entropy is $$ H(\varepsilon,\mathcal{F},d)=\log N(\varepsilon,\mathcal{F},d), $$ where $\log$ denotes the natural logarithm.

Because $\mathcal{F}$ itself can be used as a set of centers, a finite nonempty class always has a finite covering number. At radius zero, each ball contains just its center, so $N(0,\mathcal{F},d)=|\mathcal{F}|$. As the radius increases, covers can only become easier to construct: if $0\leq\varepsilon_1\leq\varepsilon_2$, then $N(\varepsilon_2,\mathcal{F},d)\leq N(\varepsilon_1,\mathcal{F},d)$. Metric entropy is therefore nonincreasing in the radius.

The Cardinality Bound and Its Exact Range

Write $m=|\mathcal{F}|$. One ball centered at each element gives a cover at every nonnegative radius, while every cover of a nonempty class uses at least one ball. These observations give the universal cardinality bounds.

Theorem: For every finite nonempty $\mathcal{F}$ in a metric space and every $\varepsilon\geq 0$, $$ 1\leq N(\varepsilon,\mathcal{F},d)\leq |\mathcal{F}|, \qquad 0\leq H(\varepsilon,\mathcal{F},d)\leq \log|\mathcal{F}|. $$

The proof does not require a special form for the metric. For the upper bound, use all $m$ class elements as centers: each element lies in the ball centered at itself, since its distance from itself is zero. For the lower bound, at least one ball is necessary to cover a nonempty class. Applying the increasing function $\log$ gives the entropy bounds.

A sharper statement identifies when the upper bound is attained. If $\mathcal{F}$ contains at least two elements, define its minimum pairwise distance by $$ \delta(\mathcal{F},d)=\min_{\substack{f,g\in\mathcal{F}\\f\ne g}}d(f,g). $$ There are finitely many pairwise distances, and each is strictly positive because $d$ is a metric. Hence $\delta(\mathcal{F},d)>0$.

Theorem: If $|\mathcal{F}|\geq 2$, then for every $0\leq\varepsilon<\delta(\mathcal{F},d)$, $$ N(\varepsilon,\mathcal{F},d)=|\mathcal{F}|, \qquad H(\varepsilon,\mathcal{F},d)=\log|\mathcal{F}|. $$ For a singleton class, these equalities hold at every radius.

To prove the claim, take any two distinct elements $f,g\in\mathcal{F}$. By definition of the minimum, $d(f,g)\geq\delta(\mathcal{F},d)>\varepsilon$. Thus a radius-$\varepsilon$ ball centered at $f$ cannot contain $g$. Each ball centered in the class covers only its own center, so covering all $m$ elements requires at least $m$ balls. The cardinality bound already gives $N\leq m$, proving equality; taking logarithms proves the entropy equality. In particular, a finite class's entropy equals $\log m$ at all sufficiently small radii, even though it can be much smaller at coarser resolutions. $\square$

Worked Example: A Discrete Metric

Let $\mathcal{F}$ contain five distinct points, with the discrete metric $d(f,g)=1$ when $f\ne g$ and $d(f,f)=0$. The minimum pairwise distance is $\delta=1$.

If $0\leq\varepsilon<1$, each radius-$\varepsilon$ ball contains only its center. Therefore $N(\varepsilon,\mathcal{F},d)=5$, and $H(\varepsilon,\mathcal{F},d)=\log 5$, approximately $1.609$.

If $\varepsilon\geq1$, every ball centered at a class element contains all five points, because every pairwise distance is at most $1$. Consequently $N(\varepsilon,\mathcal{F},d)=1$ and $H(\varepsilon,\mathcal{F},d)=0$. The class cardinality stays five throughout; only its covering number changes with the resolution.

Calculating Covering Numbers from the Metric

The cardinality theorem gives bounds, not the covering number at every radius. To calculate that number at a particular radius, check which elements can share a ball under the chosen metric and find the smallest collection of centers that covers the class.

Worked Example: Four Points on the Real Line

Take $\mathcal{F}=\{0,1,3,7\}$ with the usual distance $d(x,y)=|x-y|$, and require centers to lie in $\mathcal{F}$. The minimum pairwise distance is $1$, so the theorem gives $N=4$ for $0\leq\varepsilon<1$. The remaining ranges can be checked by listing which points each center reaches.

For $1\leq\varepsilon<2$, the ball centered at $1$ covers $0$ and $1$, since their distances from $1$ are $1$ and $0$. No ball can cover both $1$ and $3$, whose distance is $2>\varepsilon$, and the point $7$ cannot share a ball with another point at these radii. Thus three centers are necessary and sufficient: use centers $1,3,7$. Hence $N=3$ and $H=\log 3$.

For $2\leq\varepsilon<4$, the ball centered at $1$ covers $0,1,3$, because their distances from $1$ are $1,0,2$. The point $7$ remains uncovered by that ball. No single center covers both $0$ and $7$: their distance is $7>2\varepsilon$ when $\varepsilon<3.5$, and for $3.5\leq\varepsilon<4$ no class center is within $\varepsilon$ of both (the only candidate centers between the points are $1$ and $3$, and neither is). Two centers suffice, for example $1$ and $7$. Therefore $N=2$ and $H=\log 2$ on this range.

For $\varepsilon\geq4$, the ball centered at $3$ covers all four points: the distances are $3,2,0,4$. Thus $N=1$ and $H=0$. Combining the ranges, $N$ is $4,3,2,1$ on $[0,1),[1,2),[2,4),[4,\infty)$, respectively.

The lower-bound check in the middle range illustrates a useful method: if a proposed one-ball cover would need to reach two points farther apart than $2\varepsilon$, the triangle inequality rules it out. Indeed, if both $x$ and $y$ were within $\varepsilon$ of a center $c$, then $d(x,y)\leq d(x,c)+d(c,y)\leq2\varepsilon$. The explicit list of possible class centers handles the remaining radii in this example.

Worked Example: Empirical Distance Between Binary Functions

Consider four binary vectors on three fixed observations: $f_0=(0,0,0)$, $f_1=(1,0,0)$, $f_2=(1,1,0)$, and $f_3=(1,1,1)$. Use empirical $L_1$ distance, which here is the proportion of coordinates on which two vectors differ: $d(f,g)=\frac{1}{3}\sum_{i=1}^3|f_i-g_i|$. Consecutive vectors in the list are at distance $1/3$; vectors separated by two or three steps are at distance $2/3$ or $1$. Thus the minimum pairwise distance is $1/3$.

At radius $\varepsilon=1/4$, which is below $1/3$, each ball covers only its center. Therefore $N=4$ and $H=\log 4$.

At radius $\varepsilon=1/3$, the centers $f_1$ and $f_2$ cover the whole class: $f_1$ covers $f_0,f_1$, and $f_2$ covers $f_2,f_3$. One ball cannot suffice, since no class element is within $1/3$ of all four vectors; for instance, $f_0$ is distance $1$ from $f_3$. So $N=2$ and $H=\log 2$.

At radius $\varepsilon=2/3$, the ball centered at $f_1$ covers $f_0,f_1,f_2$, but not $f_3$. The ball centered at $f_2$ covers all four: its distances to $f_0,f_1,f_2,f_3$ are $2/3,1/3,0,1/3$. Hence $N=1$ and $H=0$. This example shows how the same finite class can have different entropy at different resolutions under a data-dependent metric.

What Changes if Centers May Be Outside the Class?

Some conventions allow cover centers to lie anywhere in an ambient metric space containing $\mathcal{F}$. The universal upper bound $N(\varepsilon,\mathcal{F},d)\leq|\mathcal{F}|$ still holds, because class elements remain available as centers. But the exact small-radius threshold can change: an external point may lie within radius $\varepsilon$ of two class elements.

For example, in the real line the class $\{0,1\}$ can be covered by one closed ball of radius $1/2$ centered at $1/2$, if that center is allowed. For any finite class with minimum pairwise distance $\delta>0$, a ball of radius $\varepsilon<\delta/2$ cannot contain two class elements: if it contained $f$ and $g$, the triangle inequality would give $d(f,g)\leq2\varepsilon<\delta$, a contradiction. Thus the cardinality bound is attained below $\delta/2$ under the ambient-center convention. The convention must be specified when an exact threshold matters.

A genuine metric assigns positive distance to distinct points. If the distance is instead a pseudometric, distinct functions may have distance zero—for example, if they agree on every observation in a fixed sample. The positive minimum separation argument then does not apply to the original list of functions. One can first identify functions at distance zero as equivalent and apply the small-radius statement to the resulting finite set of equivalence classes; the universal upper bound by the original cardinality remains valid.

Common Pitfall and Why the Bounds Matter

Incorrect: “The class has $m$ elements, so its metric entropy is always $\log m$.” This confuses a universal upper bound with an equality at every radius. A single sufficiently large ball may cover the whole class, giving entropy zero.
Correction: Cardinality guarantees $H(\varepsilon,\mathcal{F},d)\leq\log m$. The metric determines whether this bound is attained at the chosen radius. For a finite class under a genuine metric, it is attained whenever $\varepsilon$ is below the minimum pairwise distance under the internal-cover convention.

The cardinality bound is useful because it applies without assumptions about the geometry of the class. The small-scale equality adds a precise limit to that statement: finite classes cannot remain compressed at arbitrarily fine resolution when distinct elements have positive distance. At coarser scales, however, cardinality alone does not determine entropy. Two classes of the same size can have very different covering numbers under their respective metrics. This distinction is central when a later analysis uses covering numbers to quantify complexity: both the size of the class and the metric scale must be kept in view.

Check Your Understanding

Use the stated internal-cover convention unless a question specifies otherwise.

For a nonempty finite class of $m$ elements, state the universal bounds on its covering number and metric entropy.
Why is the minimum pairwise distance positive for a finite set of distinct points in a metric space?
A finite class has minimum pairwise distance $0.2$. What are its covering number and entropy at radius $0.1$, in terms of its cardinality $m$?
For the class $\{0,1\}$ on the real line, explain why allowing an external center changes the one-ball covering threshold.
What adjustment is needed before applying the minimum-separation result to a finite class under a pseudometric?