Bandit Algorithms

5.6 Exercises 79

5.5 (Berry–Esseen inequality) Let X 1 ,X 2 ,...,Xn be a sequence of

independent and identically distributed random variables with meanμ, variance

σ^2 and bounded third absolute moment

ρ=E[|X 1 −μ|^3 ]<∞.

LetSn=

∑n

t=1(Xt−μ)/σ. The Berry-Esseen theorem shows that

∣∣

∣∣

∣∣

∣∣

P

(

Sn

√

n

≥x

)

−

1

√

2 π

∫x

−∞

exp(−y^2 /2)dy

︸ ︷︷ ︸

Φ(x)

∣∣

∣∣

∣∣

∣∣

≤

Cρ

√

n

,

whereC < 1 /2 is a universal constant.

(a)Letμˆn=n^1

∑n
t=1Xtand derive a tail bound from the Berry-Esseen theorem.
That is, give a bound of the formP(ˆμn≥μ+ε) for positive values ofε.
(b)Compare your bound with the one that can be obtained from the Cramer-
Chernoff method. Argue pro- and contra- for the superiority of one over the
other.

5.6(Central limit theorem) We mentioned that invoking the central

limit theorem to approximate the distribution of sums of independent Bernoulli

random variables using a Gaussian can be a bad idea. LetX 1 ,...,Xn∼ B(p)

be independent Bernoulli random variables with common meanp=λ/nwhere

λ∈(0,1). Forx∈Nnatural number, letPn(x) =P(X 1 +···+Xn=x).

(a)Show thatlimn→∞Pn(x) =e−λλx/(x!), which is a Poisson distribution with
parameterλ.
(b)Explain why this does not contradict the CLT and discuss the implications
of the Berry-Esseen.
(c)In what way does this show that the CLT is indeed a poor approximation in
some cases?
(d)Based on Monte-Carlo simulations, plot the distribution ofX 1 +···+Xnfor
n= 30 and some well-chosen values ofλ. Compare the distribution to what
you would get from the CLT. What can you conclude?

5.7(Properties of subgaussian random variables) Prove Lemma 5.4.

Hint Use Taylor series.

5.8(Properties of subgaussian random variables (ii)) LetXibeσi-

subgaussian fori∈{ 1 , 2 }withσi≥0. Prove thatX 1 +X 2 is (σ 1 +σ 2 )-subgaussian.

Donotassume independence ofX 1 andX 2.

5.9(Properties of moment/cumulative generating functions) LetX

be a real-valued random variable and letMX(λ) =E[exp(λX)]be its moment-

generating function defined over dom(MX)⊂Rwhere the expectation takes on

finite values. Show that the following properties hold: