Applying McDiarmid to a median

ProofAdvanced⏱ 30 minHigh-Dim Probabilitymcdiarmidbounded differencesmedianorder statistics

Problem

Let $X_1,\dots,X_n$ be independent with values in $[0,1]$ and let $f(X)$ be the sample median. Determine the bounded-differences constants $c_i$ and deduce a concentration bound for the sample median around its mean. Compare with the constants for the sample mean.

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

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
Azuma for a random walk with drift	High-Dim Probability	Proof	Intermediate	30 min
Derive Hoeffding's inequality from Hoeffding's lemma	High-Dim Probability	Proof	Intermediate	30 min
Locating the Bernstein crossover	High-Dim Probability	Numerical	Intermediate	30 min
Measure fan-out amplification and the value of hedging run	AI Systems	Coding	Intermediate	1 hour