A man have been given a random number from 1-100 and then sent to a room having 100 boxes containing a random number. He can check maximum of 50 boxes to find his number. What is the probability that he will find his number?

Intuitively, the answer to this question is \frac{1}{2}, this article tries to mathematically arrive to the answer by using Conditional Probabilities and the Total Probability Theorem. [Disclaimer: This is a very overcomplicated way to arrive to the result.]

Solution

Here, there exist two random elements - selection of number, and arrangement of boxes in the room - making it difficult to perform a probability calculation. Let us fix one of them for now. Say, his randomly chosen number is N = 10.

Now, let us assume that the boxes are arranged randomly, and he checks them in order of their positioning. So he checks the first box, then the second, then the third, and so on.

Let A_{n} denote the event that he finds his number (10) in the n^{\text{th}} box.

Before he opens any box, he has no knowledge of any number, so the probabilities are:

P\left( A_{1} \right) = \frac{1}{100},P\left( A_{2} \right) = \frac{1}{100},P\left( A_{3} \right) = \frac{1}{100},\ldots,P\left( A_{100} \right) = \frac{1}{100} Once he has opened box 1, he suddenly has gained new information, which is the number in box 1. There are two cases:

Case 1: He has found his number (Success), A_{1}: Now the probabilities will become:

P\left( \frac{A_{1}}{A_{1}} \right) = \frac{100}{100},P\left( \frac{A_{2}}{A_{1}} \right) = 0,P\left( \frac{A_{3}}{A_{1}} \right) = 0,\ldots,P\left( \frac{A_{100}}{A_{1}} \right) = 0

Case 2: He has not found his number, A'_{1}: Now the probabilities will become:

P\left( \frac{A_{1}}{{A}'_{1}} \right) = 0,P\left( \frac{A_{2}}{{A}'_{1}} \right) = \frac{1}{99},P\left( \frac{A_{3}}{{A}'_{1}} \right) = \frac{1}{99},\ldots,P\left( \frac{A_{100}}{{A}'_{1}} \right) = \frac{1}{99}

(He will equally distribute the probabilty in all the remaining boxes)

So clearly, the probability values A_{n} are not static but instead dynamic, i.e. they change as per information gained by the player. These are denoted as conditional probabilities. (Incidentally, this concept is key to understanding many famous probability “paradoxes”, like the Monty Hall Problem for example.)

So, to find the overall probability A_{2}, we can use the Total Probability theoremn:

\begin{aligned} P\left( A_{2} \right) & = P\left( A_{1} \cap A_{2} \right) + P\left( A'_{1} \cap A_{2} \right) \\ & = P\left( A_{1} \right)P\left( \frac{A_{2}}{A_{1}} \right) + P\left( A'_{1} \right)P\left( \frac{A_{2}}{{A}'_{1}} \right) \\ & = \frac{1}{100} \cdot 0 + \frac{99}{100} \cdot \frac{1}{99} \\ & = \frac{1}{100} \end{aligned}

Similarly, for A_{3} we can write

\begin{aligned} P\left( A_{3} \right) & = & & P\left( A_{2} \cap A_{3} \right) + P\left( A'_{2} \cap A_{3} \right) \\ & = & & P\left( A_{1} \cap A_{2} \cap A_{3} \right) + P\left( A'_{1} \cap A_{2} \cap A_{3} \right) + P\left( A_{1} \cap A'_{2} \cap A_{3} \right) + \\ & & & P\left( A'_{1} \cap A'_{2} \cap A_{3} \right) \end{aligned}

These are all the possibilities of A_{1} and A_{2}, which might have occured before opening the third box. But, we can clearly see, just like the above case, here the first three terms will become 0. This is because all A_{n} are disjoint events, and hence they cannot occur simultaneously. So any event of the type A_{i} \cap A_{j} will obviously become an impossible event.

So, we can simplify to:

\begin{aligned} P\left( A_{1} \right) & = P\left( A_{1} \right) & & = P\left( A_{1} \right) & & = \frac{1}{100} \\ P\left( A_{2} \right) & = P\left( A'_{1} \cap A_{2} \right) & & = P\left( A'_{1} \right)P\left( \frac{A_{2}}{{A}'_{1}} \right) & & = \frac{99}{100} \cdot \frac{1}{99} \\ P\left( A_{3} \right) & = P\left( A'_{1} \cap A'_{2} \cap A_{3} \right) & & = P\left( A'_{1} \right)P\left(\frac{A'_{2}}{{A}'_{1}} \right)P\left( \frac{A_{3}}{A'_{1} \cap A'_{2}} \right) & & = \frac{99}{100} \cdot \frac{98}{99} \cdot \frac{1}{98} \\ P\left( A_{4} \right) & = P\left( A'_{1} \cap A'_{2} \cap A'_{3} \cap A_{4} \right) & & = P\left( A'_{1} \right)P\left(\frac{A'_{2}}{{A}'_{1}} \right)\ldots P\left( \frac{A_{4}}{A'_{1} \cap A'_{2} \cap A'_{3}} \right) & & = \frac{99}{100} \cdot \frac{98}{99} \cdot \frac{97}{98} \cdot \frac{1}{97} \end{aligned}

Following the pattern, we can say that A_{n} = \frac{1}{100}, for every n. (We could’ve directly stated this without doing any calculations, that it is equally likely that he finds his number in any of the boxes, because the order of arrangement is random.)

Now, this result is obviously not specific for N = 10, it is true for any N, and all N are equally likely to be picked. So, the final result we will get, is that A_{n} = \frac{1}{100}, meaning each A_{n} is equally likely.

Finally, to find probability of success,

\begin{aligned} P\left( \text{Success} \right) = \frac{\text{Favourable}}{\text{ Total}} & = \frac{P\left( A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup \ldots \cup A_{50} \right)}{1} \\ & = 50 \times \frac{1}{100} = \frac{1}{2} \end{aligned}