Optimal Control and Filtering

Sameer Kamal School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Saturday, 31 Oct 2009 (all day)
A-212 (STCS Seminar Room)
Consider the problem: A committee interviews a stream of N candidates for selecting one. It has to accept or reject each candidate immediately after his/her interview. By rejecting the first half and accepting the first candidate thereafter who is the best so far, the committee can select the best person with a probability 1/4. Playing around with different cut-off times, one can increase this probability to 1/e. We'll use Optimal Stopping to show that 1/e is the best one can do (the material is borrowed from S.R.S. Varadhan's notes for a first Probability course).