Dimostrare la probabilità di cui una funzione hash è priva di collisioni

Question

Supponiamo $ H = {h_1, ..., h_t } $ essere una famiglia di funzioni hash indipendenti a coppie mappatura $ {0, 1 }^n $ a $ {0, 1 }^{n/2} $. Permettere $ M = frac {2^{n/4}} {10} $ e lascia $ x_1, ..., x_m $ essere qualsiasi M Punti distinti in $ {0, 1 }^n $. Se scegliamo $ H $ forma casualmente $ H $ e lascia $ E $ Sii l'evento che $ h (x_1), ..., h (x_m) $ sono tutti distinti. Dobbiamo dimostrarlo $ Pr [e] ge frac {3} {4} $.

$ textbf {disuguaglianza di Markove:} $ Se $ X $ è una variabile casuale che richiede solo valori non negativi quindi, per qualsiasi $ t ge 0 $, $ Pr [x ge t] leq e [x]/t $.

L'idea è di calcolare $ Pr [h (x_i) = h (x_j)] $, calcola l'aspettativa della variabile casuale $ Z = | {(i, j): h (x_i) = h (x_j) } | $ E usa la disuguaglianza di Markove per dimostrare la domanda.

Per due punti indipendenti $ x_i $ e $ x_j $, la probabilità che $ h (x_i) $ e $ h (x_j) $ sono uguali è $ 1 - { text {La probabilità che due punti indipendenti hanno i diversi valori hash} } $, che è $ 1 - frac {2^{n/2}} {2^{n/2}} CDOT frac {2^{n/2} - 1} {2^{n/2}} $. Questo mostra $ Pr [h (x_i) = h (x_j)] = frac {1} {2^{n/2}} $.

Per quanto riguarda la variabile casuale $ Z $, forse possiamo lasciarci $ Z_ {i, j} = 1 text {if} h (x_i) = h (x_j) $. Altrimenti, $ Z_ {i, j} = 0 $. Allora possiamo ottenere $ Pr (z _ {(i, j)}) = frac {1} {2^{n/2}} $. Qui è dove mi sono bloccato. So come calcolare l'aspettativa la singola variabile casuale, che è $ sum_ {i = 1}^{n} x_i p (x = x_i) $. Ma non ho idea di come espandere questa formula alla variabile casuale della coppia $ (i, j) $. Inoltre sono un po 'confuso su come la disuguaglianza di Markove possa essere usata in questa prova.

Qualcuno potrebbe darmi qualche suggerimento? Qualsiasi aiuto sarebbe apprezzato. Grazie in anticipo.