Bounds for Tail Probabilities of the Sample Variance

Volume 2009, Article ID 941936,20pages doi:10.1155/2009/941936

Research Article

Bounds for Tail Probabilities of the Sample Variance

V. Bentkus

and M. Van Zuijlen

1Vilnius Pedagogical University, Studentu 39, LT-08106 Vilnius, Lithuania

2IMAPP, Radboud University Nijmegen, P.O. Box 9010, 6500 GL Nijmegen, The Netherlands

Correspondence should be addressed to V. Bentkus,bentkus@ktl.mii.lt Received 11 February 2009; Accepted 20 June 2009

Recommended by Andrei Volodin

We provide bounds for tail probabilities of the sample variance. The bounds are expressed in terms of Hoeffding functions and are the sharpest known. They are designed having in mind applications in auditing as well as in processing data related to environment.

Copyrightq2009 V. Bentkus and M. Van Zuijlen. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction and Results

LetX, X1, . . . , Xn be a random sample of independent identically distributed observations.

Throughout we write

μEX, σ²EX−μ², ωEX−μ⁴ 1.1

for the mean, variance, and the fourth central moment ofX, and assume thatn≥2. Some of our results hold only for bounded random variables. In such cases without loss of generality we assume that 0≤X≤1. Note that 0≤X≤1 is a natural condition in audit applications.

The sample varianceσ²of the sampleX₁, . . . , X_nis defined as

σ² 1

n−1 n

i1

Xi−X², 1.2

whereXis the sample mean,nXX1· · ·Xn. We can rewrite1.2as

σ² 1 nn−1

i /j,1≤i,j≤n

Xi− X_j²

2 . 1.3

We are interested in deviations of the statisticσ² from its meanσ² Eσ², that is, in bounds for the tail probabilities of the statisticT σ²−σ²,

P{T ≥t}P

σ²≤σ²−t

, 0≤t≤σ², 1.4

P{T ≤ −t}P

σ²≥σ²t

, t≥0. 1.5

The paper is organized as follows. In the introduction we give a description of bounds, some comments, and references. InSection 2we obtain sharp upper bounds for the fourth moment. InSection 3we give proofs of all facts and results from the introduction.

If 0≤X ≤1, then the range of interest in1.5is 0≤t≤γ², where

γ²

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ 1

4 −σ² 1

4n−1, if nis even, 1

4 −σ² 1

4n, if nis odd.

1.6

The restriction 0≤t≤σ²on the range oftin1.4 resp., 0≤t≤γ²in1.5in cases where the condition 0≤X≤1 is fulfilledis natural. Indeed,P{T ≥t}0 fort > σ², due to the obvious inequalityσ²≥0. Furthermore, in the case of 0≤X ≤1 we haveP{T≤ −t}0 fort > γ²since

σ²≤γ²σ²seeProposition 2.3for a proof of the latter inequality.

The asymptoticasn → ∞properties ofTseeSection 3for proofs of1.7and1.8 can be used to test the quality of bounds for tail probabilities. Under the conditionEX⁴ <∞ the statisticT σ²−σ²is asymptotically normal provided thatXis not a Bernoulli random variable symmetric around its mean. Namely, ifω > σ⁴, then

nlim→ ∞P√

nT ≥y

ω−σ⁴

1−Φ y

, y∈R. 1.7

Ifω σ⁴which happens if and only ifX is a Bernoulli random variable symmetric around its mean, then asymptoticallyThasχ²type distribution, that is,

nlim→ ∞P

nT ≥yσ² P

η²−1≥y

, y∈R, 1.8

whereηis a standard normal random variable, andΦy P{η≤y}is the standard normal distribution function.

Let us recall already known bounds for the tail probabilities of the sample variance see1.19–1.21. We need notation related to certain functions coming back to Hoeffding 1 . Let 0< p≤1 andq1−p. Write

H x;p

1 qx p

_−qx−p

1−x^qx−q, 0≤x≤1. 1.9

Forx ≤ 0 we defineHx;p 1. For x > 1 we setHx;p 0. Note that our notation for the functionHis slightly different from the traditional one. Letλ ≥0. Introduce as well the function

Πx;λ e^x 1x

λ −x−λ

forx≥0, 1.10

andΠx;λ 1 forx≤0. One can check that H

x;p

≤Π

x;p q

. 1.11

All our bounds are expressed in terms of the functionH. Using1.11, it is easy to replace them by bounds expressed in terms of the functionΠ, and we omit related formulations.

Let 0≤p <1 andσ²≥0. Assume that

p σ²

1σ², q 1

1σ², pq1. 1.12

Letεbe a Bernoulli random variable such thatP{ε−σ²}qandP{ε1}p. ThenEε0 andEε²σ². The functionHis related to the generating functionthe Laplace transformof binomial distributions since

H x;p

inf

h>0exp{−hx}Eexp{hε}, 1.13

