Đối với một đầu vào ngẫu nhiên. Mỗi bit có xác suất $\frac{1}{2}$ bằng không.
Sau đó, bởi vì chúng tôi giả sử tính độc lập (hàm băm lý tưởng ngụ ý giả định này). Đối với mỗi đầu vào, xác suất để có $4$ số không trong các bit hàng đầu là $\frac{1}{2^4}=\frac{1}{16}$.
Sau đó $k$ tính toán, bởi vì chúng tôi coi mỗi đầu ra là độc lập (vẫn bởi vì đó là một hàm băm lý tưởng). Xác suất đợi chính xác $i$ các bước là một đầu ra tốt là $\frac{1}{16}\left(15/16\right)^{i-1}$. (vì bạn có đầu ra sai cho $(i-1)$ băm, và sau đó là một hàm băm).
Và kỳ vọng về thời gian tính toán là $\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$$.
Sau đó, trung bình bạn phải tính toán $16$ băm để tìm một cái tốt.
Bạn có thể dễ dàng khái quát hóa bằng chứng này bằng cách thay thế $16$ qua $2^m$, và bạn sẽ suy ra rằng trung bình bạn cần tính $2^m$ băm.
Lưu ý rằng bởi vì chúng ta chọn trước các tọa độ mà chúng ta muốn có các số 0, nên tổng đầu ra của hàm băm không thành vấn đề nếu chúng ta nhìn vào số lượng giá trị băm mà chúng ta nên tính toán (nhưng nó có thể làm được nếu chúng ta xem xét thời gian tính toán của $H$).
