SignedRankMargin

Exclusion count for one-sample signed-rank based bounds.

• Purpose — determines extreme pairwise averages to exclude when constructing bounds
• Based on — Wilcoxon signed-rank distribution under weak symmetry
• Returns — total margin split evenly between lower and upper tails
• Used by — $\operatorname{CenterBounds}$ to select appropriate order statistics
• Complexity — exact for $n \leq 63$, approximated for larger
• Domain — $n \geq 2$, $\mathrm{misrate} \geq 2^{1-n}$
• Unit — count
• Note — assumes weak symmetry and weak continuity

Properties

• Bounds $0 \leq \operatorname{SignedRankMargin}(n, \mathrm{misrate}) \leq \frac{n(n+1)}{2}$
• Monotonicity lower misrate $\rightarrow$ smaller margin $\rightarrow$ wider bounds

Example

• SignedRankMargin(10, 0.05) = 18
• SignedRankMargin(30, 1e-4) = 112
• SignedRankMargin(100, 1e-6) = 706

This is a supporting function that $\operatorname{CenterBounds}$ uses internally, so most users do not need to call it directly. It calculates how many extreme pairwise averages should be excluded when constructing bounds, based on sample size and the desired error rate. A lower misrate (higher confidence) results in a smaller margin, which produces wider bounds. The function automatically chooses between exact computation for small samples and a fast approximation for large samples.

Algorithm

The $\operatorname{SignedRankMargin}$ function determines how many extreme pairwise averages to exclude when constructing bounds around $\operatorname{Center}(\mathbf{x})$. Given a sample $\mathbf{x} = (x_1, \ldots, x_n)$, the $\operatorname{CenterBounds}$ estimator computes all $N = \frac{n(n+1)}{2}$ pairwise averages $w_{i j} = \frac{x_i + x_j}{2}$ for $i \leq j$ and sorts them. The bounds select specific order statistics from this sorted sequence: $[w_{(k_{\text{left}})}, w_{(k_{\text{right}})}]$. The challenge lies in determining which order statistics produce bounds that contain the true center with probability $1 - \mathrm{misrate}$.

The margin function is the one-sample analog of $\operatorname{PairwiseMargin}$. While $\operatorname{PairwiseMargin}$ uses the Mann-Whitney distribution for two-sample comparisons, $\operatorname{SignedRankMargin}$ uses the Wilcoxon signed-rank distribution for one-sample inference. Under the weak symmetry assumption, the signed-rank statistic has a known distribution that enables exact computation of bounds coverage.

For symmetric distributions, consider the signs of deviations from the center. The Wilcoxon signed-rank statistic $W$ sums the ranks of positive deviations:

where $R_i$ is the rank of $\lvert x_i - \theta \rvert$ among all $\lvert x_j - \theta \rvert$, and $\theta$ is the true center. Under symmetry, each deviation is equally likely to be positive or negative, giving $W$ a discrete distribution over $[0, \frac{n(n+1)}{2}]$.

The connection to pairwise averages is fundamental: the $k$-th order statistic of sorted pairwise averages corresponds to a specific threshold of the signed-rank statistic. By computing the distribution of $W$, we determine which order statistics provide bounds with the desired coverage.

Two computational approaches provide the distribution of $W$: exact calculation for small samples and approximation for large samples.

Exact method

Small sample sizes allow exact computation without approximation. The Wilcoxon signed-rank distribution has $2^n$ equally likely outcomes under symmetry, corresponding to all possible sign patterns for deviations from the center.

Dynamic programming builds the probability mass function efficiently. Define $p(w)$ as the number of sign patterns producing signed-rank statistic equal to $w$. The recurrence considers whether to include rank $i$ in the positive sum:

with base case $p_0(0) = 1$. This builds the distribution incrementally, rank by rank.

The algorithm computes cumulative probabilities $\Pr(W \leq w)$ sequentially until the threshold $\frac{\mathrm{misrate}}{2}$ is exceeded. For symmetric two-tailed bounds, the margin becomes $\operatorname{SignedRankMargin} = 2w$. Memory is $O(n^2)$ for storing the probability array, and time is $O(n^3)$ for the full computation.

The sequential computation performs well for small misrates. For $\mathrm{misrate} = 10^{-6}$, the threshold $w$ typically remains small, requiring only iterations through the lower tail regardless of sample size.

Approximate method

Large samples make exact computation impractical. For $n > 63$, the Wilcoxon distribution is approximated using an Edgeworth expansion.

Under symmetry, the signed-rank statistic $W$ has:

The basic normal approximation uses these moments directly, but underestimates tail probabilities for moderate sample sizes.

The Edgeworth expansion refines this through moment-based corrections. The fourth central moment of $W$ is:

