On the Rates of Convergence of Induced Ordered Statistics and their Applications

On the Rates of Convergence of Induced Ordered Statistics and their Applications

KEYWORDS: total variation distance, Hellinger distance, induced order statistics, rank tests, permutation tests.

JEL classification codes: C12, C14.

\thispagestyle{empty}

Introduction

Induced order statistics arise when units in a sample are reordered according to the value of an auxiliary variable, and one then studies the associated responses in that induced order. Classical work on induced order statistics (IOS) has developed their basic probabilistic properties, limit distributions, and representations in terms of mixtures and conditional laws; see, for instance, david/galambos:74,bhattacharya:74,reiss:89,kaufmann/reiss:92 and the book-level treatment by falk/husler/reiss:2010. More recently, IOS have proved useful in a number of econometric and statistical applications in which one wishes to approximate the conditional distribution of an outcome given a covariate taking a specific value. A prominent example is the regression discontinuity design, where identifying assumptions are formulated in terms of the distribution of potential outcomes at a cutoff and IOS provide a natural way to approximate this distribution using observations whose running variable lies closest to the cutoff; see, for example, canay/kamat:18,goldman/kaplan:2018,bugni/canay:21,bugni2023permutation,bugni/canay/kim:2025. Similar constructions appear in $k$-nearest-neighbor methods, distributionally robust optimization, and related problems where analysis focuses on the subsample formed by observations closest to a point of interest; see, for example, esteban/morales:22.

In the vast majority of these applications, the dimension of the IOS vector is kept fixed in the asymptotic approximations. Existing results that allow the dimension to grow with the sample size rely on smoothness assumptions that are often too restrictive for the underlying data-generating process. This raises the question of whether one can obtain general convergence results for IOS under primitive and comparatively weak conditions, in a form that can serve as a reusable toolkit for analyzing tests and estimators based on $k$ nearest neighbors as $k$ grows with the sample size.

The present paper answers this question. We derive convergence rates in the Hellinger and total variation distances for the joint law of the IOS, and we trace how these rates depend on the smoothness of the underlying model. Our main results are widely applicable: they rely on quadratic mean differentiability (QMD) of the conditional densities at the conditioning point, a standard condition in asymptotic statistics, and accommodate both interior and boundary conditioning points---as required in regression discontinuity designs and related settings. Under this condition, we obtain sharp marginal rates for approximating the target conditional distribution and show how these translate into joint convergence rates for the IOS vector, with explicit growth conditions on $k$. In the supplementary appendix, we provide complementary results under a Taylor/H\"older remainder condition, which yield a wider range of marginal exponents and clarify how rates slow down or fail as smoothness weakens.

Formally, we consider a pair of random vectors $(X,Y)$ taking values in $\mathbf R^d\times\mathbf R^m$, with joint density $f$. The conditional law of $Y$ given $X=x_0$ is denoted by $P$, while for small $r>0$ the conditional law of $Y$ given $X\in B_r:=\{x:\|x-x_0\|<r\}$ is denoted by $P_r$. Given an i.i.d.\ sample $\{(X_i,Y_i):1\le i\le n\}$, we use Euclidean distance to $x_0$ to identify the set of the $k$ nearest observations and collect the associated responses into the vector, with components listed in original sample order, \[ S_n := (S_{n,1},\dots,S_{n,k})~. \] The ideal benchmark experiment for many applications would be an i.i.d.\ sample of size $k$ from $P$, say $S=(\tilde Y_1,\dots,\tilde Y_k)$ with $\tilde Y_1,\dots,\tilde Y_k$ i.i.d.\ with law $P$. Our primary object of interest is the discrepancy between the laws $\mathcal L(S_n)$ and $\mathcal L(S)$ as a function of $n$ and $k$, measured in Hellinger distance $\mathrm{H}(\cdot)$ and total variation distance $\mathrm{TV}(\cdot)$. These metrics control the error of tests and estimators based on $S_n$ relative to their infeasible counterparts based on $S$ via classical variational characterizations, so their rates directly translate into size and risk bounds for procedures built from induced order statistics.

The paper makes three main contributions. First, we provide general high-level results that map marginal approximation rates for the conditional law $P_r$ to joint convergence rates for the IOS vector $S_n$. Specifically, under a mild Lipschitz condition on the density of $X$, we show how bounds on the marginal rates of the form

translate directly into joint convergence rates for the IOS vector $S_n$ of the form

as $n\to\infty$ and $k=k_n$ grows with $n$. By separating the analysis into (i) a high-level result linking marginal and joint rates and (ii) primitive conditions that determine the marginal exponents $(a_h,a_{tv})$, our approach isolates precisely when and how smoothness assumptions affect the behavior of IOS. In addition, the framework treats Hellinger and total variation distances on equal footing, allowing their distinct behaviors to be characterized transparently and under comparable assumptions.

Second, we develop primitive conditions that deliver the required marginal rates under QMD of the conditional densities at $x_0$, which is a standard condition that accommodates both interior and boundary points. The supplementary appendix provides a complementary smoothness framework based on differentiability of $f$ in $x$ with a H\"older remainder, which delivers a wider range of marginal exponents $(a_h,a_{tv})$ and clarifies how rates slow down as smoothness weakens. A key distinction is that the joint Hellinger rate depends solely on the marginal exponent $a_h$, whereas the joint total variation rate is shaped by both $a_h$ and $a_{tv}$ through the minimum in (ref). Under H\"older smoothness, $a_{tv}=2a_h$, so total variation decays faster than Hellinger and this improvement carries over to the joint rates. Yet both metrics impose the same growth condition on $k$, so the faster total variation rate does not relax the admissible order of $k$.

Third, we formally compare our assumptions with those of falk/husler/reiss:2010 (FHR), which is a benchmark result in this setting. We identify the features of that condition that generate the unusually fast rate $\mathrm{H}(P_r,P)=O(r^2)$, and we show that these features impose strong structure on the joint density, including local exponential–family behavior and stringent restrictions on how the support of $Y$ may vary with $X$. In contrast, our assumptions allow for substantially more flexible data-generating processes, including boundary points and other non-smooth features that are ruled out by the FHR conditions.

