I have a problem. Our professor is giving us at the exam the opportunity to choose to answer only one topic among eight on the exam. The total number of topics in the subject is twenty-two.

I would like to know what is the minimum number of topics to study in order to get at least 90% probability to know at least one of the topics on the exam. I am assuming that all topics are selected with equal probability.

If it's possible I would like to have an explanation on the results.

  • 3
    $\begingroup$ Please do not use unrelated tags -- e.g. your question has literally nothing to do with deep learning and machine learning! $\endgroup$ – Tim May 31 '17 at 8:58
  • $\begingroup$ 90% probability of what, exactly? Under what assumptions? Are you assuming that all topics are selected with equal probability? Are you assuming that no matter the topic you will learn it as well as any other topic if you study it? What's the subject? $\endgroup$ – Glen_b -Reinstate Monica May 31 '17 at 9:05
  • $\begingroup$ I edited glen_b! $\endgroup$ – DanielM May 31 '17 at 9:49
  • 1
    $\begingroup$ Is the subject you're studying probability? ... is this an exercise you've been set? $\endgroup$ – Glen_b -Reinstate Monica May 31 '17 at 10:00
  • $\begingroup$ No, I only want to know how many topics to study to get 90% $\endgroup$ – DanielM May 31 '17 at 10:04

First I did simulation and got:

 1: 0.365067
 2: 0.605832
 3: 0.764096
 4: 0.862886
 5: 0.923471
 6: 0.959731
 7: 0.979571
 8: 0.990522
 9: 0.995992
10: 0.998401
11: 0.99944
12: 0.999864
13: 0.999978
14: 0.999995
15: 1.0
16: 1.0
17: 1.0
18: 1.0
19: 1.0
20: 1.0
21: 1.0
22: 1.0

It provides answer 5 and more realistic values for k starting from 15.

I believe that right formula based on $$ P(X_i>k) = \frac{22-k-i}{22-i} $$ where i is in 0..7

Example: You have studied only 5 topics from 22. And now your professor "creating" exam topics pool. To fail you, he should choose 22-5=17 "unstudied" topics from 22 at first step. After this only 21 topics left. So on the second step the professor should choose 21-5=16 "unstudied" topics from 21. And so on.
Total chance to fail you: $$ \frac{22-5}{22}*\frac{21-5}{21}*...*\frac{15-5}{15}=0.076 $$ You win: ~0.924

Edit: Above formula return 0 for k > 14 as it should be - if you studied 15+ topics, there is no chance to create 8topics exam to fail you. One of the factors turns into 0 because of 22 - k - i.

  • $\begingroup$ Can you explain how the phrase sumulation.( k ) calls the call method ? Which feature of ruby is this ? $\endgroup$ – bsd May 31 '17 at 17:06
  • $\begingroup$ Its syntax sugar called "dot-parentheses notation" from Ruby's lambda world. You can find a lot of info right on SO. .(params) is equal to .call(params) $\endgroup$ – Pavel Mikhailyuk Jun 1 '17 at 7:22

$^\textit{(The first version of this answer didn't account for the fact that topics are selected without replacement. Corrected.)}$

Assume the topics on the exam are chosen at random. Then (without loss of generality) assume you study the topics numbered $1, 2, ..., k$.

Then if the lowest numbered topic on the exam is $\leq k$ you will have studied at least one of the exam topics.

Let's work with the complement -- the probability that none of the topics we chose are on the exam. Imagine each topic in the subject is represented by a ball -- the $k$ topics we study are white balls and the ones we didn't ($22-k$) are black. The professor's random choice of topics selects $8$ balls at random from the $22$ available. What's the chance the professor draws only black balls?

The chance the first draw is black is $(1-\frac{k}{22}$. Given it was black the chance the second is black is $(1-\frac{k}{21}$, and so on down to $(1-\frac{k}{15}$. The probability all were black is the product, and the complement of that is the probability we're interested in:

So $\,\text{at least one white ball } = 1-(1-\frac{k}{22})\times(1-\frac{k}{21})\times...(1-\frac{k}{15})$ (we can write this as a product of combinations (it's just a hypergeometric) but I'll leave it in this form for now.

So (as long as the assumptions are reasonable) if you study $k$ topics this gives the probability there's at least one of those topics on the exam.

    topics  %Chance >0
   studied   on exam
       1     36.36
       2     60.61
       3     76.36
       4     86.32
       5     92.40
       6     95.98
       7     97.99
       8     99.06
       9     99.60

(If the exam topics aren't chosen completely randomly with equal probability, you'd need to choose study topics at random to get these values)

A 10% chance (well, more like 8% as it turns out) of not having studied any of the topics seems like a bit of a risk but the required minimum number of topics is $5$, as we see in the table (not 6 as I said earlier)

  • $\begingroup$ I think by elevating with 8 the probability you are picking a combination multiple times i.e. you are taking both the probability for 1 2 3 4 5 6 7 8 and 2 5 6 7 8 1 3 4 which should be the same. $\endgroup$ – DanielM May 31 '17 at 15:56
  • $\begingroup$ Actually, my answer is wrong but for a different reason. $\endgroup$ – Glen_b -Reinstate Monica May 31 '17 at 15:58
  • $\begingroup$ @DanielM I fixed it -- I did it as sampling topics with replacement when it is (obviously) without replacement. Sorry about that. That reduces the number of topics by 1 $\endgroup$ – Glen_b -Reinstate Monica Jun 1 '17 at 4:37

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.