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)}. \]