The end result is a unified set of conditions and rates that can serve as a toolkit for analyzing tests and estimators based on induced order statistics across a broad range of applications. We illustrate the relevance of our results through several examples. First, we revisit permutation–based inference in the regression discontinuity design of canay/kamat:18 and show how our theory yields new asymptotic results for that framework. Existing large-sample approximations treat the dimension of $S_n$ as fixed, and commonly used heuristics for selecting $k$ rely on rate calculations that are not consistent with the findings established here. Our analysis provides formally valid growth conditions on $k$, clarifies how smoothness assumptions shape the behavior of IOS--based procedures, and offers guidance for constructing data-dependent rules for choosing $k$ in practice. We then discuss applications to $k$-nearest-neighbor estimators and to distributionally robust optimization. In particular, the recent work of esteban/morales:22 on distributionally robust optimization relies on the regularity conditions of falk/husler/reiss:2010 to control the discrepancy between empirical and true conditional laws, providing another example in which the tools developed here can be used to relax smoothness requirements and refine asymptotic guarantees. Across these settings, our results provide a unified framework for deriving asymptotic properties of IOS--based methods under transparent and verifiable smoothness conditions.

The remainder of the paper is organized as follows. Section (ref) introduces the main notation and revisits the existing result of falk/husler/reiss:2010. Section (ref) presents the main formal results. Section (ref) covers the quadratic–mean differentiability setting, while the Taylor/H\"older–type smoothness framework is developed in the supplementary appendix (see Appendix (ref)). Section (ref) illustrates how our results apply to several econometric and statistical problems, with a focus on the properties of permutation-based tests in the regression discontinuity design. Section (ref) examines the interplay between these assumptions, explaining why the conditions of falk/husler/reiss:2010 yield faster convergence relative to the ones we present here. The proofs of the main theorems appear in Appendix (ref). Finally, the supplementary appendix collects auxiliary lemmas, technical proofs, and additional examples. To keep the main text uncluttered, all results in the supplement are numbered with an “S.” prefix (e.g., Lemma S.1, Theorem S.2).

Setup and Notation

Let $X\in\mathcal X \subseteq \mathbf{R}^d$ and $Y\in\mathcal Y \subseteq \mathbf{R}^m$, and let $Q$ denote the distribution of $(X,Y)$, assumed to belong to a model class $\mathbf{Q}$. Assume $Q$ is dominated by the product measure $d\mu := dx\otimes \nu(dy)$, where $dx$ is Lebesgue measure on $\mathbf{R}^d$ and $\nu$ is an arbitrary fixed $\sigma$-finite measure on $\mathbf{R}^m$. We denote the joint density with respect to $d\mu$ by $f(x,y)$ and the marginal density of $X$ by \[ g(x):=\int f(x,y)\,\nu(dy)~. \] We denote the conditional distribution of $Y$ given $X=x_0$ by $P$, assumed to belong to a model class $\mathbf P$ induced by $\mathbf Q$. For any $x\in\mathbf{R}^d$ with $g(x)>0$, we denote the density of the conditional distribution of $Y$ given $X=x$ by \[ p_x(y) := \frac{f(x,y)}{g(x)}~. \] This setup allows $Y$ to be continuous, discrete, or mixed, while requiring that $X$ admits a Lebesgue density.

Fix $x_0\in\mathcal{X}$ and let $r>0$ be given. We denote the Euclidean distance of $X$ from $x_0$ by

and the open ball of radius $r$ with center $x_0$ by \[ B_{r}:=\{x\in \mathbf R^d:\|x-x_0\|< r\}~. \] We denote by $P_{r}$ the distribution that determines the local conditional distributions of $Y$ conditional on the event $X\in B_r$ and let \[ h_r(y) := \frac{\int_{B_r} f(x,y)\,dx}{\int_{B_r} g(x)\,dx}~. \] Under the smoothness conditions introduced in the next section, it follows that $h_r(y)$ approximates $p_{x_0}(y)$ as $r\to 0$. For notational simplicity, the dependence of $B_{r}$ and $h_r(y)$ on $x_0$ is kept implicit, since the center $x_0$ remains fixed throughout the paper.

We observe an i.i.d.\ sample of size $n$ from $Q\in\mathbf Q$ and denote it by

We also denote the order statistics of $\{R_i:1\le i\le n\}$ in (ref) by $R_{(1)}\le \cdots\le R_{(n)}$. Note that by our assumptions on $\mathbf Q$, ties occur with probability $0$. Define the (random) permutation $\sigma_n$ of $\{1,\ldots,n\}$ by \[ \sigma_n(i)=j\quad\Longleftrightarrow\quad R_i=R_{(j)}~, \qquad i,j=1,\ldots,n~, \] so that $\sigma_n(i)$ is the rank of observation $i$. The index set of the $k$ observations closest to $x_0$ is \[ K_n:=\{\,i\in\{1,\ldots,n\}:\ \sigma_n(i)\le k\,\}~. \] Let $\iota_n$ be the increasing rearrangement of $K_n$ (i.e., $\iota_n(1)<\cdots<\iota_n(k)$ and $\{\iota_n(1),\ldots,\iota_n(k)\}=K_n$). Finally, for $j=1,\ldots,k$, let $Y_{\iota_n(j)}$ be the response attached to the observation whose distance from $x_0$ ranks among the $k$ smallest, with the indices $\iota_n(1)<\cdots<\iota_n(k)$ listed in the original sample order. In this paper, these are our induced order statistics, listed in original sample order (equivalently, a permutation of distance-ordered concomitants) (see, e.g., david/galambos:74,bhattacharya:74,canay/kamat:18).

Collect these induced order statistics into

By definition, $S_n$ is a $k$-tuple of outcomes of $Y$ corresponding to those $X$’s that fall closest to $x_0$. Example (ref) below provides an illustrative example. Under suitable smoothness conditions, one could use this sample to approximate the distribution of $Y$ given $X=x_0$, which we previously denoted by $P$. This is important because many hypotheses and parameters of interest are formulated in terms of $P$. For these problems, the “ideal” random sample would be

