Prouver la probabilité de quelle fonction de hachage est sans collision

Question

Supposer $ H = {h_1, ..., h_t } $ être une famille de fonctions de hachage indépendantes par paires cartographie $ {0, 1 } ^ n $ à $ {0, 1 } ^ {n / 2} $. Laisser $ M = frac {2 ^ {n / 4}} {10} $ et laisser $ x_1, ..., x_m $ être des points distincts dans $ {0, 1 } ^ n $. Si nous choisissons $ h $ former au hasard $ H $ et laisser $ E $ être l'événement qui $ h (x_1), ..., h (x_m) $ sont tous distincts. Nous devons montrer que $ Pr [e] ge frac {3} {4} $.

$ textbf {l'inégalité de Markove:} $ Si $ X $ est une variable aléatoire qui ne prend que des valeurs non négatives alors, pour tout $ t ge 0 $, $ Pr [x ge t] leq e [x] / t $.

L'idée est de calculer $ Pr [h (x_i) = h (x_j)] $, calculer l'attente de la variable aléatoire $ Z = | {(i, j): h (x_i) = h (x_j) } | $ Et utilisez l'inégalité de Markove pour prouver la question.

Pour deux points indépendants $ x_i $ et $ x_j $, la probabilité que $ h (x_i) $ et $ h (x_j) $ sont égaux est $ 1 - { text {la probabilité Deux points indépendants ont les différentes valeurs de hachage} } $, lequel est $ 1 - frac {2 ^ {n / 2}} {2 ^ {n / 2}} cdot frac {2 ^ {n / 2} - 1} {2 ^ {n / 2}} $. Cela montre $ Pr [h (x_i) = h (x_j)] = frac {1} {2 ^ {n / 2}} $.

Quant à la variable aléatoire $ Z $, peut-être que nous pouvons laisser $ Z_ {i, j} = 1 text {if} h (x_i) = h (x_j) $. Autrement, $ Z_ {i, j} = 0 $. Ensuite, nous pouvons obtenir $ Pr (z _ {(i, j)}) = frac {1} {2 ^ {n / 2}} $. C'est là que je suis resté. Je sais comment calculer l'attente de la variable aléatoire unique, qui est $ sum_ {i = 1} ^ {n} x_i p (x = x_i) $. Mais je ne sais pas comment étendre cette formule à la variable aléatoire de la paire $ (i, j) $. Je suis également un peu confus comment l'inégalité de Markove pourrait être utilisée dans cette preuve.

Quelqu'un pourrait-il me donner quelques indices? Toute aide serait appréciée. Merci d'avance.