Why Merge Heights Need Their Own Error Bound
A density cluster tree records how connected components of high-density regions join as the level decreases. The merge height of two points describes the level at which they first belong to the same component. An estimated density can move that level even when its overall error is small, so a useful guarantee should quantify the movement directly.
The key fact is that a uniform density error of at most \(\varepsilon\) shifts every merge height by at most \(\varepsilon\). That is an additive guarantee, not a guarantee that the estimated tree has exactly the same components at every level. To preserve the ordering of distinct branch merges as well, their population merge heights must be separated by a sufficiently large gap.
Merge Height and Uniform Density Error
Let \(X\) be a topological space, and let \(f:X\to[0,\infty)\) be a density. For a level \(\lambda\geq 0\), define the upper level set \(L_f(\lambda)=\{x\in X:f(x)\geq\lambda\}\). Its connected components are the clusters at that level. For \(x,y\in X\), define their merge height as the supremum of levels at which they belong to the same connected component.
The argument below uses only the inclusions between level sets implied by uniform error. If \(\|\hat f-f\|_\infty\leq\varepsilon\), then, for every \(\lambda\geq\varepsilon\),
Indeed, \(f(x)\geq\lambda+\varepsilon\) implies \(\hat f(x)\geq\lambda\), while \(\hat f(x)\geq\lambda\) implies \(f(x)\geq\lambda-\varepsilon\). A connected subset of a level set is contained in one of its connected components. This lets the inclusions control whether two points can have merged.
Proof. First suppose \(m_f(x,y)>\varepsilon\). Choose any \(q\) with \(0\leq q<m_f(x,y)-\varepsilon\). By the definition of a supremum, there is a level \(t>q+\varepsilon\) at which \(x,y\) belong to the same connected component of \(L_f(t)\). That component is a connected subset of \(L_f(t)\), and the uniform error bound gives \(L_f(t)\subseteq L_{\hat f}(t-\varepsilon)\). Thus \(x,y\) belong to the same component of \(L_{\hat f}(t-\varepsilon)\), so \(m_{\hat f}(x,y)\geq t-\varepsilon>q\). Since this holds for every such \(q\), \(m_{\hat f}(x,y)\geq m_f(x,y)-\varepsilon\). If \(m_f(x,y)\leq\varepsilon\), the same lower bound follows from \(m_{\hat f}(x,y)\geq0\).
For the other direction, suppose \(m_{\hat f}(x,y)>m_f(x,y)+\varepsilon\). By the supremum definition, some \(\lambda>m_f(x,y)+\varepsilon\) has \(x,y\) in the same component of \(L_{\hat f}(\lambda)\). This connected component lies in \(L_f(\lambda-\varepsilon)\), because \(\hat f\leq f+\varepsilon\). Consequently \(x,y\) belong to the same component of \(L_f(\lambda-\varepsilon)\), which implies \(m_f(x,y)\geq\lambda-\varepsilon>m_f(x,y)\), a contradiction. Therefore \(m_{\hat f}(x,y)\leq m_f(x,y)+\varepsilon\), proving the result. \(\square\)
Worked Example: A Two-Peak Density and Its Merge Level
On \(X=[0,1]\), let \(g\) be the piecewise-linear function with knot values \(g(0)=0\), \(g(0.25)=2\), \(g(0.5)=0.5\), \(g(0.75)=2\), and \(g(1)=0\). The trapezoid areas on the four equal intervals are \(0.25\), \(0.3125\), \(0.3125\), and \(0.25\). Their sum is \(1.125=9/8\), so \(f=(8/9)g\) is a density. Its two peaks are at \(0.25\) and \(0.75\), and the intervening valley has height \(f(0.5)=4/9\). In one dimension, the two peak points are connected in a superlevel set exactly when the whole interval between them is included. Thus their merge height is \(m_f(0.25,0.75)=4/9\).
Now define \(\hat f\) by linear interpolation through the same knots except that the changes to the normalized knot values at \(0,0.25,0.5,0.75,1\) are, respectively, \(0,-0.015,0.03,-0.015,0\). The trapezoid integral of this change is \[ 0.25\{(-0.015)+0.03+(-0.015)\}=0, \] so \(\hat f\) still integrates to one. It remains nonnegative, and the largest absolute change is \(0.03\). Its valley is \(4/9+0.03\), while both peak heights remain greater than the valley. The estimated merge height is therefore \(4/9+0.03\), and the actual merge distortion is \(0.03\), equal to the uniform error bound in this example.
Separated Merge Heights Preserve Their Ordering
A merge-distortion bound also gives a simple way to assess whether the relative heights of several specified branches are stable. Fix a finite collection of anchor pairs \((a_j,b_j)\), and write \(m_j=m_f(a_j,b_j)\) for their population merge heights. These pairs act as fixed witnesses for the merges of interest; the result does not itself identify estimated components or match branches without such anchors.
Proof. The first claim follows by applying the merge-height theorem to each anchor pair. Consider two pairs with \(m_j>m_k\). The separation condition gives \(m_j-m_k\geq\Delta>2\varepsilon\). Hence \[ m_{\hat f}(a_j,b_j)\geq m_j-\varepsilon >m_k+\varepsilon\geq m_{\hat f}(a_k,b_k). \] Thus their estimated ordering is unchanged. The argument applies to every pair of anchor pairs, so their full strict ordering is preserved. \(\square\)
The same calculation shows why the threshold \(2\varepsilon\) appears: each of two merge heights can move in the direction that reduces their gap by as much as \(\varepsilon\). A positive gap smaller than or equal to \(2\varepsilon\) may be obscured by those two errors.
Worked Example: Two Branch Merges with a Verified Gap
Consider the piecewise-linear profile on \([0,6]\) with values at integer knots \(0,1,\ldots,6\) equal to \(0,2,0.8,1.6,0.5,1.2,0\), and normalize it to have integral one. The six trapezoid areas are \(1,1.4,1.2,1.05,0.85,0.6\), whose sum is \(6.1=61/10\). Thus the normalized density is the profile divided by \(6.1\).
Take the anchor pair at the peaks \(x=1\) and \(x=3\). The minimum profile value between them is \(0.8\), so their merge height is \(0.8/6.1=8/61\). For the peaks at \(x=3\) and \(x=5\), the minimum between them is \(0.5\), giving merge height \(0.5/6.1=5/61\). Their gap is \(3/61\), approximately \(0.04918\).
Suppose an estimated density has uniform error at most \(\varepsilon=0.015\). Since \(2\varepsilon=0.03<3/61\), the ordering is preserved. More explicitly, the first estimated height is at least \(8/61-0.015\approx0.11615\), while the second is at most \(5/61+0.015\approx0.09697\). The first merge therefore remains higher than the second.
From Density Rates to Merge-Distortion Rates
The deterministic theorem transfers any valid uniform density-estimation guarantee directly to the merge heights. In particular, if a sequence of estimates satisfies \(\|\hat f_n-f\|_\infty=O_p(r_n)\), then the largest merge-height error over all point pairs is \(O_p(r_n)\). A high-probability version follows by applying the deterministic bound on the event where the density error is small.
Indeed, on the event \(\|\hat f_n-f\|_\infty\leq r_n\), the theorem bounds the error for every pair \(x,y\) by the same \(r_n\). The event involving the supremum therefore contains the density-error event, which proves the probability inequality.
Worked Example: Converting a Uniform Estimation Rate
Suppose a two-dimensional density is sufficiently smooth for a kernel estimator to satisfy, with probability at least \(0.95\), \[ \|\hat f_n-f\|_\infty\leq C_1\sqrt{\frac{\log n}{nh^2}}+C_2h^2, \] where \(C_1+C_2=2\), and take \(h=(\log n/n)^{1/6}\). Substitution gives \[ \sqrt{\frac{\log n}{n(\log n/n)^{1/3}}} =\sqrt{(\log n/n)^{2/3}} =(\log n/n)^{1/3}, \qquad h^2=(\log n/n)^{1/3}. \] Therefore the density error is at most \(2(\log n/n)^{1/3}\) on the stated event, and the same bound holds for every merge-height error.
For \(n=1{,}000{,}000\), \((\log n/n)^{1/3}\approx0.0240\), so the bound is approximately \(0.0480\). If two anchor-pair merge heights have a population gap of \(0.10\), then twice this error bound is approximately \(0.0960<0.10\). On the event of probability at least \(0.95\), their ordering is preserved. The conclusion uses the stated uniform error guarantee; the rate formula alone does not supply its constants or probability without the estimator’s regularity assumptions.
What the Guarantee Does—and Does Not—Say
Merge distortion is useful because it measures a central feature of a cluster tree in the same units as the density. It gives an immediate way to translate estimator accuracy into uncertainty in merge levels, and a branch-height gap larger than twice the error bound makes the corresponding ordering robust.
A common mistake is to treat a small uniform density error as proof that every estimated level set has exactly the same connected components as the population level set. The theorem proves a bound on merge heights, not exact component recovery at every threshold. Near a merge level, even a small vertical shift can change which level-set components are joined. Conversely, if two merge heights are closer than or equal to twice the error bound, the bound does not certify their ordering; it does not prove that the ordering must change.
There is also an important distinction between density error and merge-height error: no extra factor of two is needed for an individual pair’s merge height. The factor \(2\) arises only when comparing two estimated merge heights, because both can move toward one another. To obtain a valid ordering claim, state the population gap and check that it exceeds \(2\varepsilon\).
Check Your Understanding
Use the definitions and bounds above to answer these questions.
- If \(\|\hat f-f\|_\infty\leq0.02\), what is the largest merge-height error the theorem permits for any fixed pair of points?
- Two anchor pairs have population merge heights \(0.60\) and \(0.55\). Does a uniform error bound of \(0.02\) certify their ordering? Show the gap comparison.
- Why does a connected component of \(L_{\hat f}(\lambda)\) lie inside \(L_f(\lambda-\varepsilon)\) when the uniform error is at most \(\varepsilon\)?
- If a density estimator has a uniform error bound \(r_n\) with probability at least \(1-\alpha_n\), what probability guarantee follows for the supremum of merge-height errors?
- Does a merge-distortion bound alone guarantee identical component counts at every level? Explain the distinction.