10
$\begingroup$

Suppose there are $n$ potential grad students and $n$ Universities. Each University has one scholarship to do a PhD. Each student has a strict ranking of Universities so that each University is comparable and she is not indifferent between any two Universities. The preferences of each student are independent and generated uniformly at random.

Students are ordered according to their height (or some other irrelevant attribute) and can choose their favourite University to study in based on this order. Universities accept the first student who applies to them and their decision is final and irrevocable.

My question is: for the $k$ tallest applicant, what is the probability that they end up in their $j$-th best University?

For example, for the tallest guy, the probability that she gets in her first-choice is 1, and 0 for any other University.

For the second tallest guy, the probability that she gets in her first choice is $\frac{n-1}{n}$, into her second choice is $1/n$ (i.e. that the tallest guy chose her favourite school), 0 for any other Unversity.

For the third tallest guy, the probability that she gets her top choice is $\frac{n-1}{n} \times \frac{n-2}{n-1}$ and the second-best choice equals $\frac{2}{n}$, and so on.

Many thanks in advance.

Edit: I'm thinking for the k-th tallest applicant, the chance of getting into her top choice is $\frac{n+1-k}{n}$.

Second edit: Suppose now that, if a student gets her first choice, she completes her PhD with probability 1, if she gets her second choice, she does with probability 1/2 and so on, so in general, if a student gets her k choice, she finishes her PhD with probability $\frac{1}{2^{k-1}}$. What is the expected number of students that fail to complete their PhD? Simulations tell me it is $0.38 n$, but I would like to understand why.

$\endgroup$
5
  • 21
    $\begingroup$ Sympathizing with whoever wrote this problem $\endgroup$
    – Elliot G
    Sep 27 at 9:49
  • $\begingroup$ What have you done so far? Have you computed those probabilities any further than first two? Please show your work. $\endgroup$
    – Radost
    Sep 27 at 9:54
  • $\begingroup$ @Radost edits made $\endgroup$
    – fox
    Sep 27 at 13:07
  • $\begingroup$ Do you mean the expected number of students who complete their PhD? $\endgroup$ Sep 28 at 9:11
  • $\begingroup$ Yes, thanks @BearCakes100 $\endgroup$
    – fox
    Sep 28 at 9:13
3
+50
$\begingroup$

Using the same notation as OskarSzarowicz's answer, let $p_{k,j}$ denote the probability that $k$-th tallest student gets to their $j$-th most preferred university (both $k$ and $j$ start at $1$). This probability can be expressed in a closed form by realizing that:

  • The previous $(k-1)$ students have "used up" $(k-1)$ universities in total and thus in order for the current student to be only accepted by their $j$-th choice, each of the first $(j-1)$ universities had to come this pool of $(k-1)$ universities. That can happen in $\binom{k-1}{j-1}(j-1)!$ ways.
  • The next university in the list must be a non-eliminated one, which means $(n+1-k)$ choices.
  • The remaining $(n-j)$ on their list can be chosen arbitrarily; giving us $(n-j)!$ possibilities.

Putting it all together and dividing by the total number of possible preference lists ($n!$) yields:

$$p_{k,j}=\frac{1}{n!}\binom{k-1}{j-1}(j-1)!(n+1-k)(n-j)!$$

This rather unwieldy expression can be rearranged a bit by combining the factorials into another binomial coefficient and moving the extra $j$ into the other one which pulls out one extra $k$:

$$p_{k,j}=\frac{(n+1-k)}{k}\binom{k}{j}/\binom{n}{j}$$

While this expression might not look really simpler than the previous one, it will come handy when it comes to calculating the expected number of students who are going to fail. It will actually be easier to consider a slightly more general problem, where student's probability of succeeding at their $j$-th choice is equal to $x^{j-1}$ (so the original problem corresponds to $x=\frac{1}{2}$). The expected number of students succeeding is equal to the double sum $$S = \sum_{k=1}^n \sum_{j=1}^k p_{k,j}x^{j-1}$$

Exchanging the other of summation allows us to pull out some terms in front of the inner sum and keep only one binomial coefficient in it (one whose bottom part is independent of the summation variable): $$S=\sum_{j=1}^n \left(x^{j-1}/\binom{n}{j}\sum_{k=j}^n \frac{(n+1-k)}{k}\binom{k}{j}\right)$$

For the inner sum, we have $$I(n,j)=\sum_{k=j}^n \frac{(n+1-k)}{k}\binom{k}{j}= (n+1)\sum_{k=j}^n \frac{1}{k}\binom{k}{j} - \sum_{k=j}^n \binom{k}{j}$$

The first sum can be also written as $$\sum_{k=j}^n \frac{1}{k}\binom{k}{j} = \frac{1}{j}\sum_{k=j}^n \binom{k-1}{j-1}=\frac{1}{j}\sum_{k=j-1}^{n-1} \binom{k}{j-1}$$

