Question 1: If X = N/2 (you look through half of the numbers before considering stopping), what are the odds you win the game?

Question 2: By setting X = N/2, are you getting the best odds?

If this doesn't makes sense, consider this example. If N is 10 and X is 0, you pull out the first piece and stop, because you haven't seen anything larger. Your chance of winning is 1/10, or 1/N. If you set X to 1, your chance of winning is slightly greater, because you will only stop if the number is larger than the first.

An interviewer has n people applying for a job. The interviewer sees them one at a time, and either hires them on the spot or rejects them, in which case they cannot ever be hired. The interviewer can tell exactly how suitable an applicant is for the job, and there are never ties. The interviewer decides on the following strategy: interview a fixed number x of applicants and then having seen and rejected those applicants, hire the next person to come along that beats all the first x applicants. If no one does, then the interviewer does not hire anyone.

Typical questions include: "what is the chance that the interviewer hires no one?" and "What is the optimal value of x for the interviewer to maximize the probability of hiring the best person?"

I've also come across this problem as a dating problem: when should you "settle down" and marry the person you are currently dating? Unfortunately I couldn't track down a reference for this problem, but here is one solution method.

First, let the random variable A have value i if you see exactly i people, select the ith person you see, and that turns out to be the best person. Then the probability that you select the best person will be P(A = x + 1) + P(A = x + 2) + ... + P(A = n).

Now, for A to equal i several things have to happen. 1) The best person has to be person i (occurs with probability 1 / n). 2) The second best person from person 1 up to i - 1 has to be one of the first x people interviewed. If the second best person has been any of people from x + 1 up to i - 1, then you would have hired them rather than hiring person i. Number 2) occurs with probability (conditioned on 1) occuring) x / (i - 1) since the second best person among people 1 through i - 1 is equally likely to be in any of the first i - 1 positions.

So altogether
P(i <= A <= n) = sum_{i=x+1}^n (1/n)(x / (i - 1))
or just
P(i <= A <= n) = (x/n) sum_{i=x}^{n-1} 1 / i.
Now the sum of 1 / i is a well studied object known as the harmonic series, and sum_{i=a}^b 1 / i is approximately ln b - ln a, where ln denotes the natural logarithm.

So P(i <= A <= n) is approximately (x/n). Note that when x = 1, this is ln (n - 1) / n, or ln (n - 1) times what the probability was when x = 0! This is an enormous improvement, but isn't the best. When x = n / 2, this indicates that the probability of hiring is about (1/2)(ln 2) or approximately 34.7%.

To find the best value of x, you can maximize this approximation for the probability. This gives a value of x = n / e, where e is approximately 2.7183. At this value the probability of hiring the best person is about 1 / e. This is the limiting answer: for actual values of n you can just sum the equation above to get the best answer and probabilities. Some results follow (p is probability of hiring the best person):

n = 5: x = 2, p = .4333
n = 6; x = 2, p = .4278
n = 7; x = 2, p = .4143
n = 8; x = 3, p = .4098
n = 9; x = 3, p = .4060
n = 10; x = 3, p = .3987
n = 100; x = 37, p = .3710
n = 1000; x = 368, p. = .3682

For the record, 1 / e = .3679 to 4 decimal places.

Mark