 # 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}.$

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