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

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.

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