In such settings, $S_n$ can serve as an “approximation” of $S$. Section (ref) gives detailed examples.

For hypothesis testing, let $\phi:\mathbf R^k\to[0,1]$ be a measurable test functional. Working with the infeasible test $\phi(S)$ would be ideal, but in practice, we resort to $\phi(S_n)$ instead. Since $\phi\le 1$, the variational characterization of total variation implies

where $\mathcal L(\cdot)$ denotes the law of a random vector and $\mathrm{TV}$ denotes the total variation distance. Moreover, the standard comparison between total variation and the Hellinger distance $\mathrm{H}$ yields

Thus, any rate for either distance immediately delivers a rate for the size error in (ref).

For estimation, consider an IOS--based estimator $\psi(S_n)$ of a scalar parameter $\theta(P)$, where $\theta(P)$ is defined as a bounded functional of the conditional law $P$. Examples include the conditional CDF or the conditional mean under $\|Y\|\le B$ for some constant $B$. Then \[ E_Q \big[(\psi(S_n)-\theta(P))^2\big] \le 2 E\big[(\psi(\tilde S_n)-\psi(\tilde S))^2\big] + 2 E_P \big[(\psi(S)-\theta(P))^2\big]~, \] where the expectation in the first term is taken with respect to any joint distribution of $(\tilde S_n,\tilde S)$ whose marginals satisfy $\tilde S_n\sim\mathcal L(S_n)$ and $\tilde S\sim\mathcal L(S)$. The second term is the standard $k$--sample risk of the infeasible estimator $\psi(S)$ based on $k$ i.i.d.\ draws from $P$, and is typically of order $O(1/k)$ for sample means or CDF estimators under mild moment conditions. Under the assumption that $|\psi|\le B$, a maximal coupling yields

Thus, any convergence rate for $\mathrm{H}(\mathcal{L}(S_n),\mathcal{L}(S))$ or $\mathrm{TV}(\mathcal{L}(S_n),\mathcal{L}(S))$ yields an immediate, uniform bound on the mean squared error of $\psi(S_n)$.

Taken together, these two applications demonstrate that the convergence rates developed in this paper provide generic control over the performance of IOS--based procedures, whether for hypothesis testing or estimation. The monograph falk/husler/reiss:2010 provides an influential benchmark for the convergence of induced order statistics in Hellinger distance, obtained under a relatively strong smoothness condition tailored to their framework. Before presenting our results, we briefly summarize the key result in falk/husler/reiss:2010 and its main assumption.

Existing results

falk/husler/reiss:2010 provide an approximation result for $S_n$ by deriving a rate of convergence for $\mathrm{H}\big(\mathcal L(S_n),\mathcal L(S)\big)$. The intuition of this result goes as follows. Since $R$ has a continuous CDF, it follows from kaufmann/reiss:92 that, conditional on $R_{(k+1)}=r$, the vector $S_n$ consists of $k$ i.i.d.\ draws from $P_{r}$: \[ \mathcal L\big(S_n\,\big|\,R_{(k+1)}=r\big) = P_{r}^{k}~. \] For small $r>0$, $P_{r}$ approximates the target conditional law $P$, so unconditionally we expect

In words: the $Y$–values attached to the $k$ nearest $X$–neighbors of $x_0$ behave approximately like $k$ independent draws from $P$. In falk/husler/reiss:2010, a formal proof of this approximation is given under the assumption stated below. For completeness, we reproduce their theorem after the assumption.

Theorem (ref) implies that any procedure based on $S_n$ behaves asymptotically like the corresponding one based on the i.i.d.\ vector $S=(S_1,\ldots,S_k)$ in (ref) with common law $P$. While powerful, this result rests critically on Assumption (ref). That assumption imposes substantive restrictions on the joint density $f(x,y)$ and is often too strong for the applications we study. First, it rules out boundary points: the uniform expansion (ref) must hold for all $t$ in a full neighborhood of the origin, so $x_0$ is necessarily in the interior of $\mathcal X$. Regression discontinuity designs, however, condition on a known cutoff of the running variable and perform local analysis separately on observations just below and just above that cutoff, so that $x_0$ is a boundary point of the support of the running variable in each subsample; see Section (ref) for more details. Second, Assumption (ref) forces the local behavior of $f(x,y)$ in $x$ to take an exponential tilt form in $y$, so that the model is locally indistinguishable from an exponential family; see Section (ref). Third, it requires that the zero-density set $\{y:f(x_0,y)=0\}$ remain exactly invariant under local perturbations of $x$, which excludes many models in which the conditional support of $Y$ varies with $X$. Finally, Theorem (ref) yields a rate for $\mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big)$ only indirectly via (ref), and the resulting bound may not be sharp for total variation. These considerations motivate the next section, where we develop convergence rates for both $\mathrm{H}\big(\mathcal L(S_n),\mathcal L(S)\big)$ and $\mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big)$ under weaker primitive conditions that accommodate both interior and boundary points. In the Supplemental Appendix, we also make explicit the trade--off between smoothness and speed of convergence, including regimes in which the rate deteriorates and thresholds beyond which convergence fails.

Rates of Convergence of Induced Ordered Statistics

In this section, we study new, weaker conditions under which the laws of the induced order statistics converge to the “ideal” limit experiment. Our rates for $\mathrm{H}\big(\mathcal L(S_n),\mathcal L(S)\big)$ and $\mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big)$ hinge on the marginal approximation errors $\mathrm{H}(P_r,P)$ and $\mathrm{TV}(P_r,P)$, where $P_r$ is the conditional law of $Y$ given $X\in B_r$ and $P$ is the conditional law of $Y$ given $X=x_0$. Importantly, we allow $x_0$ to be either an interior point or a boundary point of $\mathcal X$. Throughout the paper, we say that $x_0$ is an interior point of $\mathcal X$ if there exists $\tilde r>0$ such that $B_r\subset\mathcal X$ for all $r\in(0,\tilde r]$, and we say that $x_0$ is a boundary point of $\mathcal X$ otherwise. This distinction is required for accommodating applications in regression discontinuity designs.

