SpreadBounds

where $m = \lfloor \frac{n}{2} \rfloor$, $\mathbf{d}$ is the sorted absolute differences from a random disjoint pairing, $k_L = r + 1$, $k_U = m - r$, and $r$ is the randomized sign-test cutoff for $\text{Binomial}(m, \frac{1}{2})$.

Robust bounds on $\operatorname{Spread}(\mathbf{x})$ with specified coverage.

• Interpretation $\mathrm{misrate}$ is probability that true spread falls outside bounds
• Domain any real numbers, $n \geq 2$, $\mathrm{misrate} \geq 2^{1-m}$
• Assumptions sparity(x)
• Unit same as measurements
• Note disjoint-pair sign-test inversion; randomized cutoff matches requested misrate exactly under weak continuity; conservative with ties

Properties

• Shift invariance $\operatorname{SpreadBounds}(\mathbf{x} + c, \mathrm{misrate}) = \operatorname{SpreadBounds}(\mathbf{x}, \mathrm{misrate})$
• Scale equivariance $\operatorname{SpreadBounds}(c \cdot \mathbf{x}, \mathrm{misrate}) = \lvert c \rvert \cdot \operatorname{SpreadBounds}(\mathbf{x}, \mathrm{misrate})$
• Non-negativity $\operatorname{SpreadBounds}(\mathbf{x}, \mathrm{misrate}) = [a, b]$ where $a \geq 0, b \geq 0$
• Monotonicity in misrate smaller $\mathrm{misrate}$ produces wider bounds

Example

• SpreadBounds([1..30], 0.01) where Spread = 9
• Bounds fail to cover true spread with probability $\approx \mathrm{misrate}$

$\operatorname{SpreadBounds}$ provides distribution-free bounds on the $\operatorname{Spread}$ estimate. It uses disjoint pairs and an exact sign-test inversion, which guarantees coverage regardless of the underlying distribution. Set $\mathrm{misrate}$ to control how often the bounds might fail to contain the true spread: use $10^{-3}$ for everyday analysis or $10^{-6}$ for critical decisions. The cutoff $r$ is clamped so that $\lfloor \frac{r}{2} \rfloor \leq \frac{m - 1}{2}$, ensuring the lower and upper order statistics remain within the sorted differences.

Minimum sample size the sign test on $m = \lfloor \frac{n}{2} \rfloor$ pairs has minimum achievable misrate $2^{1-m}$:

Algorithm

The $\operatorname{SpreadBounds}$ estimator constructs distribution-free bounds on $\operatorname{Spread}(\mathbf{x})$ by inverting a sign test on disjoint pairs.

Given a sample $\mathbf{x} = (x_1, \ldots, x_n)$, the algorithm proceeds as follows:

• Random disjoint pairing Randomly pair the $n$ observations into $m = \lfloor \frac{n}{2} \rfloor$ disjoint pairs. If $n$ is odd, one observation is discarded. The randomization ensures that the pairing does not depend on the data ordering.

• Absolute differences For each pair $(x_{a_i}, x_{b_i})$, compute the absolute difference $d_i = \lvert x_{a_i} - x_{b_i} \rvert$. Under the sparity assumption, these $m$ absolute differences are exchangeable.

• Sort Sort the differences to obtain $d_{(1)} \leq d_{(2)} \leq \ldots \leq d_{(m)}$.

• SignMargin cutoff Compute $r = \operatorname{SignMargin}(m, \mathrm{misrate})$ (see SignMargin). This determines how many extreme order statistics to exclude from each tail.

• Order statistic selection Return $[d_{(k_L)}, d_{(k_U)}]$ where $k_L = \lfloor \frac{r}{2} \rfloor + 1$ and $k_U = m - \lfloor \frac{r}{2} \rfloor$. Clamping ensures the indices remain within $[1, m]$.

The key insight is that disjoint pairs provide independence under the symmetry assumption. Under weak symmetry around the true spread, each absolute difference is equally likely to exceed or fall below the population spread. This makes the count of differences exceeding the spread a $\text{Binomial}(m, \frac{1}{2})$ variable, enabling exact coverage control via the sign test.

