7
$\begingroup$

Suppose you have two people take an exam which is composed of 30 questions which are randomly chosen from a test bank of n questions.

Person A and Person B both take different randomly generated instances of the exam, and then compare the question sets they were given. Person B notices that 7 of their 30 questions were repeated from Person A's question set.

Is there anyway to deduce the likely total number of questions in the test bank given you know 7/30 of them were repeated in a second instance of the exam? Obviously you would not get an exact value, but could you determine a range of probabilities for each different size of the test bank? How you would you go about solving this?

Thank you!

$\endgroup$
  • 4
    $\begingroup$ You have a population of $n$ questions, from which $K=30$ are tagged as successes (Questions of Person A) and you draw a sample of $m=30$ questions (Questions for Person B). Then the number of successes (same questions) is hypergeometrically distributed with the above parameters and hence the probability of $k=7$ successes (same questions) is equal to $$\dfrac{\dbinom{30}{7}\dbinom{n-30}{23}}{\dbinom{n}{30}}=\frac{30!^2(n-30)!^2}{n!7!23!^2(n-53)!}$$ So, you need to solve $$\max_n \frac{(n-30)!(n-30)!}{n!(n-53)!}$$ $\endgroup$ – Jimmy R. Jan 1 '16 at 20:41
  • 3
    $\begingroup$ @Stef, it's probably enough to use Stirling's formula to approximate the factorials, perhaps something simplifies in the process. $\endgroup$ – vonbrand Jan 1 '16 at 20:44
  • 2
    $\begingroup$ @GregoryGrant I cheated a little :) I read your comment (came second) so posted this only for comparison. $\endgroup$ – Jimmy R. Jan 1 '16 at 20:50
  • 2
    $\begingroup$ @Stef Got it, nobody can say you're not honest :-) $\endgroup$ – Gregory Grant Jan 1 '16 at 20:51
  • 2
    $\begingroup$ Use a numeric method $\endgroup$ – vonbrand Jan 1 '16 at 21:09
3
$\begingroup$

The minimum number in the pool must be $53$. Suppose there are $n$ in total.

So it's like if you had an urn with $n$ balls, $30$ are white and $n-30$ are red. Then you pull $30$ balls at random. You want to know how many of the balls you pulled are white. Or more specifically you want to know the probability that $7$ of the $30$ you pull are white.

Let $A$ be the number of white balls. Then $P(A=k)$ is hypergeometric and equal to

$\frac{{{30}\choose{k}}{ {n-30}\choose{30-k}}}{{n}\choose{30}}$

So in your case:

$\frac{{{30}\choose{7}}{{n-30}\choose{23}}}{{n}\choose{30}}$

This is the probability of an overlap of exactly $7$.

You now need to find the $n$ that maximizes that probability.

If you start plugging in numbers (using a calculator) starting at $n=53$ you'll probably see that it goes up and then soon starts to go back down. Choose the max before it starts going back down. Shouldn't be too much larger than 53. I'm guessing somewhere around 100.

$\endgroup$
  • $\begingroup$ Thank you for this explanation! It was extremely clear and I really appreciate it! After a little WolframAlpha magic, I found 128 questions to be the maximum. So if I understand this correctly, the test bank is composed of anywhere between 53-128 questions, with 128 questions being the most probable? $\endgroup$ – ProfessorStealth Jan 1 '16 at 20:59
  • 1
    $\begingroup$ @ProfessorStealth Well there could be more than $128$ questions, it's just that $128$ is the most likely. There could be $500$ questions, but then having $7$ come up in common starts to be quite unlikely when there are that many in the pool. $\endgroup$ – Gregory Grant Jan 1 '16 at 21:01
  • 1
    $\begingroup$ @ProfessorStealth Oh and you're very welcome :-) $\endgroup$ – Gregory Grant Jan 1 '16 at 21:03
4
$\begingroup$

This can be solved by 'capture-recapture' or 'mark-recapture' methods of estimating population size. One person is 'capture' and the other is 'recapture'. The 'Chapman' estimator (see Wikipedia on 'mark recapture') in this case is $\hat N_C = (30 + 1)(30 + 1)/(7 + 1) -1 \approx 119.$ Based on a hypergeometric model, this estimator is nearly unbiased. The Wikipedia gives two methods for finding a corresponding confidence interval.

The older and simpler 'Lincoln-Peterson' estimator is simply $\hat N = 30^2/7 \approx 128.$ It gives an infinite value if there happen to be no repeated questions. Thus $E(\hat N)$ does not exist, and one cannot discuss the unbiassedness of this estimator.

Addendum: The comments and the answer by @GregoryGrant are using the Lincoln-Peterson estimator, which is the maximum likelihood estimator, based on knowledge that there are 7 coincidences. Here is some relevant R code and a figure:

 N = 100:150
 like = choose(30,7)*choose(N-30, 30-7)/choose(N, 30)
 N[like==max(like)]  # value of N that maximizes 'like'
 ## 128
 plot(N, like, pch=20);  abline(v=128, lty="dotted")

enter image description here

Note: Here is one method to get an analytic solution for the maximum: Let $f(N|7) = {30 \choose 7}{N-30 \choose 23}/{N \choose 30}.$ Then look at $f(N|7)/f(N-1|7),$ simplifying it with lots of cancellation. Then notice the behavior of the ratio.

$\endgroup$
  • 3
    $\begingroup$ Based on the exact solution he found using the hypergeometric, your $129$ is remarkably close to the $128$ he found. I must say I'm impressed I'll have to look into this Lincoln-Peterson estimator. $\endgroup$ – Gregory Grant Jan 1 '16 at 21:04
  • $\begingroup$ @GregoryGrant: If $a = b$ is the number on each test and 7 is the number of repeated questions, then intuitively $7/b \approx a/N$. Then $N \approx ab/7.$ Sort of a 'method of moments' approach. $\endgroup$ – BruceET Jan 1 '16 at 21:27
  • 1
    $\begingroup$ Nice that also gives $128$ ($900/7$ right?). Obviously there are many ways to skin this cat. This was obviously a stimulating question for all. And no lack of civility. That's how it should be, heartwarming :-) $\endgroup$ – Gregory Grant Jan 1 '16 at 21:31
  • $\begingroup$ @GregoryGrant: Wishing us all a Happy Snark-Free New Year. $\endgroup$ – BruceET Jan 1 '16 at 21:35
  • $\begingroup$ Thank you, that would be wonderful :-) $\endgroup$ – Gregory Grant Jan 1 '16 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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