Hⁿ x;p

inf

h>0 exp{−hnx}Eexp{hε1· · ·ε_n}, 1.14

whereε1, . . . , εnare independent copies ofε. Note that1.14is an obvious corollary of1.13.

We omit elementary calculations leading to1.13. In a similar way Πx;λ inf

h>0 exp{−hx}Eexp h

η−λ

, 1.15

whereηis a Poisson random variable with parameterλ.

The functionsHandΠsatisfy a kind of the Central Limit Theorem. Namely, for given 0< p <1 andy≥0 we have

nlim→ ∞Hⁿ

yn^−1/2 p

q;p

lim

n→ ∞Πⁿ

yn^−1/2 λ;λ

exp

−y² 2

1.16

we omit elementary calculations leading to1.16. Furthermore, we have1 H

y

p q;p

≤exp

−y² 2

, 1

2 ≤p <1, y≥0, 1.17

and we also have2

H yp

q ;p

≤exp

− py² 2q

y1

, 0≤p≤ 1

2, y≥0. 1.18

Using the introduced notation, we can recall the known resultssee2, Lemma 3.2 . Letk n/2 be the integer part ofn/2. Assume that 0≤X ≤1. Ifσ²is known, then

P{T ≥t} ≤U0, U0def H^k t

σ²; 1−2σ²

. 1.19

The right-hand side of1.19is an increasing function ofσ² ≤1/4seeSection 3for a short proof of1.19as a corollary ofTheorem 1.1. Ifσ²is unknown butμis known, then

P{T≥t} ≤U₁, U₁^def H^k t

μ−μ²; 1−2μ2μ²

. 1.20

Using the obvious estimateσ² ≤μ1−μ, the bound1.20is implied by1.19. In cases where bothμandσ²are not known, we have

P{T ≥t} ≤U2, U2def H^k

4t;1 2

, 1.21

as it follows from1.19using the obvious boundσ² ≤1/4.

Let us note that the known bounds1.19–1.21are the best possible in the framework of an approach based on analysis of the variance, usage of exponential functions, and of an inequality of Hoeffdingsee3.3, which allows to reduce the problem to estimation of tail probabilities for sums of independent random variables. Our improvement is due to careful analysis of the fourth moment which appears to be quite complicated; seeSection 2. Briefly the results of this paper are the following: we prove a general bound involvingμ,σ², and the fourth momentω; this general bound implies all other bounds, in particular a new precise bound involvingμandσ²; we provide as well bounds for lower tailsP{T ≤ −t}; we compare the bounds analytically, mostly asnis sufficiently large.

From the mathematical point of view the sample variance is one of the simplest nonlinear statistics. Known bounds for tail probabilities are designed having in mind linear statistics, possibly also for dependent observations. See a seminal paper of Hoeffding 1 published in JASA. For further development see Talagrand3 , Pinelis4,5 , Bentkus6,7 , Bentkus et al.8,9 , and so forth. Our intention is to develop tools useful in the setting of nonlinear statistics, using the sample variance as a test statistic.

Theorem 1.1extends and improves the known bounds1.19–1.21. We can derive 1.19–1.21 from this theorem since we can estimate the fourth moment ω via various combinations ofμandσ²using the boundedness assumption 0≤X ≤1.

Theorem 1.1. Letk n/2 andω0≥0.

IfEX⁴<∞andω≤ω₀, then

P{T≥t} ≤U, U^def H^k t

σ²;p

1.22

with

p σ⁴ω0

3σ⁴ω0 s²

1s², s² σ⁴ω0

2σ⁴ . 1.23

If 0≤X≤1 andω≤ω₀, then

P{T ≤ −t} ≤L, L^def H^k 2t

1−2σ²;p

1.24

with

p 2σ⁴2ω₀

1−4σ²6σ⁴2ω₀ s²

1s², s² 2σ⁴2ω₀

1−2σ²². 1.25 Both boundsUandLare increasing functions ofp,ω0,ands².

Remark 1.2. In order to derive upper confidence bounds we need only estimates of the upper tailP{T ≥ t} see2 . To estimate the upper tail the conditionEX⁴ < ∞is sufficient. The lower tailP{T ≤ −t}has a different type of behavior since to estimate it we indeed need the assumption thatXis a bounded random variable.

For 0≤X≤1Theorem 1.1implies the known bounds1.19–1.21for the upper tail of T. It implies as well the bounds1.26–1.29for the lower tail. The lower tail has a bit more complicated structure,cf. 1.26–1.29with their counterparts1.19–1.21 for the upper tail.

Ifσ²is known, then

P{T ≤ −t} ≤L0, L0def H^k 2t

1−2σ²; 2σ²

. 1.26

One can showwe omit detailsthat the boundL₀is not an increasing function ofσ². A bit rougher inequality

P{T ≤ −t} ≤L^∗₀, L^∗₀^def H^k

