Quiz with questions sampled from a pool. How many new questions at each iteration? [duplicate]

Question

I am taking a quiz which is a sample of $g$ questions from a pool of $n$ total questions. At every iteration $i$ I get a new sample of $g$ questions. I want to know the expected number of new questions (ie questions that I have not seen before) at iteration $i$

If $X_i$ is the random variable that models the number of new questions at iteration $i$, I would like to know $E[X_i]$. Is there a closed form for this?

• I do understand that at iteration $0$ I have $X_0=g$.
• At iteration $1$, $X_1$ is a Hypergeometric random variable with parameters $g$, $n-g$, and $n$, which are respectively the size of the sample, the number of successes, and the total number of items. Then, $$ E[X_1] = \frac{g(n-g)}{n} $$
• At iteration $2$, I know $X_2|X_1$ which is a Hypergeometric random variable with parameters $g$, $n-g-x_1$, and $n$. Then, $$ E[X_2] = \sum_{x_1} E[X_2|X_1=x_1]P(x_1) $$ I guess I could compute $E[X_i]$ with: $$ E[X_i] = \sum_{x_1,\dots,x_{i-1}} E[X_i|X_1=x_1, \dots, X_{i-1}=x_{i-1}]P(x_1,\dots,x_{i-1}) = \sum_{x_1,\dots,x_{i-1}} E[X_i|X_1=x_1, \dots, X_{i-1}=x_{i-1}]P(x_{i-1}|x_1,\dots,x_{i-2})\cdots P(x_1) $$ where I know all the conditional probabilities and also the expected value for $X_i|X_{i-1}\dots X_1$.

Does this sound correct? Is there any closed form for this?

I know that this is related the Coupon collector's problem. In particular, it is a generalization of it to Coupons in groups of constant size (see page 18 in here)

I also would like to know how far am I from the correct value if I take this approximation:

• $E[X_0] = g$
• $E[X_1] = \frac{g(n-E[X_0])}{n} = \frac{g(n-g)}{n}$
• $E[X_2] = \frac{g(n-E[X_0]-E[X_1])}{n} = \frac{g(n-g-\frac{g(n-g)}{n})}{n}$
• $E[X_i] = \frac{g(n-E[X_0]-E[X_1]-\cdots-E[X_{i-1}])}{n}$

Answer 1

Each question has a probability $1-g/n$ of not being picked in each iteration. Hence after the $i$'th iteration (letting $i=0$ denote the first iteration), each question has not been picked with probability $(1-g/n)^{i+1}$. The total number of questions not picked after round $i$, say $Y_i$, thus has expectation $E Y_i=n(1-g/n)^{i+1}$. The number of new questions at iteration $i$ is $X_i=Y_{i-1}-Y_i$. Thus $$ E X_i = n(1-g/n)^{i}-n(1-g/n)^{i+1} = g(1-g/n)^i. $$