Now we can use the combinatorial identity $\sum_{k=j}^n \binom{k}{j} = \binom{n+1}{j+1}$ to obtain $$I(n,j)=\frac{n+1}{j}\binom{n}{j} - \binom{n+1}{j+1} = (n+1)\left(\frac{1}{j} - \frac{1}{j+1}\right)\binom{n}{j}$$

Returning back to our expression for $S$ and cancelling out the binomial coefficients, we get

$$S=(n+1)\sum_{j=1}^n \left(\frac{1}{j} - \frac{1}{j+1}\right)x^{j-1}$$

or, moving the $(n+1)$ factor to the other side and rearranging the terms a bit:

$$\frac{S}{n+1}=\frac{1}{x} - \frac{x^{n-1}}{n+1} + \frac{x-1}{x^2}\sum_{j=1}^n \frac{x^{j}}{j}$$

Unfortunately, this is the point where we might have ran out of luck when it comes to exact calculations for fixed $n$; the latest sum does not have a closed-form expression (at least as far as I know). It is a truncated form of the Taylor expansion of $-\log(1-x)$, though, so if we are only interested in the asymptotic behaviour, we can get the following result:

$$S^* = \lim_{n\to\infty}\frac{S}{n+1} = \frac{1}{x} + \frac{1-x}{x^2}\ln(1-x)$$

Note that this limit would be the same if we divided by $n$ rather than $(n+1)$ since we are going to infinity. Thus, the fraction of students who fail their tests tends to $(1-S^*)$. For the specific choice of $x=\frac{1}{2}$, we get $1-S^*=\ln{4}-1\approx 0.386294$.

$\endgroup$
1
  • $\begingroup$ Thanks for this! Would you mind explaining the first three bullet points in more detail? $\endgroup$
    – fox
    Oct 3 at 11:04
1
$\begingroup$

This is a very sketch proof I will edit in the morning to make cleaner, ultimately we use and abuse the complete uniform indifference, that is at any point if we know there are $m$ colleges remaining we know that any college is equally likely to be taken or not.

Let $p_{k,j}$ denote the probability that the $k^{th}$ tallest gets into preference $j$. Notice that $p_{k,j} = 0 $ for all $j > k$

You correctly noted that $p_{k,1} = \frac{n+1-k}{n} = 1 -\frac{k-1}{n}$

We can then progress to $p_{k,2}$:

We need to have failed getting into our first choice and then have our second college amonst the $n - (k-1)$ colleges that have not been selected. However we must condition on the fact that we failed to get into our first college. We have only $n-1$ colleges to care about because we know our top choice is removed. We know that $k-1$ colleges have already been taken of which $1$ of them is our top choice so only $ k-2 $ other colleges that we care about have already been selected. Hence the probability our second choice has also been selected given our first one is gone is $\frac{k-2}{n-1}$

Hence $p_{k,2} = (1-p_{k_1})\cdot (1-\frac{k-2}{n-1})$

Going forward to $p_{k,3}$:

As before, we need to have failed getting into our first, failed getting into our second and then have our third preference not already selected.

Failling to get into our first and second is simply $(1-p_{k,1}) (1-p_{k,2})$

Given that we have failed to get into these colleges we know there are $n-2$ possible colleges remaining. We know the already selected colleges contain our top preference and our second top and then $k-1-2$ others. So the probability that our third college is amongst these is simply $\frac{k-3}{n-2}$.

Hence $p_{k,3} = (1-p_{k,1}) (1-p_{k,2}) (1-\frac{k-3}{n-2})$

And in general it is easy to see $p_{k,j} = (1-\frac{k-j}{n+1-j})\prod_{i=1}^{k-1} (1-p_{k,i})$

Someone with better real analysis might be able to express this product in a clean closed-form hopefully! I think the recurrence can be put into a nice sum. For now if you want to calculate $p_{k,j}$ you will have to start with your formula for $p_{k,1}$ and work upwards.

$\endgroup$
5
  • 1
    $\begingroup$ Thanks @BearCakes100 for this, I hope somebody can suggest a more succinct formula! Very helpful, thanks. $\endgroup$
    – fox
    Sep 28 at 9:07
  • 1
    $\begingroup$ I added a new comment with a cooler question, If you have any insights I would be very grateful. $\endgroup$
    – fox
    Sep 28 at 9:07
  • $\begingroup$ Do you mean the expected number of students who complete it? @fox $\endgroup$ Sep 28 at 9:11
  • $\begingroup$ Unfortunately, I have noticed via simulations that the results do not carry over for $j>2$. $\endgroup$
    – fox
    Sep 28 at 12:09
  • $\begingroup$ Thanks for the answer! Can you explain the first three bullet points in more detail please @Peter Košinár? $\endgroup$
    – fox
    Oct 3 at 10:58

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.