The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

Question

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with each order being equally likely. Given the fact that the lengths of sticks are not known to Py in advance. On each step, Py takes a single stick from Px. After that, he/she either picks the stick and finishes the game or discards the stick and moves on to the next stick. Note that Py can compare relative lengths of all already seen sticks.

• Note that: The answer is considered correct if the absolute or relative error does not exceed 10e-7

• Constraints: 1 <= N <= 10e5

---

Sample Inputs and Outputs:(n -> probability)

• 1 -> 1
• 2 -> 0.5
• 3 -> 0.5
• 10 -> 0.398690476190

---

Notes: In the first test, Py chooses the first stick because it is the only one stick. In the second test, it does not matter if he/she chooses the first or the second stick. The probability of choosing the longest one is 0.5. In the third example, he bypasses the first stick, because if Py chooses it the probability would be 1/3. Then if the second stick is longer than the first one he/she chooses it and if it is smaller than the first one Py moves on to the third one.

---

My Attempt: I noticed that this is a binomial distribution problem since there are n attempts and each attempt is independent. Using the formula for the binomial distribution, I can not find the answer for n = 10, x =1, p = 1 /10, I got 0.387420489. I am struggling to find a solution is there any misconception I did? How to approach to a solution?

Answer 1

If you tried to get the longest stick out of 10, and they were shown to you in random order, how would you proceed?

Here’s a simple strategy, based on the simple idea that it’s daft to pick a stick that isn’t the longest so far: Don’t take any of the first four sticks, then pick the first stick that is longer than the longest so far. How will this work out?

If the first four contain the longest stick, you lose. If the first four contain the second longest stick, you win because you will pick the longest. If the first four contain the third longest stick, then you will pick the longest or second longest, 50% chance to win, and so on.

Chances are 65.61% that the first four don’t contain the longest, and 40.96% that they contain neither of the two longest; that alone gives you a 24.65% chance to win because you must pick the longest stick. You can calculate your chances to win quite easily: let p(k) be probability (“None of the p largest”) - probability (“None of the p+1 largest”), then your chance to win is p(1) + p(2)/2 + p(3)/3 ...

You would also check if skipping the first three or five or any other number might be better.

If you ignore about the first n/e sticks, this will give you a winning chance around 1/e even when n is very large.