Worked Population Quantizers in One Dimension

Population Quantizers and Squared-Distance Risk

A population quantizer replaces each possible observation by its nearest representative, or center. With squared-distance loss, its quality is measured by the expected squared distance from an observation to its nearest center. In one dimension, centers have a natural order and their Voronoi cells are intervals, which makes several population problems exactly solvable.

Definition: Let $X$ be a real-valued random variable with $E[X^2]<\infty$. For a nonempty finite set of centers $C\subset\mathbb{R}$, its squared-distance population risk is $$ R(C)=E\left[\min_{c\in C}(X-c)^2\right]. $$ A population-optimal $k$-center codebook minimizes $R(C)$ over codebooks with at most $k$ centers. The Voronoi cell of a center consists of the points at least as close to it as to any other center; ties may be assigned to either neighboring cell.

For two distinct ordered centers $c_1<c_2$, comparison of squared distances gives $$ (x-c_1)^2\leq (x-c_2)^2 \quad\Longleftrightarrow\quad x\leq \frac{c_1+c_2}{2}. $$ Thus their Voronoi boundary is the midpoint $t=(c_1+c_2)/2$. The cells are the two half-lines separated by $t$, with the boundary assigned by a tie convention. This geometric fact turns a two-center problem into a search over possible one-dimensional splits.

One Center: The Mean and the Variance

With one center $c$, the risk is $E[(X-c)^2]$. The mean is optimal because squared error separates into variance plus squared distance from the mean.

Result: If $E[X^2]<\infty$, the unique optimal one-center codebook is $\{E[X]\}$, and its risk is $\operatorname{Var}(X)$.

To prove this, expand around the mean. Since $E[X-E[X]]=0$, for every $c\in\mathbb{R}$,

\begin{aligned} E[(X-c)^2] &=E\left[\{X-E[X]+E[X]-c\}^2\right]\\ &=\operatorname{Var}(X)+(E[X]-c)^2 +2(E[X]-c)E[X-E[X]]\\ &=\operatorname{Var}(X)+(E[X]-c)^2. \end{aligned}

The second term is nonnegative and equals zero exactly when $c=E[X]$. This proves both optimality and uniqueness.

Worked Example: One Center for a Uniform Distribution

Let $X$ be uniform on $[-2,4]$. Its mean is the midpoint of the interval, $({-2}+4)/2=1$. Its variance is the squared interval length divided by 12:

\operatorname{Var}(X)=\frac{(4-(-2))^2}{12} =\frac{36}{12}=3.

Therefore the optimal one-center codebook is $\{1\}$, and its population risk is 3. The result is not that every point in the interval is equally close to 1; the risk is the average of those squared distances, which is exactly the variance.

Two Centers for a Uniform Distribution

For a uniform distribution on an interval, a two-center solution divides the interval into two equal halves. The following derivation verifies that this split is globally optimal, rather than merely a plausible symmetric choice.

Result: If $X$ is uniform on $[a,b]$, where $a<b$, the optimal two centers are $a+(b-a)/4$ and $a+3(b-a)/4$. The Voronoi boundary is $(a+b)/2$, and the minimum risk is $(b-a)^2/48$.

First consider any distinct centers $c_1<c_2$, with midpoint boundary $t$. If $t\in[a,b]$, their cells cut the interval into $[a,t]$ and $(t,b]$. For any fixed cell, replacing its assigned center by the conditional mean cannot increase that cell's squared error. A uniform distribution on an interval of length $h$ has variance $h^2/12$, so the risk after these center replacements is

\frac{t-a}{b-a}\frac{(t-a)^2}{12} +\frac{b-t}{b-a}\frac{(b-t)^2}{12} =\frac{(t-a)^3+(b-t)^3}{12(b-a)}.

Write $L=b-a$ and $u=(t-a)/L$, so $0\leq u\leq1$. The expression becomes

\frac{L^2}{12}\{u^3+(1-u)^3\} =\frac{L^2}{12}\left\{3\left(u-\frac12\right)^2+\frac14\right\} \geq \frac{L^2}{48}.

If the midpoint lies outside $[a,b]$, all observations are assigned to one center, so the risk is at least the optimal one-center risk $L^2/12$, which is larger than $L^2/48$. The lower bound is attained by splitting at $t=(a+b)/2$ and placing each center at the mean of its half-interval. Those means are $a+L/4$ and $a+3L/4$, and their midpoint is the proposed boundary. This proves the result.

Worked Example: Two Centers for a Uniform Distribution on [0, 1]

For $X$ uniform on $[0,1]$, the optimal centers are $1/4$ and $3/4$. Their midpoint is $1/2$, so the induced cells are $[0,1/2]$ and $(1/2,1]$, using the convention that the tie goes to the left cell.

Each cell has probability $1/2$. Conditional on either cell, $X$ is uniform on an interval of length $1/2$, with variance $(1/2)^2/12=1/48$. The overall risk is therefore

\frac12\cdot\frac{1}{48}+\frac12\cdot\frac{1}{48} =\frac{1}{48}.

This agrees with the general formula for an interval of length 1. Notice that each center is the conditional mean within its own cell; the boundary is halfway between the centers, not at either center.

Discrete Distributions: Enumerating Contiguous Splits