Our analysis proceeds in two steps. We begin with a high-level result that translates bounds on the marginal rate of convergence of $P_r$ to $P$, together with a mild continuity condition on the density $g$ of $X$, into bounds on the joint rate of convergence of $\mathcal L(S_n)$ to $\mathcal L(S)$. We then develop primitive conditions that deliver the required marginal rates under quadratic mean differentiability (QMD) of the conditional laws at $x_0$ (see Section (ref)). A complementary smoothness framework based on Taylor/H\"older-type differentiability with explicit remainder control is deferred to the Supplemental Appendix (see Section (ref) therein). This separation clarifies the key ways in which our assumptions differ from, and weaken, the original condition of falk/husler/reiss:2010.

We begin with a mild regularity condition on the marginal density $g$ at $x_0$.

Continuity of the distribution of $X$ together with positivity $g(x_0)>0$ are standard primitives in the induced order statistics literature; see, for example, reiss:89, kaufmann/reiss:92, and falk/husler/reiss:2010. We strengthen these conditions slightly by imposing local Lipschitz regularity of $g$ at $x_0$ and a local thickness condition on $B_r\cap\mathcal X$, a formulation that remains compatible with $x_0$ being a boundary point.

Although Assumption (ref) may appear unusual at first glance, it is quite mild once one distinguishes between interior and boundary points. If $x_0$ is an interior point of $\mathcal X$, then for all sufficiently small $r$ we have $B_r\subset\mathcal X$, hence $\mathrm{Vol}(B_r \cap \mathcal X)=\mathrm{Vol}(B_r)$ is of order $r^d$, so condition (ii) holds automatically. In this case, Assumption (ref) reduces to condition (i), which imposes local Lipschitz regularity of $g$ at $x_0$. If $x_0$ is a boundary point of $\mathcal X$, condition (ii) simply requires that $\mathcal X$ occupy a nonvanishing fraction of each small ball centered at $x_0$, a property that holds, for example, when $\mathcal X$ has a Lipschitz boundary near $x_0$. Condition (i) remains a one-sided Lipschitz condition on $g$ at $x_0$. As mentioned earlier, allowing for such boundary points is essential for regression discontinuity design applications.

Finally, as discussed in Section (ref), Assumption (ref) implies Assumption (ref) with $x_0$ necessarily being an interior point in the support $\mathcal X$, so the result below introduces no additional restrictions beyond those already present in Theorem (ref).

The proof of this result parallels that of Theorem (ref), but differs in several important respects. First, Theorem (ref) is formulated directly in terms of the marginal convergence rates $\mathrm{H}(P_r,P)=O(r^{a_h})$ and $\mathrm{TV}(P_r,P)=O(r^{a_{tv}})$, making explicit how smoothness of the conditional distribution of $Y$ near $x_0$ feeds into the joint rates of convergence of the induced order statistics. Second, the theorem provides an explicit rate for $\mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big)$ alongside the Hellinger bound, thereby allowing the two metrics to be compared on equal footing. Third, and more subtly, the joint total variation rate depends on both marginal exponents $a_h$ and $a_{tv}$. This reflects a structural bottleneck: the total variation rate can be controlled either directly through the marginal total variation discrepancy, or indirectly via the inequality $\mathrm{TV}\le\sqrt{2} \mathrm{H}$ in (ref). Consequently, even if the marginal total variation distance decays very rapidly ($a_{tv}$ is large), this does not relax the growth restriction on ($k$) needed for joint total variation convergence beyond what is already imposed by the Hellinger channel. In contrast, the joint Hellinger rate depends only on the marginal exponent $a_h$ and cannot be improved via the inequality $\mathrm{H}^2\le\mathrm{TV}$. This distinction is structural and follows from the exact tensorization of the Hellinger affinity over product measures, which implies that joint Hellinger convergence is fully determined by marginal Hellinger rates. Consequently, improvements in marginal total variation smoothness beyond what is implied by $a_h$ do not translate into faster joint Hellinger convergence. The primitive conditions developed in this paper determine when the exponents $a_h$ and $a_{tv}$ equal one, two, or other values, thereby tracing precisely how marginal smoothness translates into joint convergence rates for the induced order statistics.

We note that under Assumption (ref) and $g(x_0)>0$, Lemma (ref) implies $\mathrm{H}(P_r,P)=O(r^2)$ and $\mathrm{TV}(P_r,P)=O(r^2)$. In this case, part (a) of Theorem (ref) reproduces exactly the rate in Theorem (ref), illustrating that the two results are consistent.

Differentiability in Quadratic Mean

In this section, we develop marginal approximation rates for the conditional densities $p_x$ at $x_0$ under QMD. We show that QMD yields linear marginal convergence of $P_r$ to $P$ in both Hellinger and total variation distances. We also study sharpness and the limits of possible improvements over the linear rate, distinguishing what can and cannot be strengthened at boundary points versus interior points. These marginal results feed into joint convergence bounds for $\mathcal L(S_n)$ through Theorem (ref).

QMD is a central smoothness condition in asymptotic statistics. It underlies the local asymptotic normality (LAN) framework and plays a key role in the asymptotic theory of likelihood–based procedures (see, e.g., lecam:86, vandervaart:00). Beyond likelihood theory, QMD also supports diffusion/LAN approximations in statistical decision problems, such as optimal design and inference for adaptive experiments and bandits, by justifying Gaussian limit experiments and the associated risk analyses; adusumilli:bandits.

Lemma (ref) in the supplemental appendix shows that Assumption (ref) implies Assumption (ref), but not conversely. Section (ref) provides a detailed comparison of the two sets of primitive conditions, highlighting the distinct restrictions they impose on $\mathbf Q$ and the implications for the behavior of $P_r$. The next theorem gives the linear marginal rates under QMD and characterizes sharpness and the limits of uniform improvements.

Theorem (ref) implies that under QMD the marginal discrepancy is of order $O(r)$ in both $\mathrm{H}(P_r,P)$ and $\mathrm{TV}(P_r,P)$, and this order does not hinge on whether $x_0$ is an interior point or a boundary point of $\mathcal X$. Because sharpness is established via a boundary-point construction, one might suspect that interior points deliver uniformly faster rates. The theorem clarifies the limits of this intuition: while for interior points allow for $\mathrm{TV}(P_r,P)=o(r)$, no polynomial improvement over the $O(r)$ bound can be obtained uniformly over the QMD model class. This no-polynomial-improvement conclusion also applies to the Hellinger distance, though, in that case, we do not obtain an analogous $o(r)$ refinement.

