{'fraction_non_alphanumeric': 0.05968212779759974, 'fraction_numerical': 0.03589577251594767, 'mean_word_length': 4.107675317504142, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An improvement of Tusn\'ady's inequality in the bulk

We prove a non-asymptotic generalization of the refined continuity correction developed in Cressie (1978) for the Binomial distribution, which we then use to improve the versions of Tusn\'ady's inequality from Massart (2002) and Carter&Pollard (2004) in the bulk.


Introduction
Let Z ∼ Normal(0, 1), let Φ denote the cumulative distribution function (c.d.f.) of Z, and let F be the c.d.f. of the Binomial(m, 1/2) distribution. If where F (p) := inf{x ∈ R : F (x) ≥ p} denotes the generalized inverse distribution function (or quantile function) associated with F , then Tusnády's inequality refers to , for all m ∈ N.
(1.2) This inequality originated in G. Tusnády's PhD thesis, i.e., Tusnády (1977), although the author did not provide a complete proof. For the uninitiated reader, Tusnády's inequality (also called Tusnády's lemma) lies at the heart of the modern approach to the proof of the Komlós-Major-Tusnády (KMT) approximation of the empirical process by a sequence of Brownian bridges on the same probability space, which is one of the most important results of probability theory in the past 50 years. The original proof of the KMT approximation was given in Komlós et al. (1975Komlós et al. ( , 1976 who applied a diadic scheme together with a somewhat different quantile inequality, whereas (Csörgő & Révész, 1981, Chapter 4) presented a way to prove the KMT approximation using the diadic scheme with Tusnády's inequality instead (although they didn't prove the inequality either). A full proof of Tusnády's inequality first appeared in Bretagnolle & Massart (1989) who used it to improve the rate of convergence of the KMT approximation. Throughout the years, many other authors revisited the details of the proof of the KMT approximation such as Mason & van Zwet (1987), Major (2000) and Mason (2001), some of them (more recently) using some version of Tusnády's inequality such as (Csörgő & Horváth, 1993, Chapter 3), Massart (2002), (Dudley, 2005, Chapter 1) and Lawler & Trujillo Ferreras (2007). The KMT approximation has been extended to the multivariate setting in Einmahl (1989) and Zaitsev (1998), to the functional setting in Grama & Nussbaum (2002), and to the dependent setting in Berkes et al. (2014). For a review and new results on quantile coupling inequalities and their applications, we refer the reader to Mason & Zhou (2012) and references therein.
The proof of Tusnády's inequality proposed in the Appendix of Bretagnolle & Massart (1989) was considered to be highly technical and hard to read by the mathematical community, so it was later simplified in Massart (2002), who also improved (1.2) as follows: , for all m ∈ N. (1. 3) The main idea behind the proof of (1.3) is to sum up local comparisons between Binomial and Gaussian probabilities; the methods are elementary but it still requires a careful analysis. Around the same time as Massart, Carter & Pollard (2004) came up with a different approach to improve Tusnády's inequality. They applied Laplace's method to the integral representation of the survival function of X m ∼ Binomial(m, 1/2), i.e., ( 1.4) to give yet another version of Tusnády's inequality: where C, C > 0 are universal constants assumed large enough but whose explicit form is unknown. As pointed out in Massart (2002), the estimate (1.5) is not strictly comparable to (1.3): it is better asymptotically but the absolute constants are less precise. Massart also explains that improving the constant 3/4 to 1/2 is impossible but the optimal constant should be closer to 1/2 than 3/4. In particular, he conjectured that C = 1/2 + const./ √ m could potentially work by refining the approach in Carter & Pollard (2004).
In this paper, our goal is to improve both (1.3) and (1.5) under the restrictions that m is large enough (with an explicit threshold) and Z falls in the "bulk" of the standard normal distribution. The precise statement is in the theorem below, where we obtain the aforementioned 1/2 constant plus an asymptotically negligible residual, but the expansion is also more precise in terms of Z. Our approach to the proof is outlined in Section 2.
for one instance ω, as a function of m.

Our approach
The first main step in our proof of Theorem 1.1 is to establish a non-asymptotic expansion for the c.d.f. and survival function associated with the Binomial probabilities in terms of the c.d.f. and survival function of the normal distribution with the same mean and variance, i.e., Normal(mx, mx(1 − x)), the density of which is Note that (2.2) can also be written as 1 More specifically, if Φ and Ψ denote the c.d.f. and the survival function of the standard normal distribution, respectively, then our first goal is to obtain real numbers c m,x (a) and d m,x (a), as accurate as possible, such that, for some values a ∈ {0, 1, . . . , m}, These types of results are referred to as continuity corrections in the literature. In Theorem 2 of Cressie (1978), general expressions for c m,x (a) and d m,x (a) were found for any fixed a, using only elementary methods (Taylor expansions and Stirling's formula), but his results are asymptotic. Similarly to Massart (2002), although the details are very different, the idea of the proof in Cressie (1978) is to develop a local limit theorem for the Binomial distribution and sum up the approximated probabilities to get an estimate of the survival function in terms of the Gaussian survival function Ψ. One important difference is that the errors are additive in Cressie (1978), whereas they are multiplicative in Massart (2002) (and Carter & Pollard (2004)). Since Tusnády's inequality is generally valid for finite samples (with possibly an explicit lower bound on the parameter m), the results in Cressie (1978) are not sufficient for our purpose. To achieve our first goal, we will therefore prove a non-asymptotic version of (Cressie, 1978, Theorem 2), using the same elementary methods (see Theorem 2.1). However, compared to Cressie, we need to find exact bounds for every single error term that arises in the proof, which adds a significant layer of difficulty (this is apparent from the proof). Our approximation is also uniform for a in the bulk of the Binomial distribution and uniform for x in a compact set away from the boundary values 0 and 1, namely for a ∈ B m,x := k ∈ {0, 1, . . . , m} : max where τ ≥ 2 is a fixed parameter. Below is the precise statement: Theorem 2.1 (Non-asymptotic refined continuity correction). Let τ ≥ 2 be given, and let m be an integer satisfying m ≥ 10 3 ∨ (2 3/2 τ 3 ) and 41τ 3 exp − m 1/3 8τ ≤ 750 000 m −4/3 . (2.7) Then, uniformly for a ∈ B m,x and x ∈ X τ , we have (2.10) A direct consequence of (2.8) and (2.9) is that, uniformly for a + 1 ∈ B m,x and x ∈ X τ , we have The proof of Theorem 2.1 will follow by summing up approximated Binomial probabilities using the local limit theorem we develop in Lemma 3.1. By applying Equations (2.9) and (2.11) with the specific choices x = 1/2, τ = 2 and a = m 2 + t , we obtain the corollary below for the Binomial(m, 1/2) distribution, which is key for the proof of Theorem 1.1.
In the second main step of our proof, we will control the derivative of Φ with the mean value theorem and invert the role of t andz := √ m 2 z + 10 6 2 5 m −3/2 φ( √ log m) = (1 − 1 12m )s + 1 3m 2 s 3 in (2.13) using a Taylor expansion on the unique real solution of the cubic equation. From this, we will be able to deduce (2.14) By applying F on both sides, we get The statement of Theorem 1.1 will then follow by the symmetry of X m − m 2 and Z. Remark 2.3. As mentioned below (2.4), the errors throughout the paper are additive instead of multiplicative as in Massart (2002) and Carter & Pollard (2004). This is why we only need to control Φ (which is simply φ) in the second main step of the proof, instead of −(log Ψ) as in Carter & Pollard (2004). In a sense, we sacrifice a bit on the range of a's for which Theorem 2.1 holds, but the additivity of the errors makes the second main step of the proof of Theorem 1.1 much easier, which in turn allows us to be more precise with the expansion in terms of Z. This is why we can bring the constant 3/4 down to 1/2 + o(1) and get the extra correction factor Z−Z 3 24 √ m in (1.6), which doesn't appear in any other version of Tusnády's inequality.

Proofs
First, we prove a uniform and non-asymptotic generalization of the local limit theorem from Cressie (1978) (i.e., the refined version of Equation (2.4) in that paper). We have to be especially careful about the handling of the error terms.
Lemma 3.1 (Local limit theorem). Let τ ≥ 2 be given and let m ∈ N be such that m ≥ 10 3 ∨ τ 3/2 . Recall the definitions of B m,x and X τ from (2.5) and (2.6), respectively. Then, uniformly for k ∈ B m,x and x ∈ X τ , we have For good conscience, the terms in the braces in (3.1) coincide exactly with the ones in Result 4.1.10 of Govindarajulu (1965), which again is only asymptotic. The following remark will be useful to bound some expressions in the proof of Lemma 3.1 and Theorem 2.1.
By summing up the Binomial probabilities using the local limit theorem (Lemma 3.1), we can now approximate the survival function of the Binomial distribution.