[Math] Coupon Collector’s problem with unequal probabilities

coupon-collectorprobability

Given 4 different items, each with different chance of being selected, select an item, replace it and select another.

What is the expected mean number of selections that is required to select at least one of each item.

Through some research, this appears to be a variation of the coupon collector's problem where each of my "coupons" doesn't have the same probability.

From the final formula this post, I deduced that the average number of draws is given by:

$$
n\sum\limits_{j=1}^n {1\over j}
$$

How can I amend this for items of unequal probability of selection please?

From the partial answer from @John:

$p_1 = 1$
$p_2 = p_a (p_b + p_c + p_d) + p_b (p_c + p_d + p_a) + p_c (p_d + p_a + p_b) + p_d (p_a + p_b + p_c)$

Am I then right in thinking $p_3$ would be
$
p_ap_b(p_c + p_d) +
p_ap_c(p_b + p_d) +
p_ap_d(p_b + p_c) +
p_bp_c(p_a + p_d) +
p_bp_d(p_a + p_c) +
p_cp_d(p_a + p_b)
$

and $p_4$ would be
$
p_ap_bp_c(p_d) +
p_ap_bp_d(p_c) +
p_ap_cp_d(p_b) +
p_bp_cp_d(p_c)
$ simplified to $4(p_ap_bp_cp_d)$


I put these values into a spreadsheet, but there's something I've done wrong. For the purpose of testing, I gave my coupons equal probability where I know the result should be 8.33. However, I'm getting the result 71.67 and can't see what is wrong. Any suggestions please?

enter image description here

Best Answer

$\def\m{\boldsymbol\mu}\def\p{\mathbf p}$

The expected value in question reads: $$ \mathbb E=\sum_i\frac1{p_i}-\sum_{(i,j)}\frac1{p_i+p_j}+\sum_{(i,j,k)}\frac1{p_i+p_j+p_k}-\cdots-\frac{(-1)^n}{\underbrace{p_1+p_2+\cdots+p_n}_{=1}}.\tag1 $$

It can be written in a compact notation as: $$ \mathbb E=\sum_{\m\ne0}\frac{(-1)^{|\m|-1}}{\m\cdot\p},\tag2 $$ where $\m$ are $2^n$ binary vectors of the length $n$ with $|\m|=\sum_{i=1}^n\mu_i$, and $\p=(p_1,p_2,\dots, p_n)$. The summation in (2) runs over all $\m$ except for $(0,0,\dots,0)$.