Combining (ref) in Theorem (ref) with Theorem (ref) yields

Here $a_h = a_{tv} = 1$, so the relevant bound for $\mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big)$ is provided by the inequality $\mathrm{TV} \le \sqrt{2}\mathrm{H}$, and both distances share the same joint rate. This rate directly determines how fast $k$ may grow relative to $n$ while still ensuring convergence of $\mathcal L(S_n)$ to $\mathcal L(S)$: \[ k^{1/2}(k/n)^{1/d} \to 0 \qquad\Longleftrightarrow\qquad k = o\big(n^{2/(2+d)}\big)~. \] In particular, for $d=1$ this becomes $k = o(n^{2/3})$. This threshold coincides with the growth conditions derived, through different arguments, in bugni/canay:21 and bugni/canay/kim:2025 for the specific uses of induced order statistics in those papers.

Theorem (ref) delivers a simple benchmark rate. While we view this result as clean and widely applicable, it does not describe how stronger or weaker smoothness assumptions translate into faster or slower rates. Appendix (ref) provides complementary results. Under the Taylor/H\"older remainder condition of the joint density in Assumption (ref), Theorem (ref) delivers a range of marginal rates through explicit exponents $(a_h,a_{tv})$ that depend on the smoothness order $\kappa_{\rm s}+\kappa_{\rm r}$. As $\kappa_{\rm s}+\kappa_{\rm r}$ decreases, these exponents decrease, so the marginal convergence slows down, and the joint IOS approximation becomes more demanding through Theorem (ref). For example, in the H\"older continuity case $\kappa_{\rm s}=0$, the theorem gives $\mathrm{H}(P_r,P)=O(r^{\kappa_{\rm r}/2})$ and $\mathrm{TV}(P_r,P)=O(r^{\kappa_{\rm r}})$, so the rate can be arbitrarily slow as $\kappa_{\rm r}\downarrow 0$. In such cases, IOS--based approximations can break down regardless of the speed at which $k$ grows.

Applications

We start this section by describing how the general framework developed in this paper applies to the permutation test based on induced order statistics proposed in canay/kamat:18. That paper considers a sharp regression discontinuity design (RDD) in which treatment is assigned when a real-valued running variable $X$ crosses a known cutoff (normalized to zero), and focuses on a popular testable implication: that the distribution of baseline covariates is continuous at the cutoff. Formally, their null hypothesis is that the conditional law of a baseline covariate $Y$ is the same when approaching the cutoff from the left and from the right, \[ H_0:\ \mathcal L(Y\mid X=0^-) = \mathcal L(Y\mid X=0^+)~, \] which is the distributional analogue of the usual continuity-of-means checks routinely reported in empirical applications of RDD. Here, $0^+$ denotes the limit as $x\downarrow 0$ and $0^-$ the limit as $x\uparrow 0$ of the conditional laws $\mathcal L(Y\mid X=x)$. Under $H_0$, the $Y$ observations whose running variable lies closest to the cutoff on either side should be approximately exchangeable, and canay/kamat:18 exploit this by constructing a permutation test based on induced order statistics formed by the $q$ nearest neighbors to the left and the $q$ nearest neighbors to the right of the cutoff.

In the notation of this paper, the $2q$ induced order statistics used by canay/kamat:18 correspond to the special case $x_0=0$ and $k=2q$, where we separately order the observations with $X_i<0$ and $X_i>0$ by their distance to the cutoff. Let $\iota^{-}_n(1),\ldots,\iota^{-}_n(q)$ denote the indices of the $q$ observations with $X_i<0$ whose values are closest to $0$, listed in the original sample order; and similarly let $\iota^{+}_n(1),\ldots,\iota^{+}_n(q)$ denote the indices of the $q$ observations with $X_i>0$ closest to $0$. The induced order statistics used in the test can then be written as \[ S_n = (S_{n,1},\ldots,S_{n,k}) = \big(Y_{\iota^{-}_n(1)},\ldots,Y_{\iota^{-}_n(q)},\, Y_{\iota^{+}_n(1)},\ldots,Y_{\iota^{+}_n(q)}\big)~. \] The test statistic in canay/kamat:18 is the Cram\'er--von Mises functional $T(S_n)$ in (ref) that compares the empirical distribution functions constructed from the left and right subsamples. Critical values are obtained via permutation, based on the permuted vectors $S^{\pi}_{n} = (S_{n,\pi(1)},\ldots,S_{n,\pi(k)})$. We denote their resulting test by $\phi(S_n)$.

canay/kamat:18 establish the asymptotic validity of their approximate permutation test under an asymptotic framework in which $k$ is held fixed as $n\to\infty$, and they do not analyze regimes in which $k$ grows with $n$. Since $E_Q[\phi(S)]\le \alpha$ under their assumptions, the bound in (ref), together with Theorems (ref) and (ref) (applied separately to the left and right blocks of size $q$), and the fact that $d=1$, yield \[ E_Q[\phi(S_n)] \le \alpha + \mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big) = \alpha + O\big(k^{3/2}/n\big)~, \] for $k=2q$. Note that in this application, the conditioning points $x_0=0^{-}$ and $x_0=0^{+}$ lie on the boundary of the support of $X$ in the corresponding subsamples. This feature, which is intrinsic to RDDs, underscores the importance of Assumption (ref) for allowing boundary points. It follows that their permutation test remains asymptotically valid provided

recalling that $k=2q$ in their notation. Hence, the machinery developed in this paper delivers a simple and transparent characterization of how quickly $q$ may grow while maintaining asymptotic size control for the test in canay/kamat:18.

