Home / Curated / Mathematical Methods / Sequential nonparametric quantile confidence sequences

Sequential nonparametric quantile confidence sequences

Mathematical Methods AIMech:SequentialNonparametricQuantileConfidenceSequences DRAFT

Aliases: Anytime-Valid Nonparametric Quantile Confidence Sequences, Time-Uniform Empirical Distribution Function and Quantile Bands, Double-Stitched Log-Odds Quantile-Uniform Confidence Sequences, Quantile Lower-Upper Confidence Bound (QLUCB) Best-Arm Identification, Two-Sample Sequential Nonparametric Quantile Test

A distribution-free, nonasymptotic sequential estimation and hypothesis testing framework (Howard & Ramdas 2022) for arbitrary fixed quantiles [Q(p), Q^+(p)] and simultaneously across all quantiles p in (0, 1) (and equivalently the empirical distribution function F_hat_t(x) uniformly over x in R and time t in N) of independent and identically distributed observations X_1, X_2, ... from any distribution F without moment, continuity, or density assumptions, constructing order-statistic confidence sequences [Q_hat_t^-(p - u_t(p)), Q_hat_t(p + u_t(p))] with P(forall t in N, forall p in I : Q_hat_t^-(p - u_t(p)) <= Q(p) <= Q^+(p) <= Q_hat_t(p + u_t(p))) >= 1 - alpha via exact Galois inversion of upper and lower empirical CDFs (F_hat_t, F_hat_t^-) and empirical quantiles (Q_hat_t, Q_hat_t^-) coupled with sub-Bernoulli/sub-gamma polynomial stitching (Theorem 1a), beta-binomial conjugate mixtures (Theorem 1b), time-uniform empirical-process finite-LIL/DKW chaining (Theorems 2 and 4), and double-stitched log-odds quantile grids (Theorem 5), with direct extensions to two-sample sequential quantile tests (Theorem 6) and quantile best-arm identification via QLUCB (Theorem 3).

Identity Notes & Concept Scope No normalized identity match for Sequential nonparametric quantile confidence sequences across all 442 pinned AIO records and 576 maintained IDs, names, aliases and scoped synonyms. Fixed-string searches across data, sources, research, history, and reviews returned only lines in Round 180 and Round 181 discovery artifacts where Howard & Ramdas (2022, arXiv:1906.09712) was cited and queued as a pending frontier lead. Distinct from AIMech:SubPsiUniformBoundaryConfidenceSequences (Howard, Ramdas, McAuliffe, & Sekhon 2021), which bounds scalar or matrix martingale sums S_t over intrinsic variance time V_t, whereas SequentialNonparametricQuantileConfidenceSequences maps probability-scale boundaries into state-space order statistics via exact Galois inversions for upper/lower quantiles [Q(p), Q^+(p)] with point-mass randomization martingales S_t(p), constructs time- and quantile-uniform empirical process finite-LIL bands via stratified dyadic chaining (Theorems 2 and 4) and double-stitched log-odds grids (Theorem 5, Lemma 10), and introduces the two-sample sequential quantile product supermartingale test (Theorem 6) and QLUCB quantile bandit algorithm (Theorem 3).

Claims & Grounded Evidence

4 Claims

Mechanism #galois-order-statistic-inversion-and-point-mass-quantile-martingale

For any real sample X_1, ..., X_t with order statistics X_{(1)} <= ... <= X_{(t)}, the empirical CDFs F_hat_t(x) = t^{-1} sum_{i=1}^t 1(X_i <= x) and F_hat_t^-(x) = t^{-1} sum_{i=1}^t 1(X_i < x) and empirical quantile functions Q_hat_t(p) = X_{(lfloor t p rfloor + 1)} and Q_hat_t^-(p) = X_{(lceil t p rceil)} satisfy the exact Galois equivalences F_hat_t^-(x) <= p iff x <= Q_hat_t(p) and F_hat_t(x) >= p iff Q_hat_t^-(p) <= x for all x in R and p in (0, 1) even in the presence of arbitrary ties or point masses (Section 7.1, Equation 35), and when P(X = Q(p)) > 0, the linearly interpolated process S_t(p) = t[(1 - gamma_p) F_hat_t^-(Q(p)) + gamma_p F_hat_t(Q(p)) - p] with gamma_p = (p - F^-(Q(p))) / (F(Q(p)) - F^-(Q(p))) is an exact zero-mean random walk with increments in [-p, 1 - p] whose CGF is bounded by the 1-sub-Bernoulli function psi_B(lambda) <= psi_{G,c_p}(lambda) with scale c_p = (1 - 2p)/3 and variance process V_t = p(1 - p)t while bounding t(F_hat_t^-(Q^+(p)) - p) <= S_t(p) <= t(F_hat_t(Q(p)) - p) almost surely.

