How is this the expected number of of probes in open-address hashing?

Question

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.

Answer 1

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