The expected number of takes from a discrete distribution before observing the given element

Let’s consider a discrete distribution $X$ defined by its probability mass function $p_X(x)$. We randomly take elements from $X$ until we observe the given element $x_0$. What’s the expected number of takes in this process?

This classic statistical problem could be solved in various ways. I would like to share one of my favorite approaches that involves the derivative of the series $\sum_{n=0}^\infty x^n$.

Let’s denote the result (the expected number of takes) as $K$ and the probability $p_X(x_0)$ of observing $x_0$ as $\alpha$. First of all, let’s write down the straightforward equation for $K$. The probability of observing $x_0$ after the first take is just $\alpha$. The probability of observing $x_0$ after the second take is $\alpha(1-\alpha)$. The probability of observing $x_0$ after the third take is $\alpha(1-\alpha)^2$. Continuing this process, we have

$$ K = 1 \cdot \alpha + 2 \cdot \alpha(1-\alpha) + 3 \cdot \alpha(1-\alpha)^2 + 4 \cdot \alpha(1-\alpha)^3 + \ldots = \alpha \sum_{n=0}^\infty n (1-\alpha)^{n-1}. $$

Now consider the following series:

$$ S(y) = \sum_{n=0} y^n. $$

It’s easy to see that

$$ S(y) = \sum_{n=0}^\infty y^n = 1 + \sum_{n=1}^\infty y^n = 1 + y \cdot \sum_{n=1}^\infty y^{n-1} = 1 + y \cdot \sum_{n=0}^\infty y^n = 1 + y \cdot S(y). $$

Solving $S(y) = 1 + y \cdot S(y)$, we get

$$ \sum_{n=0}^\infty y^n = S(y) = \frac{1}{1-y}. $$

By taking the derivative of both sides of this expression, we get

$$ \sum_{n=0}^\infty n \cdot y^{n-1} = \frac{1}{(1-y)^2}. $$

Putting $y = 1-\alpha$, we get

$$ K = \alpha \sum_{n_0}^\infty n \cdot y^{n-1} = \alpha \frac{1}{(1-y)^2} = \alpha \frac{1}{\alpha^2} = \frac{1}{\alpha}. $$

Thus, we get the answer:

$$ K = \frac{1}{p_X(x_0)}. $$