This enables kurtosis correction:

The approximated CDF becomes:

where $z = \frac{w - \mu + 0.5}{\sigma}$ includes a continuity correction.

Binary search locates the threshold efficiently. Each CDF evaluation costs $O(1)$, and $O(\log N)$ evaluations suffice. The approximate method completes in constant time regardless of sample size.

The toolkit uses exact computation for $n \leq 63$ and approximation for $n > 63$. At $n = 63$, the exact method requires arrays of size $2,016$ ($= 63 \times \frac{64}{2}$), which remains practical on modern hardware. The transition at $n = 63$ is determined by the requirement that $2^n$ fits in a 64-bit integer. The approximation achieves sub-1% accuracy for $n > 100$, making the transition smooth.

Minimum achievable misrate

The $\mathrm{misrate}$ parameter controls how many extreme pairwise averages the bounds exclude. However, sample size limits how small misrate can meaningfully become.

The most extreme configuration occurs when all signs are positive (or all negative): $W = \frac{n(n+1)}{2}$ or $W = 0$. Under symmetry, this extreme occurs with probability:

Setting $\mathrm{misrate} < \mathrm{misrate}_{min}$ makes bounds construction problematic. Pragmastat rejects such requests with a domain error.

The table below shows $\mathrm{misrate}_{min}$ for small sample sizes:

For meaningful bounds construction, choose $\mathrm{misrate} > \mathrm{misrate}_{min}$. With $n \geq 10$, standard choices like $\mathrm{misrate} = 10^{-3}$ become feasible. With $n \geq 20$, even $\mathrm{misrate} = 10^{-6}$ is achievable.

using JetBrains.Annotations;
using Pragmastat.Exceptions;

namespace Pragmastat.Functions;

/// <summary>
/// SignedRankMargin function for one-sample bounds.
/// One-sample analog of PairwiseMargin using Wilcoxon signed-rank distribution.
/// </summary>
/// <param name="threshold">Maximum n for exact computation; larger n uses approximation</param>
internal class SignedRankMargin(int threshold = SignedRankMargin.MaxExactSize)
{
  public static readonly SignedRankMargin Instance = new();

  private const int MaxExactSize = 63;

  [PublicAPI]
  public int Calc(int n, double misrate)
  {
    if (n <= 0)
      throw AssumptionException.Domain(Subject.X);
    if (double.IsNaN(misrate) || misrate < 0 || misrate > 1)
      throw AssumptionException.Domain(Subject.Misrate);

    double minMisrate = MinAchievableMisrate.OneSample(n);
    if (misrate < minMisrate)
      throw AssumptionException.Domain(Subject.Misrate);

    return n <= threshold
      ? CalcExact(n, misrate)
      : CalcApprox(n, misrate);
  }

  internal int CalcExact(int n, double misrate)
  {
    int raw = CalcExactRaw(n, misrate / 2);
    return checked(raw * 2);
  }

  internal int CalcApprox(int n, double misrate)
  {
    long raw = CalcApproxRaw(n, misrate / 2);
    long margin = raw * 2;
    if (margin > int.MaxValue)
      throw new OverflowException($"Signed-rank margin exceeds supported range for n={n}");
    return (int)margin;
  }

  /// <summary>
  /// Compute one-sided margin using exact Wilcoxon signed-rank distribution.
  /// Uses dynamic programming to compute the CDF.
  /// </summary>
  private static int CalcExactRaw(int n, double p)
  {
    ulong total = 1UL << n;
    long maxW = (long)n * (n + 1) / 2;

    var count = new ulong[maxW + 1];
    count[0] = 1;

    for (int i = 1; i <= n; i++)
    {
      for (long w = Min(maxW, (long)i * (i + 1) / 2); w >= i; w--)
        count[w] += count[w - i];
    }

    ulong cumulative = 0;
    for (int w = 0; w <= maxW; w++)
    {
      cumulative += count[w];
      double cdf = (double)cumulative / total;
      if (cdf >= p)
        return w;
    }

    return (int)maxW;
  }

  /// <summary>
  /// Compute one-sided margin using Edgeworth approximation for large n.
  /// </summary>
  private static long CalcApproxRaw(int n, double misrate)
  {
    long maxW = (long)n * (n + 1) / 2;
    long a = 0;
    long b = maxW;

    while (a < b - 1)
    {
      long c = (a + b) / 2;
      double cdf = EdgeworthCdf(n, c);
      if (cdf < misrate)
        a = c;
      else
        b = c;
    }

    return EdgeworthCdf(n, b) < misrate ? b : a;
  }