2t; 2σ² 12σ²

1.27

0 0.25 0.5 0.75 1 μ

0 0.25

σ2

D1

D₂

D3

Figure 1:DD1∪D2∪D3.

has the monotonicity property sinceL^∗₀ is an increasing function ofσ². Ifμis known, then using the obvious inequalityσ²≤μ1−μ, the bound1.27yields

P{T≤ −t} ≤L1, L1def

H^k

2t; 2μ−2μ² 12μ−2μ²

. 1.28

If we have no information aboutμandσ², then usingσ²≤1/4, the bound1.27implies P{T ≤ −t} ≤L₂, L₂ ^def H^k

2t;1

3

. 1.29

The bounds above do not cover the situation where both μ and σ² are known. To formulate a related result we need additional notation. In case of 0 ≤ X ≤ 1 we use the notation

f₁

1−μ 1 2 −μ

, f₃μ

μ− 1 2

. 1.30

In view of the well-known upper boundσ² ≤μ1−μfor the variance of 0 ≤X ≤1, we can partition the set

D

μ, σ²

∈R²: 0≤μ≤1,0≤σ²≤μ 1−μ

1.31

of possible values ofμandσ²into a unionDD₁∪D₂∪D₃of three subsets D₁

μ, σ²

∈D:σ²≤f₁

, D₃

μ, σ²

∈D:σ²≤f₃

, 1.32

andD2D\D1∪D3; seeFigure 1.

Theorem 1.3. Writek n/2 . Assume that 0≤X≤1.

The upper tail of the statisticT satisfies

P{T ≥t} ≤U3, U3def

H^k t

σ²;pu

1.33 withpus²/1s², where

s²

⎧⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎨

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎩

σ⁴ 1−μ⁴ 21−μ²σ² , if

μ, σ²

∈D₁, abσ²4σ⁴

8σ⁴ , if μ, σ²

∈D2, σ⁴μ⁴

2μ²σ² , if μ, σ²

∈D3,

1.34

and where one can write

aμ 1−μ

2μ−1², b8μ²−8μ3. 1.35 The lower tail ofT satisfies

P{T ≤ −t} ≤L3, L3def H^k 2t

1−2σ²;pl

1.36

withp_ls²/c²s², wherec 1−2σ²/2σ², ands²is defined by1.34.

The bounds above are obtained using the classical transformG→HG, HGx inf

h<xEexp{hY−x} 1.37

of survival functions Gx P{Y ≥ x} cf. definitions 1.13 and 1.14 of the related Hoeffding functions. The bounds expressed in terms of Hoeffding functions have a simple analytical structure and are easily numerically computable.

All our upper and lower bounds satisfy a kind of the Central Limit Theorem. Namely, if we consider an upper bound, sayUUt resp., a lower boundLLtas a function of t, then there exist limits

nlim→ ∞U t

√n

exp

−ct²

, lim

n→ ∞L t

√n

exp

−dt²

1.38 with some positivec and d. The values ofc and dcan be used to compare the bounds—

the larger these constants, the better the bound. To prove1.38it suffices to note that with k n/2

nlim→ ∞H^k x

√n;p

exp

−qx² 4p

. 1.39

The Central Limit Theorem in the form of1.7restricts the ranges of possible values ofcand d. Namely, using1.7it is easy to see thatcanddhave to satisfy

c, d≤a^def 1 2

ω−σ⁴. 1.40

We provide the values of these constants for all our bounds and give the numerical values of them in the following two cases.

iXis a random variable uniformly distributed in the interval0,1/2 . The moments of this random variable satisfy

μ1

4, σ² 1 48,

μ, σ²

∈D₁, ω 1

1280, a1440. 1.41

Forμ, σ², ωdefined by1.41, the constantscanddwe give asc1, d1. iiXis uniformly distributed in0,1 , and in this case

μ 1

2, σ² 1 12,

μ, σ²

∈D₂, ω 1

80, a90. 1.42

For the constantscanddwithμ, σ², ωdefined by1.42we give asc2, d2. We have

U₂: c4, c₁4, c₂4,

U₁: c 1

2μ−2μ²

1−2μ2μ², c₁ 4.26. . . , c₂4, U₀: c 1

2σ²−4σ⁴, c₁25.04. . . , c₂7.2, U₃: c 1

4σ⁴s², c₁ 42.60. . . , c₂18, 1.43

U: c 1

2σ⁴2ω₀, c₁411.42. . . , c₂25.71. . . , 1.44 L₂: d2, d₁2, d₂2,

L1: d 1

2μ−2μ², d12.66. . . , d22, L^∗₀: d 1

2σ², d124, d26, L0: d 1

2σ²−4σ⁴, d125.04. . . , d27.2, L3: d 1

4σ⁴s², d1 42.60. . . , d2 18,

1.45

L: d 1