The randomized cutoff from $\operatorname{SignMargin}$ matches the requested misrate exactly under weak continuity. With tied values, the bounds become conservative (actual coverage exceeds $1 - \mathrm{misrate}$).

using Pragmastat.Functions;
using Pragmastat.Exceptions;
using Pragmastat.Internal;
using Pragmastat.Randomization;

namespace Pragmastat.Estimators;

/// <summary>
/// Distribution-free bounds for Spread using disjoint pairs with sign-test inversion.
/// Randomizes the cutoff between adjacent ranks to match the requested misrate.
/// Requires misrate >= 2^(1 - floor(n/2)).
/// </summary>
public class SpreadBoundsEstimator : IOneSampleBoundsEstimator
{
  public static readonly SpreadBoundsEstimator Instance = new();

  public Bounds Estimate(Sample x, Probability misrate)
  {
    return Estimate(x, misrate, null);
  }

  public Bounds Estimate(Sample x, Probability misrate, string? seed)
  {
    Assertion.Validity(x, Subject.X);

    if (double.IsNaN(misrate) || misrate < 0 || misrate > 1)
      throw AssumptionException.Domain(Subject.Misrate);

    int n = x.Size;
    int m = n / 2;
    double minMisrate = MinAchievableMisrate.OneSample(m);
    if (misrate < minMisrate)
      throw AssumptionException.Domain(Subject.Misrate);

    Assertion.Sparity(x, Subject.X);

    var rng = seed == null ? new Rng() : new Rng(seed);

    int margin = SignMargin.Instance.CalcRandomized(m, misrate, rng);
    int halfMargin = margin / 2;
    int maxHalfMargin = (m - 1) / 2;
    if (halfMargin > maxHalfMargin)
      halfMargin = maxHalfMargin;

    int kLeft = halfMargin + 1;
    int kRight = m - halfMargin;

    int[] indices = Enumerable.Range(0, n).ToArray();
    var shuffled = rng.Shuffle(indices);
    var diffs = new double[m];
    for (int i = 0; i < m; i++)
    {
      int a = shuffled[2 * i];
      int b = shuffled[2 * i + 1];
      diffs[i] = Math.Abs(x.Values[a] - x.Values[b]);
    }
    Array.Sort(diffs);

    double lower = diffs[kLeft - 1];
    double upper = diffs[kRight - 1];

    return new Bounds(lower, upper, x.Unit);
  }
}

Notes

$\operatorname{SpreadBounds}$ targets the population spread $\operatorname{Spread} = \operatorname{median} \lvert X_1 - X_2 \rvert$ with distribution-free coverage. This note records the approaches we discussed and tried, why most of them fail, and which theoretical limits force the final design. Here distribution-free means the stated misrate bound holds for all distributions of $X$, not just for a parametric family or under smoothness assumptions.

Setup and notation

Let $X_1, .., X_n$ be i.i.d. real-valued observations. Let $m = \lfloor \frac{n}{2} \rfloor$ and let $\pi$ be a random disjoint pairing of indices independent of the values. Define

for $i = 1..m$, and let $d_{(1)} \leq .. \leq d_{(m)}$ be their order statistics.

Let $G$ be the distribution of $D = \lvert X_1 - X_2 \rvert$ and let $\theta$ be any median of $G$. The target parameter is $\operatorname{Spread} = \theta$.

Valid pivot and exact coverage

Assume weak continuity of $G$ (no ties), so $P(D \leq \theta) = \frac{1}{2}$. Then the sign count $S$ (the number of indices $i$ with $d_i \leq \theta$) has distribution $B \sim \text{Binomial}(m, \frac{1}{2})$. For any integer $r$,

Therefore the interval $[ d_{(r+1)}, d_{(m-r)} ]$ has coverage $1 - 2 P(S \leq r)$ for all distributions of $X$. This is the core distribution-free pivot used by $\operatorname{SpreadBounds}$.

If $G$ has atoms (ties), then $P(D \leq \theta) \geq \frac{1}{2}$ for any median $\theta$. The binomial pivot becomes conservative: the same interval still covers with probability at least $1 - 2 P(S \leq r)$, but exact matching of a requested misrate is impossible.

