Secratry Puzzle ( A Kind of Hat having Balls)

A hat contains n balls, each with a number on it. On each turn, a ball is drawn uniformly at random and without replacement, and shown to you. If you are able to identify the ball with the largest number when it is drawn, you win the game. Give an algo/technique that wins with probability at least 1/4.


The secretary problem is an optimal stopping problem that has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem. The solution is sometimes called the 37% rule. The problem can be stated as follows:

1. There is a single secretarial position to fill.
2. There are n applicants for the position, and the value of n is known.
3. The applicants can be ranked from best to worst with no ties.
4. The applicants are interviewed sequentially in a random order, with each order being equally likely.
5. After each interview, the applicant is accepted or rejected.
6. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
7. Rejected applicants cannot be recalled.
8. The objective is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.

Terminology: A candidate is an applicant who, when interviewed, is better than all the applicants interviewed previously. Skip is used to mean "interview and reject".

Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) has a surprising feature. Specifically, for large n the optimal policy is to interview and reject the first n/e applicants (where e is the base of the natural logarithm) and then to accept the next who is better than these interviewed candidates. As n gets larger, the probability of selecting the best applicant from the pool goes to 1/e, which is around 37%. Whether one is searching through 100 or 100,000,000 applicants, the optimal policy will select the single best one about 37% of the time.

Solution http://en.wikipedia.org/wiki/Secretary_problem