We next illustrate how our main results can be used to justify normal approximations for a broad class of IOS--based estimators (also known as $k$-nearest-neighbor estimators). Let $P$ denote the conditional law of $Y$ given $X=x_0$, and let $\theta(P)\in\mathbf R^\ell$ be the target parameter of interest. Examples include mean-type functionals $\theta(P)=E_P[Y]$ and quantile-type functionals defined by $P(Y\le \theta(P))=q$ for a fixed $q\in(0,1)$. We consider IOS--based estimators of $\theta(P)$ of the form $\psi(S_n)$, where $S_n=(S_{n,1},\ldots,S_{n,k})$ denotes the $k$ induced order statistics and where $\psi:\mathbf R^k\to\mathbf R^\ell$ is a Borel-measurable map. Let $S=(S_1,\ldots,S_k)$ be the infeasible benchmark consisting of $k$ i.i.d.\ draws from $P$. Under suitable conditions, standard normal approximation arguments imply that \[ \sup_{t\in\mathbf R^\ell}\Big| P^k\big(\sqrt{k}\,(\psi(S)-\theta(P))\le t\big)-\Phi_{\Sigma}(t) \Big| =O(k^{-1/2}) \] where $\Phi_{\Sigma}(t)$ is the normal distribution function with mean zero and covariance matrix $\Sigma$.

Combining the i.i.d.\ normal approximation for the infeasible benchmark $S$ with a total variation bound yields asymptotic normality of the IOS--based estimator $\psi(S_n)$. To see this, for each $t\in\mathbf R^\ell$, let $A_t= (-\infty, t/\sqrt{k}+\theta(P)]$ with the inequality interpreted componentwise. Since $\psi$ is Borel measurable,

where $Q$ is the law of $(X,Y)$. Taking the supremum over $t$ and using the $O(k^{-1/2})$ normal approximation for $\psi(S)$ therefore gives \[ \sup_{t\in\mathbf R^\ell}\Big| Q^n\big(\sqrt{k}\,(\psi(S_n)-\theta(P))\le t\big)-\Phi_{\Sigma}(t) \Big| \le \mathrm{TV}\big(\mathcal L(S_n),\mathcal L(S)\big)+O(k^{-1/2})~. \] Consequently, $\psi(S_n)$ has the same asymptotic normal limit as the infeasible i.i.d.\ benchmark provided the total variation distance $\mathrm{TV}(\mathcal L(S_n),\mathcal L(S))$ vanishes as $n$ grows. Under Assumptions (ref)--(ref), $\psi(S_n)$ is asymptotically normal provided \[ k=o \Big(n^{\tfrac{2}{d+2}}\Big)~. \]

While our analysis is motivated by IOS--based procedures, the results also speak to settings in which local conditional laws are approximated using shrinking neighborhoods around a conditioning point. One example arises in conditional stochastic optimization with side information, where a decision maker seeks to choose an action $z\in\mathcal Z$ (e.g., an order quantity, a portfolio allocation, or a policy parameter) that minimizes the conditional expected cost \[ \inf_{z\in\mathcal Z} E_Q\big[c(z,Y,X)\mid X=x_0\big] = \inf_{z\in\mathcal Z} E_P\big[c(z,Y,x_0)\big]~, \] with $P$ denoting the conditional law of $Y$ given $X=x_0$. A recent contribution by esteban/morales:22 studies this problem using a distributionally robust formulation, in which decisions are chosen to be robust against misspecification of the conditional law within a neighborhood of an empirical approximation constructed from observations with $X$ close to $x_0$. Two key tuning parameters in their approach are a trimming fraction $\alpha_n$ and a tolerance radius $\rho_n$, which controls the size of the distributional neighborhood over which robustness is imposed. The feasibility of their robust optimization problem, and hence the validity of their finite-sample guarantee, requires $\rho_n$ to decay at a rate that is sufficiently slow relative to the discrepancy between the local empirical conditional law and the target law $P$. A key ingredient in their analysis is a bound on this discrepancy, measured in Hellinger distance. Their argument implies that if $\mathrm{H}(P_r,P)=O(r^{a})$ and $r\asymp \alpha_n^{1/m}$, then feasibility requires $\rho_n$ not to decay faster than $\rho_n \gtrsim \alpha_n^{\min\{1,a\}/m}$ (up to lower–order terms). Under the smoothness condition of falk/husler/reiss:2010 one has $a=2$, while under Assumption (ref) one has $a=1$, so in both cases $\min\{1,a\}=1$ and the feasibility lower bound scales as $\rho_n \gtrsim \alpha_n^{1/m}$. Thus, QMD preserves the same admissible scaling for $\rho_n$ as the classical framework while requiring substantially weaker local structure (and allowing boundary points). A genuinely different scaling for $\rho_n$ arises only under rougher regimes with $a<1$, as in the alternative smoothness conditions in the Supplemental Appendix (Section (ref)).

Taken together, these examples, RDDs, $k$–nearest-neighbor methods, and distributionally robust optimization illustrate how our results apply to both IOS–based procedures and to a broader class of problems that rely on local conditional distributions.

Understanding the Assumptions

In this section, we take a closer look at the structure of the assumptions introduced earlier, with the goal of isolating the features that determine the achievable rates of convergence. Notably, Assumption (ref) in falk/husler/reiss:2010 implies the approximation error $\mathrm{H}(P_r,P)=O(r^{2})$, a rate that is substantially faster than the feasible rates delivered by Theorem (ref), which are sharp within the class of models satisfying its assumptions. Here, we highlight the key factors that determine this discrepancy in rates.

We start with a closer look at Assumption (ref). For simplicity, let $d=1$. Fix $y$ and note that (ref) implies that \[ \frac{f(x_0+t,y)-f(x_0,y)}{t} = f(x_0,y) \left\{ \zeta_1(y) + \frac{O(t^{2}\zeta_2(y))}{t} \right\}~. \] As $t\to 0$, the remainder term satisfies $O(t\zeta_2(y))\to 0$, so taking the limit yields \[ \frac{\partial f(x_0,y)}{\partial x} = f(x_0,y)\,\zeta_1(y) \quad \text{and} \quad \frac{\partial}{\partial x}\log f(x_0,y)=\zeta_1(y)~. \] Thus, wherever $f(x_0,y)>0$, Assumption (ref) pins down the local score at $x_0$ as a function of $y$ alone. Rewriting the expansion more explicitly,