Approaches that look reasonable but fail

All pairwise differences as if independent. Construct $N = \frac{n(n-1)}{2}$ absolute differences and apply a sign-test or binomial confidence interval as if those $N$ values were i.i.d. This ignores strong dependence between pairs, so coverage can be arbitrarily wrong. Correcting for dependence would require the joint law of all pairwise differences, which depends on the unknown distribution and is not distribution-free.

U-statistic inequalities for the median. Hoeffding-type bounds give distribution-free confidence bands for U-statistics, but for a median of pairwise differences they are extremely conservative. Intervals frequently collapse to almost $[\min, \max]$, which is unusable in practice. Asymptotic U-quantile results require smoothness and density assumptions, so they are not distribution-free.

Deterministic pairing based on order or sorting. Pairing consecutive elements in the given order is value-independent, but it is not permutation-invariant: changing the input order changes the result. If the order is adversarial (or structured), coverage can deviate arbitrarily. Pairing after sorting (or pairing extremes) is value-dependent, so the distribution-free pivot no longer applies.

Choose the best pairing based on the data. Searching many pairings and picking the tightest interval is data-dependent. The selection event depends on the observed values, so coverage is not unconditional. Coverage can become arbitrarily low.

Bootstrap, asymptotic normality, or variance estimation. These are not distribution-free and can be anti-conservative for heavy tails or small samples. Studentization helps asymptotically but still depends on distributional regularity (density, smoothness, finite moments).

Mid-p or continuity-corrected binomial intervals. These reduce discreteness but do not guarantee the nominal misrate even for the binomial model itself, so the distribution-free guarantee is lost.

Deterministic disjoint pairs: why it is conservative

With disjoint pairs, the pivot is valid, but the binomial CDF is discrete. The achievable misrates form a grid

. If the requested misrate falls between grid points, a deterministic method must round down, which is conservative by design. The minimum achievable misrate is $2^{1-m}$.

Deterministic interpolation between neighboring order statistics would use value distances instead of ranks, making coverage distribution-dependent and invalidating the distribution-free guarantee. As $m$ grows, the grid becomes finer (step size is $O(\frac{1}{\sqrt{m}})$), so deterministic rounding converges asymptotically, but exact matching remains impossible for any finite $n$.

Working approach: randomized cutoff

The final design keeps disjoint pairs but randomizes the cutoff $r$ between adjacent grid points. Let $t = \frac{\mathrm{misrate}}{2}$. Define $F(r) = P(B \leq r)$ and $f(r) = P(B = r)$. Let $r_l$ be the largest integer such that $F(r_l) \leq t$ and let $r_h = r_l + 1$. Choose $r = r_h$ with probability

and $r = r_l$ otherwise. This makes the tail probability exactly $t$.

Randomization affects only the cutoff and is independent of data values, so the distribution-free property is preserved.

Theoretical limits

• Distribution-free + deterministic + exact misrate is impossible for finite $n$. The pivot statistic is integer-valued, so the coverage function takes only finitely many values. Exact matching requires randomization.
• Exact matching for all distributions is impossible because ties break the binomial pivot. Under weak continuity (no ties), randomized cutoffs achieve exact misrate; with atoms, coverage is only guaranteed to be conservative.
• Deterministic exact misrate is possible only with extra assumptions (parametric family, smooth density at the target, known variance), which violates distribution-free guarantees.
• Any method that treats all pairwise differences as independent is invalid because dependence destroys the binomial pivot.
• Any data-dependent choice of pairing or cutoff breaks unconditional coverage and can make the method arbitrarily anti-conservative.

Tests

Let $m = \lfloor \frac{n}{2} \rfloor$. Draw a value-independent random disjoint pairing of the sample, compute $\mathbf{d} = { \lvert x_{\pi(2i-1)} - x_{\pi(2i)} \rvert }$ for $i = 1..m$, and sort ascending.

Let $r$ be the largest integer such that $sum_{i=0}^r \frac{\binom{m}{i}}{2^m} \leq \frac{\mathrm{misrate}}{2}$. If the target lies between two adjacent CDF steps, $r$ is randomized between $r$ and $r + 1$ to match the requested misrate. Define $k_L = r + 1$ and $k_U = m - r$.