For a distribution with finitely many ordered support points, any two-center Voronoi partition assigns lower support points to the left center and higher support points to the right center. Consequently, candidate nonempty partitions can be enumerated by cutting the ordered list once. For a fixed partition, the best center in each cell is its probability-weighted mean: the one-center calculation applied to the conditional distribution in that cell gives this directly.

Worked Example: Two Centers for Three Equally Likely Atoms

Let $P(X=-2)=P(X=0)=P(X=2)=1/3$. With two centers, the two possible nonempty contiguous splits are after $-2$, or after $0$.

For the split $\{-2\}\mid\{0,2\}$, the cell means are $-2$ and $1$. The singleton contributes zero risk. In the second cell, the points 0 and 2 each have conditional probability $1/2$, so its conditional squared error is

\frac12(0-1)^2+\frac12(2-1)^2=1.

That cell has total probability $2/3$, giving population risk $2/3$. Its centers are $-2$ and $1$, with boundary $(-2+1)/2=-1/2$. The support points in the left cell are $-2$; those in the right cell are 0 and 2.

For the split $\{-2,0\}\mid\{2\}$, the means are $-1$ and 2. The first cell has conditional squared error

\frac12(-2+1)^2+\frac12(0+1)^2=1,

so this split also has population risk $2/3$. Its boundary is $(-1+2)/2=1/2$, and its cells contain $-2,0$ and 2, respectively. Since every two-center partition of these three ordered atoms is one of these two splits (or has an empty cell), both listed codebooks are optimal. An empty cell cannot improve on the best nonempty two-cell split because it uses only one effective center.

A Symmetric Two-Component Distribution

Symmetry can suggest a boundary, but it does not by itself prove that a proposed symmetric codebook is optimal. For a finite symmetric distribution, a complete check is to compare all possible contiguous splits. The next example is an equal mixture of two discrete uniform components, one on each side of zero.

Worked Example: Two Centers for a Symmetric Two-Component Mixture

Let $X$ have probability $1/4$ at each of $-3,-1,1,3$. Equivalently, it is an equal mixture of a uniform distribution on $\{-3,-1\}$ and a uniform distribution on $\{1,3\}$. For the split $\{-3,-1\}\mid\{1,3\}$, the conditional means are $-2$ and $2$. The midpoint boundary is 0, so the induced cells are $x\leq0$ and $x>0$; there is no probability mass at the boundary.

Within each component, the two support points are one unit from their component mean. Thus each component has conditional squared error 1, and the mixture risk is

\frac12\cdot1+\frac12\cdot1=1.

To check optimality, enumerate the other two nonempty contiguous splits. For $\{-3\}\mid\{-1,1,3\}$, the second cell mean is 1. Its three squared deviations are $4,0,4$; weighting each by its original probability $1/4$ gives risk $(4+0+4)/4=2$. By symmetry, the split $\{-3,-1,1\}\mid\{3\}$ also has risk 2. The split into the two component supports, with risk 1, is therefore optimal. The one-center mean is 0 and its risk is $E[X^2]=(9+1+1+9)/4=5$, so using two centers substantially reduces distortion.

Why the Cell Calculation Matters

A reliable way to solve these examples is to separate the geometry from the averaging. For two ordered centers, first determine the midpoint boundary and hence the cells. For a fixed cell, calculate its conditional mean; then weight its conditional squared error by the cell probability. In one dimension, discrete support points make it possible to compare all contiguous splits exactly, while uniform intervals often reduce the calculation to interval lengths and variances.

For any fixed measurable cell $A$ with $P(X\in A)>0$, the same mean calculation gives

E[(X-c)^2\mid X\in A] =\operatorname{Var}(X\mid X\in A) +\{E[X\mid X\in A]-c\}^2.

Thus the conditional mean minimizes squared error within that cell. An optimal codebook must also be compatible with its own nearest-center cells: for every cell of positive probability, its center is that cell's conditional mean. For a two-center codebook, the centers determine the midpoint boundary, while the resulting cells determine the conditional means. Both conditions matter.

Common pitfall: A tempting but incomplete argument is to divide a symmetric distribution at zero and declare the two conditional means optimal because the proposed centers are symmetric. Symmetry alone does not rule out a different, asymmetric split with lower risk. The correction is to verify the candidate's Voronoi boundary and compare the risk against all feasible contiguous splits, as in the discrete mixture example. For a continuous distribution, a proof may instead minimize the risk over possible boundaries, as in the uniform derivation.

Key takeaway: For squared-distance population quantization, a one-center codebook is the mean. With two ordered centers in one dimension, the Voronoi boundary is their midpoint, and each positive-probability cell is represented optimally by its conditional mean. Use these facts together to compute and verify the risk.

Check Your Understanding

For each question, identify both the centers and the induced cells when the information permits.

What condition on $X$ ensures that its one-center squared-distance risk is finite, and what center minimizes that risk?
For a uniform distribution on $[2,6]$, give the optimal two centers, their boundary, and the minimum risk.
Why can the two-center problem for finitely many ordered support points be checked by considering contiguous splits?
For centers $-3$ and $1$, calculate the Voronoi boundary and state which center is nearest to $x=0$.
Why is symmetry by itself insufficient to establish that a proposed two-center codebook is globally optimal?