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 α=n/m<1, the expected number of probes in an unsuccessful search is at most 1/(1−α), assuming uniform hashing.

In the proof they are saying -

$p_i$ = It is the probability of exactly i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

$q_i$ = It is the probability of at least i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

Then it says -

$$\sum_{i=0}^\infty i\,p_i\, = \sum_{i=1}^\infty q_i$$

How it is so?

$\endgroup$
1
$\begingroup$

For any $i$, $q_i = p_i + p_{i+1} + p_{i+2} + \dots$. Now look at $\sum_{i\geq 1}q_i$ and how many times each $p_i$ occurs. $p_1$ occurs only in $q_1$; $p_2$ occurs in $q_1$ and $q_2$; and, in general, $p_i$ occurs only in $q_1,\dots, q_i$. In other words, each $p_i$ occurs $i$ times in the sum of the $q_i$s.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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