Explicit error bounds for lattice Edgeworth expansions
J.P. Buhler, A.C. Gamst, R.L. Graham, and A.W. Hales

arXiv:1710.08845v1 [math.ST] 24 Oct 2017

October 25, 2017
Abstract
Motivated, roughly, by comparing the mean and median of an IID sum of bounded
lattice random variables, we develop explicit and effective bounds on the errors involved in the one-term Edgeworth expansion for such sums.

Let X be a bounded integer-valued random variable (these will occasionally be referred
to below as “dice”), and let X[n] denote the sum of n independent and identically distributed (IID) copies of X (sometimes referred to as “rolls”). If px denotes Pr(X = x),
then we say that x is a value of X if px > 0, and the mean of X is
X
E X = µ1 (X) = µ1 =
x px ,
x

the higher (central) moments of X are µk (X) = µk = E (X − µ1 )k , and the standard
deviation σ = σ(X) is the square root of µ2 . (Here, and below, the random variable X is
omitted from the notation if it can be inferred easily from context.)
The tilt of X is
T (X) := Pr(X > µ1 ) − Pr(X < µ1 ).
Modulo the annoying question of the precise definition of the median, the sign of T measures
whether the median is to the right or left of the mean. The primary focus of this paper is
on the sign of the tilt of X[n] for large n, which will be denoted
Tn = Tn (X) = T (X[n]).
As n goes to infinity the Central Limit Theorem says that the distribution of X[n], suitably
shifted and scaled, converges to the standard normal distribution. This implies that the
tilt goes to zero as n goes to infinity, and this will require us to accurately estimate Tn
in order to say anything at all about its sign. This will be done by using the one-term
Edgeworth expansion (an asymptotic refinement of the Central Limit Theorem) for lattice
random variables. The key goal of this paper is to prove explicit formulas for the error in
these approximations sufficient to enable the determination of the sign of Tn , for all n.
It turns out that the sign of Tn for large n depends on the third moment µ3 (associated
with the “skew” or “tilt” of the distribution) but also, perhaps more surprisingly, on the
congruence class of n modulo the so-called “span” of X. We will see that for large n the
sign of the tilt is (almost always) completely determined by these two pieces of data.
1

To make this more precise, it is convenient to make some definitions. The span of a die
X is the largest integer b such that all values of X are contained in a single congruence
class modulo b, i.e., an arithmetic progression of the form a + bn, for n ∈ Z. The integer
a is called a shift of X, and it is only well-defined modulo b. It isn’t hard to see that the
span is the gcd (greatest common divisor) of all x − a as x ranges over the values of X.
(For the span to be nonzero, X has to have at least two values, and we will always assume
that this is the case.)
If x is an integer and b is any positive integer then let x mod b denote the unique integer
congruent to x modulo b that is in the interval [0, b).
Theorem 1. Let X, σ, a, b, and µ3 be as above. Then for positive integers n,
L(na)
+E
Tn = √
2πn
where
L(c) =
and

µ3
(−c) mod b − c mod b
− 3,
σ
3σ
√
E = o(1/ n).

Note that L(na) only depends on the congruence class of√n modulo b, and that if n
goes to infinity in a fixed congruence class then the limit of 2πn Tn exists and is equal
to L(na). The error E will turn
to be bounded by terms that are, roughly, constant
√ out
p
multiples of 1/n and exp(−c n)/n for various c and p.
Proofs of the lattice Edgeworth expansions in the literature do not seem to include
explicit error bounds on the error E, and our goal is to exhibit such bounds, for bounded
lattice random variables. Such bounds are necessary if one wants to find an n0 together
with a proof that
n ≥ n0 , an ≡ c mod b imply that sign(Tn ) = sign(L(c)).
Briefly, one could say that “asymptopia” has arrived when the sign of Tn is equal to its
asymptotic sign.
This question arose for us in [BGH16] where the existence of “maximally intransitive”
dice was shown. We1 felt that it should be possible to determine when asymptopia arrives, i.e., when the desired dominance relation between the dice constructed in [MID] was
absolutely guaranteed for n ≥ n0 (see that article for details).
It is possible for L(c) to be zero, though “unlikely” if X is not symmetric. In this case,
higher order Edgeworth expansions are necessary, and this case will be left to the motivated
and energetic reader.
No prior understanding of Edgeworth expansions is required to read this paper, and we
consider only a specific case. For a broader perspective, the reader could consult [Fel71],
[Pet95], [BR10]. The techniques described here should be applicable more generally.
The first section below develops some of the basic ideas necessary needed to approximate
Pr(X[n] < 0). The second section proves such an approximation, together with explicit
error bounds. The third section applies this to prove a refined version of Theorem 1, and
looks at examples.
1

Well, especially RLG

2

1

Preliminaries

It is convenient to focus on the case of real-valued X with mean 0 and span 1. If Y is a
die with span b then
Y − µ1 (Y )
X :=
b
is a bounded lattice random variable with mean 0 and span 1, which says that the values
of X lie in a lattice a + Z but are not contained in a larger lattice a + dZ, d > 1. The tilt
is invariant under affine transformations X → bX + a so Tn (Y ) = Tn (X). It is convenient
to fix this situation from now on: X will be a random variable with span 1, mean 0, and
shift a. If X arises from dice as above then the shift a is a rational number. In this case it
might make sense to take a limit as n goes to infinity through a set of values where {na}
is fixed. Here {x} denotes the fractional part of x, i.e., the unique y such that x = y + j
for some integer j, and 0 ≤ y < 1. However, the explicit estimates apply for irrational a
and an arbitrary n, and may be useful in other contexts.
The central limit theorem says that √
the cumulative probability distribution of the normalized random variable Zn := X[n]/(σ n) approaches that of a standard normal random
variable in the sense that
Z s
1
2
e−t /2 dt,
for all s ∈ R.
lim Pr (Zn ≤ s) = √
n→∞
2π −∞
Our interest in the tilt suggests focusing on the mean s = µ1 (Zn ) = 0. Then limn→∞ Pr (Zn ≤ 0) =
1/2. The Berry-Esseen Theorem gives an explicit bound on the error, i.e., in the case s = 0,
c
|Pr (Zn ≤ 0) − 1/2| ≤ √
n
for a small
√ constant c, e.g., c = 3 in [Fel71]. However, it is easy to show that the tilt Tn
is O(1/ n), so the Berry-Esseen level of accuracy is insufficient for saying anything about
the tilt The central result of this paper is of the form


`
Pr (Zn ≤ 0) − 1/2 + √
≤ E(n).
n
Here ` depends on on the second, third, and fourth moments of X and the fractional part
{na}. The error E is bounded by an expression whose principal term is of the form d/n,
γ
with about 7 other terms that are each of the form λe−τ n /nρ for various constants λ, τ ,
ρ, and γ. Although this is a very special case of the central limit theorem, the techniques
should apply more generally.
As will be seen, this explicit bound on the error in the simplest non-trivial Edgeworth
expansion allows us to prove theorems about the sign of the tilt.
Readers might remember that the skewness of the distribution of X[n] depends on the
third moment of X. This is reflected in the term µ3 /3σ 3 of L(c) in Theorem 1. One
intuitive way to see that the third moment and asymptotic tilt might have opposite signs
is that for large n the distribution of X[n] should be approximately normal, and if the
median is slightly negative then the positive values have to be somewhat larger to make
the mean equal to 0, so the third moment will be positive.
3