2σ⁴2ω0

, d1411.42. . . , d225.71. . . , 1.46

while calculating the constants in1.44and 1.46we choose ω₀ ω. The quantity s² in 1.43and1.45is defined by1.34.

Conclusions

Our new bounds provide a substantial improvement of the known bounds. However, from the asymptotic point of view these bounds seem to be still rather crude. To improve the bounds further one needs new methods and approaches. Some preliminary computer simulations show that in applications where n is finite and random variables have small means and variances like in auditing, where a typical value of n is 60, the asymptotic behavior is not related much to the behavior for smalln. Therefore bounds specially designed to cover the case of finitenhave to be developed.

2. Sharp Upper Bounds for the Fourth Moment

Recall that we consider bounded random variables such that 0 ≤ X ≤ 1, and that we write μ EX and σ² EX −μ². In Lemma 2.1we provide an optimal upper bound for the fourth moment ofX−λgiven a shiftλ∈R, a meanμ, and a varianceσ². The maximizers of the fourth moment are either Bernoulli or trinomial random variables. It turns out that their distributions, sayν, are of the following three typesi–iii:

ia two point distribution such that

ν{d} r, ν{1} p, dμ− σ²

1−μ, 2.1

r 1−μ²

1−μ²σ², p σ²

1−μ²σ²; 2.2

iia family of three point distributions depending on 1/4< λ <3/4 such that

ν{0} q, ν{d} r, ν{1} p, d≡d_λ2λ−1

2, 2.3

q σ²−f1

d_λ , r μ 1−μ

−σ²

d_λ1−d_λ , p σ²−f3

1−d_λ, 2.4

where we write f1

1−μ μ−dλ

, f3μ dλ−μ

; 2.5

notice that2.4supplies a three-point probability distribution only in cases where the inequalitiesσ² > f1andσ²> f3hold;

iiia two point distribution such that

ν{0} q, ν{d} r, dμ σ²

μ , 2.6

q σ²

μ²σ², r μ²

μ²σ². 2.7

Note that the point d in 2.2–2.7 satisfies 0 ≤ d ≤ 1 and that the probability distributionνhas meanμand varianceσ².

Introduce the set

D

μ, σ²

∈R²:μEX, σ² E X−μ₂

,0≤X≤1

. 2.8

Using the well-known boundσ² ≤μ1−μvalid for 0≤X ≤1, it is easy to see that

D

μ, σ²

∈R²: 0≤μ≤1,0≤σ² ≤μ 1−μ

. 2.9

Letλ∈R. We represent the setD⊂R²as a unionDD₁^λ∪D₂^λ∪D₃^λof three subsets setting D^λ₁

μ, σ²

∈D:σ²≤f1

, D₃^λ μ, σ²

∈D:σ²≤f3

, 2.10

andD₂^λ D\D^λ₁ ∪D^λ₃, wheref₁ andf₃ are given in2.5. Let us mention the following properties of the regions.

aIfλ≤ 1/4, thenD D₁^λsince for suchλobviouslyμ1−μ≤ f₁ for all 0 ≤μ≤1.

The setD₃^λ{0,0}is a one-point set. The setD₂^λis empty.

bIfλ ≥3/4, thenDD^λ₃ since for suchλclearlyμ1−μ≤f3for all 0≤μ≤1. The setD^λ₁ {1,0}is a one-point set. The setD^λ₂is empty.

For 1/4< λ <3/4 all three regionsD₁^λ,D₂^λ,D^λ₃ are nonempty sets. The setsD^λ₁andD^λ₃ have only one common pointdλ,0∈D, that is,D₁^λ∩D₃^λ{dλ,0}.

Lemma 2.1. Letλ∈R. Assume that a random variableXsatisfies

0≤X≤1, EXμ, EX−μ²σ². 2.11

Then

EX−λ⁴≤EX∗−λ⁴ 2.12 with a random variableX_∗satisfying2.11and defined as follows:

iifμ, σ²∈D₁^λ, thenX_∗is a Bernoulli random variable with distribution2.2;

iiifμ, σ²∈D₂^λ, thenX_∗is a trinomial random variable with distribution2.4;

iiiifμ, σ²∈D₃^λ, thenX_∗is a Bernoulli random variable with distribution2.7.

Proof. WritingY X−λ, we have to prove that if

−λ≤Y ≤1−λ, EY μ−λ, EY−EY² σ², 2.13

then

EY⁴≤EY_∗⁴ 2.14

withY_∗X_∗−λ. Henceforth we writead−λ, so thatY_∗can assume only the values−λ,a, 1−λwith probabilitiesq,r,pdefined in2.2–2.7, respectively. The distributionLY_∗ is related to the distributionνLX∗asB νBλfor allB⊂R.

