Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /home/almer/domains/almer.tigelaar.net/public_html/index.php:4) in /home/almer/domains/almer.tigelaar.net/public_html/wp-content/plugins/si-contact-form/si-contact-form.php on line 1997

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /home/almer/domains/almer.tigelaar.net/public_html/index.php:4) in /home/almer/domains/almer.tigelaar.net/public_html/wp-content/plugins/si-contact-form/si-contact-form.php on line 1997
Almer S. Tigelaar | Puzzle #1: The Student Admission Problem

popular this month

recent comments

recent articles

Almer S. Tigelaar » Puzzles

Puzzle #1: The Student Admission Problem

Almer S. Tigelaar 01 / 07 / 2011, 09:00

Background: I will occasionally present a small (mathematical) puzzle here. These are a tribute to the column “Vuiks Verhandelingen”, written by Kees Vuik which regularly appeared in the Dutch PCM Magazine nearly a decade ago. Sometimes I may think of them myself, and sometimes they may come from elsewhere.

Let’s get started: 114 students applied for a specific study, only 100 were eventually admitted by lottery. Among the 114 students were 5 foreign students. However, none of these foreigners were among the 100 that were admitted. Intuitively this seems quite unlikely. But how unlikely is it really? Were the foreigners intentionally not admitted?

Your task: find the probability that the 5 foreign students were left out due to chance. This can be solved with basic knowledge of probability and set theory. First try it yourself, then click below to expand the solution and check your answer.

More »

Tip: if you are not too familiar with mathematical notation, don’t be intimidated by it: it’s just a way to formally write things down, and the notation here should be easy to follow. I’ve added some footnotes to help: hover over them with your mousepointer to see an explanation.

Definitions
We start with some generic definitions:

  • S is the set of all students that applied.
  • F is the subset of S which is foreign.
  • n is the number of students we may select from S (without replacement[1]).
  • The resulting selection we call set L (where L is a subset of S with cardinality[2] n )

Let’s fill out the variables above for this specific case:

  • There are 114 students in total: \#S=114
  • Of which 5 are foreigners: F\subset S\wedge\#F=5[3]
  • We may select 100 students: n=100

Problem:
What is the probability that we select no foreign student when we choose 100 students out of the 114 that applied? Formal: what is the probability that the intersection of F and L is empty?: P\left(F\cap L=\varnothing\right)

Solution:

  1. We know that there are \binom{\#S}{n} ways[4] in which we can select n students from the \#S (without replacement).
  2. There are \binom{\#F}{k} ways to select k students from the foreign subset.
  3. Given (2) there are \binom{\#S-\#F}{n-k} ways to select the remaining n - k students.
  4. Combining (1-3) we get:P\left(F\cap L=\varnothing\right)=\frac{\binom{\#F}{k}\cdot\binom{\#S-\#F}{n-k}}{\binom{\#S}{n}}

In this last step we effectively state that the probability is the number of ways in which we can select k and n - k students, relative to the total number of possible selections we can make. It is a generic solution for any set sizes, for this specific instance we take the problem specific values and simply substitute them:

P\left(F\cap L=\varnothing\right)=\frac{\binom{5}{0}\cdot\binom{114-5}{100-0}}{\binom{114}{100}}=\frac{\binom{5}{0}\cdot\binom{109}{100}}{\binom{114}{100}}=\frac{\binom{109}{100}}{\binom{114}{100}}\thickapprox1.36\cdot10^{-5}

All the values are as specified in the problem specific definition. The value of k is 0, since we are interested in the probability of selecting 0 students from the Foreign group. We see that the problem simplifies, since \binom{5}{0}=1.

We can conclude that the probability of selecting none of the 5 foreign students is quite low: 0.00136 %

The probability that the lottery was unfair can be deduced from this:
P\left(F\cap L\neq\varnothing\right)=1-P\left(F\cap L=\varnothing\right)=1-1.36\cdot10^{-5}=0.9999864

Which is 99.99864%. Indeed, it is very likely that at least one foreign student would have been selected. Hence we can state that it is likely that the lottery applied was unfair in this case and that the probability of a foreign student of being selected must have been much lower than that of a local student, or even zero.

tags: linkedin, math, probability, statistics,

More in Puzzles:

2 comments

add your comment
  • ^ reply

    I have to disagree with that last conclusion. The fact that, given a fair lottery, the probability of selecting only non-foreign students is 0.00136%, does not imply that the probability of the lottery being fair is 0.00136%.

    I think the best way to explain this is to put it the other way around: assume the lottery is unfair, in the specific sense that it will never select a foreign student. Given this unfair lottery, the probability of selecting only non-foreign students is 100%. By your argument, this would mean that if you see that the lottery selects only non-foreign students, you can conclude that the lottery is unfair with 100% probability. This clearly contradicts the previous result.

    I think the only way to make a probabilistic statement about the fairness is to include it as a variable in the probability space. Say, for example, that it is a boolean variable with two values: fair and unfair. Fair means that every subset of 100 students has an equal probability of being selected; unfair means that every subset with at least one foreign student in it have probability 0 (and the others have equal probability). Then the following statements follow:

    P(only non-foreign | fair) = 0.00136%

    P(only non-foreign | unfair) = 100%

    However, what you actually want to know is P(fair | only non-foreign).

    Now it turns out that your probability distribution is not fully defined yet; you need prior probabilities for P(fair) and P(unfair) (which should add up to 100%). Say both are 50%. Then,

    P(fair | only non-foreign) = P(only non-foreign | fair) P(fair) / P(only non-foreign) = 0.00136% / (100%+0.00136%)

    Sander E
    on 11 / 08 / 2011 wrote:
  • ^ reply

    @Sander E Thanks, it's a matter of semantics and perspective, but this is an interesting view on, and contribution to, the last part of the problem.

    almer.tigelaar
    on 23 / 08 / 2011 wrote: