pith. sign in

arxiv: 2508.03833 · v3 · pith:ZT4OCTPTnew · submitted 2025-08-05 · 🧮 math.ST · math.PR· stat.TH

Computable Bounds for Strong Approximations with Applications

Haoyu Ye , Morgane Austern This is my paper

Pith reviewed 2026-05-22 00:01 UTC · model grok-4.3

classification 🧮 math.ST math.PRstat.TH
keywords strong approximationKMT inequalitycomputable boundsbounded random variableschange point detectionhitting timesmoderate deviations
0
0 comments X

The pith

Bounded i.i.d. random variables admit computable KMT bounds depending only on range and deviation

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows how to make the celebrated KMT inequality computable for bounded i.i.d. random variables. The resulting bound has constants that are explicit functions of the range and the standard deviation, with an extra logarithmic factor in the error term. An empirical variant is also derived that maintains coverage when the standard deviation is estimated from the data. These results are applied to online change point detection and calculations of first hitting times, and yield a moderate deviation bound as a side result.

Core claim

The authors establish that for bounded i.i.d. random variables there exists a computable KMT-type inequality whose constants depend only on the range and standard deviation (or an empirical estimate thereof) at the cost of an extra logarithmic factor. The analysis also produces a Cramér-type moderate deviation bound for normalized centered partial sums.

What carries the argument

The computable KMT inequality with range-and-variance dependent constants that absorbs an extra log term to become explicit and usable.

Load-bearing premise

The variables are bounded and independently and identically distributed.

What would settle it

Finding a bounded i.i.d. sequence where the approximation error exceeds the bound by more than the logarithmic factor for large sample sizes, or observing that the empirical coverage in simulations is substantially lower than the nominal level.

Figures

Figures reproduced from arXiv: 2508.03833 by Haoyu Ye, Morgane Austern.

Figure 1
Figure 1. Figure 1: Detection rate comparison across mean shifts, with each [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Minimum value of N for which the upper bound in eq. (9) becomes non-trivial. 5 A Wasserstein-p bound for sequences sampled without re￾placement A main ingredient of algorithm 4 is our computable upper bound, ω R p (n, σ), for the Wasserstein-p distance between a partial sum and a normal distribution. To achieve this, we first adapt Theorem 5 13 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of our result with Bhattacharjee and Goldstein for various alphabet sizes [PITH_FULL_IMAGE:figures/full_fig_p060_3.png] view at source ↗
read the original abstract

The Koml\'os$\unicode{x2013}$Major$\unicode{x2013}$Tusn\'ady (KMT) inequality for partial sums is one of the most celebrated results in probability theory. Yet its practical application has been hindered by a lack of practical constants. This paper addresses this limitation for bounded i.i.d. random variables. At the cost of an additional logarithmic factor, we propose a computable version of the KMT inequality that depends only on the variables' range and standard deviation. We also derive an empirical version of the inequality that achieves nominal coverage even when the standard deviation is unknown. We then demonstrate the practicality of our bounds through applications to online change point detection and first hitting time probabilities. As a byproduct of our analysis, we obtain a Cram\'er-type moderate deviation bound for normalized centered partial sums.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a computable version of the Komlós–Major–Tusnády (KMT) strong approximation inequality for partial sums of bounded i.i.d. random variables. The bounds have explicit constants depending only on the range and standard deviation (or its empirical estimate), at the cost of an extra logarithmic factor. An empirical version is derived for unknown variance, and the results are applied to online change point detection and first hitting time probabilities. A Cramér-type moderate deviation bound for normalized centered partial sums is obtained as a byproduct.

Significance. If the explicit constants and the logarithmic penalty are correctly derived from the classical KMT result plus moderate-deviation tails, the work removes a major practical obstacle to using strong approximation bounds in statistical procedures. The applications to change-point detection and hitting times illustrate concrete utility, and the moderate-deviation byproduct may be of independent interest in probability theory.

major comments (2)
  1. [§3] §3 (moderate-deviation tail): the reduction to the worst-case distribution under the given range and variance constraints must be shown to produce a tail bound whose logarithmic factor is fully explicit and does not re-introduce dependence on higher moments; otherwise the claimed computability fails.
  2. [§5] Application to online change-point detection (likely §5): the nominal coverage statement for the empirical bound needs an explicit probability guarantee that accounts for the extra log factor; without it the detection threshold calibration is not justified.
minor comments (2)
  1. [Introduction] Notation for the range parameter and the empirical standard deviation estimator should be introduced with a dedicated display equation in the introduction or §2.
  2. [Abstract] The abstract states that the empirical version 'achieves nominal coverage'; this phrase should be replaced by a precise probabilistic statement (e.g., 'with probability at least 1−α−o(1)') to avoid ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive evaluation, and constructive suggestions. The comments help clarify the computability claims and strengthen the justification for the applications. We address each major comment below and have revised the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (moderate-deviation tail): the reduction to the worst-case distribution under the given range and variance constraints must be shown to produce a tail bound whose logarithmic factor is fully explicit and does not re-introduce dependence on higher moments; otherwise the claimed computability fails.

    Authors: We agree that explicit verification is needed to uphold the computability claim. The proof of the moderate-deviation bound proceeds by reducing to the extremal two-point distribution compatible with the given range and variance; the resulting tail is then bounded using a direct Chernoff-type calculation that yields an explicit logarithmic factor depending only on these parameters. To make this reduction fully transparent, we have added a new lemma (Lemma 3.2 in the revision) that states the worst-case tail explicitly and confirms the absence of higher-moment dependence. The revised Section 3 now includes this lemma and a short remark on how the logarithmic factor remains computable. revision: yes

  2. Referee: [§5] Application to online change-point detection (likely §5): the nominal coverage statement for the empirical bound needs an explicit probability guarantee that accounts for the extra log factor; without it the detection threshold calibration is not justified.

    Authors: We concur that an explicit coverage probability is required for rigorous threshold calibration. In the revised manuscript we have inserted a new proposition (Proposition 5.1) that supplies a precise lower bound on the coverage probability of the empirical strong-approximation bound. The statement explicitly incorporates the extra logarithmic factor arising from the KMT-type inequality and yields a concrete numerical guarantee (e.g., coverage at least 1−2α−o(1) for any fixed α). This proposition is then used to justify the detection threshold in the online change-point procedure, thereby addressing the referee’s concern. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation begins from the classical KMT inequality (an external result) and augments it with explicit tail bounds and coupling constructions that depend only on the stated assumptions of bounded i.i.d. variables, range, and variance. The moderate-deviation estimates are obtained by reducing to the worst-case distribution under moment constraints and applying standard quantile or Skorokhod techniques; none of these steps are defined in terms of the final bound or fitted to the target quantity. The paper therefore remains self-contained against external benchmarks with no load-bearing self-citation chains or self-definitional reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on the classical KMT inequality plus new explicit estimates; no free parameters or invented entities are visible in the abstract.

pith-pipeline@v0.9.0 · 5667 in / 1044 out tokens · 25260 ms · 2026-05-22T00:01:37.721071+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages · 3 internal anchors

  1. [1]

    Applied probability and queues

    Søren Asmussen. Applied probability and queues . Springer, 2003

    work page 2003

  2. [2]

    Efficient concentration with Gaussian approximation

    Morgane Austern and Lester Mackey. Efficient concentration with Gaussian approximation. arXiv preprint arXiv:2208.09922, 2023

    work page arXiv 2023

  3. [3]

    Change-point analysis in financial networks

    Sayantan Banerjee and Kousik Guhathakurta. Change-point analysis in financial networks. Stat, 9(1):e269, 2020

    work page 2020

  4. [4]

    Koml´ os–Major–Tusn´ ady approximation under dependence

    Istv´ an Berkes, Weidong Liu, and Wei Biao Wu. Koml´ os–Major–Tusn´ ady approximation under dependence. The Annals of Probability , 42(2):794–817, 2014

    work page 2014

  5. [5]

    On strong embeddings by Stein’s method

    Chinmoy Bhattacharjee and Larry Goldstein. On strong embeddings by Stein’s method. Electronic Journal of Probability, 21(none):1 – 30, 2016

    work page 2016

  6. [6]

    Rates in the Central Limit Theorem and diffusion approximation via Stein's Method

    Thomas Bonis. Rates in the Central Limit Theorem and diffusion approximation via Stein’s Method. arXiv preprint arXiv:1506.06966 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  7. [7]

    Stein’s method for normal approximation in wasserstein distances with application to the multivariate central limit theorem

    Thomas Bonis. Stein’s method for normal approximation in wasserstein distances with application to the multivariate central limit theorem. Probability Theory and Related Fields, 178(3):827–860, 2020

    work page 2020

  8. [8]

    Improved rates of convergence for the multivariate central limit theorem in wasser- stein distance

    Thomas Bonis. Improved rates of convergence for the multivariate central limit theorem in wasser- stein distance. arXiv preprint arXiv:2305.14248 , 2023

    work page arXiv 2023

  9. [9]

    Automatic change detection in multimodal serial MRI: application to multiple sclerosis lesion evolution

    Marcel Bosc, Fabrice Heitz, Jean-Paul Armspach, Izzie Namer, Daniel Gounot, and Lucien Rum- bach. Automatic change detection in multimodal serial MRI: application to multiple sclerosis lesion evolution. NeuroImage, 20(2):643–656, 2003

    work page 2003

  10. [10]

    Simulation of Brownian motion at first-passage times

    Zaeem A Burq and Owen D Jones. Simulation of Brownian motion at first-passage times. Math- ematics and Computers in Simulation , 77(1):64–71, 2008

    work page 2008

  11. [11]

    Bounds on the running maximum of a random walk with small drift

    Ofer Busani and Timo Sepp¨ al¨ ainen. Bounds on the running maximum of a random walk with small drift. arXiv preprint arXiv:2010.08767 , 2020

    work page arXiv 2010

  12. [12]

    A new approach to strong embeddings

    Sourav Chatterjee. A new approach to strong embeddings. Probability Theory and Related Fields, 152(1-2):231–264, 2012

    work page 2012

  13. [13]

    Inference of breakpoints in high-dimensional time series

    Likai Chen, Weining Wang, and Wei Biao Wu. Inference of breakpoints in high-dimensional time series. Journal of the American Statistical Association , 117(540):1951–1963, 2022

    work page 1951

  14. [14]

    Some applications of first-passage ideas to finance, 2013

    R´ emy Chicheportiche and Jean-Philippe Bouchaud. Some applications of first-passage ideas to finance, 2013

    work page 2013

  15. [15]

    Sharp bounds on the absolute moments of a sum of two iid random variables

    David C Cox and Johannes HB Kemperman. Sharp bounds on the absolute moments of a sum of two iid random variables. The Annals of Probability , pages 765–771, 1983

    work page 1983

  16. [16]

    Simulation of first-passage times for alternating Brownian motions

    Antonio Di Crescenzo, Elvira Di Nardo, and LM Ricciardi. Simulation of first-passage times for alternating Brownian motions. Methodology and Computing in Applied Probability , 7(2):161–181, 2005

    work page 2005

  17. [17]

    Bounds for the absolute third moment

    Carl-Gustav Esseen. Bounds for the absolute third moment. Scandinavian Journal of Statistics , pages 149–152, 1975

    work page 1975

  18. [18]

    Multiscale change point inference

    Klaus Frick, Axel Munk, and Hannes Sieling. Multiscale change point inference. Journal of the Royal Statistical Society Series B: Statistical Methodology , 76(3):495–580, 2014

    work page 2014

  19. [19]

    Random walk models for the spike activity of a single neuron

    George L Gerstein and Benoit Mandelbrot. Random walk models for the spike activity of a single neuron. Biophysical journal, 4(1):41–68, 1964

    work page 1964

  20. [20]

    Neuronal dynamics: From single neurons to networks and models of cognition

    Wulfram Gerstner, Werner M Kistler, Richard Naud, and Liam Paninski. Neuronal dynamics: From single neurons to networks and models of cognition . Cambridge University Press, 2014. 16

    work page 2014

  21. [21]

    Bayesian online change point detection in finance

    Reza Habibi. Bayesian online change point detection in finance. Financial Internet Quarterly , 17(4):27–33, 2021

    work page 2021

  22. [22]

    Cumulative sum charts and charting for quality im- provement

    Douglas M Hawkins and David H Olwell. Cumulative sum charts and charting for quality im- provement. Springer Science & Business Media, 2012

    work page 2012

  23. [23]

    Dynamic Probabilistic Systems, Volume I: Markov Models , volume 1

    Ronald A Howard. Dynamic Probabilistic Systems, Volume I: Markov Models , volume 1. Courier Corporation, 2012

    work page 2012

  24. [24]

    Brownian motion and stochastic calculus , volume 113

    Ioannis Karatzas and Steven Shreve. Brownian motion and stochastic calculus , volume 113. Springer Science & Business Media, 2012

    work page 2012

  25. [25]

    Dynkin ′ s Games and Israeli Options

    Yuri Kifer. Dynkin ′ s Games and Israeli Options. International Scholarly Research Notices , 2013(1):856458, 2013

    work page 2013

  26. [26]

    An approximation of partial sums of independent RV’-s, and the sample DF

    J´ anos Koml´ os, P´ eter Major, and G´ abor Tusn´ ady. An approximation of partial sums of independent RV’-s, and the sample DF. I. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 32(1):111–131, 1975

    work page 1975

  27. [27]

    An approximation of partial sums of independent RV’s, and the sample DF

    J´ anos Koml´ os, P´ eter Major, and G´ abor Tusn´ ady. An approximation of partial sums of independent RV’s, and the sample DF. II. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 34(1):33–58, 1976

    work page 1976

  28. [28]

    A jump-diffusion model for option pricing

    Steven G Kou. A jump-diffusion model for option pricing. Management science, 48(8):1086–1101, 2002

    work page 2002

  29. [29]

    First exit time of a random walk from the bounds f(n) ± cg(n), with applications

    TL Lai and RA Wijsman. First exit time of a random walk from the bounds f(n) ± cg(n), with applications. The Annals of Probability , 7(4):672–692, 1979

    work page 1979

  30. [30]

    Optimal stopping and embedding

    Damien Lamberton and LCG Rogers. Optimal stopping and embedding. Journal of applied probability, 37(4):1143–1148, 2000

    work page 2000

  31. [31]

    Sequential change-point detection: Laplace concentration of scan statistics and non-asymptotic delay bounds

    Odalric-Ambrym Maillard. Sequential change-point detection: Laplace concentration of scan statistics and non-asymptotic delay bounds. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pages 610–632. PMLR. ISSN: 2640-3498

    work page

  32. [32]

    The approximation of partial sums of independent rv’s

    P´ eter Major. The approximation of partial sums of independent rv’s. Zeitschrift f¨ ur Wahrschein- lichkeitstheorie und verwandte Gebiete , 35(3):213–220, 1976

    work page 1976

  33. [33]

    Online Bayesian change point detection algorithms for segmentation of epileptic activity

    Rakesh Malladi, Giridhar P Kalamangalam, and Behnaam Aazhang. Online Bayesian change point detection algorithms for segmentation of epileptic activity. In 2013 Asilomar conference on signals, systems and computers , pages 1833–1837. IEEE, 2013

    work page 2013

  34. [34]

    Sharp empirical Bernstein bounds for the variance of bounded random variables

    Diego Martinez-Taboada and Aaditya Ramdas. Sharp empirical Bernstein bounds for the variance of bounded random variables. arXiv preprint arXiv:2505.01987 , 2025

    work page internal anchor Pith review arXiv 2025

  35. [35]

    Quantile coupling inequalities and their applications

    David M Mason and Harrison H Zhou. Quantile coupling inequalities and their applications. 2012

    work page 2012

  36. [36]

    Sequential Gaussian approximation for nonstationary time series in high dimensions

    Fabian Mies and Ansgar Steland. Sequential Gaussian approximation for nonstationary time series in high dimensions. Bernoulli, 29(4):3114–3140, 2023

    work page 2023

  37. [37]

    Introduction to statistical quality control

    Douglas C Montgomery. Introduction to statistical quality control . John wiley & sons, 2020

    work page 2020

  38. [38]

    Some inequalities for the distribution of sums of independent random variables

    SV Nagaev and IF Pinelis. Some inequalities for the distribution of sums of independent random variables. Theory of Probability & Its Applications , 22(2):248–256, 1978

    work page 1978

  39. [39]

    Asymptotic equivalence of density estimation and Gaussian white noise

    Michael Nussbaum. Asymptotic equivalence of density estimation and Gaussian white noise. The Annals of Statistics , pages 2399–2430, 1996

    work page 1996

  40. [40]

    A note on Burkholder-Rosenthal inequality

    Adam Osekowski. A note on Burkholder-Rosenthal inequality. Bull. Pol. Acad. Sci. Math , 60(2):177–185, 2012

    work page 2012

  41. [41]

    Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality

    Felix Otto and C´ edric Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Functional Analysis , 173(2):361–400, 2000. 17

    work page 2000

  42. [42]

    Continuous inspection schemes

    Ewan S Page. Continuous inspection schemes. Biometrika, 41(1/2):100–115, 1954

    work page 1954

  43. [43]

    Probability bounds for first exits through moving boundaries

    Stephen Portnoy. Probability bounds for first exits through moving boundaries. The Annals of Probability, pages 106–117, 1978

    work page 1978

  44. [44]

    System reliability theory: models, statistical methods, and applications, volume 396

    Marvin Rausand and Arnljot Hoyland. System reliability theory: models, statistical methods, and applications, volume 396. John Wiley & Sons, 2003

    work page 2003

  45. [45]

    Moment inequalities for sums of dependent random variables under projective conditions

    Emmanuel Rio. Moment inequalities for sums of dependent random variables under projective conditions. Journal of Theoretical Probability, 22(1):146–163, 2009

    work page 2009

  46. [46]

    A remark on Stirling’s formula

    Herbert Robbins. A remark on Stirling’s formula. The American mathematical monthly, 62(1):26– 29, 1955

    work page 1955

  47. [47]

    On the accuracy of normal approximation in the invariance principle

    Aleksandr Ivanovich Sakhanenko. On the accuracy of normal approximation in the invariance principle. Matematicheskie Trudy, 13:40–66, 1989

    work page 1989

  48. [48]

    Stochastic calculus for finance II: Continuous-time models , volume 11

    Steven E Shreve et al. Stochastic calculus for finance II: Continuous-time models , volume 11. Springer, 2004

    work page 2004

  49. [49]

    Staudacher, S

    M. Staudacher, S. Telser, A. Amann, H. Hinterhuber, and M. Ritsch-Marte. A new method for change-point detection developed for on-line analysis of the heart beat variability during sleep. Physica A: Statistical Mechanics and its Applications , 349(3):582–596, 2005

    work page 2005

  50. [50]

    Probability and statistics with reliability, queuing, and computer science appli- cations

    Kishor S Trivedi. Probability and statistics with reliability, queuing, and computer science appli- cations. John Wiley & Sons, 2001

    work page 2001

  51. [51]

    Survival Multiarmed Bandits with Bootstrapping Methods

    Peter Veroutis and Fr´ ed´ eric Godin. Survival Multiarmed Bandits with Bootstrapping Methods. arXiv preprint arXiv:2410.16486 , 2024

    work page arXiv 2024

  52. [52]

    American Mathematical Soc., 2003

    C´ edric Villani.Topics in Optimal Transportation, volume 58. American Mathematical Soc., 2003

    work page 2003

  53. [53]

    The rate of convergence of the binomial tree scheme

    John B Walsh. The rate of convergence of the binomial tree scheme. Finance and Stochastics , 7(3):337–361, 2003

    work page 2003

  54. [54]

    Learning from dependent obser- vations

    Ian Waudby-Smith, Edward H Kennedy, and Aaditya Ramdas. Distribution-uniform anytime- valid sequential inference. arXiv preprint arXiv:2311.03343 , 2023

    work page arXiv 2023

  55. [55]

    Nonasymptotic and distribution- uniform Koml´ os–Major–Tusn´ ady approximation.arXiv preprint arXiv:2502.06188 , 2025

    Ian Waudby-Smith, Martin Larsson, and Aaditya Ramdas. Nonasymptotic and distribution- uniform Koml´ os–Major–Tusn´ ady approximation.arXiv preprint arXiv:2502.06188 , 2025

    work page arXiv 2025

  56. [56]

    Estimating means of bounded random variables by betting

    Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology , 86(1):1–27, 2024

    work page 2024

  57. [57]

    Some current directions in the theory and application of statistical process monitoring

    William H Woodall and Douglas C Montgomery. Some current directions in the theory and application of statistical process monitoring. Journal of quality technology , 46(1):78–94, 2014

    work page 2014

  58. [58]

    Adaptive change detection in heart rate trend monitoring in anesthetized children

    Ping Yang, Guy Dumont, and John Mark Ansermino. Adaptive change detection in heart rate trend monitoring in anesthetized children. IEEE transactions on biomedical engineering , 53(11):2211–2219, 2006

    work page 2006

  59. [59]

    Estimates for the strong approximation in multidimensional central limit theorem

    A Yu Zaitsev. Estimates for the strong approximation in multidimensional central limit theorem. arXiv preprint math/0304373 , 2003. 18 A Notations We recall some notations used throughout the paper. Let ( Yi)i≥1 be a sequence of i.i.d. random variables with E[Y1] < ∞, Var(Y1) = σ2, and 0 ≤ Yi ≤ R almost surely. Define Xi = Yi − E[Yi] for i ≥ 1. Then ( Xi)...

    work page internal anchor Pith review Pith/arXiv arXiv 2003

  60. [60]

    Hence, according to the- orem 2.2, there exists ˜Z := ( ˜Zk)0≤k≤n with the same covariance as ( Wk), such that the following inequality holds: P(∃k ≤ n s.t

    ≤ α. Hence, according to the- orem 2.2, there exists ˜Z := ( ˜Zk)0≤k≤n with the same covariance as ( Wk), such that the following inequality holds: P(∃k ≤ n s.t. Wk − ˜Zk ≥ ∆k(α)) ≤ βL(ν∗

    work page

  61. [61]

    Proof of theorem 2.4

    ≤ α. Proof of theorem 2.4. A direct consequence of theorem 2.3 combined with corollary 2.2.1. 44 E Proof of proposition 3.1 Proof. Define ˜Wk := σ−1Wk and ˜Sk := σ−1Sk. Using theorems 2.3 and 2.4 we know that there exists centered Gaussian vectors ( ˜Z ∗ k), (Z ∗ k) that have the same variance as respectively ( ˜Wk) and ( ˜Sk) such that P ∃k ≤ n s.t. | ˜S...

    work page

  62. [62]

    for all k ∈ (n1, n2]. Set ˜δ∗ n2(α) := δ⋆(α∗ 1) return ( ˜∆k(α))k∈(n1,n2], ˜δ∗ n2(α) H.2 Alternative algorithms mentioned in remark 2.5 In this subsection we will let ( Cℓ) be a sequence of prespecified constants; and ( ζi(·)) be any functions such that P |Wn/2 − ˜Zn/2| ≥ ζn/2(α) ≤ α ∀α ∈ (0, 1), n ∈ N. For example we can choose Cℓ = βℓ for some β > 1 and...

    work page

  63. [63]

    < α // Step 2: Calculate intermediate δM k values using ν∗ 0 δ0 1 ← 0 for M = 1 to L do δM 2M −1 ← min min2≤p ωR p (2M ,σ) (CM ν∗ 0 )1/p , ζM(CM ν∗ 0)) for k = 1 to 2M −1 do δM k ← δM −1 k + k 2M −1 δM 2M −1 for k = 2M −1 + 1 to 2M − 1 do δM k ← δM −1 2M −k + 2M −k 2M −1 δM 2M −1 Let δL k denote the final values δL k from this step. for k = 1 to 2L do ∆k(...

    work page

  64. [64]

    Proposition H.1

    + k n δ⋆(α∗ 1) // Step 3: Return optimized thresholds return (Dk(α))k≤n It is a straightforward to check that the output of these algorithms give us the same guarantees than we have for algorithms 1 and 2. Proposition H.1. Assume that the conditions of theorem 2.4 hold. Let α > 0 and L ∈ N. Set n = 2L. Define (∆b k(α)) and (Db k(α)) as the output of respe...

    work page

  65. [65]

    We introduce the following notations • D = {b − a : a, b ∈ A} and D+ = D ∩ [0, ∞), • Define q = |D+| + 1, D = 1 2 P d∈D+ d, and Q :=P d∈D+ d2

    = 0. We introduce the following notations • D = {b − a : a, b ∈ A} and D+ = D ∩ [0, ∞), • Define q = |D+| + 1, D = 1 2 P d∈D+ d, and Q :=P d∈D+ d2. • Wk,d := 1 n P i≤k j>n (Xi − Xj)I(|Xi − Xj| = d). Theorem J.1 (Theorem 2.2 of [5]) . For n ≥ 1, let (Yi) be random variables that satisfy section 2.1 and that are in addition assumed to take values in A ⊂ R. ...

    work page

  66. [66]

    = 0. There exists a constant A such that there exists a constant λ > 0 such that for any positive integer n, it is possible to construct a version of the sequence (Sk)0≤k≤n and Gaussian random variables (Zk)0≤k≤n with mean zero and Cov(Zi, Zj) = i ∧ j on the same probability space such that E exp(λ|Sn − Zn|) ≤ A and E exp λ max 0≤k≤n |Sk − Zk| ≤ A exp(A l...

    work page

  67. [67]

    Lemma K.2 (Generalization of Rosenthal inequality with explicit constants)

    (54) The subadditivity of the p-th root now implies the result. Lemma K.2 (Generalization of Rosenthal inequality with explicit constants). The following inequality holds for all p > 2: 1 2n k X k<i≤n (X2 i − 1) + (n − k) X 1≤i≤k (X2 i − 1) p ≤ p k(n − k) 2√n min (√p − 1(R2 s − 1)1−1/p Ap p R2s − 1 + A∗ n,p(R2 s − 1)1−1/p. where recall that Ap := 21/pp p/...

    work page