The other term in L(c), which becomes ({−na} − {na})/σ in the span 1 case, shows
that for lattice random variables the third moment does not give the full story. This term is
sometimes called the lattice correction term. To get an intuitive feel for this term, consider
a lattice random variable X of span 1 and shift a with mean and third moment equal to 0
(a simple linear algebra exercise shows that these are easy to come by). Since µ3 = 0 the
lattice correction term is the only term. The support of the probability distribution of
X[n] is contained in the set of real numbers x that are congruent to na modulo 1. For
large n, the probability distribution is close to a re-scaled version of the standard normal
distribution. To first order, it seems reasonable to suspect that if c = na is less than 1/2
then the sum of the probabilities px = Pr(X = x) for {x} = c, x > 0, will be slightly
greater than the corresponding sum for x < 0 since the latter contribute more heavily to
making the mean 0, which tends to make the tilt positive.
Of course the explicit formula for L(c) emerges cleanly from the calculations below, and
perhaps this supersedes all of these heuristic remarks!

1.1

The characteristic function

As above, fix X with mean 0, span 1, shift a, central moments µk , and standard deviation σ
defined by σ 2 = µ2 . The goal of this section is to give a formula for Pr(X[n]) < 0 in terms
of an integral. This formula can be proved fairly directly using Fourier series, but we will
take a somewhat more leisurely approach that starts with a contour integral.
The probability generating function (PGF) of X is a function of a complex variable z
defined by
X
X
px z x = z a
F (z) = E z X =
pa+j z j ,
x

j

using the fact that values of X can be written x = a + j for some integer j. Note that
z −a F (z) is a finite Laurent series:
X
X
px z x−a =
pa+j z j .
z −a F (z) =
x

j

Applying Cauchy’s Theorem gives
j

pa+j = Pr(X = a + j) = [z ] z

−a

1
F (z) =
2πi

I
γ

z −a F (z) dz
zj
z

where [z j ]z −a F (z) denotes the coefficient of z j in the polynomial z −a F (z), and the contour
γ can be chosen to be a counterclockwise circle around the origin.
With an eye to ultimately applying this to the tilt, we use this integral to find a useful
expression for Pr(X < 0). The set of negative values x = a + j is the set of {a} + j as
j ranges over negative integers (where {a} is the fractional part of a, defined above; this
might reasonably be denoted a mod 1). Therefore,
I
X

1
dz
Pr(X < 0) =
p{a}+j =
z + z 2 + z 3 . . . z −{a} F (z)
2πi
z
j<0
I 1−{a}
1
z
F (z) dz
=
2πi
1−z
z
4

where the radius is less than 1 to ensure that
P the geometric series converges.
If n is a positive integer and X[n] :=
Xi , where the Xi are n independent random
variables, then independence implies that the PGF of X[n] is F (z)n . Applying the preceding
formula to X[n] gives
1
Pr(X[n] < 0) =
2πi

z 1−{na} F (z)n dz
1−z
z

I

where the contour is a counterclockwise circle around the origin of radius slightly less
than 1.

Move the contour outward to the unit circle except for an infinitesimal semicircular divot
centered at, and to the left of, 1. In other words, the contour follows the unit circle
counterclockwise from z = eiε to z = e−iε followed by a clockwise small circular arc back
to eiε . For very small ε the integrand is close to −1/(z − 1), and the contour is basically
a small clockwise semicircle; Cauchy’s Theorem implies that the value of the integral over
the divot is very close to 1/2. Taking the limit as ε goes to zero gives
1
1
Pr(X[n] < 0) = +
2 2πi

I

z 1−{na} F (z)n dz
1−z
z

where the contour is the unit circle punctured at z = 1, with the “principal value interpretation” at the puncture. With an eye to changing variables by z = eit , let
X
f (t) = F (eit ) = E eitX =
px eitx
x

be the characteristic function (CF) of X. Then
Z π
1
dt
1
eiαt f (t)n D(t)
Pr(X[n] < 0) = −
2 2πi −π
t
where α = αn = 1/2 − {na} and
D(t) = (t/2)/ sin(t/2).
The principal value interpretation of the integral at t = 0 will always be used, which means
that
Z −ε Z π 
Z π
:= lim
−π

+

ε→0

−π

.
ε

The following result summarizes the above discussion.
5

Theorem 2. With the above notation,
Pr(X[n] < 0) = 1/2 − I0 ,

1
where I0 :=
2πi

Z

π

eiαt f (t)n D(t)

−π

dt
.
t

(1)

In addition, if α0 = 1/2 − {−na}, then
Z π
Z π
1
1
dt
dt
0
iαt
n
Tn =
e f (t) D(t) −
eiα t f (−t)n D(t) .
2πi −π
t
2πi −π
t
The last statement of the theorem follows easily from the first, using several obvious
facts: (1) Pr(X[n] > 0) = Pr((−X)[n] < 0), (2) α0 is the shift of −X, and (3) the CF
of −X is f (−t).
For later use, we remark that D(t) is even, has D(0) = 1, D(π) = π/2, and has power
series coefficients that can be expressed in terms of Bernoulli numbers and are positive.
From that, or alternately by a simple calculus exercise, it follows D(t) is increasing on [0, π]
so that
D(t) ≤ D(π) = π/2
on
[−π, π].
(2)

1.2

Span

As above, X has span 1, mean 0, shift a, and CF f (t).
Lemma 3. There are integers cx , one for each value x of X, such that
X
X
cx x = 1.
cx = 0, and
x

x

Proof. Let y be a value of X. If b := gcd({x − y}) is larger than 1 then the values of X
are contained in y + bZ which contradicts the fact that X has span 1. Therefore, the gcd
is 1 and there are integers cx , for x 6= y, such that
X
cx (x − y) = 1.
P
Set cy = − x6=y cx . The stated properties are easily verified.
A set {cx } as in the lemma is said to be a certificate of the fact that X has span 1.
Lemma 4. The function |f (t)| has period 2π, and |f (t)| < 1 for t ∈ (0, 2π).
Proof. We can assume that the shift a is a value of X. Since
X
f (t) = eiat
px eit(x−a)
x

and the x − a are all integers it follows that |f (t + 2π)| = |f (t)|, and that the period of
|f (t)| is of the form 2π/b for some positive integer b. Then
1 = |f (2π/b)| = ei2πa/b

X

px e2πi(x−a)/b ≤

X

px = 1.

x

Equality in this use of the triangle inequality implies that all eπi(x−a)/b are equal to 1, i.e.,
that all x − a are multiples of b. If b > 1 then this contradicts the fact that the span of X
is equal to 1.
6

These lemmas show that if the span is 1 then gcd({x − x0 }) = 1, X has a certificate,
and |f (t)| has period 2π. It is not hard to show that any of these implies that the span
is 1, so all four conditions are equivalent.

1.3

Bounding CF power series tails

The power series of the CF for X converges for all real t, and has the form
f (t) =

X

px eitx =

x

X

µk

k≥0

µ2 t2
µ3 t3 µ4 t4
(it)k
=1−
−i
+
+ ....
k!
2
6
24

(3)

The tail of this power series has an especially tight bound, saying that the remainder after
k terms is at most the absolute value of the next term with the moment replaced by the
corresponding absolute moment.
Lemma 5. Let µk = E |X|k denote the k th absolute moment of X. Then
X µj (it)j
j≥k

