Combining e-values using demi-supermartingales

1 Introduction

• The paper asks how to combine independent e-variables into a p-value or test, against a backdrop of an open conjecture for arbitrary n.Wang and Zhao [2003] had proved their version only for n ∈ {1, 2}.Source: §1 · p. 2
• A demi-supermartingale argument settles both conjecture versions positively under co-valid dependence, using a statistic larger than supλ∈[0,1] Mn(λ).Co-valid e-variables are a dependence class more general than independence; the supremum statistic can be more powerful in some situations.Source: §1 · pp. 2–3
• The conjectured inequality also extends to nonnegative random variables with average mean at most 1, termed compound e-values in global-null testing.This generalization is stated for Theorem 5.2.Source: §1 · p. 3
• The result gives regret-free concentration for the KL-inf statistic at a fixed sample size n.Earlier work used deterministic regret bounds to obtain time-uniform concentration bounds with factors polynomial in n.Source: §1 · p. 3
• The proof strategy uses a demi-supermartingale property of the maximized family, since the polynomial process itself is not a supermartingale.The paper establishes an analogue of Ville’s inequality for nonnegative demi-supermartingales.Source: §1 · p. 3

2 Strengthening Ville’s inequality with demi-supermartingales

• A demi-supermartingale requires nonpositive expected increments when weighted by decreasing, nonnegative functions of the process history.The definition applies at each k after the initial time.Source: §2 · p. 4
• The proof obtains a Doob-like bound, E[Mτ] ≤ E[M0], for the first passage time τ.The bound applies to nonnegative demi-supermartingales.Source: §2 · p. 4
• For a nonnegative demi-supermartingale, the section establishes Ville’s inequality, a strict generalization of the usual discrete-time inequality for supermartingales.Demi-supermartingales need not themselves be supermartingales.Source: §2 · p. 5
• The paper’s target processes can be demi-supermartingales without being supermartingales, motivating the broader maximal inequality.The section gives a nonnegative demi-martingale example that is not a supermartingale.Source: §2 · pp. 5–6

3 Co-valid e-variables and the SymPol inequality

• The averages A_k of elementary symmetric polynomials form a nonnegative demi-supermartingale and upper-bound the supremum of the betting products over λ ∈ [0, 1].The proof combines this property with Ville’s inequality for nonnegative demi-supermartingales.Source: §3 · pp. 7–8
• Under co-validity, SymPol establishes the conjectured bound with a sharper statistic and weaker assumptions than conjectured.Co-validity includes independent e-variables.Source: §3 · p. 8
• When all e-variables are exact, the Ak process is a demi-martingale, which may yield sharper inference for bounded-mean confidence intervals.This property does not change the form of the downstream tests and p-values.Source: §3 · p. 8
• Sequential validity alone does not suffice for the bound in (9), as Example 3.4 provides a counterexample.Co-validity is a more restrictive dependence condition than sequential validity.Source: §3 · pp. 6, 8, 9
• Theorem 3.3 yields p-values and level-α tests for the null that the components are co-valid e-variables.The tests use the theorem’s resulting p-values.Source: §3 · p. 9

4.1 Problem setup

• Under independent [0,1]-valued observations with common mean μ, the SymPol confidence interval is valid and contains the sample mean.The independence assumption can be relaxed to a rescaled version of co-validity.Source: §4.1 · p. 10

4.2 A regret-free KL-inf confidence interval

• For independent observations with mean at most m, Corollary 4.5 gives regret-free concentration for the KL-inf statistic.The cited passage states the result but does not provide its inequality’s threshold.Source: §4.2 · p. 12

4.3 Asymptotic widths of the KL-inf confidence interval

• When σ² > 0, the confidence-interval length scales asymptotically as √(2σ² log(2/α)/n) almost surely; when σ² = 0, n w_n → log(2/α).SymPol intervals have the same limiting width as the KL-inf intervals.Source: §4.3 · pp. 13–14

4.4 A general KL-inf duality theorem

• Theorem 4.8 extends the KL-inf duality beyond bounded variables to generic nonnegative variables with mean at most one.The resulting duality generalizes the one used for the bounded-variable concentration result.Source: §4.4 · pp. 14–15

5 Extension to heterogeneous means

• For co-valid e-variables, the normalized elementary symmetric-polynomial process is a nonnegative demi-supermartingale, enabling the SymPol inequality.The proof applies Ville’s inequality to this process.Source: §5 · pp. 15–16
• Theorem 5.2 establishes the SymPol inequality for co-valid compound e-values without requiring a common-mean assumption.It allows nonnegative variables with component-specific conditional mean bounds μ_i.Source: §5 · pp. 15, 18
• For independent variables, the component-specific bounds μ_i may be chosen as their means; co-valid compound e-values satisfy the theorem with average bound one.The theorem’s conditional bounds also yield a valid p-value for testing, though the supplied passage does not specify the test.Source: §5 · pp. 18, 20
• Under the exact conditional-mean condition, SymPol confidence intervals cover the average of component means even when those means differ.The condition is weaker than independence and includes independent observations.Source: §5 · pp. 20–21

6 A fast algorithm for SymPol

• Each elementary symmetric polynomial S_k(E) is the coefficient of z^k in P(z), so the algorithm extracts all coefficients and normalizes them to obtain A_k(E).Once the coefficients are available, all A_k(E) values take an additional O(n) time.Source: §6 · pp. 21–22
• The algorithm computes max_k A_k(E) in O(M(n) log n) time, or O(n log^2 n) with FFT-based multiplication.It obtains the coefficients of P(z) = ∏_i(1 + E_i z) by recursively splitting the factors and multiplying the resulting polynomials.Source: §6 · p. 22

7 Conclusion

• SymPol combines co-valid and compound e-values into a p-value and yields a smaller or equal p-value than the KL-inf statistic.The method is based on elementary symmetric polynomials and admits a fast algorithm.Source: §7 · pp. 22–23
• The paper positively settles the Wang–Zhao [2003] conjecture and one of Gaffke [2005], with results under co-validity and heterogeneous means.The authors note that the assumptions and scope differ from later work on the stronger Gaffke conjecture.Source: §7 · p. 22

• The union bound establishes coverage for the confidence interval.Source: §A.1 · p. 24
• Maclaurin’s inequalities show the interval is nonempty and contains the sample mean.Source: §A.1 · p. 24
• The SymPol acceptance set is contained in the optimized-product acceptance set, yielding inequalities for the outer endpoints.Source: §A.1 · p. 24

• For positive variance, the confidence set is eventually confined to an O(n^-1/2) neighborhood of the sample mean.Source: §A.2 · p. 25
• For positive variance, its width is eventually bounded between 2(r−ε)/√n and 2(r+ε)/√n.Source: §A.2 · p. 26
• When the variance is zero, the interval width is 1−e^−c/n, including at the endpoint means.Source: §A.2 · p. 26

• For bounded t, the statistic near m_n,t = X_n + t/√n admits a uniform local quadratic approximation.The approximation applies over |t| ≤ K.Source: §A.3 · pp. 27–29

A.4 Proof of Theorem 4.8

• The proof of Theorem 4.8 constructs a distribution attaining the weak-duality lower bound, establishing the stated identity.Source: §A.4 · pp. 30–31

A.5 Limiting width of the SymPol interval

• The no-collision estimate is uniform when the draw count k is between fixed multiples of √n.Source: §A.5 · pp. 32, 34
• For the interval-width analysis, the maximizing degree of the elementary symmetric mean lies asymptotically in [δ√n, M√n].Source: §A.5 · p. 35
• When σ = 0, Xi = μ almost surely.Source: §A.5 · p. 37