Return $[L, U] = [d_{(k_L)}, d_{(k_U)}]$.

The $\operatorname{SpreadBounds}$ test suite contains 46 test cases (3 demo + 4 natural + 4 property + 7 edge + 3 additive + 2 uniform + 5 misrate + 5 conservatism + 8 unsorted + 5 error cases). Since $\operatorname{SpreadBounds}$ returns bounds rather than a point estimate, tests validate that bounds are well-formed and satisfy equivariance properties under a fixed seed. Each test case output is a JSON object with lower and upper fields representing the interval bounds. Because pairing and cutoff selection are randomized, tests fix seed to keep outputs deterministic.

Demo examples from manual introduction, validating basic bounds:

• demo-1: $\mathbf{x} = (1, 2, \ldots, 30)$, $\mathrm{misrate} = 0.01$, bounds containing $\operatorname{Spread} = 9$
• demo-2: $\mathbf{x} = (1, 2, \ldots, 30)$, $\mathrm{misrate} = 0.002$, wider bounds (tighter misrate)
• demo-3: $\mathbf{x} = (1, 2, \ldots, 15)$, $\mathrm{misrate} = 0.07$

These cases illustrate how tighter misrates produce wider bounds and how sample size affects bound width.

Natural sequences (misrate varies by size) 4 tests:

• natural-10: $\mathbf{x} = (1, 2, \ldots, 10)$, $\mathrm{misrate} = 0.15$
• natural-15: $\mathbf{x} = (1, 2, \ldots, 15)$, $\mathrm{misrate} = 0.05$
• natural-20: $\mathbf{x} = (1, 2, \ldots, 20)$, $\mathrm{misrate} = 0.05$
• natural-30: $\mathbf{x} = (1, 2, \ldots, 30)$, $\mathrm{misrate} = 0.05$

Property validation ($n = 10$, $\mathrm{misrate} = 0.2$) 4 tests:

• property-identity: $\mathbf{x} = (1, 2, \ldots, 10)$, bounds must contain $\operatorname{Spread}$
• property-location-shift: $\mathbf{x} = (11, 12, \ldots, 20)$ (= identity + 10), bounds must equal identity bounds (shift invariance)
• property-scale-2x: $\mathbf{x} = (2, 4, \ldots, 20)$ (= 2 $\times$ identity), bounds must be 2$\times$ identity bounds (scale equivariance)
• property-scale-neg: $\mathbf{x} = (-10, -9, \ldots, -1)$ (= $-1 \times$ identity), bounds must equal identity bounds ($\lvert k \rvert$ scaling)

Edge cases boundary conditions and extreme scenarios (7 tests):

• edge-small-non-trivial: $\mathbf{x} = (1, 2, 3, 4, 5)$, $\mathrm{misrate} = 0.8$ (small but non-trivial bounds)
• edge-large-misrate: $\mathbf{x} = (1, 2, \ldots, 10)$, $\mathrm{misrate} = 0.5$ (permissive bounds)
• edge-duplicates-mixed: $\mathbf{x} = (1, 1, 1, 2, 3, 4, 5)$, $\mathrm{misrate} = 0.5$ (partial ties)
• edge-wide-range: $\mathbf{x} = (1, 10, 100, 1000, 10000)$, $\mathrm{misrate} = 0.8$ (extreme value range)
• edge-negative: $\mathbf{x} = (-5, -4, -3, -2, -1)$, $\mathrm{misrate} = 0.8$ (negative values)
• edge-large-n: $\mathbf{x} = (1, 2, \ldots, 100)$, $\mathrm{misrate} = 0.01$ (large sample, tighter sign-test bounds)
• edge-n2: $\mathbf{x} = (1, 3)$, $\mathrm{misrate} = 1.0$ (minimum sample size, only valid misrate is 1.0)

Additive distribution (misrate varies by size) 3 tests with $\underline{\operatorname{Additive}}(10, 1)$:

