# Number of probes in a unsuccessful search in open address hashing

Theorem: Given an open-address hash table with load factor $$α = n/m < 1$$, the expected number of probes in an unsuccessful search is at most $$1/(1−α)$$, assuming uniform hashing.

Let us define the random variable $$X$$ to be the number of probes made in an unsuccessful search, and let us also define the event $$A_i$$ , for $$i = 1, 2,\cdots,$$ to be the event that there is an ith probe and it is to an occupied slot. $$X$$ is defined in terms of intersection of events $$A_1, A_2, \cdots, A_{i-1}$$, so $$A_i$$ means the event that there is an $$i$$th probe and it's to and occupied slot. Then $$Pr[X\ge i] = P[A_1 \cap A_2 \cdots A_{i-1}] = Pr[A_1] \times \cdots \times Pr[A_{i-1} | A_1 \cap \cdots A_{i-2}]$$, so we have

\begin{align} Pr[X \ge i] = \frac{n}{m}\times \frac{n-1}{m-1} \times \cdots \frac{n-i+2}{m-i+2} \le (\frac{n}{m})^{i-1} \label{tag1}\tag1\\ \end{align}

Problem 1: I have trouble proving the above formula.

The reason we decrease $$m$$ by $$1$$ each time above because once we use a slot we can not use it again. $$Pr[X\ge i]$$ means the probability of not hitting a slot as it's already occupied by another item. For example, $$Pr[X\ge 1]$$ means the probability of having at least one collision given $$m$$ slots.

Attempt: I see that for $$i=1$$ for example, we have

$$Pr[X \ge 1] = \frac{n}{m}$$

I am not sure how to get this $$\frac{n-i+2}{m-i+2}$$ in the formula \ref{tag1}.

Problem 2: Why we have $$\le (\frac{n}{m})^{i-1}$$ above in \ref{tag1} and not $$\le (\frac{n}{m})^{i}$$ please?

Problem 3: Why $$Pr[X\ge i] = P[A_1 \cap A_2 \cdots A_{i-1}]$$ and not $$Pr[X\ge i] = P[A_1 \cap A_2 \cdots A_{m}]$$? I see that if $$Pr[X\ge 1] = P[A_1 \cap A_2 \cdots A_{m}]$$, so I am not sure why it's $$P[A_1 \cap A_2 \cdots A_{i-1}]$$ please? So this means $$A_m$$ is the event that we have already searched all slots and arrived at the last slot that is also occupied as I understand based on how $$X$$ was defined.

Problem 1:

Use induction. Recall $$n

$$\frac{n(n-1)}{m(m-1)} \leq \frac{n^2}{m^2}\quad\textit{if and only if}\quad n^2 m^2 -n m^2 \leq n^2 m^2 -m n^2$$

if and only if $$n^2m^2-n m^2 \leq n^2 m^2 -m n^2 \quad\textit{if and only if}\quad -m \leq -n$$ which can be checked directly. In fact the inequality is strict.

Then assume holds for $$i$$ prove for $$i+1$$ since the extra multiplicative factor is surely less than $$n/m$$.

Problem 2:

There are only $$i-1$$ terms in the product, so the expression $$(n/m)^{i-1}$$ after bounding.

Problem 3:

If you fail in the first $$i-1$$ trials then clearly $$X$$ is at least $$i$$.

• Thank you very much. I had some mistakes in the original question. I corrected them. $P[X \ge 1] = \frac{n}{m}$ indeed and not as I wrote it before. This means the probes of unsuccessful search (at least 1). Each has $1/m$, so total is $n/m$.
– Avv
Sep 3 '21 at 15:31
• From what I've read around, $P[#probes >2] = P[#Probes = 3] + P[#Probes = 4] + P[#Probes = 5] + \cdots+ P[#Probes = m]$. Since for $P[#Probes >=1] = P[#Probes = 1] + P[#Probes = 2] + P[#Probes = 3] +\cdots + P[#Probes = m] = n/m$, we can do the same for $P[#probes >2] = (n-2)/(m-2)+ (n-3)/(m-3)+ (n-4)/(m-4) +\cdots + (n-(i-1)+1)/(m-(i+1)+1)$. What do you think please?
– Avv
Sep 3 '21 at 16:20
• So I guess the one above explains why we get n-i+2/m-i+2 and not n-i+1/m-i+1
– Avv
Sep 3 '21 at 16:21