<h2>Lecture 11</h2>
- *consistent:* given more accurate predictions, the online algorithm should perform close to the optimal offline algorithm, and
- *robust:* if the prediction is wrong, the online algorithm performance should be close to the online algorithm without predictions:

<h2>Lecture 12</h2>
- *Uniform distribution:* All chances are equal: $\text{Pr}(X=k)=\frac{1}{|\text{codom}(X)}$
- *Geometric distribution:* Number of trials until the first success in a sequence of Bernoulli trials: $\text{Pr}(X=k)=(1-p)^{k-1}p$, $\mathbb{E}[X]=\frac{1}{p}$.

<h2>Lecture 13</h2>

<ul>
<li><em>Yao’s Principle, informal:</em> The worst-case performance of the best
randomized algorithm is equal to the average performance of the best
deterministic algorithm on the worst distribution of the inputs or</li>
<li>If $$\frac{\text{min}<em>{\text{Alg}\in\mathcal{A}}\mathbb{E}</em>{\text{ADV}}\left[\text{Alg}(\mathcal{I})\right]}{\mathcal{E}<em>{\text{Adv}}\left[\text{Opt}(\mathcal{I})\right]}\geq c$$. In other words the average performance of the best deterministic algorithm is greater than $c$, then $$\frac{\mathcal{E}</em>{\text{Rand}}\left[\text{Rand}(I)\right]}{\text{Opt}(I)}\geq c$$</li>
<li><em>Coupon Collector’s Problem:</em> If each box of breakfast cereal contains a
coupon, and there are $n$ different coupons, how many boxes do you need to buy
in expectation to collect all $n$ coupon? Answer $nH_n$.</li>
</ul>
<p>Theorem
No randomized online algorithm for paging is better than Hk -competitive in
expectation, even when $M = k + 1$. For each random algorithm $\mathcal{A}$</p>