COMPX270 — Randomised and Advanced Algorithms
Chapter 2: Concentration Bounds, and Tricks
Markov, Chebyshev, Chernoff & Hoeffding bounds; the Union Bound; Randomised Median; and probability amplification techniques.
Why Concentration?
The Bus Analogy: You're waiting for a bus. Someone tells you it comes on average every 5 minutes. If you wait 20 minutes, what are the chances a bus arrives?
Knowing only the expectation (average), we can use Markov's inequality to say the probability the bus takes more than 20 minutes is at most \(\frac{5}{20} = \frac{1}{4}\). So there's at least a 75% chance you get the bus!
The Big Picture
In algorithm analysis, we often prove bounds on expected quantities: running time, output quality, resource usage. But expectations alone aren't enough — we need to know how concentrated a random variable is around its expectation.
Low Variance
The random variable is tightly clustered around its expectation. Reliable!
High Variance
The random variable can be far from its expectation. Unpredictable!
Concentration inequalities give us tools to quantify exactly how likely a random variable is to stray far from its expectation, with progressively stronger guarantees as we know more about it.
Interactive: Tail Bound Comparison
Adjust \(t\) to see how the Markov, Chebyshev, and Chernoff tail bounds compare for \(\Pr[X \geq t]\) where \(X \sim \text{Bin}(n, p)\).
Markov's Inequality
Theorem (Markov's Inequality)
Let \(X\) be a non-negative random variable with \(\mathbb{E}[X] < \infty\). For any \(t > 0\),
\[\Pr[X \geq t] \leq \frac{\mathbb{E}[X]}{t}\]Intuition: "You can't be 10 times your expectation more than 10% of the time."
For any \(t > 0\):
\[\mathbb{E}[X] = \sum_{x} x \cdot \Pr[X = x] \geq \sum_{x \geq t} x \cdot \Pr[X = x] \geq t \cdot \sum_{x \geq t} \Pr[X = x] = t \cdot \Pr[X \geq t]\]Dividing both sides by \(t\) gives the result. □
Application: Las Vegas → Monte Carlo
Lemma 4.2: If \(A\) is a Las Vegas algorithm with expected running time \(T\), then there exists a Monte Carlo algorithm \(A'\) with worst-case running time \(O(T)\) and failure probability \(\frac{1}{100}\).
Algorithm \(A'\)
- Run \(A\) on input \(x\) for at most \(100T\) steps
- if \(A\) terminated → return \(A\)'s output (always correct)
- else → return arbitrary output (likely wrong)
By Markov's inequality: \(\Pr[\text{runtime} \geq 100T] \leq \frac{T}{100T} = \frac{1}{100}\). Done!
Chebyshev's Inequality
Theorem (Chebyshev's Inequality)
Let \(X\) be a random variable with \(\mathbb{E}[X^2] < \infty\). For any \(t > 0\),
\[\Pr\!\big[|X - \mathbb{E}[X]| \geq t\big] \leq \frac{\operatorname{Var}[X]}{t^2}\]Apply Markov's inequality to the non-negative random variable \(Y = (X - \mathbb{E}[X])^2\):
\[\Pr\!\big[|X - \mathbb{E}[X]| \geq t\big] = \Pr\!\big[Y \geq t^2\big] \leq \frac{\mathbb{E}[Y]}{t^2} = \frac{\operatorname{Var}[X]}{t^2} \quad \square\]Markov vs Chebyshev: Comparison
- Requirements: \(X \geq 0\), know \(\mathbb{E}[X]\)
- Bound type: One-sided (upper tail only)
- Decay: \(1/t\) (linear)
- Advantage: Minimal assumptions
- Weakness: Often too loose
- Requirements: Know \(\mathbb{E}[X]\) and \(\operatorname{Var}[X]\)
- Bound type: Two-sided (both tails)
- Decay: \(1/t^2\) (quadratic)
- Advantage: No non-negativity needed; stronger
- Weakness: Needs variance information
The Union Bound
Lemma (Union Bound)
For any (possibly dependent, possibly countably infinite) events \(E_1, E_2, \ldots\),
\[\Pr\!\left[\bigcup_{k=1}^{\infty} E_k\right] \leq \sum_{k=1}^{\infty} \Pr[E_k]\]The union bound is deceptively simple but incredibly powerful. It lets us bound the probability that any bad event occurs, without needing to reason about dependencies between events.
Useful Corollary
The probability that none of the bad events occurs is:
\[\Pr\!\left[\bigcap_{k=1}^{\infty} \overline{E_k}\right] \geq 1 - \sum_{k=1}^{\infty} \Pr[E_k]\]Strategy: bound each bad event separately, then add them up. If the total is small, you're in good shape!
Randomised Median
Problem: Given an unsorted array \(A\) of \(n\) distinct integers, find the median.
Key idea: Sampling as a guide. Subsample a smaller array \(B\) of size \(m \ll n\), sort it, and use "approximate medians" of \(B\) to narrow down where the true median must be in \(A\).
Algorithm 3: Randomised Median (Worst-Case Linear Time)
Input: array \(A\) of \(n\) distinct integers
- Set \(\Delta = 4\sqrt{m}\)
- Create array \(B\) containing \(m\) elements of \(A\) chosen i.i.d. uniformly at random (with replacement)
- Sort \(B\) — time \(O(m \log m)\)
- Let \(b^-\) and \(b^+\) be the \(\big(\frac{m}{2} - \Delta\big)\)-th and \(\big(\frac{m}{2} + \Delta\big)\)-th elements of \(B\)
- Copy every \(x \in A\) with \(b^- \leq x \leq b^+\) into a new array \(C\) — time \(O(n)\)
- Compute \(k\) = number of elements of \(A\) smaller than \(b^-\) — time \(O(n)\)
- Compute \(\ell\) = number of elements of \(A\) larger than \(b^+\) — time \(O(n)\)
- if \(k > \frac{n}{2}\) or \(\ell > \frac{n}{2}\) then return FAIL
- else if \(|C| > \frac{16n}{\sqrt{m}} + 2\) then return FAIL
- else Sort \(C\) and return the \(\big(\frac{n+1}{2} - k\big)\)-th element of \(C\)
Choosing \(m\)
We need \(O(m \log m)\) and \(O\!\left(\frac{n}{\sqrt{m}} \log \frac{n}{\sqrt{m}}\right)\) to both be \(O(n)\). Setting them equal: \(m = \frac{n}{\sqrt{m}}\), giving \(m = n^{2/3}\).
Analysis: Three Bad Events
The algorithm fails only if one of three events occurs:
\(E_1\)
Too many elements smaller than \(b^-\): \(k > \frac{n}{2}\)
\(E_2\)
Too many elements larger than \(b^+\): \(\ell > \frac{n}{2}\)
\(E_3\)
\(C\) is too large: \(|C| > \frac{16n}{\sqrt{m}} + 2\)
By the union bound:
\[\Pr[\text{fail}] \leq \Pr[E_1] + \Pr[E_2] + \Pr[E_3]\]Bounding \(\Pr[E_1]\) (and \(\Pr[E_2]\) by symmetry)
Let \(X = \sum_{i=1}^{m} X_i\) where \(X_i \sim \text{Bern}(p)\) with \(p = \frac{1}{2} - \frac{1}{2n}\). Then \(\mathbb{E}[X] = \frac{m}{2} - \frac{m}{2n}\) and \(\operatorname{Var}[X] < \frac{m}{4}\).
We need \(X \leq \frac{m}{2} - \Delta\), which means \(X\) deviates from its expectation by at least \(\Delta - \frac{m}{2n} \geq \frac{\Delta}{2} = 2\sqrt{m}\). By Chebyshev:
\[\Pr[E_1] \leq \frac{m/4}{(2\sqrt{m})^2} = \frac{m/4}{4m} = \frac{1}{16}\]Bounding \(\Pr[E_3]\)
Using a similar Chebyshev argument on the rank of \(b^-\) and \(b^+\):
\[\Pr[E_3] \leq \frac{1}{32} + \frac{1}{32} = \frac{1}{16}\]Final Result
\[\Pr[\text{fail}] \leq \frac{1}{16} + \frac{1}{16} + \frac{1}{16} = \frac{3}{16} \approx 19\%\]Theorem 7
Randomised Median (Algorithm 3) is a linear-time Monte Carlo algorithm with failure probability at most \(\frac{3}{16}\).
Interactive: Randomised Median Simulation
Watch the algorithm step by step on an array of \(n = 10{,}001\) distinct integers. The true median is always 5001.
Probability Amplification
The Key Question
Our Randomised Median has failure probability \(\frac{3}{16} \approx 19\%\). Can we bring it down to \(1\%\)? To \(0.01\%\)? To \(\varepsilon\) for any \(\varepsilon > 0\)?
Yes! And we don't need to re-derive anything. We can amplify success probability in a black-box way.
When the algorithm "tells you" it failed
If the MC algorithm reports FAIL explicitly (like our Randomised Median), simply repeat with fresh random bits.
Run Algorithm 3 independently \(T\) times. Return the first non-FAIL output.
Probability all \(T\) runs fail: \(\left(\frac{3}{16}\right)^T\)
Setting \(\left(\frac{3}{16}\right)^T \leq \varepsilon\) gives \(T = O(\log(1/\varepsilon))\).
Corollary 7.1
For any \(\varepsilon \in (0,1]\), the repeated Randomised Median is a Monte Carlo algorithm with failure probability \(\leq \varepsilon\) and worst-case time \(O(n \log(1/\varepsilon))\).
When you can't tell if the output is wrong
Suppose each query to a data structure is correct with probability only 60%. We run \(T\) independent queries and take a majority vote.
Algorithm 5: Majority Vote Amplification
- for \(t = 1, \ldots, T\): \(y_t \leftarrow Q(x)\)
- return \(\text{majority}(y_1, \ldots, y_T)\)
Let \(Y = \sum_{t=1}^{T} \mathbf{1}[y_t \text{ is correct}]\). Then \(\mathbb{E}[Y] \geq \frac{6}{10}T\). Wrong only if \(Y < \frac{T}{2}\), which means \(Y\) is more than \(\frac{T}{10}\) below its expectation.
By the Chernoff bound: \(\Pr\!\left[Y < \frac{T}{2}\right] \leq e^{-T/120}\), which decays exponentially in \(T\)!
Setting \(T = O(\log(1/\varepsilon))\) achieves failure probability \(\leq \varepsilon\).
Monte Carlo → Las Vegas
If the MC algorithm tells us when it fails (like Algorithm 3), we can convert it to a Las Vegas algorithm:
Algorithm 4: Las Vegas via Indefinite Repetition
- repeat: run Algorithm 3 on \(A\) with fresh random bits; let \(y\) be output
- until \(y \neq \text{FAIL}\)
- return \(y\)
The number of iterations \(K\) is geometric with parameter \(p \geq \frac{13}{16}\). By the tail-sum formula:
\[\mathbb{E}[K] \leq \sum_{k=1}^{\infty} \left(\frac{3}{16}\right)^{k-1} = \frac{16}{13} \leq 1.231\]Expected running time: \(1.231 \cdot O(n) = O(n)\). A Las Vegas algorithm with expected linear time!
Interactive: Amplification Demo
Start with an algorithm that succeeds with probability 60%. See how the majority vote of \(T\) runs amplifies success.
Chernoff & Hoeffding Bounds
Theorem (Chernoff Bound)
Let \(X_1, \ldots, X_n\) be independent r.v.s taking values in \([0,1]\), and \(P := \sum_{i=1}^{n} \mathbb{E}[X_i]\). For any \(\delta \in (0,1]\):
\[\Pr\!\left[\sum_{i=1}^n X_i > (1+\delta)P\right] < \exp\!\left(-\frac{\delta^2 P}{3}\right)\] \[\Pr\!\left[\sum_{i=1}^n X_i < (1-\delta)P\right] < \exp\!\left(-\frac{\delta^2 P}{2}\right)\]Theorem (Hoeffding Bound)
Let \(X_1, \ldots, X_n\) be independent r.v.s, \(X_i \in [a_i, b_i]\). For any \(t \geq 0\):
\[\Pr\!\left[\sum_{i=1}^n X_i > \sum_{i=1}^n \mathbb{E}[X_i] + t\right] \leq \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)\]For i.i.d. \(X_i \in [0,1]\) with mean \(\mu\), Hoeffding simplifies to:
\[\Pr\!\left[\left|\frac{1}{n}\sum_{i=1}^n X_i - \mu\right| > \varepsilon\right] \leq 2\exp(-2\varepsilon^2 n)\]Chernoff vs Hoeffding: When to use which?
- Chernoff (multiplicative): Better when \(\mu = P/n \ll 1\). The bound scales with \(P\).
- Hoeffding (additive): Better for "symmetric" settings where \(\mu\) is not too small. The bound is in terms of an additive deviation \(t\).
- Both give exponential decay, far stronger than Chebyshev's polynomial decay.
- Both require full independence (unlike Chebyshev, which only needs pairwise independence).
The proof uses the moment-generating function (MGF) method:
- For any \(t > 0\): \(\Pr[X > (1+\gamma)\mu] = \Pr[e^{tX} > e^{t(1+\gamma)\mu}]\)
- Apply Markov: \(\leq \frac{\mathbb{E}[e^{tX}]}{e^{t(1+\gamma)\mu}}\)
- By independence: \(\mathbb{E}[e^{tX}] = \prod_{i=1}^n \mathbb{E}[e^{tX_i}]\)
- Bound each factor using \(\ln(1+x) \leq x\)
- Optimize over the free parameter \(t\) (set \(t = \ln(1+\gamma)\))
- Use \((1+\gamma)\ln(1+\gamma) - \gamma \geq \gamma^2/3\) to simplify
See the Math Foundations page for the full derivation. □
Concentration Inequalities: Summary
| Bound | Requirements | Result | Decay |
|---|---|---|---|
| Markov | \(X \geq 0\), know \(\mathbb{E}[X]\) | \(\Pr[X \geq t] \leq \frac{\mathbb{E}[X]}{t}\) | \(1/t\) (linear) |
| Chebyshev | Know \(\mathbb{E}[X]\), \(\operatorname{Var}[X]\) | \(\Pr[|X-\mathbb{E}[X]| \geq t] \leq \frac{\operatorname{Var}[X]}{t^2}\) | \(1/t^2\) (quadratic) |
| Chernoff | Sum of indep. \(X_i \in [0,1]\) | \(\Pr[|S-P| > \delta P] \leq 2e^{-\delta^2 P/3}\) | \(e^{-\Theta(n)}\) (exponential) |
| Hoeffding | Sum of indep. bounded r.v.s | \(\Pr[|S-\mathbb{E}[S]| > t] \leq 2e^{-2t^2/\sum(b_i-a_i)^2}\) | \(e^{-\Theta(n)}\) (exponential) |
The Independence Hierarchy
- Markov: No independence needed
- Chebyshev: Only pairwise independence needed
- Chernoff / Hoeffding: Full (mutual) independence needed
As the independence requirement increases, so does the strength of the bound!
Tutorial Problems
Tackle these problems to reinforce your understanding of concentration bounds and probability amplification.
Problem 1 Warm-up
Suppose \(E_1\) and \(E_2\) are two independent events, each happening with probability \(p\). What is the probability that at least one of them happens? Compare to what the union bound gives.
Generalise to \(k\) independent events \(E_1, \ldots, E_k\) each happening with probability \(p\).
Exact: \(\Pr[E_1 \cup E_2] = 1 - (1-p)^2 = 2p - p^2\)
Union bound: \(\Pr[E_1 \cup E_2] \leq 2p\)
For \(k\) events: exact is \(1 - (1-p)^k\), union bound gives \(kp\). They are asymptotically the same when \(p\) is small (the higher-order terms are negligible).
Problem 2 Warm-up
Prove Chebyshev's inequality using Markov's inequality.
Apply Markov's inequality to \(Y = (X - \mathbb{E}[X])^2\):
\[\Pr[|X - \mathbb{E}[X]| \geq t] = \Pr[Y \geq t^2] \leq \frac{\mathbb{E}[Y]}{t^2} = \frac{\operatorname{Var}[X]}{t^2} \quad \square\]Problem 3 Warm-up
Compute the expectation and variance of a \(\text{Poisson}(\lambda)\) random variable. (Recall: if \(X \sim \text{Poisson}(\lambda)\), then \(\Pr[X = k] = \frac{e^{-\lambda}\lambda^k}{k!}\) for \(k \geq 0\).)
Expectation:
\[\mathbb{E}[X] = \sum_{k=0}^{\infty} k \cdot \frac{e^{-\lambda}\lambda^k}{k!} = \lambda \cdot e^{-\lambda} \sum_{\ell=0}^{\infty} \frac{\lambda^\ell}{\ell!} = \lambda \cdot e^{-\lambda} \cdot e^{\lambda} = \lambda\]Variance: Compute \(\mathbb{E}[X^2]\) similarly, then \(\operatorname{Var}[X] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = \lambda\).
Both expectation and variance equal \(\lambda\).
Problem 4 Warm-up
Let \(X \sim \text{Bin}(n, p)\). Compute its expectation and variance.
(a) Bound \(\Pr[|X - \mathbb{E}[X]| > 2\sqrt{np}]\).
(b) For \(p = \frac{1}{4}\), use Markov, Chebyshev, Chernoff, and Hoeffding to bound \(\Pr[X \geq n/2]\). Compare.
(c) For \(p = \frac{1}{2n}\), bound \(\Pr[X \geq 1]\) using all four bounds. Compute the exact value and compare.
\(\mathbb{E}[X] = np\), \(\operatorname{Var}[X] = np(1-p)\).
(a) By Chebyshev: \(\Pr[|X - np| > 2\sqrt{np}] \leq \frac{np(1-p)}{4np} \leq \frac{1}{4}\).
(b) With \(p = 1/4\), \(\mathbb{E}[X] = n/4\), \(\operatorname{Var}[X] = 3n/16\):
- Markov: \(\leq \frac{n/4}{n/2} = \frac{1}{2}\)
- Chebyshev: \(\leq \frac{3n/16}{(n/4)^2} = \frac{3}{n}\)
- Chernoff (\(\gamma=1\)): \(\leq e^{-n/12}\)
- Hoeffding (\(t=n/4\)): \(\leq e^{-n/8}\)
Markov is weakest (constant). Chebyshev is polynomial. Chernoff and Hoeffding are exponential (Hoeffding slightly better here).
(c) With \(p = 1/(2n)\): Markov gives \(1/2\); Chebyshev gives a vacuous bound \(\approx 2\); Chernoff gives \(e^{-1/6} \approx 0.85\); Hoeffding gives \(\approx 1\). The exact value is \(\Pr[X \geq 1] = 1 - (1-1/(2n))^n \approx 1 - e^{-1/2} \approx 0.39\). Here Markov is actually the best bound!
Problem 5 Problem Solving
Prove Theorem 8: Let \(A\) be a Monte Carlo algorithm with worst-case running time \(T(n)\) and constant failure probability \(p \in (0,1)\), where one can detect incorrect output in \(O(1)\) time. Then there exists a Las Vegas algorithm \(A'\) with expected running time \(O(T(n))\).
Repeat: run \(A\), check output. If correct, return it; otherwise, run again with fresh random bits.
Each repetition takes \(T + O(1) = O(T)\). The number of repetitions \(K\) is geometric: \(\Pr[K \geq k] = p^{k-1}\).
\[\mathbb{E}[\text{running time}] = O(T) \cdot \sum_{k=0}^{\infty} p^k = O(T) \cdot \frac{1}{1-p} = O\!\left(\frac{T}{1-p}\right) = O(T) \quad \square\]Problem 6 Problem Solving
Given two MC algorithms \(A\) and \(B\) for a decision problem \(P\):
- If \(P(x) = \text{yes}\): \(A\) outputs yes with prob \(\geq 1/2\); \(B\) outputs yes with prob 1.
- If \(P(x) = \text{no}\): \(A\) outputs no with prob 1; \(B\) outputs no with prob \(\geq 1/2\).
Design a Las Vegas algorithm \(C\) using \(A\) and \(B\). Analyse its expected running time.
Run both \(A\) and \(B\) on \(x\):
- If \(A\) outputs "yes" → answer is "yes" (since \(A\) never says yes when the answer is no)
- If \(B\) outputs "no" → answer is "no" (since \(B\) never says no when the answer is yes)
- If \(A\) says "no" and \(B\) says "yes" → uncertain, repeat
The probability of needing to repeat is at most \(1/2\) in either case. So expected running time is \(O(T(|x|)) \cdot \sum_{k=0}^{\infty} (1/2)^k = O(T(|x|))\).
Problem 7 Problem Solving
Algorithm \(A\) outputs "good" or "bad" with: if \(x\) is good, \(\Pr[A(x) = \text{good}] \geq 9/10\); if \(x\) is bad, \(\Pr[A(x) = \text{good}] \leq 1/10\). Design \(A'\) achieving \(\Pr[\text{correct}] \geq 1-\delta\) for any \(\delta \in (0,1]\). Bound the resources used.
Repeat \(k\) times and take a majority vote. Apply the Chernoff/Hoeffding bound to show the failure probability decays exponentially in \(k\). Setting \(k = O(\log(1/\delta))\) suffices. Resources: \(T' = O(kT) = O(T\log(1/\delta))\), random bits: \(r' = O(kr) = O(r\log(1/\delta))\).
Problem 8 Problem Solving
Similar to Problem 7 but with one-sided error: if \(x\) is good, \(\Pr[A(x) = \text{good}] \geq 1/10\); if \(x\) is bad, \(\Pr[A(x) = \text{good}] = 0\). Design \(A'\) with \(\Pr[\text{good} | x \text{ good}] \geq 1-\delta\) and \(\Pr[\text{good} | x \text{ bad}] = 0\).
Repeat \(k\) times. Return "good" if any run returns "good" (this preserves zero false positive rate). The probability of never seeing "good" when \(x\) is truly good is at most \((9/10)^k\). Set \(k = \lceil\log_{10/9}(1/\delta)\rceil = O(\log(1/\delta))\).
Problem 9 Advanced
Prove the Chernoff bound: Given \(X_1, \ldots, X_n\) i.i.d. in \(\{0,1\}\) with \(\mathbb{E}[X_i] = p\), and \(X = \sum X_i\), show for \(\gamma \in (0,1]\):
\[\Pr[X > (1+\gamma)\mathbb{E}[X]] \leq e^{-\gamma^2 \mathbb{E}[X]/3}\]Steps: (a) Rewrite using \(e^{tX}\). (b) Apply Markov + independence. (c) Compute the MGF. (d) Use \(\ln(1+x) \leq x\). (e) Optimize over \(t\).
(a) \(\Pr[X > (1+\gamma)\mu] = \Pr[e^{tX} > e^{t(1+\gamma)\mu}]\) for any \(t > 0\).
(b) By Markov + independence: \(\leq \frac{(\mathbb{E}[e^{tX_1}])^n}{e^{t(1+\gamma)np}}\).
(c) \(\mathbb{E}[e^{tX_1}] = 1 + p(e^t - 1)\), giving \(\leq \frac{(1 + p(e^t-1))^n}{e^{t(1+\gamma)np}}\).
(d) Using \(\ln(1+x) \leq x\): \(\leq e^{-np \cdot f(t)}\) where \(f(t) = (1+\gamma)t - (e^t - 1)\).
(e) Maximizing \(f\): set \(f'(t) = (1+\gamma) - e^t = 0\), giving \(t = \ln(1+\gamma)\). Substituting and using \((1+\gamma)\ln(1+\gamma) - \gamma \geq \gamma^2/3\) completes the proof.
Problem 10 Advanced
Prove the other side of the Chernoff bound: \(\Pr[X < (1-\gamma)\mathbb{E}[X]] \leq e^{-\gamma^2 \mathbb{E}[X]/2}\) for \(\gamma \in (0,1]\). How can you generalise to \(X_i \in [0,1]\) (not necessarily identically distributed)?
The approach mirrors Problem 9 but uses \(e^{-tX}\) (a decreasing function) instead. The same MGF computation applies, optimising over \(t\) gives a slightly different constant, yielding the \(\gamma^2/2\) in the exponent. The generalisation to \(X_i \in [0,1]\) (not i.i.d.) follows because the MGF bound \(\mathbb{E}[e^{tX_i}] \leq 1 + \mathbb{E}[X_i](e^t - 1)\) still holds by convexity of the exponential function.
Problem 11 Advanced
The Median Trick: Given an algorithm \(A\) that outputs a "good value" for input \(x\) (in some interval \([a_x, b_x]\)) with probability guarantees \(\Pr[A(x) < a_x] \leq \alpha\) and \(\Pr[A(x) > b_x] \leq \alpha\) for \(\alpha < 1/2\). Run \(A\) independently \(k\) times and return the median. Analyse the success probability and set \(k\) to achieve \(1-\delta\).
(a) The median is less than \(a_x\) iff more than \(k/2\) outputs are below \(a_x\). Each is below \(a_x\) independently with probability \(\leq \alpha < 1/2\). By the Chernoff/Hoeffding bound, \(\Pr[\text{median} < a_x] \leq e^{-\Theta(k)}\). Similarly for exceeding \(b_x\). By union bound, the total failure probability is \(\leq 2e^{-\Theta(k)}\).
(b) Set \(k \geq C \cdot \log(2/\delta)\) for a suitable constant \(C > 0\) (depending on \(\alpha\)) to achieve failure probability \(\leq \delta\).
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).