Q: You have a queue of people outside your office door and you want to pick exactly one person at random. However you do not know the length of the queue. You are allowed to accept a person and then reject that person when you see another should you so choose. How do you do it?

Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)

A: At first look, this seems impossible to solve. How do you randomly pick when you don't know what the denominator is? It could be 5, 10 or 100s. Surprisingly, the following strategy works beautifully.

Keep a counter on the number of persons who come in, call this counter \(i\).For every person coming in, pick that user with probability \(\frac{1}{i}\)When the \(\{i + 1\}^{th}\) person comes in, with probability \(\frac{1}{i+1}\) replace the existing person.The above algorithm works by ensuring that the selected person is indeed picked up with probability \(\frac{1}{n}\) where \(n\) is the number of persons in the queue (wh…

Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)

A: At first look, this seems impossible to solve. How do you randomly pick when you don't know what the denominator is? It could be 5, 10 or 100s. Surprisingly, the following strategy works beautifully.

Keep a counter on the number of persons who come in, call this counter \(i\).For every person coming in, pick that user with probability \(\frac{1}{i}\)When the \(\{i + 1\}^{th}\) person comes in, with probability \(\frac{1}{i+1}\) replace the existing person.The above algorithm works by ensuring that the selected person is indeed picked up with probability \(\frac{1}{n}\) where \(n\) is the number of persons in the queue (wh…