Finding out all questions in test bank

159 Views Asked by At

Let’s Say that a school has a test bank for an online multiple choice math exam which contains 100 questions. When a student starts his exam the system randomly selects 15 questions for him. If my friends and I decide to find out all the 100-questions, how many trials do we need if that is possible??

Edit:(as suggested in comments)

How many trials are needed, on average, to see all the questions??

3

There are 3 best solutions below

5
On BEST ANSWER

Consider $n$ trials. There are ${100\choose 15}^n$ options on how to choose them. There are ${99\choose 15}^n$ of them which do not cover some question $j$. Using exclusion-inclusion principle, $$ \text{count(non-covering cases)} = \sum_{i=1}^{85} (-1)^{i-1} {100\choose i} {100-i\choose 15}^n $$ so $$P_n(\text{covering}) = 1 - \frac{\sum_{i=1}^{85} (-1)^{i-1} {100\choose i} {100-i\choose 15}^n}{{100\choose 15}^n} $$ and "in average", you would wait $$\sum_{n=1}^\infty n P(\text{first covering is on trial } n) =\sum_{n=1}^\infty n (P_n - P_{n-1}) $$ ($P_0 = 0$).

Not sure how to simplify to something numerically feasible. Practically, I would use computer simulation.

0
On

Let's instead assume that we're sampling from the bank of 100 multiple choice questions one-by-one and with replacement. For each $i\in \mathbb{N}$ let $X_i$ denote the number of distinct questions we observed after sampling the the $i^{th}$ multiple choice question. Then $X_1=1$ and $\{X_i\}_{i\in \mathbb{N}}$ is an absorbing Markov Chain defined on the state space $ \{1,\ldots,100\} $ having transition probabilities $$P(X_{i+1}=r|X_i=r)=\frac{r}{100}$$ $$P(X_{i+1}=r+1|X_i=r)=\frac{100-r}{100}$$ Here $r=1,\ldots ,99$ while the final state of observing all 100 multiple choice questions is absorbing; techniques for computing the expected number of steps until we reach this absorbing state can be found using the fundamental matrix. If $E$ is this expected value, we can evaluate the ceiling of $(E+1)/15$ to get the answer you're looking for.

0
On

The answer was intended to be a comment but appears to be too long for this.

Let the full number of questions be $q$ and the number of questions on a ticket be $t$. All questions on a ticket are assumed to be distinct, so that $1\le t\le q$. We are looking for the expected value of the number of tickets required to reveal all $q$ questions. This is an extended version of the classical coupon collector problem (where $t=1$).

As shown by Peter Franek the probability that not all questions are covered after $k$ drawn tickets is $$ Q_k=\frac{-\sum_{i=1}^{q-t} (-1)^i\binom qi\binom{q-i}t^k}{\binom qt^k}. $$

From this (as already mentioned in a comment) the expected value in question can be computed as: $$ E(T)=1+\sum_{k=1}^\infty Q_k=1-\sum_{i=1}^{q-t} \frac{(-1)^i\binom qi}{\frac{\binom qt}{\binom{q-i}t}-1}. $$

It can be checked that the last expression reduces to the correct value $qH_q$ for $t=1$.

Particularly for $q=100, t=15$ one obtains: $E(T)\approx 32.5588$.