0
$\begingroup$

I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor $\alpha = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1-\alpha)$, assuming uniform hashing.

In the proof they are assuming $p(i)$ to be the probability of exactly $i$ probes where we are finding all of the slots to be occupied. $i$ is $0,1,2,\dots$ so for $i > n$ we have $p(i) = 0$ since we can find $n$ slots already occupied. I have understood upto this point.

Then it says that expected number of probes in an unsuccessful search is $$1 + \sum_{i=0}^\infty i\,p(i)\,.$$ How is it so?

If there is any confusion to the question please comment. I hope I have explained the question properly. Any help would be appreciated. Thanks in advance.

$\endgroup$
1
$\begingroup$

It is the definition of expectation. When the probability of success in exactly $i$ probes is $p(i)$, it means you've been unsuccessful $i-1$ times before! Hence, the expected of unsuccessful steps is $$\sum_{i = 1}^{\infty}(i-1)\times p(i) = \sum_{i = 1}^{\infty}i\times p(i) + \sum_{i = 1}^{\infty}p(i) = 1 +\sum_{i = 1}^{\infty}i\times p(i)\,.$$

$\endgroup$
  • $\begingroup$ @eddard.stark my pleasure. $\endgroup$ – OmG Oct 2 '18 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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