
	Advertisment

Selecting a Random Secretary

A few months ago I wrote a blog posting about the optimal strategy for maximizing your chances of selecting the best candidate from a group of people where you only got chance to interview each candidate once. It’s a fun puzzle.

If you’ve not read it, I encourage you to do so.

(It's OK, I'll wait for you, click the link above, then press 'back' to return here when you've absorbed it).

A random secretary

Here’s a related puzzle:

There are an unknown number of people lined up outside your office, all are waiting to come in and see you.

You have a single chair inside your office in which one, and only one, candidate can sit at a time.

One at a time, the each person comes into your office.

When someone walks into your office you have two choices: You can either dismiss them instantly, or you can get them to trade places with the person currently sitting in the chair (or sit if the chair is currently empty). The displaced person is then dismissed.

You have no idea how many people are in the queue outside, but when the last person comes into your office they declare “I am the last person”. No other person makes any comments.

As before, once a candidate is dismissed, they cannot be revisited.

Your goal is to select a totally random person* - how do you do it?

*Meaning, if there turned out to be n people in the queue, there is a 1 in n chance for any of the candidates that they will be selected.

To aid you in this exercise you are given a random number generator with infinite precession (It will generate a fractional random number from 0.0-1.0 to as high an accuracy as you could ever need).

What is your strategy?

Strategy

Well, it should be clear that simply selecting the first candidate that walks into the room is not going to work very well (if there is more than one candidate, then these later candidates could never be selected).

It should also be obvious that the seat should never be empty. The first candidate walking in the door should be asked to sit, and then decisions made whether to swap or not.

Walkthrough

It’s worth thinking about the solution for a small number of candidates before coming up with the general solution.

1 Candidate

This is trivial. The candidate walks in, let’s call him C₁ and announces that he is the “last person”. You invite him to sit in the chair, then say “congratulations, you get the job!”

2 Candidates

This is also pretty trivial. The first candidate walks in the door and you ask him/her to sit C₁. Then the next candidate comes along C₂, announcing they are the “last person”. Here it is a coin flip. You either keep the first candidate, or you switch. You should switch with 50% probability. You spin up your random number generator, and if it ends up less than 0.5 you switch candidates.

3 Candidates

Things now get a little more complex. You need to select the last candidate with probability ¹/₃, therefore the probability of selection (C₁ + C₂) should be ²/₃. This is just then the nested version of the previous problem. With a ¹/₃ chance you should switch to C₃, but otherwise leave whoever is currently sitting in the chair as they are. You should spin up your random number generator, and if less, than 0.33333 then invite C₃ to sit, otherwise politely dismiss him.

It's clear that C₃ is selected with probability ¹/₃. For C₁ and C₂, therefore the combined probability (OR) has to be ²/₃, since it is a coin flip which of these is currently in the chair, the probability for either of them is ²/₃ x ¹/₂ = ¹/₃ also.

n Candidates

I think you can see the pattern now. When candidate C_n walks in, you should switch them and invite them to sit with probability ¹/_n.

Solution

We invite the first person to sit down. We keep track of the number of people we have seen. When a new candidate appears we roll our random number generator and see if the results is less than ¹/_n (where n is the ordinal number of the candidate).

If it is less, we switch the person. If it is greater, the person currently in the chair stays.

You can find a complete list of all the articles here. Click here to receive email alerts on new articles.