1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

Problem 1:

Use induction. Recall $n<m.$

$$\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$.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Avv
    Sep 3, 2021 at 15:31
  • $\begingroup$ 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? $\endgroup$
    – Avv
    Sep 3, 2021 at 16:20
  • $\begingroup$ So I guess the one above explains why we get n-i+2/m-i+2 and not n-i+1/m-i+1 $\endgroup$
    – Avv
    Sep 3, 2021 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.