I couldn't understand why the probability of maximum deviation being larger than epsilon is smaller than the probability of all deviations being larger than epsilon.
Since maximum deviation is in the set of all deviations, I would expect that it prob of all deviations being larger than epsilon is smaller than this. (we need to satisfy only one point on the LHS)
It is an implication of this simple fact \(\max_k A_k\geq \epsilon \implies \exists k : A_k\geq \epsilon\). Then use the fact : \(A\subset B\implies P(A)\leq P(B)\).
[Lecture 4a] Proof: A simple union bound
I couldn't understand why the probability of maximum deviation being larger than epsilon is smaller than the probability of all deviations being larger than epsilon.
Since maximum deviation is in the set of all deviations, I would expect that it prob of all deviations being larger than epsilon is smaller than this. (we need to satisfy only one point on the LHS)
1
It is an implication of this simple fact \(\max_k A_k\geq \epsilon \implies \exists k : A_k\geq \epsilon\). Then use the fact : \(A\subset B\implies P(A)\leq P(B)\).
1
Add comment