where (1) holds by the expansion $\log(1+u)=u+O(u^2)$. Dropping second--order terms gives the leading approximation \[ f(x_0+t,y)\approx f(x_0,y)\exp\{t\zeta_1(y)\}~, \] which has the exponential tilt form in $y$ with statistic $\zeta_1(y)$. Assumption (ref) thus forces the local joint density to evolve in $x$ as if through an exponential tilt in $y$, making the model locally indistinguishable, to first order, from the exponential family generated by $\zeta_1(y)$.

There are two immediate consequences of this analysis. First, Assumption (ref) rules out the possibility that $x_0$ is a boundary point of the support of $X$. This is because the uniform expansion in (ref) must hold for all perturbations $t$ in a full neighborhood of $x_0$, which implies that $B_r\subset\mathcal X$ for all sufficiently small $r$. Second, Assumption (ref) imposes a local invariance of the zero--density region,

where $\mathcal Y$ denotes the unconditional support of $Y$. If $f(x_0,y)=0$, then $f(x_0+t,y)=0$ for all sufficiently small $t$. Consequently, any model in which new $y$--values enter the support of $f(x,\cdot)$ as $x$ moves locally away from $x_0$ violates Assumption (ref), even if it satisfies weaker conditions such as QMD or the alternative smoothness conditions we discuss in the Supplemental Appendix (ref).

In contrast, QMD neither imposes this exact invariance nor rules out boundary points. What QMD does imply is that the conditional law at $x_0+t$ assigns only $o(\|t\|^2)$ mass to the region where $p_{x_0}$ vanishes. Indeed, on the set $\{y:\,p_{x_0}(y)=0\}$, the QMD integrand reduces to $p_{x_0+t}(y)$, so \[ \int_{\{y:\,p_{x_0}(y)=0\}} p_{x_0+t}(y)\,\nu(dy)=o(\|t\|^{2})~. \] Thus QMD allows $p_{x_0+t}(y)$ to be positive on $\{p_{x_0}=0\}$ for arbitrarily small $t$, but controls its total contribution in an integrated sense.

All in all, Assumption (ref) is stronger than the conditions required for Theorem (ref). In particular, it implies Assumptions (ref) (with the additional restriction $x_0\in{\rm int}(\mathcal X)$) and (ref), whereas the converse does not hold; see Lemma (ref) in the supplementary appendix.

Concluding Remarks

This paper studies the behavior of induced order statistics when the number of nearest neighbors grows with the sample size. We provide general results that link marginal approximation rates for $P_r$ to joint convergence rates for the IOS vector in Hellinger and total variation distances, and we show how these rates depend on the local behavior of the conditional distribution of interest. In the main text, we develop sharp marginal rates under quadratic mean differentiability (QMD), which delivers a simple benchmark rate while accommodating both interior and boundary points. In the supplementary appendix, we provide complementary results under a Taylor/H\"older remainder condition that yields a wider range of marginal rates. Taken together, these results clarify when IOS--based approximations remain valid, when convergence slows down as smoothness weakens, and when it breaks down altogether. In doing so, we also formalize the sense in which stronger conditions such as those of falk/husler/reiss:2010 imply comparatively fast convergence by imposing substantial structure on the underlying model.

Beyond providing new results for IOS, the framework developed here is intended as a reusable toolkit for settings in which local conditional distributions are approximated using shrinking neighborhoods around a point of interest. By making explicit the trade--offs between smoothness, boundary behavior, and admissible growth rates for $k$, the analysis facilitates more transparent asymptotic arguments and helps guide future work on inference and estimation based on IOS. While our results are motivated by IOS--based procedures, most notably those arising in regression discontinuity designs and $k$-nearest-neighbor methods, they also speak to related problems that rely on local approximations to conditional laws but are not explicitly framed in terms of IOS, such as distributionally robust optimization.

\appendices

\setcounter{equation}{0}

Proof of the main results

Proof of Theorem (ref)

Part (a). Let $r_{1}$ be as defined in Lemma (ref). Lemma (ref) implies that $F(r) \geq F( r/2) >0$ for all $r\in ( 0,r_{1}]$. Then, kaufmann/reiss:92 implies that, for all $r\in ( 0,r_{1}) $,

where $P_{r}^{k}$ denotes the $k$-fold product measure of $P_{r}$.

Consider the following derivation for any $k\in \{1,\dots,n\}$ and $n\in \mathbf{N}$,

