Success Boosting

§ Motivation

Suppose we have a randomized algorithm $A$ which outputs a value $Z$ that is correct with probability $\displaystyle{\frac{2}{3}}.$

Suppose for our application, we want to obtain the correct result with probability $0.999,$ or $1 - \displaystyle{\frac{1}{n^2}},$ or $(1 - \delta).$

§ Median of Means

To illustrate the usefulness of Chernoff bounds and other concentration inequalities, we can take the aforementioned algorithm $A$. We run $A$ a total of $\displaystyle{\mathcal{O}\left(\log \frac{1}{\delta}\right)}$ times and take the median; with probability $(1 - \delta)$ it arrives at the correct answer.

§ Framework

Suppose we design a randomized algorithm $A$ to estimate a hidden statistic $\Theta$ of a dataset and we know in advance $0 < \Theta \leq 1000.$

Suppose each time we use $A,$ it outputs a number $X$ with $\mathbb{E}[X] = \Theta$ and $\text{Var}[X] = 100\,\Theta^2.$

Suppose we want to estimate $\Theta$ within tolerance $\varepsilon$ and with probability $1 - \delta.$

• Accuracy boosting: Repeat $A$ a total of $\displaystyle{\frac{10^{12}}{\varepsilon^2}}$ times and take the mean
• Success boosting: Find the mean of a total of $\mathcal{O}\left(\log \frac{1}{\delta}\right)$ trials and take the median to be correct with probability $1 - \delta.$

§ Max Load

Suppose we have a fair $n$‑sided die that is rolled $n$ times. On average, what is the largest number of times any outcome is rolled?

• $\Theta(1)$
• $\~{\Theta}(\log n)$
• $\~{\Theta}(\sqrt{n})$
• $\~{\Theta}(n)$

Let $k \in [n]$ be a fixed value and

$$X_i = \begin{cases} 1 &\text{if $i$-th roll is $k$}\\ 0 &\text{otherwise.} \end{cases}$$

Then, $\displaystyle{\mathbb{E}[X_i] = \frac{1}{n}}.$ The total number of rolls with value $k$ is $X = \sum_{i=1}^{n}X_i$ and $\mathbb{E}[X] = 1.$ Using Chernoff bounds, we can let $\delta = 3\log n$ and find that

$$\Pr[X \geq 3\log n] \leq \frac{1}{n^2}$$

Using union bound, we have at least a $\displaystyle{\left(1 - \frac{1}{n}\right)}$ probability that no outcome will be rolled more than $3 \log n$ times.

§ Coupon Collector

Suppose we have a fair $n$‑sided die. On average, how many times should we roll the die before we see all possible outcomes among the rolls?

• $\Theta(n)$
• $\Theta(n \log n)$
• $\Theta(n \sqrt{n})$
• $\Theta\left(n^2\right)$