Motivation
A histogram asks how many observations fall in a region of a prescribed width. A nearest-neighbor estimate reverses the question: how much space is needed to collect a prescribed number of observations? A crowded neighborhood has a small radius and therefore a large estimated density. This construction is useful when a fixed width oversmooths dense regions but leaves sparse regions almost empty. Its apparent simplicity hides several choices: the distance, the volume associated with that distance, the number of neighbors, and the treatment of a boundary.
A density is probability per unit volume. Counting neighbors alone cannot estimate it. If one coordinate is measured in meters and another in millimeters, an ordinary Euclidean ball has changed its physical meaning. Similarly, a ball centered on a boundary can extend into a region where observations cannot occur. Dividing by that unavailable volume introduces a systematic error even with a large sample.
We build the estimators from these observations, prove a narrowly stated consistency result, and calculate an entire small bandwidth comparison. The theorem concerns density at one fixed location. It is not a theorem about nearest-neighbor classification, uniform error over all locations, or high-dimensional recovery. Those questions require their own assumptions and arguments.
Definitions
Definition 24.1.1
(A neighbor radius and its density height)
Let , let , and fix a query . With Euclidean distance, let be the th smallest of . Write for the volume of the unit Euclidean ball; for example, and . When , define
If a known support is used, replace the denominator volume by , obtaining whenever that volume is positive.
This is a local density height estimate. It need not integrate to one over the whole space. For example, in one dimension, to the right of every observation the radius is , so its tail is proportional to and has infinite integral. Pointwise estimation can still make sense, but the raw function is not automatically a normalized probability model for likelihood calculations. A kernel estimate with a normalized kernel has a different global normalization property.
Concept lensAnalytic
A kernel estimate whose bandwidth is the radius
Because no distances tie, exactly observations lie within distance of . Hence
which is a kernel estimate with the uniform ball kernel and a bandwidth that depends on the query and the data. A fixed-bandwidth kernel fixes the width and lets the count vary; the neighbor rule fixes the count and lets the width vary.
For observations from a Lebesgue density, a fixed query almost surely has no zero distance and no distance ties: spheres have Lebesgue measure zero. Repeated rounded measurements can violate that idealization. Specify a tie convention and a measurement model rather than dividing by zero. Replacing Euclidean distance by another norm also requires replacing by that norm's unit-ball volume.
Definition 24.1.2
(A multivariate kernel bandwidth)
For a symmetric positive definite matrix , use the Gaussian kernel
Here is a covariance bandwidth matrix: its eigenvalues are squared smoothing widths. If , the smoothing width is , not . An off-diagonal entry permits smoothing along a rotated ellipse.
A linear change of measurement units must transform the volume too. If with invertible , the corresponding bandwidths satisfy , and densities satisfy . A plot in standardized coordinates has different numerical density heights. Its mass is unchanged only after the Jacobian is included.
Theorem/Proposition
Theorem 24.1.3
(Pointwise nearest-neighbor consistency at a positive continuous density)
Let be fixed and let be independent with a common Lebesgue density on . Fix where is continuous and . For integers with , suppose and . Then
A support version holds at a fixed under the explicit local assumptions for all small positive and
Here the observations are supported on and denotes the stated limiting local density value. Use in this version. It does not require continuity of the zero-extended density across the boundary.
Theorem 24.1.4
(Reflection gives a normalized half-line kernel estimate)
Suppose and is a nonnegative symmetric density on . For and , define
This function is nonnegative and integrates to one on . For uniform observations on and , its expectation at zero equals one for , whereas the ordinary unreflected estimate has expectation there. This exact statement removes the leading boundary error in this particular example; it is not a universal unbiasedness claim.
Theorem 24.1.5
(An integrated-error score with the observation left out)
For a fixed positive definite , independent observations from a density , and , set
Then . Moreover,
Thus a declared finite grid of matrices can be compared by a fully computable score. The unbiased identity is for each fixed matrix; it does not make the minimum selected score an unbiased estimate of the selected procedure's risk.
Proof sketch or proof idea
Proof
(First control probability mass, then convert mass into volume)
Write . This is a continuous distance distribution. By the probability integral transform, are independent uniform variables on , and almost surely. The density of is
To obtain it, select which uniforms lie below a small interval at , which one lies in it, and which lie above, then divide by the interval width. Integrating this beta density gives
For , the mean of tends to one and its variance is at most . Chebyshev's inequality gives in probability. Also in probability because . Local positive density gives for every fixed : first for sufficiently small radii, then for all larger radii by monotonicity. The event implies , so in probability.
Continuity of at gives
Consequently
The support proof uses exactly the assumed local-average limit with instead of . That limit also ensures for small . The probability-mass calculation is unchanged. No mean-square rate or uniform convergence statement has been proved.
Proof X-ray
The two neighbor conditions do different jobs
The condition forces the neighborhood to shrink, so a local average approaches the density at the query. The condition stabilizes its random probability mass relative to . A neighborhood can shrink while containing too few points to give a stable density height. The fixed-one-neighbor counterexample in Common mistakes below isolates that failure.
Proof
(Reflection and the integrated score)
For each nonnegative observation, substituting into the two reflected terms gives their total integral
by symmetry. Averaging proves normalization. At zero the box-kernel summand doubles the ordinary one. The chance that a uniform observation lies within of zero is , giving expectations and respectively.
For the score, is independent of the estimate formed without it. Therefore
The estimates with and observations have the same expectation. Expanding the integrated square error proves the expectation identity. Finally, completing the square in the product of two Gaussian kernels gives ; summing gives the computable formula. For fixed the Gaussian kernels are bounded and integrable, so the required integrals and expectations are finite under .
Worked examples
Worked example 24.1.6
(Five observations and an actual boundary correction)
Take observations . At their distances are . For , the radius is and the height is . For , the radius is and the height is two. Both are calculations from the same sample; the larger height is not evidence that the smaller neighborhood is more accurate.
Suppose the support is known to be and query zero with . The radius is . The uncorrected height is , but only the interval is available, so the support-corrected height is . The factor of two repairs the unavailable half-ball at this boundary. It does not make a finite random estimate equal to the true uniform density one.
For a different estimator, use the same observations with the reflected box kernel and . Exactly two observations lie within of zero. The ordinary KDE height is and the reflected height is one. The entire reflected function is normalized on the half-line; simply doubling an ordinary KDE everywhere would instead double its whole-line mass.
Worked example 24.1.7
(A square sample and two complete matrix-bandwidth scores)
Use the four points and . At all four Gaussian contributions agree, so
For , this is . For , it is . The determinant reduces the height while the larger second-coordinate width changes the exponent. Omitting either effect would be wrong.
In the integrated square there are four self-pairs, four ordered horizontal pairs, four ordered vertical pairs and four ordered diagonal pairs. At each held-out point the other three consist of one horizontal, one vertical and one diagonal neighbor. Hence
This gives and . Among these two prespecified candidates, the second wins. A negative score is allowed because an unknown constant has been subtracted in expectation. Four points do not establish that this bandwidth is optimal in the population. The rotated choice ties here because the sample is symmetric under exchanging coordinates.
Worked example 24.1.8
(Change the units without changing the estimated mass)
Suppose has bandwidth and measured coordinates are with . Then . Since , density heights at corresponding points agree, although circular smoothing regions become ellipses. If instead , then and heights are divided by 1000. Their numerical reduction records a larger coordinate volume, not a loss of probability.
Common mistakes
Counterexample mode
One nearest neighbor can stay noisy forever
It is tempting to believe that one nearest neighbor is enough, because the radius shrinks as grows. It is not. Let observations be uniform on , query , and keep . For fixed and large enough that ,
Indeed the estimate exceeds precisely when at least one observation is within radius . At , the limiting probability is , although the true density is one. Thus the estimate does not converge in probability to one. Shrinking radii alone cannot replace the condition .
A density height divides a count by sample size and physical volume. A -neighbor classifier instead compares label frequencies among the selected neighbors; its estimated posterior for label is . There is no ball-volume divisor in that posterior. Our density theorem neither proves classification consistency nor proves that density-based plug-in decisions retain an optimal risk. Even when a neighborhood rule uses conditions resembling and , the target and proof must be identified separately.
Common mistake
(Self-counting and data-chosen bandwidths)
Replacing by inserts the self-kernel , which grows as the bandwidth shrinks and can reward overconcentration. The leave-out divisor is . A bandwidth or scaling matrix chosen from the same observations is random, so the fixed- expectation proof cannot be reused by merely calling the realized matrix fixed.
Common mistake
(Validation leakage)
For a fitted procedure, declare a candidate family and scoring rule, reserve independent outer evaluation data, and fit all means, scales, support estimates and bandwidth choices inside the development data. If a validation scheme learns scales, recompute them in each training fold and apply those saved scales to its validation fold. Refit the selected pipeline on all development data and inspect the untouched test data once. Known physical support may be fixed in advance; a support inferred from all observed extremes has used the validation observations. The exact score above is a transparent fixed-bandwidth comparison, not a complete post-selection uncertainty analysis.
Summary
Neighbor density construction estimates a small probability mass and divides by the matching available volume. Its pointwise consistency proof uses both increasing neighbor counts and shrinking mass fractions. Reflection supplies a normalized half-line kernel construction, while matrix bandwidths describe multivariate smoothing in meaningful measurement units. A leave-out integrated-error score is computable without pretending its selected minimum is an independent risk estimate.
Exercises
Quick check
(For the five observations above, query one with k equal to two and known support [0,1]. Calculate the ordinary and support-corrected neighbor heights.)
Find the second closest observation and the available interval length.
Solution · Answer
Distances from one are . The second radius is . The ordinary height is ; the support-intersection interval is of length , so the corrected height is two. Boundary correction accounts for available volume, not sampling variability.
Quick check
(For uniform observations on [0,1], query zero and fixed k greater than one. Find the exact expectation of the support-corrected height k/(n R), and explain what happens for k equal to one.)
The radius is the kth order statistic of n independent uniforms. Integrate its beta density after dividing by its argument.
Solution · Answer
The radius has beta density . For , the beta integral gives , and hence . The finite-sample estimator has upward mean bias even after the boundary volume is corrected. For the integral contains near zero and diverges. In particular, convergence in probability is not a license to assert convergence of expectations. The stated consistency theorem deliberately makes no such claim.
Quick check
(Derive the self-counting contribution when the integrated-error score uses the full estimate at each observation instead of a leave-out estimate. Why is this a dangerous change as every bandwidth width tends to zero?)
Write each full estimate as a self-term plus (n−1)/n times its leave-out estimate.
Solution · Answer
Let . Then . The incorrect score minus the correct score is . In particular, the extra negative self-term diverges as . With distinct fixed observations and , the off-diagonal kernels tend to zero, while the integrated-square diagonal is . The incorrect score then behaves as , rewarding arbitrarily narrow spikes.
Quick check
(A two-dimensional density was estimated in coordinates with bandwidth . Coordinates are changed to . Find the new bandwidth and the density-height multiplier. State whether the pointwise neighbor theorem proves classification consistency.)
Transform the covariance bandwidth and the volume separately.
Solution · Answer
The new matrix is . Density heights are multiplied by . Matching region volumes are multiplied by six, so the represented probability mass is preserved. The theorem proves density consistency at one fixed point under its stated density assumptions. No classification consistency conclusion was derived.