The Hostel Lot Problem

I am about to join my Computer Science Master’s course in around 10 days. One of the introductory and how-to mails I received mentioned that hostel rooms are allotted by drawing lots. One of the hostels is a newly constructed block, which has slightly better rooms than the others. This situation posed an interesting problem to me: how to maximize my chances of ending up in the new hostel?

Or, phrasing in a more general way:

There are p lots, out of which q are winning lots (0 < q ≤ p). Contestants draw their lots one after the other. After drawing his lot, the contestant publicizes the lot that he has got, i.e. whether it is a winning lot or not. A lot once drawn is not returned to the box. What is the ideal time to draw your lot, so as to maximize the winning probability?

There is one aspect that makes this problem slightly different from usual probabilistic reasoning questions: new information is being presented after each draw. After each lot is drawn, we know whether it was a winning or losing lot; so the present values of total number of lots (say, $n$) and number of winning lots ($m$) change accordingly.

Here was my approach to solving the problem; which seems reasonable and arrives at a reasonable-sounding answer. The factor we consider is—brace yourselves—the probability that the probability of a win increases after the next draw – some sort of a meta-probability, if you may.

Consider an arbitrary situation where there are $n$ total lots and $m$ winning lots. The current probability of the a win, $P(win)=\frac{m}{n}$. If a lot is drawn from the box, one of the two following cases may result:

1. The lot drawn was a winning lot. There are now $m-1$ winning lots and $n-1$ total lots left in the box. The new probability of a win, $P(win_{new})=\frac{m-1}{n-1}$.
2. The lot drawn was a losing lot. There are now $m$ winning lots and $n-1$ total lots left. $P(win_{new})=\frac{m}{n-1}$

Obviously, the probability of winning decreases in case 1, and increases in case 2. The idea is to quantify the probability that $P(win_{new})>P(win)$; i.e. the probability of winning goes up after the next draw.

Since there are presently $m$ winning lots in the box, there are $m$ ways to reach case 1 and $(n-m)$ ways to reach case 2. Therefore;

Probability that $P(win)$ increases; $P(increase)=\frac{n-m}{n}$. $P(decrease)=1-P(increase)$. The best time to draw your lot, then, is the moment when $P(increase)$ becomes less than $P(decrease)$.

That is;

$P(increase) \leq 1-P(increase)$

$P(increase) \leq \frac{1}{2}$

$\frac{n-m}{n} \leq \frac{1}{2}$

$m \geq \frac{n}{2} \; \; \; \; \square$

So, statistically speaking, the ideal strategy to draw your chit is as follows:

• If $m \geq \frac{n}{2}$ to start with, draw your lot immediately; as your winning probability is likely to decrease if you wait.
• As long as $m \leq \frac{n}{2}$, wait. Statistically, the probability of your winning is likely to increase after the next draw.
• If, after any draw, $m$ becomes greater than or equal to $\frac{n}{2}$, take the next turn to draw your lot. Statistically, now is the peak probability that you win.

So that sums up a probabilistic examination of the lot-taking scene and outlines some strategies that maximizes your winning chance. Statistically, of course. If all the first $m$ draws end up as winning lots while you still wait for the optimal moment, you’re screwed.