Problem of the Day #43: Optimal Thesis TimingMay 1, 2011

Posted by Billy in : potd , trackback

Albert needs to write an analytical paper for his English teacher, Mr. Miller. Mr. Miller has allotted precisely $1$ year to find a suitable thesis. Instead of letting Albert think of a thesis himself, Mr. Miller gives Albert a machine that randomly generates a unique thesis every millisecond.

Albert is instructed to monitor the machine continuously for the entire span of the year. Every time the machine creates a thesis, Albert can decide if he wants to send it to Mr. Miller or not. Only the most recently-created thesis can be sent to Mr. Miller, at which point Albert cannot send any more theses, but all previous theses created by the machine are kept and accessible. Albert knows that Mr. Miller will only consider accepting the highest-quality thesis from the machine (Mr. Miller knows the highest possible thesis quality because he created the machine, but Albert can only judge the relative quality between theses).

Albert devises the following strategy: wait $k$ milliseconds, and then choose the next thesis better than all the previous ones produced, hoping that it is the absolute best. Mr. Miller knows Albert’s strategy, and the probability that Mr. Miller will accept the thesis (if it’s the absolute best) is $\frac{k}{N}$, where $N$ is the total number of milliseconds. If Albert chooses $k$ to optimize his chance of getting his thesis accepted, what is the probability that Albert will get his thesis accepted?