Pentru o intrare aleatorie. Fiecare bit are probabilitate $\frac{1}{2}$ să fie zero.
Apoi pentru că presupunem independență (funcția hash ideală implică această presupunere). Pentru fiecare intrare probabilitatea de a avea $4$ zerouri în biții de început este $\frac{1}{2^4}=\frac{1}{16}$.
Apoi $k$ calcule, deoarece considerăm că fiecare ieșire este independentă (totuși pentru că este o funcție hash ideală). Probabilitatea de a aștepta exact $i$ pași este o ieșire bună este $\frac{1}{16}\left(15/16\right)^{i-1}$. (pentru că aveți o ieșire greșită pentru $(i-1)$ hashes, și apoi unul prost).
Și așteptarea timpului de calcul este $\sum^{\infty}_{i=1} i\frac{1}{16}\left(15/16\right)^{i-1}=
\frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=j}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=0}\left(15/16\right)^{j+i-1 }$
$$=\frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\sum^{\infty}_{i= 0}\left(15/16\right)^{i} $$
$$= \frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\frac{1}{1/16}$ $
$$=\sum^{\infty}_{j=0} \left(15/16\right)^{j}
=16$$.
Apoi, în medie, trebuie să calculezi $16$ hashes pentru a găsi unul bun.
Puteți generaliza cu ușurință această dovadă prin înlocuire $16$ de $2^m$, și veți deduce că, în medie, trebuie să calculați $2^m$ hashuri.
Observați că, deoarece alegem în avans coordonatele unde vrem să avem zerourile, rezultatul total al funcției hash nu contează dacă ne uităm la numărul de hashuri pe care ar trebui să le calculăm (dar ar putea fi dacă ne uităm la timpul de calcul de $H$).
