Fork-convex exchangeability testing via universal safe e-processes
Mathematical Methods AIMech:ForkConvexExchangeabilityTestingBySafeEProcesses DRAFT
Aliases: Fork-Convex Hull Characterization of Composite Test Supermartingales, Jeffreys'-Mixture Universal-Inference Safe E-Process for Exchangeability, Context-Tree Krichevsky-Trofimov Exchangeability E-Processes, Running-Maximum Adjuster E-Processes for Exchangeability Testing
A sequential hypothesis testing and game-theoretic probability framework (Ramdas, Ruf, Larsson, & Koolen 2022, International Journal of Approximate Reasoning 141:83-109, arXiv:2102.00630) for testing whether an observed data stream X_1, X_2, ... is exchangeable (H_0: bar{Q} = convex hull of i.i.d. distributions Q = {Ber(p)^infty : p in [0, 1]} in the canonical filtration (F_t)_{t>=1}) that proves every nonnegative supermartingale (NSM) under Q remains an NSM under the closed fork-convex hull tilde{Q} (which for exchangeable binary laws equals the set of all probability measures on {0, 1}^infty, rendering every canonical-filtration Q-NSM pathwise nonincreasing and powerless), characterizes when a Q-safe e-process E_t satisfying sup_{Q in bar{Q}, tau} E_Q[E_tau] <= 1 is dominated by a Q-NSM via the composite Q-Snell envelope under fork-convexity, and constructs powerful bar{Q}-safe e-processes R_t = inf_{p in [0, 1]} R_t^{JP, p} by dividing k-th order Markov Jeffreys'-prior (Krichevsky-Trofimov) mixtures, countable context-tree double mixtures, or predictable non-anticipating betting likelihoods by the composite i.i.d. maximum likelihood sup_p L_p(X^t).
Identity Notes & Concept Scope
No normalized identity match for fork-convex exchangeability testing via universal safe e-processes across all 442 pinned AIO records and 583 maintained IDs, names, aliases and scoped synonyms. Fixed-string searches across data, sources, research, history, and reviews returned only prior discovery frontier entries where Ramdas, Ruf, Larsson, & Koolen (2022, IJAR 141:83-109, arXiv:2102.00630) was tracked as a pending frontier lead. Distinct from AIMech:UniversalInferenceSplitLikelihoodRatioTest (Wasserman, Ramdas, & Balakrishnan 2020), which tests parametric/nonparametric composite nulls under i.i.d. data rather than testing the composite exchangeability null bar{Q} or characterizing fork-convex hulls and composite Snell envelopes; distinct from AIMech:ReverseSubmartingaleConvexDivergenceConfidenceSequences (Manole & Ramdas 2023), which operates in the reverse exchangeable filtration (E_t)_{t>=1} under the assumption of i.i.d. sampling to estimate convex divergences; and distinct from AIMech:SequentialKernelizedIndependenceTestingByBetting (Podkopaev et al. 2023), which pairs i.i.d. bivariate observations (X_{2t-1}, Y_{2t-1}), (X_{2t}, Y_{2t}) to test independence rather than testing exchangeability of a single sequence in its canonical filtration.
Claims & Grounded Evidence
4 Claims
Mechanism
#fork-convex-hull-composite-snell-envelope-and-exchangeable-nsm-impossibility
For two locally dominated laws Q, Q' with density processes Z_t, Z_t' wrt a reference measure R, a fork-convex combination at fork time s in N_0 with F_s-measurable weight h in [0, 1] is defined by Z_t'' = Z_t for t <= s and Z_t'' = h Z_t + (1 - h) Z_s (Z_t' / Z_s') for t > s (Section 3.1, Definition 10, Equation 13); every nonnegative supermartingale (NSM) under Q remains an NSM under its fork-convex hull and sequential closure tilde{Q} (Lemma 12, Theorem 13), and when Q is locally dominated and fork-convex the composite Q-Snell envelope L_t := ess sup_{tau >= t, Q in Q} E_Q[E_tau | F_t] is the smallest Q-NSM dominating a Q-safe e-process E_t (Theorem 14), so E_t is dominated by a Q-NSM if and only if E_t is already tilde{Q}-safe (Corollary 16); because the closed fork-convex hull of the i.i.d. Bernoulli family Q = {Ber(p)^infty : p in (0, 1)} equals the set of all probability measures on {0, 1}^infty (Theorem 17), every canonical-filtration Q-NSM (and hence every bar{Q}-NSM) is pathwise nonincreasing (L_t <= L_{t-1} <= 1) and the only Q-martingale is M_t == 1 (Section 1.6 Proposition 5, Section 3.2 Theorem 17), proving that any powerful canonical-filtration test of exchangeability must use e-processes that are not supermartingales.
Mechanism
#jeffreys-mixture-universal-inference-safe-e-process-and-krichevsky-trofimov-regret
Dividing the first-order Markov factorized Jeffreys' prior Beta(1/2, 1/2) x Beta(1/2, 1/2) marginal likelihood R_t^{JP} = (1 / (2 pi^2)) [Gamma(n_{0|0} + 1/2) Gamma(n_{1|0} + 1/2) / Gamma(n_{0|0} + n_{1|0} + 1)] [Gamma(n_{0|1} + 1/2) Gamma(n_{1|1} + 1/2) / Gamma(n_{0|1} + n_{1|1} + 1)] (equivalently updated sequentially in O(1) time via the Krichevsky-Trofimov predictive rule q_t(1) = (n_{1|X_{t-1}}(t-1) + 1/2) / (n_{0|X_{t-1}}(t-1) + n_{1|X_{t-1}}(t-1) + 1), Equations 5–6) by the composite i.i.d. Bernoulli maximum likelihood sup_{p in [0, 1]} L_p(X^t) = (n_1(t)/t)^{n_1(t)} (n_0(t)/t)^{n_0(t)} yields the statistic R_t = inf_{p in [0, 1]} R_t^{JP, p} (Section 1.4 Equation 7, Section 2.2), where each R_t^{JP, p} = R_t^{JP} / L_p(X^t) is an exact nonnegative Ber(p)^infty-martingale (Proposition 4); consequently, by de Finetti's theorem and convex closure (Proposition 2), (R_t)_{t>=1} is a bar{Q}-safe e-process satisfying sup_{Q in bar{Q}} sup_tau E_Q[R_tau] <= 1 and P_Q(exists t >= 1 : R_t >= 1/alpha) <= alpha for every exchangeable law Q in bar{Q} (Theorem 6) while achieving the Krichevsky-Trofimov universal coding regret bound ln R_t >= ln(sup_{p_{1|0}, p_{1|1}} L_{p_{1|0}, p_{1|1}}(X^t) / sup_p L_p(X^t)) - ln t - ln(2 pi) (Section 2.1, Equation 8).
Mechanism
#pathwise-exponential-growth-rate-and-context-tree-countable-double-mixtures
For any binary sequence whose empirical transition proportions converge to alpha = lim n_{1|1}/t, beta = lim n_{0|0}/t, gamma = lim n_{1|0}/t = lim n_{0|1}/t, and p = lim n_1/t = alpha + gamma, the asymptotic per-step log-growth rate of R_t is lim_{t->infty} (ln R_t)/t = r^* = h(p) + alpha ln(alpha / (alpha + gamma)) + beta ln(beta / (beta + gamma)) + gamma ln(gamma^2 / ((alpha + gamma)(beta + gamma))) >= 0, where r^* > 0 if and only if alpha (1 - p) != gamma p and lim_{t->infty} R_t = 0 almost surely under every exchangeable law Q in bar{Q} (Section 2.4, Theorem 7, Equations 9–12); because first-order transition counts are blind to higher-order dependencies where alpha (1 - p) = gamma p — such as the deterministic 2nd-order cycle 00110011... where alpha = beta = gamma = 1/4, p = 1/2, r^* = 0, and R_t^{1, 2} -> 0 (Example 9) — extending the numerator to k-th order d-ary Dirichlet(1/2, ..., 1/2) context-tree mixtures R_t^{k, d} with regret (d^k(d - 1)/2) ln t + O(1) (Section 2.5) and countable double mixtures E_t = sum_{k=1}^infty w_k R_t^{k, d} or active-prefix mixtures tilde{E}_t = sum_{k=1}^{f(t)} w_k R_t^{k, d} guarantees power-one consistency against all stationary k-th order Markov chains outside bar{Q} (Section 2.6), while replacing the mixture numerator by any predictable non-anticipating product prod_{s=1}^t g_s(X_s) preserves bar{Q}-safety (Section 2.7).
Mechanism
#empty-intersection-confidence-sequence-duality-and-running-maximum-adjuster
Defining the level-(1 - alpha) confidence set C_t := {p in [0, 1] : R_t^{JP, p} < 1/alpha} yields exact pathwise stopping-time equivalence inf{t >= 1 : C_t = emptyset} = inf{t >= 1 : R_t >= 1/alpha} (Section 4.6, Equation 16), while rejecting when the running intersection becomes empty at tau_{cap} := inf{t >= 1 : cap_{s<=t} C_s = emptyset} remains a valid level-alpha test of i.i.d. Bernoulli exchangeability that can stop strictly earlier than inf{t >= 1 : R_t >= 1/alpha} under regime shifts; furthermore, when departure from exchangeability is transient (Section 4.4, Section 4.7) so that R_t peaks above 1/alpha and subsequently decays toward zero, applying a p-to-e calibrator f to the running-minimum p-process p_t = 1 / max_{s<=t} R_s or an adjuster F: [1, infty) -> [0, infty) satisfying int_1^infty F(y) y^{-2} dy = 1 (such as F(y) = y / (1 + ln y)^2) yields a nondecreasing bar{Q}-safe e-process A_t = F(max_{s<=t} R_s) = Theta((max_{s<=t} R_s) / (ln max_{s<=t} R_s)^2) that permanently retains peak evidence (Section 4.7).
⚠️ Curated Limitations & Negative Results
- As proven in Proposition 5 and Theorem 17, no nontrivial canonical-filtration nonnegative supermartingale exists for testing i.i.d. or exchangeable binary sequences (every Q-NSM is almost surely nonincreasing), so safe e-processes R_t cannot be combined with supermartingale-only constructions that require E_Q[E_t | F_{t-1}] <= E_{t-1}.
- For any fixed order k >= 1 and alphabet size d >= 2, the k-th order context-tree Jeffreys'-mixture e-process R_t^{k, d} incurs universal coding regret ((d^k(d - 1)) / 2) ln t + O(1) that scales exponentially in the Markov order k and linearly in d^k (Section 2.5), and a fixed-order R_t^{k, d} has zero asymptotic growth rate against stationary non-exchangeable processes whose k-th order transition marginals match an i.i.d. law (such as 00110011... for k=1, Example 9).
- Under transient departures from exchangeability (such as a single changepoint between two i.i.d. regimes or a temporary Markov burst followed by i.i.d. data, Section 4.4 & Section 4.7), the unadjusted universal-inference e-process R_t eventually decays toward 0 as t -> infty unless wrapped in a running-maximum adjuster F(max_{s<=t} R_s), which pays an unavoidable O((ln max_{s<=t} R_s)^2) logarithmic divisor penalty.
- All 1,263 lines of Ramdas, Ruf, Larsson, & Koolen (2022, International Journal of Approximate Reasoning 141:83-109, arXiv:2102.00630v4) were read. Constructed numerical checks in research/discovery/fork-convex-exchangeability-testing-by-safe-e-processes-boundaries.py verify (1) Section 3.1 Definition 10 exact fork-convex martingale identity (max diff 4e-16) and Section 3.2 Theorem 17 / Corollary 16 composite Q-Snell envelope exceeding 1 (R_8 = 10.9375 > 1 on alternating path 01010101, proving impossibility of dominating Q-NSMs), (2) Section 1.4 Equations 5-6 exact agreement between sequential Krichevsky-Trofimov updates and closed-form Gamma-function R_t^{JP} across all {0,1}^7 sequences (max diff 0.0), Section 2.1 Equation 8 universal coding regret bound (max excess -1.457486 <= 0), and Theorem 6 exact optimal-stopping safety sup_tau E_Q[R_tau] = 1.0 under a Beta(2,2) Polya urn exchangeable law, (3) Section 2.4 Theorem 7 asymptotic log-growth rate on 010101... (empirical 0.678431 vs. r^* = ln 2 = 0.693147) and Example 9 decay of first-order R_t^{1,2} = 0.002552 on 2nd-order cycle 00110011... vs. exponential growth 0.665104 of the Section 2.6 context-tree double mixture, and (4) Section 4.6 Equation 16 exact stopping-time equality inf{t: C_t = empty} == inf{t: R_t >= 1/alpha} (0 mismatches), earlier stopping of running intersection tau_intersection = 41 < tau_R = 43 under a regime shift, and Section 4.7 running-maximum adjuster retention A_T = 246.022558 > 20 vs. decayed unadjusted R_T = 0.024891 after a transient Markov burst.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:DataDredgingBias
Data Dredging Bias
|
related_match | Safe e-processes for exchangeability satisfy sup_{Q in bar{Q}} sup_tau E_Q[E_tau] <= 1 and P_Q(exists t >= 1 : E_t >= 1/alpha) <= alpha under arbitrary data-dependent stopping times tau (Ramdas et al. 2022, Proposition 2 & Theorem 6), preventing optional-stopping inflation (AIO:DataDredgingBias). |
AIO:TimeSeriesAnalysis
Time Series Analysis
|
related_match | Fork-convex exchangeability e-processes sequentially monitor time-series data streams in their canonical filtration to detect Markov serial dependence, regime shifts, and departures from exchangeability (AIO:TimeSeriesAnalysis). |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
ramdas2022-exchangeability-ar5iv
|
Aaditya Ramdas, Johannes Ruf, Martin Larsson, Wouter M. Koolen
|
primary paper
full_text
|
ID: https://doi.org/10.1016/j.ijar.2021.06.017
sha256:c26efcd568ae…
|
ramdas2022-exchangeability-crossref
|
Aaditya Ramdas, Johannes Ruf, Martin Larsson, Wouter M. Koolen
|
primary paper
abstract_only
|
ID: https://doi.org/10.1016/j.ijar.2021.06.017
sha256:f95719b0d50d…
|
ramdas2022-exchangeability-abs
|
Aaditya Ramdas, Johannes Ruf, Martin Larsson, Wouter M. Koolen
|
primary paper
abstract_only
|
ID: https://doi.org/10.48550/arXiv.2102.00630
sha256:59f57aab3f19…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini 3
Created: 2026-10-17T14:05:00Z
Updated: 2026-10-17T14:05:00Z
Source File:
data/curated/ForkConvexExchangeabilityTestingBySafeEProcesses.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