Are the geometric random variables in coupon collector problem independent?

362 Views Asked by At

Based on the "Calculating Variance" section in https://en.wikipedia.org/wiki/Coupon_collector%27s_problem, it appears that the geometric RVs in the coupon collector problem are independent.

I am having trouble understanding why they are independent. Let $X_i$ be the geometric random variable for the number of turns to get the $i-th$ item after having collected the first $i-1$ items. This is the typical definition of the geometric RV for the coupon collector problem, but doesn't this imply dependence, and not independence, since each subsequent $X_i$ depends on having collected the first $i-1$ items?

1

There are 1 best solutions below

3
On

If I understand you correctly, you are thinking about the time to get the $i$th item, but the article is talking about the difference between the time to get the $i$th and the time to get the $(i-1)$st item.

Let $Y_i$ be the time to get the $i$th item. Then $Y_i$ and $Y_{i+1}$ are certainly not independen, as you say. For example, $Y_{i+1}>Y_i$. However, $X_i=Y_i-Y_{i-1}$ and intuitively, at least, $X_i$ and $X_{j}$ are independent if $i\ne j$. $X_i$ is the number of coupons you had to buy after collecting the first $i-1$ until you got a new one. Not only does that seem independent of $X_j$, but also of $Y_{i-1}$.

The number of coupons you had to buy after collecting $4$ coupons, until you get the fifth, should have no effect on the number of coupons you have to buy between collecting the fifth and collecting the sixth, and neither should be affected by how long in took you to get to the fourth coupon.

Of course, this isn't a proof of independence, but the proof follows from the assumption that coupon draws are independent and identically distributed.