Formally in our proof we do not need the description2.17of measuressatisfying 2.15. However, the description helps to understand the idea of the proof. Leta ∈ Rand σ²≥0. Assume that a signed measureof subsets ofRis such that the total variation measure ₋is a discrete measure concentrated in a three-point set{−λ, a,1−λ}and

Rdx 1,

Rxdx μ−λ,

Rx−μλ²dx σ². 2.15 Thenis a uniquely defined measure such that

q^def {−λ}, r^def {a}, p^def {1−λ} 2.16 satisfy

q σ²

a−μλ 1−μ

aλ , r μ

1−μ

−σ²

aλ1−a−λ, p σ²−

a−μλ μ 1−a−λ .

2.17

We omit the elementary calculations leading to2.17. The calculations are related to solving systems of linear equations.

Leta, b, c∈R. Consider the polynomial

Pt t−cb−tt−a²≡c₀c₁tc₂t²c₃t³−t⁴, t∈R. 2.18 It is easy to check that

c₃0⇐⇒bc2a0. 2.19

The proofs ofi–iiidiffer only in technical details. In all cases we finda,b, andc depending onλ,μandσ²such that the polynomialP defined by2.18satisfiesPt ≥ 0 for−λ ≤ t ≤ 1−λ, and such that the coefficientc3 in2.18vanishes,c3 0. Usingc3 0, the inequalityPt ≥ 0 is equivalent tot⁴ ≤ c₀c₁tc₂t², which obviously leads toEY⁴ ≤ c₀c₁μ−λ c₂σ². We note that the random variableY_∗assumes the values from the set

{t:Pt 0}

t:c0c1tc2t²t⁴

. 2.20

Therefore we have

EY⁴≤c0c1

μ−λ

c2σ²EY_∗⁴, 2.21 which proves the lemma.

iNowμ, σ²∈D^λ₁. We choosec1−λandaμ−λ−σ²/1−μ. In order to ensure c30cf.2.19we have to take

b−c−2a≡ −2μ−13λ 2σ²

1−μ. 2.22

Ifb≤ −λ, thenPt≥0 for all−λ≤t≤1−λ. The inequalityb≤ −λis equivalent to σ²≤

1−μ

μ−2λ1 2

≡f₁⇐⇒

μ, σ²

∈D₁^λ. 2.23

To complete the proof we note that the random variable Y_∗ X_∗ −λ with X_∗ defined by2.2assumes its values in the set{a,1−λ} ⊂ {t : Pt 0}. To find the distribution ofY_∗we use2.17. Settingaμ−λ−σ²/1−μin2.17we obtain q0 andr,pas in2.2.

iiNowμ, σ² ∈D₂^λor, equivalentlyσ² > f₁ andσ² > f₃. Moreover, we can assume that 1/4 < λ < 3/4 since only for suchλthe region D₂^λis nonempty. We choose c1−λandb−λ. ThenPt≥0 for all−λ≤t≤1−λ. In order to ensurec3 0 cf.2.19we have to take

a−bc

2 ≡λ− 1

2. 2.24

By our construction {t : Pt 0} {−λ, a,1−λ}. To find a distribution of Y_∗ supported by the set{−λ, a,1−λ}we use2.17. It follows thatX_∗Y_∗λhas the distribution defined in2.4.

iiiWe choosec−λandaμ−λσ²/μ. In order to ensurec₃ 0cf.2.19we have to take

b−c−2a≡3λ−2μ−2σ²

μ . 2.25

Ifb≥1−λ, thenPt≥0 for all−λ≤t≤1−λ. The inequalityb≥1−λis equivalent to

σ²≤μ

2λ−μ−1 2

≡f₃⇐⇒

μ, σ²

∈D^λ₃. 2.26

To conclude the proof we notice that the random variableY_∗X_∗−λwithX_∗given by2.7 assumes values from the set{−λ, a} ⊂ {t:Pt 0}.

To prove Theorems1.1and1.3we applyLemma 2.1withλμ. We provide the bounds of interest asCorollary 2.2. To prove the corollary it suffices to plug λ μin Lemma 2.1 and, using2.2–2.7, to calculateEX∗−μ⁴explicitly. We omit related elementary however cumbersome calculations. The regionsD₁,D₂, andD₃are defined in1.32.

Corollary 2.2. Let a random variable 0≤X≤1 have meanμand varianceσ². Then

EX−μ⁴≤

⎧⎪

⎪⎪

⎪⎪

⎪⎨

⎪⎪

⎪⎪

⎪⎪

⎩

σ⁶1−μ⁻²−σ⁴σ²1−μ², if μ, σ²

∈D1,

μ

1−μ μ−1

2 ₂

σ²

2μ²−2μ3 4

, if

μ, σ²

∈D₂, σ⁶μ⁻²−σ⁴σ²μ², if

μ, σ²

∈D3.

2.27

Proposition 2.3. Let 0≤X≤1. Then, with probability 1, the sample variance satisfiesσ²≤γ²σ² withγ²given by1.6.

