Case Splitting
--------------

.. raw:: latex

 Sia $B=B1 \U B2$, con $B1 \cap B2 = 0$, allora

      \eal{&  \Pr(A|B) = Pr(A | B1)Pr(B1 | B) + Pr(A | B2)Pr(B2 | B) }
                 

 Pf:
   per definizione di Pr(A|B),
   e anche perche' card(A ^ B) = card(A^B1)+ card(A^B2)



Chernoff Bound
---------------

http://en.wikipedia.org/wiki/Chernoff_bound
Una miglioria della Markov e Chebyshev inequality

[theorem 4.2 pg 81  Randomized-algorithms-Cambridge.pdf]
[theorem 4.1 pg 79  Randomized-algorithms-Cambridge.pdf]

vedi expected-cut-quasi-random-wireless-network.pdf

        Pr[ X ≤ (1 − eps)E[X] ] ≤ exp(−E[X]eps^2 /2)

expected minimo numero di lanci da fare per determinare se una moneta e' truccata
expected minimo numero di run per determinare che la maggioranza dei risultati di un algoritmo f() random e' il risultato corretto.