THE PROBLEM

You are given n cards, each with an distinct real number on them.  You
job is to have a method by which you can, with highest probability,
determine which card has the largest value.

You proceed as follows: first you flip over the top card and look at it.
Then you must decide, is this card that I am currently considering the
highest valued card in the deck. If you decide 'yes', then we stop right
here and check whether you're right or not. If you decide 'no', then you
place the current card in the discard pile and move on to the next card.
Note that you can't undo or peek ahead or anything like that.  Also, the
cards are ordered randomly.



THE SOLUTION
- Yisong Yue, with help from Justin Blanchard

One way of succeeding is to have the second largest number amongst the 
p*n cards I have checked and for the largest number not be among the p*n 
cards.  The probability of that is p * (1-p) (this is, of course, 
assuming n is arbitrarily large so sampling without replacement doesn't 
impact the probability of sampling with replacement all that much).

So, in this case, the probability of succeeding is p * (1-p).

What if both the largest and the second largest number are not among the
p*n cards I have checked?  The probability of that happening is (1-p)^2.

Suppose in this case the third largest number is among the p*n I checked.
The probability of this case is  p * (1-p)^2

So if I have the third largest card and I want the next card that larger
than it to the one I proclaim as the largest, I must check the largest
card before I check the second largest card.  The probability of that
happening is 1/2.  So in my second case, my probability of succeeding is

p * (1-p)^2 * 1/2.

Suppose the three largest numbers are not among the p*n cards I have
checked.  The probability of that happening is (1-p)^3.  Also suppose the
fourth largest number is among the p*n I have checked.  The total
probability for that case is p * (1-p)^3.  Of the three largest numbers, I
must check the largest number before I check the second or third largest
number.  Otherwise, I will proclaim the incorrect number as the largest
number.  The probability that I will check the largest number before the
second or third is 1/3.  The total probability of success for this case is
p * (1-p)^3 * 1/3.

This line of reasoning will eventually arrive at a sum of a lot of cases, 
namely SUM[ p * (1-p)^x * (1/x) ] where x goes from 1 to n.  As n grows 
without bound, this turns into an infinite series.

SUM[ x^k / k ] is the Taylor series for -ln(1-x)

The above summation then becomes p*-ln( 1-(1-p) ) = -p*ln(p) which has a 
max at 1/e with max value of 1/e

This means that you should always flip past n/e cards, which will give you
the max probability of 1/e of being correct.