Proof. Using the representation 1.3 of the sample variance as anU-statistic, it suffices to show that the functionf:Rⁿ → R,

fx

i /k,1≤i,k≤n

xi−xk², x x1, . . . , xn∈Rⁿ, 2.28

in the domain

D{x∈Rⁿ: 0≤x1 ≤1, . . . ,0≤xn≤1} 2.29 satisfiesf ≤2nn−1γ²σ². The functionfis convex. To see this, it suffices to check thatf restricted to straight lines is convex. Any straight line can be represented asL{xth:t∈R}

with somex, h ∈Rⁿ. The convexity offonLis equivalent to the convexity of the function gt^def fxthof the real variablet∈R. It is clear that the second derivativegt 2fh is nonnegative sincef≥0. Thus bothgandfare convex.

Since both f and D are convex, the function f attains its maximal value on the boundary ofD. Moreover, the maximal value off is attained on the set of extremal points of D. In our case the set of the extremal points is just the set of vertexes of the cube D.

In other words, the maximal value off is attained when each ofx1, . . . , xn is either 0 or 1.

Sincefis a symmetric function, we can assume that the maximal value offis attained when x₁ · · · x_m 1 and x_m1 · · · x_n 0 with somem 0, . . . , n. Using 2.28, the corresponding value off is 2mn−m. Maximizing with respect tomwe getf ≤ n²/2, if nis even, andf ≤ n² −1/2, ifnis odd, which we can rewrite as the desired inequality f≤2nn−1 γ²σ².

3. Proofs

We use the following observation which in the case of an exponential function comes back to Hoeffding 1, Section 5 . Assume that we can represent a random variable, sayT, as a weighted mixture of other random variables, sayT₁, . . . , T_m, so that

T α₁T₁· · ·α_mT_m, α₁, . . . , α_m≥0, α₁· · ·α_m1, 3.1 where α_s are nonrandom numbers. Let f be a convex function. Then, using Jensen’s inequalityfT≤α1fT1 · · ·αmfTm, we obtain

EfT≤α₁EfT1 · · ·α_mEfTm. 3.2

Moreover, if random variablesT1, . . . , Tmare identically distributed, then

EfT≤EfT1. 3.3

One can specialize3.3forU-statistics of the second order. Letux, y uy, xbe a symmetric function of its arguments. For an i.i.d. sampleX1, . . . , Xnconsider theU-statistic

U 1

nn−1

i /k,1≤i,k≤n

uXi, X_k. 3.4

Write

V 1

kuX1, X2 uX3, X4 · · ·uX2k−1, X2k, kn 2

. 3.5

Then3.3yields

EfU≤EfV 3.6

for any convex functionf. To see that3.6holds, letπ π1, . . . , πnbe a permutation of 1, . . . , n. Define Vπ as 3.5 replacing the sample X₁, . . . , X_n by its permutation X_π1, . . . , X_πn. Thensee1, Section 5

U 1 n!

π

Vπ, 3.7

which means thatUallows a representation of type3.1withmn! and allVπidentically distributed, due to our symmetry and i.i.d. assumptions. Thus,3.3implies3.6.

Using1.3we can write

T 1

nn−1

i /k,1≤i,j≤n

u X_i, X_j

3.8

withux, y σ²−x−y²/2. By an application of3.6we derive EfT≤Ef

Zk

k

, Ef−T≤Ef

−Zk

k

, kn 2

3.9

for any convex functionf, whereZk Y1· · ·Yk is a sum of i.i.d. random variables such that

Y₁^Dσ²− X1−X₂²

2 . 3.10

Consider the following three families of functions depending on parameterst, h∈R:

f y

y−h

t−h, t∈R, h < t, 3.11 f

y

y−h²

t−h² , t∈R, h < t, 3.12 f

y exp

h y−t

, t∈R, h >0. 3.13 Any of functionsfgiven by3.11dominates the indicator functiony→I{y∈t,∞}of the intervalt,∞. ThereforeP{T ≥t} ≤EfT. Combining this inequality with3.9, we get

P{T ≥t} ≤inf

h Ef Z_k

k

, P{T≤ −t} ≤inf

h Ef

−Z_k k

3.14

withZ_kbeing a sum ofki.i.d. random variables specified in3.10. Depending on the choice of the family of functionsf given by3.11, the inf in3.14 is taken overh < t orh > 0, respectively.

Proposition 3.1. One has

EX1−X₂⁴2ω6σ⁴. 3.15

If 0≤X≤1, thenωEX−μ⁴≤σ²−3σ⁴.

Proof. Let us prove3.15. Using the i.i.d. assumption, we have

EX1−X2⁴E

X1−μ μ−X2₄ 2EX−μ⁴−8E

X₁−μ

X2−μ³6EX1−μ²X2−μ² 2ω6σ⁴.

3.16