where (1) holds by the convexity lemma (e.g., reiss:1993), (2) by (ref), $S\perp R_{(k+1) }$, and $S\sim P^{k}$, and (3) by $\mathrm{H}^{2}(P',P'') \leq 1$ and Bernoulli's inequality, which states that $1-( 1-x) ^{k}\leq kx$ for any $x\in [ 0,1] $ and $k\in \mathbf{N}$.

Given (ref), we complete the proof by finding constants $C_1,C_2 \in (0,\infty)$ such that, for all $k\in \{1,\dots,n\}$ and $n\in \mathbf{N}$,

We begin by proving (ref). By $\mathrm{H}(P_{r},P)=O(r^{a_{h}})$, there is $C_{3}\in ( 0,\infty ) $ such that, for all $r\geq 0$,

Then, consider the following derivation:

where (1) holds by (ref), (2) by quantile transformation, which gives $R_{(k+1) }=F^{-1}( U_{(k+1:n) }) $ for $F^{-1}$ as defined in Lemma (ref), (3) by the fact that $F^{-1}(U_{(k+1:n)})\leq r_1$ implies $U_{(k+1:n) }\leq F(r_1)$ and Lemma (ref), which implies that $F(r_1)\leq C_{L}r_{1}^{d}$, (4) by Lemma (ref) applied to $U_{(k+1:n)}\leq C_{L}r_{1}^{d}$, and (5) by Lemma (ref) with $m=2a_{h}/d$. By setting $C_{1}:=C_{3}C_{L}^{-2a_{h}/d}C_{4}$, (ref) follows.

We now show (ref). Let $\tilde{r}_{1}\in (0,r_{1}]$ be a arbitrary continuity point of $F$. We divide the argument into two cases. First, consider any $k\in \{1,\dots ,n\}$ and $n\in \mathbf{N}$ such that $k/n\leq F(\tilde{r}_{1})/2$. Let $\mu :=k/(n+1)\leq (k/n)(n/(n+1))\leq F(r_{1})/2<1$ and $\sigma ^{2}:=\mu (1-\mu )$. Then,

where (1) holds by $\tilde{r}_{1}\leq r_{1}$, (2) by $\{ F^{-1}(U_{(k+1:n)})\geq \tilde{r}_{1}\} \subseteq \{ U_{(k+1:n)}\geq F(\tilde{r} _{1})\} $, which relies on $\tilde{r}_{1}$ being a continuity point of $F$, (3) by $F(\tilde{r}_{1})-\mu \geq F(\tilde{r}_{1})/2>0$ and reiss:89 with $\varepsilon =\sqrt{n}(F(\tilde{r}_{1})-\mu )/\sigma >0 $ and $\sigma ^{2}=\mu (1-\mu )$, (4) by $\mu \in [ 0,F(\tilde{r}_{1})/2]$, which yields $(F(\tilde{r}_{1})-\mu )^{2}\geq F(\tilde{r}_{1})^{2}/4$ and $F(\tilde{r}_{1})\geq F(\tilde{r}_{1})-\mu ^{2}>0$, (5) follows from $\exp(-cn)=O(n^{-\delta})$ for any $\delta>0$, and (6) by $ k\geq 1$.

Second, for any $k\in \{1,\dots ,n\}$ and $n\in \mathbf{N}$ such that $k/n>F(\tilde{r}_{1})/2$, we have

where (1) holds for $C_6 := (2/F(\tilde r_1))^{2a_h/d}$, and (2) holds since $k\geq 1$. To conclude, note that (ref) and (ref) imply (ref) holds with $C_{2}:=\max \{ C_{5},C_{6}\}$ for all $k\in \{1,\dots ,n\}$ and $n\in \mathbf{N}$, as desired.

\noindentPart (b). By part (a) and (ref), we obtain that, for any $k\in \{1,\dots ,n\}$ and $n\in \mathbf{N}$, $\mathrm{TV}(\mathcal{L}(S_{n}),\mathcal{L}(S))=O(k^{1/2} (k/n)^{a_{h}/d})$. To complete the proof, it then suffices to show that, for any $k\in \{1,\dots ,n\}$ and $n\in \mathbf{N}$, we also have $\mathrm{TV}(\mathcal{L}(S_{n}),\mathcal{L}(S))=O(k(k/n)^{a_{tv}/d})$.

Our proof follows the arguments of part (a) very closely. Recall that $a_{tv}\in [a_h,2a_h]$, which follows again from $\mathrm{H}(P_{r},P)=O(r^{a_{h}})$ and (ref), and note that the arguments used to derive (ref) continue to apply. Then, for any $k\in {1,\dots,n}$ and $n\in\mathbf{N}$, we have

where (1) holds by the law of total probability and using $\mathcal{B}$ to denote the common $\sigma$-algebra to $\mathcal{L}(S_{n})$ and $\mathcal{L}(S)$, and (2) by (ref), $ S\perp R_{(k+1)}$, and $S\sim P^{k}$, and (3) by hoeffding/wolfowitz:1958. Given (ref), we complete the proof by finding constants $C_{1},C_{2}\in (0,\infty )$ such that, for all $k\in \{1,\dots ,n\}$ and $ n\in \mathbf{N}$,

Then, (ref) and (ref) follow by repeating the arguments used to derive (ref) and (ref), with $\mathrm{H}(P_r,P)=O(r^{a_h})$ replaced by $\mathrm{TV}(P_r,P)=O(r^{a_{tv}})$.

Proof of Theorem (ref)

We start by proving (ref) and begin with a preliminary result. For any $x\in \mathcal{X}$, we define $D(x)$ as in Lemma (ref), and note that $\mathrm{H}^{2}(P_{x},P)=D(x)/2$. Lemma (ref) shows that, as $||x - x_0|| \to 0$,

Moreover, Assumption (ref) implies

By (ref) and (ref), there are constants $C>0$ and $\bar{r}>0$ so that, for all $\Vert x - x_0 \Vert < \bar{r}$,

Let $r_{1}$ be as in Lemma (ref). By this result, for all $ r\in ( 0,r_{1}) $,

For any $r\in ( 0,r_{1}) $, we can then define the following measure on $\mathcal{X}$:

By this definition, note that $h_{r}(y)=\int p_{x}(y)\mu _{r}(dx)$ and $P_{r}=\int P_{x}\mu _{r}(dx)$.

Let $r_2 := \min\{r_1,\bar{r}\}$. For any $r\in ( 0,r_{2})$, consider the following derivation.

where (1) holds by the convexity lemma (e.g., reiss:1993), with measure $\mu _{r}(dx)$ and $P_{r}=\int P_{x}\mu _{r}(dx)$, (2) by $\mathrm{H}^{2}(P_{x},P)=D(x)/2$ and (ref), (3) by (ref), (4) by (ref) and Assumption (ref), and (5) by $\int_{B_{r}}\Vert x-x_{0}\Vert ^{2}dx=O(r^{d+2})$. From (ref), we obtain

The convergence rate of the total variation distance follows from its relationship with the Hellinger, $\mathrm{TV}(P_{r},P)\leq \sqrt{2} \mathrm{H}(P_{r},P)$. This completes the proof of (ref).

Part (i) of the Theorem follows from Lemma (ref). The first statement in Part (ii) follows from Lemma (ref), while the result delivering $\mathrm{TV}(P_{r},P) = o(r)$ follows from Lemma (ref). This completes the proof. \rule{2mm}{2mm}

Auxiliary results

\numberwithin{equation}{section} \setcounter{section}{0} \setcounter{theorem}{0} \setcounter{lemma}{0} \cleardoublepage \setcounter{section}{0} \setcounter{lemma}{0} \setcounter{equation}{0}

\startcontents[appendix] \printcontents[appendix]{l}{1}{