• additive-20: $n = 20$, $\mathrm{misrate} = 0.02$
• additive-30: $n = 30$, $\mathrm{misrate} = 0.01$
• additive-50: $n = 50$, $\mathrm{misrate} = 0.01$

Uniform distribution (misrate varies by size) 2 tests with $\underline{\operatorname{Uniform}}(0, 1)$:

• uniform-20: $n = 20$, $\mathrm{misrate} = 0.02$
• uniform-50: $n = 50$, $\mathrm{misrate} = 0.01$

Misrate variation ($\mathbf{x} = (1, 2, \ldots, 25)$) 5 tests with varying misrates:

• misrate-5e-1: $\mathrm{misrate} = 0.5$
• misrate-1e-1: $\mathrm{misrate} = 0.1$
• misrate-5e-2: $\mathrm{misrate} = 0.05$
• misrate-1e-2: $\mathrm{misrate} = 0.01$
• misrate-2e-3: $\mathrm{misrate} = 0.002$

These tests validate monotonicity: smaller misrates produce wider bounds.

Conservatism tests ($\mathrm{misrate} = 0.1$) 5 tests unique to $\operatorname{SpreadBounds}$:

• conservatism-12: $\mathbf{x} = (1, 2, \ldots, 12)$, sign-test bounds are wide relative to $\operatorname{Spread}$
• conservatism-15: $\mathbf{x} = (1, 2, \ldots, 15)$
• conservatism-20: $\mathbf{x} = (1, 2, \ldots, 20)$
• conservatism-30: $\mathbf{x} = (1, 2, \ldots, 30)$
• conservatism-50: $\mathbf{x} = (1, 2, \ldots, 50)$

These tests document how discreteness-driven conservatism decreases with increasing sample size. For small $n$, bounds may span a large part of the pairwise-difference range. For large $n$, bounds tighten to a practical interval around $\operatorname{Spread}$.

Unsorted tests verify stable behavior on non-sorted inputs (8 tests):

• unsorted-reverse-10: $\mathbf{x} = (10, 9, \ldots, 1)$, $\mathrm{misrate} = 0.2$
• unsorted-reverse-15: $\mathbf{x} = (15, 14, \ldots, 1)$, $\mathrm{misrate} = 0.07$
• unsorted-shuffle-10: $\mathbf{x}$ shuffled, $\mathrm{misrate} = 0.2$
• unsorted-shuffle-15: $\mathbf{x}$ shuffled, $\mathrm{misrate} = 0.07$
• unsorted-negative-5: negative values unsorted ($\mathrm{misrate} = 0.8$)
• unsorted-mixed-signs-5: mixed signs unsorted ($\mathrm{misrate} = 0.8$)
• unsorted-duplicates: $\mathbf{x} = (1, 3, 1, 3, 2)$, unsorted with duplicates ($\mathrm{misrate} = 0.8$)
• unsorted-wide-range: $\mathbf{x} = (1000, 1, 100, 10, 10000)$, unsorted wide range ($\mathrm{misrate} = 0.8$)

These tests validate that $\operatorname{SpreadBounds}$ produces sensible bounds for arbitrary input order under a fixed seed.

Error cases inputs that violate assumptions (5 tests):

• error-empty-array: $\mathbf{x} = ()$, $\mathrm{misrate} = 0.5$ — empty array violates validity
• error-single-element: $\mathbf{x} = (1)$, $\mathrm{misrate} = 0.5$ — $m = 0$ violates domain ($n$ too small to form pairs)
• error-misrate-zero: $\mathbf{x} = (1, 2, \ldots, 10)$, $\mathrm{misrate} = 0$ — below minimum achievable misrate
• error-invalid-misrate: $\mathbf{x} = (1, 2, 3, 4, 5)$, $\mathrm{misrate} = 0.001$ — below minimum achievable misrate ($2^{1-2} = 0.5$)
• error-constant-sample: $\mathbf{x} = (1, 1, 1, 1, 1)$, $\mathrm{misrate} = 0.5$ — constant sample violates sparity ($\operatorname{Spread} = 0$)

Note: $\operatorname{SpreadBounds}$ has a minimum misrate constraint. The sign-test inversion requires $\mathrm{misrate} \geq 2^{1-m}$.