Simulate and compare the concentration inequalities

CodingIntermediate⏱ 1 hourHigh-Dim Probabilitysimulationhoeffdingbernsteincomparison

Problem

Write code that, for a given distribution on $[0,1]$ and sample size $n$ , estimates $\P(|\bar X_n - \mu| \ge t)$ by Monte Carlo and plots it against the Markov, Chebyshev, Hoeffding and Bernstein bounds on a logarithmic axis.

Verify that all four curves lie above the empirical one for every $t$ .
Identify, for Bernoulli $(0.5)$ and for Bernoulli $(0.05)$ , which bound is tightest in which range of $t$ .
Explain what limits the resolution of the empirical curve, and how to see that limit in the plot.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here5 tests · Python runs in your browser

⌘/Ctrl + ↵ to run · limit 30s · draft saved in this browser

5 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints

Hints — 0 of 2 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
Markov and Chebyshev are attained	High-Dim Probability	Proof	Foundation	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Two different curses of dimensionality	Classical ML	Numerical	Beginner	15 min
Azuma for a random walk with drift	High-Dim Probability	Proof	Intermediate	30 min