  /// <summary>
  /// Edgeworth expansion for Wilcoxon signed-rank distribution CDF.
  /// </summary>
  private static double EdgeworthCdf(int n, long w)
  {
    double mu = (double)n * (n + 1) / 4.0;
    double sigma2 = n * (n + 1.0) * (2 * n + 1) / 24.0;
    double sigma = Sqrt(sigma2);

    // +0.5 continuity correction: computing P(W ≤ w) for a left-tail discrete CDF
    double z = (w - mu + 0.5) / sigma;
    double phi = Exp(-z * z / 2) / Sqrt(2 * PI);
    double Phi = AcmAlgorithm209.Gauss(z);

    double nd = n;
    double kappa4 = -nd * (nd + 1) * (2 * nd + 1) * (3 * nd * nd + 3 * nd - 1) / 240.0;

    double e3 = kappa4 / (24 * sigma2 * sigma2);

    double z2 = z * z;
    double z3 = z2 * z;
    double f3 = -phi * (z3 - 3 * z);

    double edgeworth = Phi + e3 * f3;
    return Min(Max(edgeworth, 0), 1);
  }

}

Tests

The $\operatorname{SignedRankMargin}$ test suite contains 39 correctness test cases (4 demo + 6 boundary + 7 exact + 20 medium + 2 error).

Demo examples ($n = 30$) — from manual introduction:

• demo-1: $n=30$, $\mathrm{misrate}=10^{-6}$, expected output: $46$
• demo-2: $n=30$, $\mathrm{misrate}=10^{-5}$, expected output: $74$
• demo-3: $n=30$, $\mathrm{misrate}=10^{-4}$, expected output: $112$
• demo-4: $n=30$, $\mathrm{misrate}=10^{-3}$, expected output: $158$

These demo cases match the reference values used throughout the manual to illustrate $\operatorname{CenterBounds}$ construction.

Boundary cases — minimum achievable misrate validation:

• boundary-n2-min: $n=2$, $\mathrm{misrate}=0.5$ (minimum misrate for $n=2$, expected output: $0$)
• boundary-n3-min: $n=3$, $\mathrm{misrate}=0.25$ (minimum misrate for $n=3$)
• boundary-n4-min: $n=4$, $\mathrm{misrate}=0.125$ (minimum misrate for $n=4$)
• boundary-loose: $n=5$, $\mathrm{misrate}=0.5$ (permissive misrate)
• boundary-tight: $n=10$, $\mathrm{misrate}=0.01$ (strict misrate)
• boundary-very-tight: $n=20$, $\mathrm{misrate}=0.001$ (very strict misrate)

These boundary cases validate correct handling of minimum achievable misrate (formula: $2^{1-n}$) and edge conditions.

Exact computation ($n \leq 10$) — validates dynamic programming path:

• exact-n5-mr1e1: $n=5$, $\mathrm{misrate}=0.1$
• exact-n6-mr1e1: $n=6$, $\mathrm{misrate}=0.1$
• exact-n6-mr5e2: $n=6$, $\mathrm{misrate}=0.05$
• exact-n10-mr1e1: $n=10$, $\mathrm{misrate}=0.1$, expected output: $22$
• exact-n10-mr1e2: $n=10$, $\mathrm{misrate}=0.01$
• exact-n10-mr5e2: $n=10$, $\mathrm{misrate}=0.05$
• exact-n10-mr5e3: $n=10$, $\mathrm{misrate}=0.005$

These cases exercise the exact Wilcoxon signed-rank CDF computation for small samples where dynamic programming is used.

Medium samples ($n in {15, 20, 30, 50, 100}$ × 4 misrates) — 20 tests:

• Misrate values: $\mathrm{misrate} in {10^{-1}, 10^{-2}, 10^{-3}, 10^{-4}}$
• Test naming: medium-n{n}-mr{k} where $k$ encodes the misrate
• Examples:
• medium-n15-mr1e1: $n=15$, $\mathrm{misrate}=0.1$
• medium-n30-mr1e2: $n=30$, $\mathrm{misrate}=0.01$, expected output: $220$
• medium-n50-mr1e3: $n=50$, $\mathrm{misrate}=0.001$
• medium-n100-mr1e4: $n=100$, $\mathrm{misrate}=0.0001$

The medium sample tests validate the transition region between exact computation ($n \leq 63$) and approximate computation, ensuring consistent results across sample sizes and misrate values.

Error case — domain violation:

• error-n1: $n=1$, $\mathrm{misrate}=0.5$ (invalid: misrate below minimum achievable $2^{1-1} = 1.0$)
• error-n0: $n=0$, $\mathrm{misrate}=0.05$ (invalid: n must be positive)

This error case verifies that implementations correctly reject $n=1$ with $\mathrm{misrate}=0.5$ as invalid input, since the minimum achievable misrate for $n=1$ is $2^0 = 1.0$.