j!

≤

µk |t|k
.
k!

Proof. The expansion
X (it)j
(it)k
+ θ(t)
,
e =
j!
k!
0≤j<k
it

|θ(t)| ≤ 1,

follows from several standard integral forms of the remainder in Taylor’s Theorem. Replace
t by tx, where x is a value of X, multiply by px , and sum over all values x to arrive at
f (tx) =

XX
j<k

x

px

(itx)j X
(itx)k X (it)j X
(itx)k
+
θ(tx)px
=
µj
+
θ(tx)px
.
j!
k!
j!
k!
x
x
j<k

Taking the absolute value of the remainder gives the bound
X
x

k
X
(itx)k
k |t|
θ(tx)px
≤
px |x|
= µk |t|k /k!
k!
k!
x

as claimed.

1.4

Bounding the CF

P
Fix a certificate {cx }, as above, and let C = x |cx | be its `1 norm. Note that C ≥ 2 since
at least two of the integers cx are nonzero. Before proving a bound on the CF f (t) outside
a neighborhood of 0, a preliminary lemma is needed.
Lemma 6. If 0 < t < π then no interval on the circle of arc length less than 2t/C contains
eitx for all values x of X.
7

Proof. Suppose, to the contrary, that all eitx lie in the interior of the arc from eiu to ei(u+2t/C)
on the circle. (Since 2t/C < π the interior is well-defined — it is the smaller of the arcs
into which those two points divide the circle.) Then there are integers jx such that
u < tx + 2πjx < u + 2t/C .
Subtract u + t/C to get
−t/C < tx + 2πjx − u − t/C < t/C.
Multiply by cx and sum, noting that the inequalities reverse if cx is negative, to get
P
P
|cx |t
− |cx |t
< t + 2πM <
=t
−t =
C
C
for some integer M . If M is nonnegative the right inequality is false, and if M is negative
the left inequality is false. This finishes the proof of the lemma.
Theorem 7. Let X be a random variable as above, and f (t) its CF. Let m := min{px } be
the minimum probability of a value. If |t| ≤ π then
|f (t)| ≤ 1 −

8mt2
.
π2C 2

Proof. By the preceding Lemma there are two values x, y such that x < y and the “arclength” distance between eitx and eity on the unit circle is at least 2t/C and at most π,
i.e.,
2t
≤ ty − tx ≤ π.
C
Then
X
pu eitu = T + meitx + meity ,
f (t) =
u

where T is a trigonometric sum with nonnegative coefficients that sum to 1 − 2m, and
therefore

|f (t)| ≤ 1 − 2m + meit(x+y)/2 eit(x−y)/2 + eit(y−x)/2
= 1 − 2m + 2m cos(t(y − x)/2)
≤ 1 − 2m + 2m cos(t/C) = 1 − 2m(1 − cos(t/C))
= 1 − 4m sin2 (t/2C).
Since x/ sin(x) is increasing on [0, π/4] it follows that
√
2t
t sin(π/4)
=
.
sin(t/2C) ≥
2C π/4
πC
Thus
1 − 4m sin2 (t/2C) ≤
finishing the proof.
8

8mt2
,
π2C 2

A similar bound |f (t)| ≤ 1 − dt2 can be found in [Ben75], for a completely different
constant d (not consistently better or worse than the constant in the above theorem).
In addition a technique is given in [Ben75] to improve the bound when there are several
independent certificates, and that idea also applies to our bound. Note that from (3) it is
clear that any such constant has to be strictly smaller than µ2 /2. Later we will see how
to, for practical purposes, find bounds that, roughly, say that in a practical context the
constant can be made as close to µ2 /2 as desired.

1.5

Facts about the Gamma function

Several facts about values of the Gamma function (and its upper and lower variants) at
integers and half-integers will be needed below. To slightly complicate matters, these will
arise here as integrals of functions of the form of tx exp(−ct2 /2). It is convenient to collect
these in one place for the sake of future reference. In the Proposition below the “double
factorial” x!! of a nonnegative integer denotes the product of all positive integers up to x
that have the same parity as x, i.e.,
Y
x!! =
(x − 2k).
0≤k<x/2

Proposition 8. Let c and s be positive real numbers, and k a positive integer.
(1)
(2)
(3)

r
π
= c (2k − 2)!!, 0
=c
(2k − 3)!!
t
0
2c 

 R
2
R s 2 −ct2 /2 dt
1 
2
cs
2
2
2
s
−cs /2
4 −ct /2 dt
−cs /2
t
e
=
=
1
−
e
t
e
)
1
−
e
(1
+
t
t
0
0
c
c2
2
2
2
R ∞ −ct2 /2
R ∞ −ct2 /2 dt
e−cs /2
e−cs /2
≤
,
te
dt =
e
t
s
s
cs2
cs
2 /2
−cs
R ∞ 2 −ct2 /2
e
2
te
dt <
(1 + cs ).
s
c2 s

R∞

2k

2
e−ct /2 dtt

−k

R∞

2
t2k−1 e−ct /2 dtt

−k+1

From now on, WGFFx (“well-known gamma function fact x”) will refer to some statement in part (x) of this Proposition. The only nontrivial part in the entire Proposition
is the case k = 1 of the second part of (1), which is a famous integral. Everything else
follows from elementary integration or a sufficiently cunning application of the integration
by parts formula
Z

x −ct2 /2

t e

dt
−tx−2 e−ct
=
t
c

2 /2

x−2
+
c

Z

2 /2

tx−2 e−ct

For instance, the first WGFF3 follows from
"
#∞
Z ∞
Z
2
−ct2 /2
dt
−e
2 ∞ e−ct /2
2
−ct /2
e
=
−
dt.
t
ct2
c s
t3
s
s

9

dt
.
t

(4)

2

Main Theorem

The main technical theorem of this paper, Theorem 17, says that
Pr(X[n] < 0) =

1
L−
−√
+ E− (n),
2
2πn

L− = L− ({na}) =

1/2 − {na} ν3
−
σ
6

where explicit bounds on E− (n) are given. As alluded to earlier, the formula for L− is
“well-known” from Edgeworth expansions; the point of the theorem is of course the bound
on E− . The precise statement of this will be deferred until the end of this section. This can
be used to give an analogous statement for the tilt; our aim is for this to be good enough
to use in practice to find an n0 such that the sign of Tn is constant for n ≥ n0 .
The following subsections (a) introduce a “scale-invariant” version of the earlier notation
and results, (b) outline the steps of the proof of the theorem, (c) methodically work through
those steps, and then (d) finally give a full statement of the theorem.

2.1

Scale-Invariance

It is convenient to modify the notation slightly by introducing scale-invariant quantities
where possible. Note that Tn is scale-invariant: it is unchanged if X is replaced by a
multiple of X. We introduce scale-invariant versions of µk , α, f (t), and D(t) by advancing
alphabetically:
P
νk := µk /σ k
g(t) := f (t/σ) = νk (it)k /k!
E(t) := D(t/σ) = (t/(2σ))/ sin(t/2σ)
β := α/σ = (1/2 − {na})/σ
The key results of the preceding section using this notation are:
• The value of the cumulative distribution function of X[n] at 0, in terms of an integral,
Theorem 2, becomes
Z πσ
dt
1
eiβt g(t)n E(t) .
(5)
Pr(X[n] < 0) = 1/2 −
2πi −πσ
t
• The bound on the tail of the power series of the CF, Lemma 5, becomes
X νj (it)j
j≥k

j!

≤

ν k tk
.
k!

(6)

• Finally, the bound on the CF, Theorem 7, becomes (introducing a factor of 2 with
an eye to the earlier gamma function facts)
|g(t)| ≤ 1 −

rt2
,
2

where r =

16m
,
(πCσ)2

for |t| ≤ πσ.

(7)

Since the power series for g(t) starts out with 1 − t2 /2, the constant r measures how
“tractable” X is; if r is small then the tail integral estimate will be weak, and the closer r
is to 1 the better the estimate will be.
10

2.2

Proof Outline

Throughout the proof, X is a bounded lattice random variable with mean 0, span 1, shift a,
√
and scale-invariant CF function g(t) = E eitX/σ . The standard deviation is σ = µ2 , and
scale-invariant central moments are νk = µk /σ k . Moreover, when n is given, βn = β =
(1/2 − {na})/σ.
Fix a positive integer n and let s be a positive real number s. During the proof various
upper bounds will be placed on s, and it will be assumed throughout that they hold. The
bounds on the various approximation errors are in practice smallest when s is as large as
possible. As will be seen, s will in practice be a constant (that depends on X) times n−1/4 .
For the sake of a (reasonably) simple statement of error bounds, no attempt will be
made to optimize various constants that arise. This seems appropriate in the motivating
example of determining the sign of the tilt by the fact that nowadays a computer can
calculate Tn for large n. Thus the point of the estimates is to enable a proof of when the
asymptotic tilt has arrived so that, when combined with computation, the sign is known
for all Tn . Thus finding the absolute best possible n0 may not be important.
The technique for proving Theorem 17 is as follows. From (5) above we know that
Pr(X[n] < 0) = 1/2 − I0 , where
Z πσ
dt
1
eiβt g(t)n E(t) .
I0 :=
2πi −πσ
t
This integral will be approximated by defining a sequence of further integrals Ik , 1 ≤ k ≤ 5.
Each Ik will be a reasonable approximation to Ik−1 , and the error between them will
be explicitly
bounded. The last integral I5 can be evaluated directly, and is equal to
√
L− / 2πn. The difference between I0 and I5 is of course bounded by the sum of bounds on
the differences between consecutive integrals, leading to a bound on E− .
The core idea of these approximations is that the dominant contribution to I0 should
come from a small interval around 0 whose size depends on n.
The modus operandi of the proof here is then summarized by the following sequence of
approximations; the subscript on each approximation gives the number of the subsection

11

in which the corresponding error is bounded
Z πσ
dt
1
eiβt g(t)n E(t)
I0 =
2πi −πσ
t
Z s
1
dt
'3
eiβt g(t)n E(t)
tail integral bound
2πi −s
t
Z s
nν3 t3
dt
1
2
u = βt −
eiu e−nt /2 E(t) ,
'4
2πi −s
t
6
Z s
1
dt
cos(u)
2
=
sin(u) e−nt /2 E(t) ,
is odd
2π −s
t
t
Z s
1
dt
2
'5
sin(u) e−nt /2 ,
E(t) ' 1
2π −s
t
Z s
dt
1
2
'6
u e−nt /2 ,
sin(u) ' u
2π −s
t
Z ∞
1
2
(β − nν3 t2 /6) e−nt /2 dt, another tail bound.
'7
2π −∞

2.3

Bounding the tail integral

For large n the dominant contribution to the integral
Z πσ
1
dt
eiβt g(t)n E(t) ,
I0 =
2πi −πσ
t
should come from a small neighborhood of the origin. In fact the approximation
2 /2

g(t)n ' (1 − t2 /2)n ' e−nt

√
suggests that the width of the neighborhood might be on the order of 1/ n. Let s ≤ πσ
be an arbitrary positive real number and define
Z s
dt
1
eiβt g(t)n E(t) .
I1 =
2πi −s
t
The parameter s will be chosen later, and its optimal value will actually turn out to be
O(n−1/4 ).
Recall from (7) that |g(t)| ≤ 1 − rt2 /2 for t on the interval of integration, where the
constant r was defined above to be r = 16m/(πCσ)2 , m is the smallest probability of a
point on the support of some certificate, and C is the L1 -norm of that certificate.
Theorem 9.
|I0 − I1 | ≤

exp(−nrs2 /2)
.
2nrs2

Proof. Use |g(t)| ≤ 1 − rt2 /2 and 1 − x ≤ e−x to get
|g(t)|n ≤ (1 − rt2 /2)n ≤ exp(−nrt2 /2).
12

The difference I0 − I1 is the sum of a right tail and a left tail integral that are bounded in
exactly the same way. So it suffices to multiply the bound on the upper tail by 2, Recall
the upper bound |E(t)| ≤ π/2, and use the bound on g(t)n :
Z πσ
1
dt
eiβt g(t)n E(t)
|I1 − I0 | ≤ 2
2πi s
t
Z ∞
2
1 π
e−nrs /2
−nrt2 /2 dt
≤2·
·
e
≤
2π 2 s
t
2nrs2
where the last inequality is WGFF3.

2.4

Bounding the power series tail

In order to analyze the g(t)n term in the integrand it is convenient to introduce notational
shorthand for terms and tails of the power series of g(t):
gj :=

νj (it)j
,
j!

Gk :=

X

gj .

j≥k

Although this lighter notation is pleasant it is important to remember that gk and Gk
depend on t. Note that (6) above says that |Gk | ≤ |gk | for even k, and |Gk | ≤ ν k |t|k /k! for
odd k.
The critical term in the integrand of I1 is g(t)n , and the purpose of this section is to
bound the error incurred in the approximations
g(t)n = exp(n log(1 + G2 )) ' exp(nG2 ) ' exp(n(g2 + g3 )).
It is convenient to introduce further notation. Let
q1 :=

1 ν4
+ .
5 24

Motivated by replacing g(t) = exp(log(1 + G2 )) by exp(g2 + g3 ) , define a “remainder” R
by
R = log(1 + G2 ) − g2 − g3 .
This should be small if n is large.
The following obvious bound (OB) on tails of power series with positive coefficients will
be used three times below; the proof is embedded in the statement of the lemma (!).
Lemma 10. (OB) Let P (x) = pk xk + pk+1 xk+1 + . . . be a power series power with nonnegative coefficients pj , and suppose that P (y) converges for some positive real number y.
Then if |x| ≤ y,
|P (x) − pk xk | = |x|k+1 ·

k
P (x) − pk xk
k+1 P (y) − pk y
≤
|x|
.
xk+1
y k+1

13

(8)

Theorem 11. Let s be a positive real number and assume throughout that |t| ≤ s. If s ≤ 1
then |G2 | ≤ 1/2, and the power series for log(g(t)) = log(1 + G2 ) converges. Moreover,
|R| ≤ q1 t4 ,

where q1 :=

1 ν4
+ ,
5 24

R = log(1 + G2 ) − g2 − g3 .

If also s ≤ (q1 n)−1/4 , i.e., nq1 s4 ≤ 1, then
enR − 1 ≤ np0 |R| ≤ np0 q1 t4 ,

where p0 := e − 1 ' 1.71828.

Proof. Part 1 follows from |G2 | ≤ g2 = t2 /2 ≤ s2 /2 ≤ 1/2 and the fact that the logarithm
series
log(1 + G2 ) = G2 − G22 /2 + G32 /3 − . . .
converges by comparison with a geometric series of ratio 1/2.
For the second part, first note that
|R| ≤ | log(1 + G2 ) − G2 | + |G2 − g2 − g3 |.
4
The second term is just |G4 | ≤ g4 =
Pν4kt /24. The first term can be bounded by applying
the OB to P (x) = − log(1 − x) =
x /k with k = 1, x = −G2 and y = 1/2. Note that
2
2
|x| = |G2 | ≤ t /2 ≤ s /2 ≤ 1/2. The OB gives




t4 log(2) − 1/2
t4
− log(1 − 1/2) − 1/2
2
=
≤ .
| − log(1 + G2 ) + G2 | ≤ G2
(1/2)2
4
1/4
5

(By choosing an even smaller bound on s, this could be made as close to t4 /8 as desired,
but no lower.) All in all this gives
| log(1 + G2 ) − g2 − g3 | ≤ q1 t4 ,

q1 =

1 ν4
+
5 24

as desired.
For the third part, note that the assumed bound on s implies that
|nR| ≤ nq1 t4 ≤ nq1 s4 ≤ 1.
Apply OB to P (x) = ex with k = 0, x = nR and y = 1 to get
 1

e −1
nR
≤ np0 q1 t4 , p0 := e − 1
e − 1 = |nR|
1
as desired.
Before using this lemma for the central goal of this section — bounding the difference
between I1 and a soon-to-be defined I2 — we prove a corollary that will be used later to
improve the tail integral bound in the previous subsection.
Corollary 12. With the above notation, if s ≤ 1 then


Z 1
1
2p0 q1
n dt
−ns2 /2
2
|g(t)|
≤e
+
+ p0 q1 s .
t
ns2
n
s
14

Proof. The last part of the theorem says that


2
|g(t)|n = eng2 +ng3 1 + (enR − 1) ≤ e−nt /2 1 + θnp0 q1 t4
so that
Z

1

n dt

Z

1

Z

1

dt
.
t
t
t
s
s
s
The first of the integrals on the right hand side can be estimated by (extending the interval
to infinity and) using the first WGFF3, and the second can be evaluated exactly by taking
the difference of two instances of the second WGFF2. The result is

!
Z 1
2
2
e−ns /2 2np0 q1 e−ns /2
ns2
n dt
≤
1+
|g(t)|
+
t
ns2
n2
2
s
|g(t)|

≤

−nt2 /2 dt

e

+ np0 q1

2 /2

t4 e−nt

which simplifies to the expression in the corollary.
Returning to the problem of approximating I1 , note that the first two factors in the
integrand can be written
eiβt g(t)n = exp(iβt + n log(1 + G2 ))
= exp(iβt + ng2 + ng3 + nR)
= exp(iu) exp(−nt2 /2) exp(nR)
where the quantity
u = βt − nν3 t3 /6
captures the key imaginary terms. This motivates the definition of the next integral:
Z s
dt
1
2
eiu e−nt /2 E(t) .
I2 :=
2πi −s
t
Theorem 13. If s ≤ min(1, (q1 n)−1/4 ) (so that previous theorem holds) then
p0 q 1
|I1 − I2 | ≤
,
2n
Proof. From everything above (e.g., as in the proof of Theorem 9)
Z s
dt
1
2
enR − 1 e−nt /2 E(t)
|I1 − I2 | ≤
2π −s
t
Z s
1 π
dt
2
≤2·
· · np0 q1
t4 e−nt /2 .
2π 2
t
0
WGFF2 says that the last integral is equal to

1 
−ns2 /2
2
1−e
(1 + ns /2) .
n2
An easy calculus exercise shows that the factor in parentheses is between 0 and 1, and the
upshot is that the |I1 − I2 | is bounded by p0 q1 /(2n) as claimed.
Remark : The last factor could be retained explicitly, giving a better estimate, especially
when n is small. However, we ignore this because of (a) the general philosophy of not
worrying too much about small constant factors, and (b) if one is struggling with having
to take n large in an unfavorable situation then the factor will be very close to 1 anyway.
15

2.5

Eliminating E

Define I3 to be the result of erasing E(t) in the integrand of I2 :
Z s
dt
1
2
eiu e−nt /2 .
I3 =
2πi −s
t

(9)

Theorem 14. If s ≤ σπ/3 then
|I2 − I3 | ≤

p1
,
µ2 n

where p1 :=

3(π − 3)
' .0136997 . . . .
π3

Proof. The power series t/ sin(t) is even and has positive coefficients, so we apply the OB
to it and get


s/ sin(s) − 1
t
2
−1≤t
, if |t| ≤ s.
sin(t)
s2
Taking s = π/6 (for simplicity) gives t/ sin(t) − 1 ≤ 12(π − 3)/π 2 t2 if |t| ≤ π/6. Replacing
t by t/(2σ) and doing a little algebra gives
|E(t) − 1| ≤

πp1 t2
,
µ2

if |t| ≤ πσ/3.

The theorem now follows from WGFF2:
Z
Z ∞
dt
p1
p1
1 s −nt2 /2 πp1 t2 dt
2
e
e−nt /2 t2
≤
=
.
|I2 − I3 | ≤
π 0
µ2 t
µ2 0
t
µ2 n

2.6

Eliminating sin

The integral of the odd function cos(u)/t on the symmetric interval t ∈ [−s, s] is 0 (using
the earlier principal value convention). Then eiu = cos(u) + i sin(u) can be replaced i sin(u)
and therefore
Z s
dt
1
2
sin(u) e−nt /2 .
(10)
I3 =
2π −s
t
For small t, the quantity u = βt − nν3 t3 /6 is small, and the approximation sin(u) ' u
motivates defining
Z s
1
dt
2
I4 :=
u e−nt /2 .
(11)
2π −s
t
Theorem 15.
|I3 − I4 | ≤ √
where
q3 = |β|,

q4 = |ν3 |/6,

q5 =

q5
2π n3/2

q33 3q32 q4 15q3 q42 35q43
+
+
+
.
6
2
2
2

16

Proof. For any real number x, | sin(x) − x| ≤ |x|3 /6. Applying this to u = βt − nν3 t3 /6
gives

1 33
|u|3
≤
q3 t + 3q32 q4 nt5 + 3q3 q42 n2 t6 + q43 n3 t9 .
| sin(u) − u| ≤
6
6
The claimed inequality follows by integrating and using the second WGFF1, i.e.,
r
Z ∞
π
2k−1 −ct2 /2 dt
−k+1
t
e
=c
(2k − 3)!!
,
(12)
t
2c
0
for k = 2, 3, 4, 5 to get
Z s
1
|u|3 −nt2 /2 dt
|I4 − I3 | ≤
e
2π −s 6
t
Z ∞

1
2
≤
q33 t3 + 3q32 q4 nt5 + 3q3 q42 n2 t6 + q43 n3 t9 e−nt /2 dt
6π 0
r
 3

q3 + 9q32 q4 + 45q3 q42 + 105q43
1
π
.
=
6π
2n
n

2.7

Extending to the whole real line

The next (and final!) integral is obtained by extending the interval of integration to the
whole real line, i.e.,
Z ∞
1
dt
2
I5 :=
u e−nt /2 .
2π −∞
t
This integral can be evaluated immediately using WGFF1 above for k = 1 and k = 2:
Z ∞
1
2
I5 =
(β − nν3 t2 /6) e−nt /2 dt
2π −∞
Z
Z
nν3 ∞ 2 −nt2 /2
β ∞ −nt2 /2
e
dt −
t e
dt
=
π 0
6π 0
1 
L−
ν3 
=√
=√
β−
.
6
2πn
2πn
Theorem 16.


q3 + q4 + q4 ns2
2
|I4 − I5 | ≤
e−ns /2 .
πns
Proof. The two tails of I5 − I4 are equal. Multiplying by 2 and using the last two parts of
WGFF3 gives
Z
1 ∞
2
|I5 − I4 | ≤
(q3 + q4 nt2 ) e−nt /2 dt
π s
2
2
q3 e−ns /2 q4 n e−ns /2
≤
·
+
·
· (1 + ns2 )
2
π
ns
π
ns
−ns2 /2

e
= q3 + q4 (1 + ns2 )
.
πns

17

2.8

Finishing the proof

During the proof the constant s was required to be smaller than πσ, 1, πσ/3, and 1/(q1 n)1/4 ,
which can be summarized as
s ≤ min(1, πσ/3, (q1 n)−1/4 ).

(13)

We remind the reader of the notation and then state the main theorem: X is a lattice
random variable with mean 0, span 1, shift a, and finitely many values; X[n] denotes
the sum of n IID copies of X. The standard deviation of X is σ, and the moments and
normalized moments are denoted µk = E X k , νk = µk /σ k . Moreover, β = βn is shorthand
for (1 − {na})/σ. Various further constants are defined as follows:
p1 := 3(π − 3)/π 3 ' .0136997 . . .
p 0 q1 p 1
q2 :=
+
2
µ2
q4 = |ν3 |/6
16m
r :=
(πCσ)2

p0 = e − 1 ' 1.71828 . . .
1 ν4
q1 := +
5 24
q3 := |β|
q 3 3q 2 q4 15q3 q42 35q43
q5 := 3 + 3 +
+
6
2
2
2

where, as earlier, C is the L1 norm of a certificate {cx } for X (i.e., a guarantor that X has
span 1), and m = min(px ) is the minimum probability of the values of X that are in the
support of the certificate.
Theorem 17. Fix a positive integer n and let s be a positive real number s that satisfies (13). Then
1
L−
Pr(X[n] < 0) = − √
+ E−
2
2πn
where
L− = β −

ν3
6

and
q5
q2 e−nr/2
2
+
+√
+ e−ns /2
|E− | ≤
n
2nr
2πn3/2



2p0 q1 q3 + q4 q4 s
1
2
+
+
p0 q1 s + 2 +
.
ns
n
πns
π

Proof. The bound (13) above guarantees that all of the results that required s to be small
enough are valid. If I(j, j + 1) denotes the bound proved above on the difference between
Ij and Ij+1 then
|E− | ≤ I(0, 1) + I(1, 2) + I(2, 3) + I(3, 4) + I(4, 5).
The last four terms were proved in Theorem 13, Theorem 14, Theorem 15, and Theorem 16
respectively, giving


q5
q3 + q4 + q4 ns2
q2
−ns2 /2
I(1, 2) + I(2, 3) + I(3, 4) + I(4, 5) =
+√
+e
.
n
πns
2π n3/2

18

We improve the bound for |I0 − I1 | given in Theorem 9 by writing
Z πσ
Z 1
Z πσ
dt
n dt
n dt
|g(t)|
|g(t)|
|g(t)|n
=
+
t
t
t
s
s
1
and apply Theorem 9 to the last integral and Corollary 12 to the integral from s to 1. The
result is


e−nr/2
1
2p0 q1
2
−ns2 /2
+
+
p
q
s
.
|I1 − I0 | ≤ e
+
0
1
ns2
n
2nr
The theorem follows with a little algebra.
In the next section this will be used to state a theorem about the tilt, and some simple
assumptions will be made that will simplify and clarify this expression.
One possible major improvement to the estimate would come from using the next higher
order Edgeworth expansion. The error term would become O(1/n2 ). However, our hunch
is that this would introduce two further problems: the number of terms in the algebraic
expressions would explode, and the upper bound on s would probably be O(n−1/6 ), so it is
not immediately clear that the resulting n0 would be much better.

3

Tilt

The goal of this section is to apply the Main Theorem to the tilt.
The first subsection makes a few observations about the error bounds. The second
reverts to the case of dice, giving a theorem about the tilt. Finally, the third subsection
considers some numerical examples.

3.1

Observations

With the notation in Theorem 17, fix n and consider the error bound as a function of s.
The only two terms that are not obviously decreasing as s increases are (constant multiples
2
2
of) se−ns /2 and s2 e−ns /2. Differentiating with respect to s shows that these are both
decreasing if ns2 ≥ 2. Since this is a very mild assumption, we will just assume it from
now on. This implies that the optimal s is just the smallest value in (13) above.
In that bound
s ≤ min(1, πσ/3, (q1 n)−1/4 ).
the last quantity will usually be the smallest. To simplify and focus the notation, assume
that this is the case, i.e., that
1
≤ min(1, πσ/3).
(q1 n)1/4
Assuming this, requiring ns2 ≥ 2 as above, setting s = (q1 n)−1/4 , and adopting the notational shorthand
p
η = 2 n/q1
(so that ns2 /2 = η), allows a restatement of the error bound as follows:
19

If


n ≥ max

81
q1 1
, ,
4 q1 q1 π 4 µ22



then
q2 e−nr/2
q5
|E− | ≤
+
+√
+ e−η
3/2
n
2nr
2πn



p0 + 1 2p0 q1
1
+
+ √
2η
n
π 4 q1 n



q 3 + q4
+ q4
2η


.

For the sake of the next section we note that if X is replaced by −X in the theorem
then, as should be expected, the bounds on the error are unchanged. Indeed, the only
relevant change is that the sign of a is negated, so that q3 might change. However, if
x = {na} then and y = {−na} then either x = y = 0, or y = 1 − x. If x = y = 0 then q3 is
obviously unchanged. If y = 1 − x then
q3 =

|1/2 − x|
| − 1/2 + y|
|1/2 − y|
=
=
σ
σ
σ

and q3 is again unchanged.

3.2

Tilt for dice

For the sake of applications it is convenient to return to looking at the tilt in the case of
dice. Let X be a bounded integer-valued random variable with span b, shift a, mean 0,
and moments µk = E X k , σ 2 = µ2 , and νk = µk /σ k .
Apply the Main Theorem (using the reformulation in the preceding section) to X/b.
Scale-invariant quantities are unchanged, but σ(X/b) = σ/b. The quantity β is unchanged,
but note that
β=

b/2 − b{na/b}
b/2 − na mod b
1/2 − {na/b}
=
=
.
σ/b
σ
σ

The other constants are changed only in so far as σ has to be replaced by σ/b:
p1 := 3(π − 3)/π 3 ' .0136997 . . .
p 0 q1 b 2 p1
q2 :=
+
2
µ2
q4 = |ν3 |/6
16b2 m
r :=
(πCσ)2

p0 = e − 1 ' 1.71828 . . .
1 ν4
q1 := +
5 24
q3 := |β|
q 3 3q 2 q4 15q3 q42 35q43
+
q5 := 3 + 3 +
6
2
2
2

where, as earlier, C is the L1 norm
{cx } for X, i.e., a collection {cx } for a
P of a certificate
P
set of values x of X such that
cx = 0, cx x = b. Note that the inclusion of b in the
formulae does not actually change the values of the constants. For instance, in the span-1
case of X/b the standard deviation is σ/b, where now “σ” refers to the span of X and not
that of X/b.
Theorem 18. Let X be as above. Fix n with n ≥ max (q1 /4, 1/q1 , 81b4 /(q1 π 4 µ22 )). Then


1
(−na) mod b − (na mod b) ν3
Tn = √
−
+E
σ
3
2πn
20

where
2q5
2q2 e−nr/2
+
+√
|E| ≤
+ e−η
n
nr
2πn3/2
p
and η = 2 n/q1 so that ns2 /2 = η.



1
1 + p0 4p0 q1
+
+ √
4
η
n
π q1 n



q3 + q 4
+ 2q4
η



Proof. The theorem follows from the fact that
Tn = Pr(X[n] > 0) − Pr(X[n] < 0) = Pr((−X)[n] < 0) − Pr(X[n] < 0)
and the earlier remarks on the error bounds.

3.3

Examples

We apply the above results to several examples, comparing the actual n0 at which asymptopia arrives to various approximations that emerge from Theorem 18.
Let X be the random variable that takes values −3, 1, 5 with respective probabilities
1/2, 1/4, 1/4, so that its PGF is
X(z) = (2z −3 + z + z 5 )/4
(it is convenient to identify dice with their PGFs). Then X has mean 0, span 4 and shift
1, so there are really four cases that have to be considered: n going to infinity through
integers that are c mod 4 for c = 0, 1, 2, 3; in the table below data connected with case c is
on the line labeled Xc .
With c fixed, let n0 be the smallest integer such that the sign of Tn is equal to the sign
of L for all n ≥ n0 , n ≡ c mod b, i.e., n0 is the exact point at which asymptopia has arrived
in the congruence class c.
√
The term 2q2 /n in the error bound for Tn − L/ 2πn is unavoidable in any bound
obtained by using Edgeworth expansions as above, and we will call this the “principal
term” of the error, motivated by the fact that in sufficiently favorable circumstances it will
be the dominant term. In particular, it is impossible for us to prove that asymptopia has
arrived unless n is large enough so that
√
2q2
2πn
< |L|,
n

i.e., n ≥ n1 :=

8πq22
.
L2

Thus n1 is a lower bound on asymptopia arrival that could be proved by our techniques.
Given the nature of some of the error bounds, it is reasonable to expect that n1 might
might actually be larger than n0 in many cases; however, a later example gives an instance
where n1 is lower than n0 .
Finally, let n2 be the number, produced by using the error estimates for a fixed congruence class modulo b directly
√ as stated in Theorem 18, such that for n ≥ n2 (and in
the given congruence class), 2πn EB(n) < |L|, where EB(n) is the error bound in the
theorem. In other words, Theorem 18 can be used to show that asymptopia has arrived by
n2 in the given congruence class.
21

The values found using (a computer and) Theorem 18 are:

X0
X1
X2
X3

L n 0 n1
−0.16446 4 59
0.43856 5 9
−0.16446 2 59
−0.76748 3 3

n2
74
37
70
27

As expected, smaller values of |L| require larger n. A close examination of the seven terms
in the error bound show that the last five rapidly become negligible as n becomes large,
whereas the first two terms — the principal term and the tail bound, e−rn/2 /(rn), are
significant. The tail bound can be decreased, as we will see below, by looking at the tail
integral more closely. However, in the Xc cases the amount of computer time required to
compute the tilts up to n2 is negligible, so we will not bother trying to improve the tail
bound in these cases, despite the gap between n0 and n2 .
Let Y be the random variable that takes the value −8 with probability 1/2, the value
0 with probability 1/18, and the value 9 with probability 4/9; its PGF is
Y (z) = (9z −8 + 1 + 8z 9 )/18.
The span of Y is 1. One (of the several) indications that this might be a problematic case
is that the probability of 0 is small, and the span changes to 17 if this probability is set to
0 (while suitably rebalancing the other two probabilities).
To give a sense of the various components of the error, write
EB =

2q2 e−rn/2
+
+ TR
n
rn

where EB is the total error bound and TR (“the rest”) is the sum of five other terms. In
the following table n is either close to n0 = 761, n1 = 682, or n2 = 182024. The columns
are: n, the total
√ error EB, the principal error, and the tail error. (All errors have been
multiplied by 2πn to make comparison with L easy). In all cases, TR is less than 10−5
and it is not tabulated. All decimal expansions are truncated rather than rounded, and the
constant L is equal to −0.0404226 . . ..
n
681
682
761
182023
182024

EB
1128.163
1127.289
1063.690
0.040423
0.040421

2q2 /n
e−rn/2 /(rn)
0.0404310 1128.122
0.0404013 1127.248
0.0382468 1063.652
0.0024730 0.0379500
0.0024729 0.0379483

√
The delicate nature of this case is illustrated by the graph of 2πn Tn for n from 1 to
800, and for n from 740 to 800, given in Figure 1 and Figure 2.
Clearly Y “nearly” has span 17, so that the graph is the result of applying a damping
function to a function that is periodic of period 17. However, at n0 = 761 the damping

22

1

0.5

100

200

300

400

500

600

700

800

-0.5

Figure 1:

0

740

750

760

√
2πn Tn , 1 ≤ n ≤ 800

770

780

-0.02

-0.04

-0.06

-0.08

Figure 2:

√
2πn Tn , 740 ≤ n ≤ 800

23

790

800

finally forces to the tilt to become, and forever stay, negative. The actual numerical values
in the vicinity of n0 , and the next local maxima, are:
760
761
762
0.001195 −0.003066 −0.011796
···
n
776
777
778
779
√
2πn Tn −0.007300 −0.002028 −0.001415 −0.005505

√

n
2πn Tn

759
0.000439

The size of the tail bound near n0 was a surprise to us; it is 15 times the size of the
principal error term. Moreover, we had thought that Corollary 12√shifted the extreme tail
bound to an exponential term of the form e−cn rather than e−c n , and that this would
be good enough. The key point is of course that the constant r is uncomfortably small.
We wondered whether the alternate r in [Ben75] would be better, but in the case of Y
Benedick’s constant is very slightly worse than ours, and gives essentially the same n2 . We
tried to replace r with the optimal value
1 − |f (t)|
.
t∈[−π,π]
t2

ropt = min

This gave a factor of improvement to n2 of somewhat more than 2:
r
n2
Benedicks .0026144 . . . 194,081
ours
.0028144 . . . 182,024
optimal
.0055834 . . . 88,181
The graph of the absolute value |f (t)| of the CF shows what the problem is. The goal
is to find an upper bound for the integral of |f (t)|n /t outside [−1/σ, 1/σ], as n gets large.
2
The function 1 − rt2 ≤ e−rt is a natural choice, but does not work well for a characteristic
function whose secondary peaks are so high.
There are several things that can be done to improve the bound on the tail integral.
The following extremely simple device made a dramatic improvement compared to the n2
1

0.8

0.6

0.4

0.2

-3

-2

-1

1

Figure 3: |fY (t)|

24

2

3

given above. The heights of the peaks in the graph of |f (t)| (starting from 0 and moving
to the right) are
1, 0.88989, 0.99645, 0.89768, 0.98621, 0.91204, 0.97048, 0.93077, 0.95118.
The third peak is dominant. It occurs at t = t0 = 4π/17 and has height h0 = .99645. The
fifth peak has height h1 = .98621 and is the second most dominant peak. Let f ∗ be the
function that is the constant h1 on [−π, −1/σ] ∪ [1/σ, π] except for the small section of the
parabola h0 · (1 − 34(t − t0 )2 ) that is above the line y = h1 , and the mirror image of this
parabola section at t = −t0 . One can check that f ∗ is an upper bound on |f | outside of
[−1/σ, 1/σ], and it is easy to estimate the integral of f ∗ (t)n /|t| on 1/σ ≤ |t| ≤ π.
Using this tail bound we get an improved n02 = 1455, which was much smaller than we
had expected. The only significant contributions to the error are the 2q2 /n term and the
tail bound, which are, respectively, 0.02766, and 0.012709 so that the total error is just less
than |L|:
0.0276602867 + 0.01270946 = .040370408 < |L| = .0404226.
All other contributions to the error are less than 10−6 , and the tail bound has been reduced
to under half of the primary contribution.
One can push this further by considering all of the peaks and lowering the “threshold”
to, say, the value of the CF at 1/σ, i.e., the value of the normalized CF g(t) at t = 1. This
seems to move n02 further down to an n002 just above 1200 (and we think that this is about
the limit of what can be done). However, the time required to program this correctly far
exceeds the time that a computer takes to compute the tilts between 1200 and 1455, so our
general philosophy says that it would be silly to implement this improvement.
Finally, we consider an example that originally motivated this investigation. Consider
three nontransitive dice, that appeared in one of Martin Gardner’s columns many years
ago, whose PGFs are
A = (z 2 + z 6 + z 7 )/3,

B = (z 1 + z 5 + z 9 )/3,

C = (z 3 + z 4 + z 8 )/3.

Write A > B to mean that Pr(A > B) > Pr(B > A), i.e., it is more likely that a roll of A
is larger than a roll of B than the reverse. This is the same thing as saying that the tilt
T (A − B) of the difference U = A − B is positive. Note that the PGF of U is A(z)B(z −1 ).
Similarly, let V = B − C and W = C − A. It turns out that
A > B, B > C, C > A,

whereas A[2] < B[2], B[2] < C[2], C[2] < A[2].

In fact, the various dominance orders oscillate until n = n0 = 8 when A becomes dominant,
and B dominates C, in the sense that
A[n] > B[n], A[n] > C[n], B[n] > C[n],

for all n ≥ n0 .

This can be verified by computer for n as large as your hardware can go, but to prove that
asymptopia arrives at n0 = 8 we use Theorem 18. It turns out that
U (z) = A(z)B(z −1 ) = B(z)C(z −1 ) = V (z)
25

so there are really only two dice to which that theorem has to be applied: U and W . By
now we can give a guess as to how large n will have to be, namely, we find the needed error
|L| and then choose n large enough so that
√

2πn Tn '

√

2πn

2q2
< |L|, i.e.,
n

n>

8πq22
.
L2

Since q2 = 1/5 + ν4 /24, for many random variables it is reasonable to bound q2 by 1/4, so
that n has to be at least as large as π/(2L2 ).
For W we find that L = 0.033310 . . ., which is unusually small. The approximation
n ' 8πq22 /L2 suggests n0 ≤ 1407, and in fact in this case L is so small that n is large
enough so that all other terms of the error are negligible. In other words, the n required
by the principal error term so large that this gives the best possible value.
For U , the limit L is larger, namely L ' −0.14028 . . .. In this case the bound implied
by the principal term is n = 83. Although the main tail bound term is then large, we can
apply the earlier techniques of piecewise bounding the characteristic function, to show that
n0 ≤ 83. In other words, this shows that the smallest possible bound is achievable with a
bit more work.
All of the above experiments are summarized in the following table.
n002
L n0
n1
n2
n02
X0 −0.16446
4
59
74
X1
0.43856
5
9
37
X2 −0.16446
2
59
70
X3 −0.76748
3
3
27
Y −0.040422 761 682 182,024 1455 1206
U −0.14028
9
83
1933
83
W
0.03333
5 1407
4591 1407
where n02 is the result of replacing the tail bound using a little bit of work (e.g., roughly
where one could imagine that the necessary estimates could be verified by hand, as in
the simple improvement for Y above), and n002 is the result of replacing the tail bounds
by bounds that require a computer to perform all of the verifications, as in the more
complicated improved estimate for Y earlier.
We close with some further comments.
1. The primacy of the 1/n term is a surprise. If we take the “poor man’s approximation”
q2 ' 1/4, which is a good approximation unless X takes very large values with very
small probability, then the error is about 1/2n, independent of X! And this says that
the lower bound n1 , and often the arrival bound n2 , is almost entirely determined by
the target error |L|. As a first guess, n2 ' π/(2L2 ), especially if this number is large
enough so that the exponential terms are small; if this approximation to n2 isn’t that
large then further work might be required to decrease the tail bound.
2. A curious philosophical difficulty is hiding in the weeds. The value of n0 becomes
“obvious” from calculations when the sign of the tilt becomes constant and stays
there for as large an n as one cares to compute. However, this gives no hint of how
26

one might prove that this will continue to be the case, and the point of the work
here is to be able to actually prove an upper bound on n0 . What computer results
are admissible in such a proof? The computation of tilts would seem innocuous to
many since any floating point error can be easily bounded, and the programs are
short and “easily” proved to be correct — the computer is “just” doing stable, wellunderstood arithmetic . The error bounds in calculating n2 straight from Theorem 18
can be done by hand, and perhaps the estimates for n02 could also be done by hand,
though few, if any people would do them nowadays without using a computer; the
calculations needed to support the determination of n002 seem to be intrinsically even
more demanding.
3. It would be interesting to apply these ideas here to more general situations (more
general RVs, approximation not at the mean, etc.). Extending to higher order Edgeworth approximations seems viable, but would require algebraic stamina. We have
thoughts on how this might be automated. However, as noted earlier, we expect that
the lower bounds on n will have to increase, so that the utility of this approach isn’t
entirely clear.
Acknowledgments. We would like to thank Richard Arratia, Steve Butler, Persi Diaconis, Larry Goldstein, Fred Kochman, and Sandy Zabell for interesting and useful feedback.

References
[Ben75]

Michael Benedicks, An estimate of the modulus of the characteristic function of
a lattice distribution with application to remainder term estimates in local limit
theorems, Ann. Probability 3 (1975), 162–165.

[BGH16] J.P. Buhler, R.L. Graham, and A.W. Hales, Maximally nontransitive dice,
Preprint, 2016.
[BR10]

Rabi N. Bhattacharya and R. Ranga Rao, Normal approximation and asymptotic
expansions, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010.

[Fel71]

William Feller, An introduction to probability theory and its applications. Vol.
II., Second edition, John Wiley & Sons, Inc., New York-London-Sydney, 1971.

[Pet95]

Valentin V. Petrov, Limit theorems of probability theory, Oxford Studies in Probability, The Clarendon Press, Oxford University Press, New York, 1995.

27

