# Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most

There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions.

The hash function was chosen randomly among a set of uniform functions. A set $H$ of hash-functions $h:U\to\{0,\dots,m-1\}$ is called uniform, if for every tuple of different keys $x,y \in U$ the number of hash-functions $h \in H$ with $h(x) = h(y)$ is $\frac{|H|}{m}$ at most.

Show that the propability that for $i = 1, 2, \dots,n$ the $i$-th insert operation needs more than $k$ attempts, is $2^{-k}$ at most.

This is an assignment, which I got as homework. What I already worked out:

The propability $p_1$ for a collision is 0 of course for an empty table.

The propability $p_i$ for a collision after k attempts should be $\frac{i - 1}{2n}\cdot k$ assuming that the table is filled with $i-1$ elements to this point and the tables size is $2n$ as worst case.

So I have $$p_i= \frac{i-1}{2n} \cdot k \leq 2^{-k},$$

but I don't know where to go from here.

The method of open hashing used here simply iterates over different hash-functions until a free place is found (for example $h(x) = (x \bmod j) \bmod n$ with increasing prime numbers for $j$.

• There are several different variants of open hashing. Can you give pseudocode for your version? – Yuval Filmus Oct 7 '13 at 4:39

Hint: Show that at a given value of $i$, the probability of failure of the $l$th attempt is at most $i/m \leq 1/2$ (perhaps using a union bound), and the events are independent for different attempts.