3
$\begingroup$

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}$
$\endgroup$
3
  • 1
    $\begingroup$ The answers at stats.stackexchange.com/questions/101255 will help you a great deal. We have many threads about variations of the Coupon Collector's Problem and a large fraction of them provide relevant information. Try this site search. BTW, there are two ways to interpret your question: do you want the initial expectation or do you want the conditional expectation at each stage? (The latter is easy to find, BTW, and would seem more relevant in an actual test situation.) $\endgroup$
    – whuber
    Apr 21, 2022 at 13:01
  • $\begingroup$ Thanks @whuber for the links. Though, I don't really understand the difference between initial and conditional. If I want for example, the number of expected new questions at my 3 attempt, is this conditional on the fact that I already had 2 quizzes? $\endgroup$
    – Simone
    Apr 21, 2022 at 13:33
  • 1
    $\begingroup$ Suppose after several rounds you have seen all the questions. The conditional expectation of the number of new ones is zero. The unconditional expectation is what you would guess before starting the quiz. $\endgroup$
    – whuber
    Apr 21, 2022 at 14:02

1 Answer 1

2
$\begingroup$

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. $$

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.