Let us prove thatω≤σ²−3σ⁴. If 0≤X≤1, thenX1−X2²≤1. Using3.15we have 2ω6σ⁴EX1−X₂⁴≤EX1−X₂²2σ², 3.17

which yields the desired bound forω.

Proposition 3.2. LetY be a bounded random variable such thata≤ Y ≤ bwith some nonrandom a, b∈R. Then for any convex functiong:a, b → Rone has

EgY≤Egε, 3.18

whereεis a Bernoulli random variable such thatEY EεandP{εa}P{εb}1.

IfY ≤bfor someb >0, andEY 0,EY²≤r², then3.18holds with g

y

y−h2

, h∈R, g

y exp

hy

, h≥0, 3.19

and a Bernoulli random variableεsuch thatEε0, varεr²,

p_r ^def P{εb} r²

b²r², q_r ^def P

ε−r² b

b²

b²r², 3.20

p_rq_r 1.

Proof. See2, Lemmas 4.3 and 4.4 .

Proof ofTheorem 1.1. The proof is based on a combination of Hoeffding’s observation3.6 using the representation 3.8 of T as a U-statistic, of Chebyshev’s inequality involving exponential functions, and ofProposition 3.2. Let us provide more details. We have to prove 1.22and1.24.

Let us prove1.22. We apply3.14with the family3.13of exponential functionsf.

We get

P{T≥t} ≤inf

h>0exp{−ht}Eexp hZ_k

k

. 3.21

By3.10, the sumZ_k Y₁· · ·Y_kis a sum ofkcopies of a random variable, sayY, such that

Y σ²−X1−X2²

2 . 3.22

We note that

Y ≤σ², EY 0, EY² ωσ⁴

2 ≤ ω0σ⁴

2 . 3.23

Indeed, the first two relations in3.23are obvious; the third one is implied byω≤ω₀,

EY² EX1−X2⁴

4 −σ⁴, 3.24

andEX1−X₂⁴2ω6σ⁴; seeProposition 3.1.

LetMstand for the class of random variablesYsatisfying3.23. Taking into account 3.21, to prove1.22it suffices to check that

J^def inf

h>0exp{−ht} sup

Y1,...,Yk∈MEexp hZk

k

H^k t

σ²;p

, 3.25

whereZ_kis a sum ofkindependent copiesY₁, . . . , Y_kofY. It is clear that the left-hand side of 3.25is an increasing function ofω₀. To prove3.25, we applyProposition 3.2. Conditioning ktimes on all random variables except one, we can replace all random variablesY1, . . . , Ykby Bernoulli ones. To find the distribution of the Bernoulli random variables we use3.23. We get

sup

Y∈MEexp hZk

k

Eexp hSk

k

, 3.26

whereS_kε₁· · ·ε_kis a sum ofkindependent copies of a Bernoulli random variable, say ε, such thatEε 0 andP{ε σ²} pwithpas in1.23, that is,p σ⁴ω0/3σ⁴ω0. Note that in3.26we have the equality sinceε∈ M.

Using3.26we have

Jinf

h>0exp{−ht}Eexp hS_k

k

infh>0 exp

−ht k

Eexp

hε k

k

infh>0 exp

−ht σ²

Eexp

hε σ²

_k

H^k t

σ²;p

.

3.27

To see that the third equality in3.27holds, it suffices to change the variablehbykh/σ². The fourth equality holds by definition1.13of the Hoeffding function sinceε/σ²is a Bernoulli random variable with mean zero and such thatP{ε/σ² 1} p. The relation3.27proves 3.25and1.22.

A proof of1.24repeats the proof of1.22replacing everywhereT andY by−Tand

−Y, respectively. The inequalityY ≤σ²in3.23has to be replaced by−Y ≤1/2−σ², which holds due to our assumption 0 ≤ X ≤ 1. Respectively, the probabilityp now is given by 1.25.

Proof of1.19. The bound is an obvious corollary ofTheorem 1.1since byProposition 3.1we haveω ≤σ²−3σ⁴, and therefore we can chooseω0 σ²−3σ⁴. Setting this value ofω0 into 1.22, we obtain1.19.

Proof of1.26and1.27. To prove1.26, we setω₀ σ²−3σ⁴in1.24. Such choice ofω₀is justified in the proof of1.19.

To prove1.27we use1.26. We have to prove that

H 2t

1−2σ²; 2σ²

≤H

2t; 2σ² 12σ²

, 3.28

and that the right-hand side of3.28is an increasing function ofσ². By the definition of the Hoeffding function we have

H 2t

1−2σ²; 2σ²

inf

h>0exp

− 2ht 1−2σ²

Eexp{hδ}

inf

h>0exp{−2ht}Eexp h

1−2σ² δ

,

3.29

where δ is a Bernoulli random variable such that P{δ 1} 2σ² and Eδ 0. It is easy to check that δ assumes as well the value−2σ²/1−2σ² with probability 1−2σ². Hence

