Number of probes in a successful search in open address hashing

Question

Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$

I read this in a book and the proof starts by saying

Searching for k follows the same probe sequence as inserting it. If $k$ is the $i+1$th key inserted into the table, then $\frac{1}{1-\frac{i}{m}}$ is the maximum expected number of probes for the search.

However I don't understand how $\frac{1}{1-\frac{i}{m}}$ gives the number of maximum probes needed. Imagine we have $n=5$ and $m=10$ with linear probing. Now if we want to insert the 6th key, based on the fraction above it should take us at most $\frac{1}{1-\frac{5}{10}}=2$ probes. However imagine if slots 0 through 4 were occupied in our table and we start at index 0, then I guess it would take 5 probes to find an empty slot, right?

Answer 1

You are almost right about "5 probes". It will take, in fact, 6 linear probes to find an empty slot if the probe starts at index 0 of a table with slots 0 through 4 occupied (and slot 5 available). They are 5 failing probes and 1 successful probe at last.

However, you are, apparently, skipping the meaning of the word "expected". That word here means "on average" basically.

---

While the number of probes can be as big as 4 sometimes, it can be as low as 1 many times as well. So it is not surprising the expected number of probes can be as low as 2.

To be exact and rigorous, the phrase "expected number" as in "the expected number of probes" and "the maximum expected number of probes" has a specific meaning defined in mathematical terms.

The expected value of a discrete random variable $X$ is $E[X]=\sum_xx\cdot \text{pr}\{X=x\}$, where $\text{pr}\{X=x\}$ is the probability of $X$ taking value $x$.

"The expected number of probes" is the shorthand for "the expected value of the discrete random variable that stands for the number of probes." You can understand it simply as "the average number of probes".

I would recommend you read sections in the textbook you are reading that introduce or review related concepts. Or section 3, Discrete random variables in Appendix C of the book CLRS.

Answer 2

Most books/notes do not tend to emphasize this point, however when talking about expected values one has to be clear about what exactly is random. Since we're talking about open addressing, we have a hash function $h: U\times [m]\rightarrow [m]$, and we're dealing with a uniformly distributed input. The standard uniform hashing assumption in this context is that every probe sequence is equally likely, i.e. when $X\in U$ is chosen uniformly at random, then $\left(h(X,1),h(X,2),...,h(X,m)\right)$ is uniformly distributed over the set of $m!$ permutations of $[m]$.

Now, if $X$ is chosen uniformly at random, and is inserted to a hash table with load factor $\alpha=n/m$, it makes sense to talk about the expectation of the random variable $T_X$ which denotes the number of probes until finding an empty cell (where again, the source of the randomness is at the choice the element $X\in U$). In Cormen's introduction to algorithms, theorem 11.6, it is proven that under the uniform hashing assumption, $\mathbb{E}[T_X]\le \frac{1}{1-\alpha}$. The word "maximum" is a bit misplaced, this is just an upper bound on the expectation. Your question follows immediately from applying this bound to the $i+1$ element inserted.