Number of probes in a unsuccessful search in open address hashing

Question

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.

Answer 1

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