Lehmer code: Difference between revisions

Revision as of 18:36, 1 June 2013

Revision as of 12:40, 15 October 2013

Line 60:

This is an optimal stop problem, a classic in decision theory, statistics and applied probabilities, where a random permutation is gradually revealed through the first elements of its Lehmer code, and where the goal is to stop exactly at the element k such as σ(k)=n, whereas the only available information (the k first values of the Lehmer code) is not sufficient to compute σ(k).

In less mathematical words : a series of n applicants are interviewed one after the other. The interviewer must hire the best applicant, but must make his decision (“Hire” or “Not hire”) on the spot, without interviewing the next applicant ( and ''a fortiori'' without interviewing all applicants).

The interviewer thus knows the rank of the k^th applicant, therefore, at the moment of making his k^th decision, the interviewer knows only the k first elements of the Lehmer code whereas he would need to know all of them to make a well informed decision.