The maharajah's problem

“The maharajah's problem” has been submitted by Alan Matthews to Marco Velli and myself one day during the early 90s (long before #MeeToo).   At that time, we were unaware of the fact that the problem had been treated before in the literature, so we rediscovered it. 

Rule: The maharajah has decided to get married. His court has been contacted by 100 ladies willing to get married to him. The 100 ladies are presented to the maharajah one after the other. The maharajah has two options: either he accepts the proposition of the nth lady, or he proceeds to the nth+1. The maharajah is a gentleman and imposes to himself the constraint not to change his mind after having rejected a candidate.   

Objective: The maharajah's objective is to become married to the most beautiful lady among the 100 candidates. We therefore assume that the 100 ladies can be sorted from 1 to 100 on a “scale of beauty”. 

Strategy and solution: The first thing the maharajah has to do is to define a strategy to maximize the probability to choose the most beautiful lady given the “no return” rule specified above. With no strategy (i.e. a random choice) the probability is obviously only 1%.  On the other hand, with the strategy given below, the probability can be increased to 37%. Is there a better strategy ? Not to our knowledge.    

Adopted strategy: A strategy, much better than random choice, goes as follows:

1. Let a fraction p of the total number of ladies pass (the observation group). 

2. Chose (among the remaining fraction 1-p of ladies) the first lady more beautiful than all the ladies in the observation sample. 

Success probability of the adopted strategy: In order to compute the probability of success, we have to add the probability of all possible winning combinations.  To simplify computation, we shall assume that the number N of ladies is much larger than unity, which is a fair assumption for N=100. 

The first combination is the one where the 2nd (most beautiful) lady is in the observation sample. Its probability is obviously the probability p of the 2nd lady to be in the observation group multiplied by the probability 1-p of the 1st lady to be in the second group, i.e. p(1-p). The second combination is the one where the 3rd lady is in the observation group (probability p) and the 1st and 2nd ladies in the second group (each with probability 1-p) with the 1st lady preceding the 2nd, corresponding to a probability (1/2)p(1-p)². The third combination is one where the 4th lady is in the observation group (probability p) and the 1st, 2nd and 3rd ladies in the second group with the constraint that the 1st precedes both the 2nd and the 3rd, corresponding to a probability (1/3)p(1-p)³ ... 

By induction, the summation of the probabilities of all combinations leading to success can be written as: 

p(1-p) +  1/2 p(1-p)² +  1/3 p(1-p)³ + … = p[(1-p) + 1/2 (1-p)² + 1/3 (1-p)³ + ….] = -p ln(p)