supports Source: Sequential estimation of quantiles with applications to A/B testing and best-arm identification · Locator: Section 2, lines 125–160, Equations 1–5; Section 7.1, lines 621–676, Equations 35–40; Appendix C.1, lines 865–885 (Proof of Theorem 1)

Mechanism #fixed-quantile-stitched-and-beta-binomial-mixture-confidence-sequences

For any fixed quantile p in (0, 1), Theorem 1a's polynomial-stitched sub-gamma radius f_t(p) = S_p(t vee m)/t with S_p(t) = sqrt(k_1^2 p(1 - p)t l_t + k_2^2 c_p^2 l_t^2) + c_p k_2 l_t (Equation 41) achieves the law-of-the-iterated-logarithm rate O(sqrt(p(1 - p) t^{-1} log log t)) as t -> infinity, while Theorem 1b's one-sided beta-binomial conjugate mixture radius f_tilde_t(p) = t^{-1} sup{s in [0, (r + p(1 - p)t)/p) : M_{p,r}(s, p(1 - p)t) < 1/alpha} with closed-form Beta-function supermartingale M_{p,r}(s, v) (Equations 45–46) and Lambert W_{-1}-tuned prior scale r (Equation 21, Appendix D) exploits the reduced Bernoulli variance p(1 - p) near extreme quantiles p close to 0 or 1 to produce substantially tighter tail-quantile confidence sequences than variance-agnostic sub-Gaussian normal-mixture bounds (Equation 12) while maintaining guaranteed nonasymptotic anytime coverage even on heavy-tailed distributions with undefined moments such as the standard Cauchy distribution.

supports Source: Sequential estimation of quantiles with applications to A/B testing and best-arm identification · Locator: Section 3.1, lines 201–267, Theorem 1, Equations 8–12; Section 4.1, lines 386–434, Equation 21, Figure 1; Section 7.2–7.3, lines 677–745, Equations 41–46; Appendix C.1, lines 865–885; Appendix D, lines 1045–1070
supports Source: Time-uniform, nonparametric, nonasymptotic confidence sequences · Locator: Section 3.1–3.2, lines 221–277, Theorem 1, Propositions 3 and 7 (Stitched sub-gamma and beta-binomial conjugate mixture boundaries)

Mechanism #time-and-quantile-uniform-empirical-process-lil-and-double-stitching

Simultaneously across all t >= m and all p in (0, 1) (and all x in R), Theorem 2's and Theorem 4's stratified dyadic chaining over quantile partitions combines sub-Bernoulli exponential supermartingales with adaptive switchover from Bennett's to Hoeffding's CGF bound to establish the finite-sample iterated-logarithm empirical process bound sup_{x in R} |F_hat_t(x) - F(x)| <= A sqrt(t^{-1}(log log(e t / m) + C)) with valid crossing probability for any A > 1/sqrt(2) without a naive O(sqrt(t^{-1} log t)) time-axis union bound over fixed-sample Dvoretzky-Kiefer-Wolfowitz inequalities (Corollary 2 giving 0.85 sqrt(t^{-1}(log log(e t / 32) + 8.123)) at alpha = 0.05), while Theorem 5's double-stitched sequence u_t(p) stitches across both time epochs and a log-odds-spaced quantile grid (controlled by Lemma 10's hyperbolic-tangent spacing bound q_p - p <= tanh(a/2) sqrt(p(1 - p)) <= (a/2) sqrt(p(1 - p))) to preserve extreme-tail scaling O(sqrt(p(1 - p) t^{-1} (log log t + log |log(p(1 - p))|))) as p -> 0 or 1.

supports Source: Sequential estimation of quantiles with applications to A/B testing and best-arm identification · Locator: Section 3.2, lines 268–385, Theorem 2, Corollaries 1–2, Equations 13–20; Section 4.2, lines 435–485, Figures 2–3; Section 7.4–7.5, lines 746–863, Theorems 4–5, Equations 47–59; Appendix C.2–C.3, lines 886–1014, Lemmas 4–10

Application #two-sample-sequential-quantile-testing-and-qlucb-best-arm-identification

