From an exponential tail bound to almost sure convergence

ProofIntermediate⏱ 30 minProbabilityborel cantellialmost sureconcentration

Theory: Probability Spaces and Random Variables →

Problem

Let $X_1,X_2,\dots$ be i.i.d. with $X_i\in[0,1]$ and mean $\mu$ , and let $\bar X_n$ be the sample mean. Using Hoeffding's inequality and Borel–Cantelli, prove that

\bar X_n \to \mu \quad\text{almost surely},

and moreover that $|\bar X_n - \mu| \le \sqrt{\frac{2\log n}{n}}$ for all sufficiently large $n$ , almost surely.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Pairwise independence does not imply independence	Probability	Proof	Foundation	15 min
When is the union bound tight?	Probability	Proof	Foundation	15 min
Distance contrast and the failure of nearest neighbours	Classical ML	Proof	Intermediate	30 min
Simulate the measure of a spherical cap run	High-Dim Probability	Coding	Intermediate	30 min
Distance contrast in high dimension	High-Dim Probability	Proof	Advanced	1 hour