# Expected number of distinct items seen before a given item when drawing from a probability distribution

We have a set of n items $a_1, a_2, a_3, \cdots, a_n$ with probabilities $p_1 \ge p_2 \ge p_3 \ge \cdots \ge p_n$ ($a_i$ has probability $p_i$). We draw items from this probability distribution. Let $n_i$ be the expected number of distinct items seen before we draw $a_i$ (for the first time). How do we compute $n_i$?

-

Hints:

• $n_i=\mathrm E(N_i)$ where $N_i=\sum\limits_{k\ne i}\mathbf 1_{A_k^i}$ and $A_k^i$ denotes the event that item $a_k$ is seen before item $a_i$.
• For each $k\ne i$, $\mathrm P(A_k^i)=\dfrac{p_k}{p_k+p_i}$ (sub-hint: heads or tails).
• Hence $n_i=\underline{\qquad\qquad}$.
-
Thanks. I was thinking along the same lines, but was confused about some of the details. –  M K Jul 12 '12 at 19:27
Hint : $n_i = \sum_{j \ne i} n_{ji}$ where $n_{ji}$ is $1$ if we see item $a_j$ before $a_i$, $0$ otherwise.