For sequential A/B testing of H_0 : Q_2(p) - Q_1(p) = delta between two independent streams, Theorem 6 and Section C.5 avoid conservative union bounds over separate arm confidence sequences when delta = 0 (or under simultaneous equality of all quantiles) by bounding the joint product supermartingale log L_{1,t} + log L_{2,t} from below via min_{x in R} (G_{1,t}(x) + G_{2,t}(x)) evaluated over observed order statistics (giving a sequential median difference confidence sequence under a location-shift model in Corollary 3), and for multi-armed quantile bandits (Section 6), replacing the loose DKW-style union bound of Szorenyi et al.'s (2015) QPAC algorithm with fixed-quantile stitched bounds f_t(pi - epsilon) and f_t(1 - pi - epsilon) inside the LUCB sampling rule yields the QLUCB algorithm (Theorem 3), guaranteeing (epsilon, pi, delta)-correct best-arm identification with substantially smaller stopping times.

supports Source: Sequential estimation of quantiles with applications to A/B testing and best-arm identification · Locator: Section 5, lines 486–549, Corollary 3, Figure 4; Section 6, lines 550–619, Theorem 3, Equations 26–34, Figure 5; Appendix B, lines 864–864; Appendix C.4–C.5, lines 1015–1044, Theorem 6

⚠️ Curated Limitations & Negative Results

Unlike sub-psi mean confidence sequences (Howard et al. 2021) which hold under arbitrary martingale dependence with time-varying conditional expectations, the quantile confidence sequences of Theorems 1–2 and 4–5 require observations X_1, X_2, ... to be independent (or conditionally sharing the same marginal quantile Q(p)) so that the indicator/interpolated quantile increments have predictable Bernoulli probability p (Section 2, Section 7.1).
When the underlying distribution F has a flat plateau at level p (so the lower quantile Q(p) < Q^+(p) differs strictly from the upper quantile), any valid nonparametric confidence sequence must cover the entire interval [Q(p), Q^+(p)] simultaneously, preventing the state-space interval width from shrinking below Q^+(p) - Q(p) (Section 2, Equations 1–5).
In two-sample sequential quantile testing (Section 5, Appendix C.5), the tighter single-parameter product supermartingale test (Theorem 6) applies directly to H_0 : Q_2(p) = Q_1(p) (delta = 0) or to testing simultaneous equality of all quantiles under a location-shift assumption (Corollary 3); testing H_0 : Q_2(p) - Q_1(p) = delta != 0 for a single quantile without a shift assumption requires combining two separate arm confidence sequences at level alpha_1 + alpha_2 = alpha.
All 1,139 lines of Howard & Ramdas (2022, arXiv:1906.09712) were read. Constructed numerical checks in research/discovery/sequential-nonparametric-quantile-confidence-sequences-boundaries.py verify Equation 35's exact Galois order-statistic inversions on samples with ties and point-mass quantile martingale sub-Bernoulli CGF dominance, Theorem 1a/1b tail-quantile tightness and anytime coverage on heavy-tailed Cauchy(0, 1) streams vs. naive asymptotic CLT failure, Theorem 2/4 and Corollary 2 empirical-process finite-LIL bounds plus Lemma 10 log-odds spacing, and Theorem 6's two-sample product supermartingale bound and Theorem 3's QLUCB sample reduction.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:DataDredgingBias` Data Dredging Bias	related_match	Sequential nonparametric quantile confidence sequences guarantee nonasymptotic coverage across all sample sizes t >= 1 and arbitrary data-dependent stopping times without parametric or moment assumptions, preventing false-positive inflation from continuous monitoring of quantiles and empirical CDFs in sequential A/B tests (AIO:DataDredgingBias).
`AIO:TimeSeriesAnalysis` Time Series Analysis	related_match	Sequential quantile confidence sequences and time-uniform empirical distribution bands track order statistics and quantile differences across sequential observation streams and multi-armed bandit pull sequences over time t (AIO:TimeSeriesAnalysis).

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`howard-ramdas2022-quantile-cs`	Sequential estimation of quantiles with applications to A/B testing and best-arm identification Steven R. Howard, Aaditya Ramdas	primary paper full_text	ID: https://doi.org/10.3150/21-BEJ1388 sha256:09a883cff34d…
`howard-ramdas-mcauliffe-sekhon2021-subpsi`	Time-uniform, nonparametric, nonasymptotic confidence sequences Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, Jasjeet Sekhon	primary paper full_text	ID: https://doi.org/10.1214/20-AOS1991 sha256:aef352a6e271…
`waudby-smith-ramdas2024-betting`	Estimating means of bounded random variables by betting Ian Waudby-Smith, Aaditya Ramdas	primary paper full_text	ID: https://doi.org/10.1093/jrsssb/qkad009 sha256:c41bcb5ff7e3…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini 3

Created: 2026-10-17T12:35:00Z

Updated: 2026-10-17T12:35:00Z

Source File: data/curated/SequentialNonparametricQuantileConfidenceSequences.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories