Expected amount of tries to get $x$ amount of each of $y$ different elements in pool of $z$ elements

41 Views Asked by At

Let’s say I have a pool of $z$ different elements. Now I take one element of that pool at random, then add it back to the pool. Now suppose I only want, say, two specific elements of that pool, but $x$ of each of those. That 2 can be replaced with any number $ y \leq z $. How could I calculate the expected amount of tries that it would need to get at least $x$ of each of the wanted.

From a Wikipedia search on the coupon-collecter (thanks for the hint) problem I came to the conclusion that, given the variables I chose, I could calculate this using $E(t)= x\times z\times H_y$ where $H_y$ is the $y$-th harmonic number. That is assuming that the expected amount of tries to get at least $x$ of each of all of the coupons (elements of the pool) that are missing (wanted) is the same as getting each of them at least once, $x$ times over, which I am, quite honestly, not so sure of. Actually, now that I think about it, it seems logical that this is the case, even though the way I said it seems counter-intuitive.

Revisiting this problem after a couple of days it has come to my attention that the statement in the previous paragraph is incorrect. I calculated through an example with $x=2$, $y=4$ and $z=11$, going through it with the technique used to find the solution of the coupon collector‘s problem and came to the conclusion that the result is actually less ($\frac{134849}{3456}$ as opposed to $\frac{275}{6}$), due to the fact that getting two of the needed does not necessarily lead to the expected amount of tries to get a needed coupon increasing, as it can be distributed among two of them, leading to still $y$ of the $z$ possible options giving a needed coupon. I am still looking for a way to compute this for any numbers, without having to go through all of the options of distribution of successes. If there is no way to do so, I will simply write a computer program to compute this.