−2σ²/1−2σ²≤δ≤1. Therefore−2σ²≤1−2σ²δ≤1−2σ², and we can write Eexp

h

1−2σ² δ

≤ sup

W∈MEexp{hW}, 3.30

whereMis the class of random variablesWsuch thatEW0 and−2σ²≤W≤1. Combining 3.29and3.30we obtain

H 2t

1−2σ²; 2σ²

≤inf

h>0 exp{−2ht}sup

W∈MEexp{hW}. 3.31

The definition of the latter sup in 3.31 shows that the right-hand side of 3.31 is an increasing function ofσ². To conclude the proof of1.27we have to check that the right- hand sides of3.28and3.31are equal. Using3.18ofProposition 3.2, we getEexp{hW} ≤ Eexp{hε}, whereεis a mean zero Bernoulli random variable assuming the values−2σ²and 1 with positive probabilities such thatP{ε1}2σ²/12σ². Sinceε∈ M, we have

sup

W∈MEexp{hW}Eexp{hε}. 3.32

Using the definition of the Hoeffding function we see that the right-hand sides of3.28and 3.31are equal.

Proof ofTheorem 1.3. We useTheorem 1.1. In bounds of this theorem we substitute the value ofω₀ being the right-hand side of2.27, where a bound of typeω ≤ ω₀ is given. We omit related elementary analytical manipulations.

Proof of the Asymptotic Relations1.7and1.8. To describe the limiting behavior ofT we use Hoeffding’s decomposition. We can write

nn−1

2σ² T n−1

1≤i≤n

u₁Xi

1≤i<k≤n

u₂Xi, X_k 3.33

with kernelsu1andu2such that

u₁x σ²−x−μ²

2σ² , u₂x

x−μ y−μ

σ² . 3.34

To derive3.33, use the representation ofTas aU-statistic3.8. The kernel functionsu₁and u2are degenerated, that is,Eu1X 0 andEu2X, x 0 for allx∈R. Therefore

var

nn−1 2σ² T

nn−1²varu₁nn−1

2 varu₂ 3.35

with

varu₁ ω−σ⁴

4σ⁴ , varu₂1, ωEX−μ⁴. 3.36

It follows that in cases whereω > σ⁴the statisticTis asymptotically normal:

√nT

√ω−σ⁴ −→η, asn−→ ∞, 3.37

whereη is a standard normal random variable. It is easy to see thatω σ⁴ if and only if X is a Bernoulli random variable symmetric around its mean. In this special case we have u1X≡0, and3.33turns to

nn−1T σ²

εD 1· · ·εn²−n, 3.38

whereε1, . . . , εnare i.i.d. Rademacher random variables. It follows that ωσ⁴⇒ n−1T

σ² −→η²−1, asn−→ ∞, 3.39 which completes the proof of1.7and1.8.

Acknowledgment

Figure 1was produced by N. Kalosha. The authors thank him for the help. The research was supported by the Lithuanian State Science and Studies Foundation, Grant no. T-15/07.

References

1 W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol. 58, pp. 13–30, 1963.

2 V. Bentkus and M. van Zuijlen, “On conservative confidence intervals,” Lithuanian Mathematical Journal, vol. 43, no. 2, pp. 141–160, 2003.

3 M. Talagrand, “The missing factor in Hoeffding’s inequalities,” Annales de l’Institut Henri Poincar´e B, vol. 31, no. 4, pp. 689–702, 1995.

4 I. Pinelis, “Optimal tail comparison based on comparison of moments,” in High Dimensional Probability (Oberwolfach, 1996), vol. 43 of Progress in Probability, pp. 297–314, Birkh¨auser, Basel, Switzerland, 1998.

5 I. Pinelis, “Fractional sums and integrals ofr-concave tails and applications to comparison probability inequalities,” in Advances in Stochastic Inequalities (Atlanta, Ga, 1997), vol. 234 of Contemporary Mathematics, pp. 149–168, American Mathematical Society, Providence, RI, USA, 1999.

6 V. Bentkus, “A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand,”

Lithuanian Mathematical Journal, vol. 42, no. 3, pp. 262–269, 2002.

7 V. Bentkus, “On Hoeffding’s inequalities,” The Annals of Probability, vol. 32, no. 2, pp. 1650–1673, 2004.

8 V. Bentkus, G. D. C. Geuze, and M. van Zuijlen, “Trinomial laws dominating conditionally symmetric martingales,” Tech. Rep. 0514, Department of Mathematics, Radboud University Nijmegen, 2005.

9 V. Bentkus, N. Kalosha, and M. van Zuijlen, “On domination of tail probabilities ofsupermartingales:

explicit bounds,” Lithuanian Mathematical Journal, vol. 46, no. 1, pp. 3–54, 2006.