Question prompt:

Given n iid Uniform distributed r.v.s. xi ~ U(0,1). x1 is drawn first, then x2, then x3...

Let r1, r2, r3,..., rn be the order of x1, x2, x3, ..., xn after all n draws have been made.

You must guess ri when xi is drawn (so basically you need to guess ri when you have only seen r1 ~ ri and not ri+1 ~rn)

If you correctly guessed all rns correctly, you win the game. What is your best strategy and what's the probability of you winning with this strategy?

My attempt:

When n = 2,

if x1 < 0.5 : guess r1 = 1

else: guess r1 = 2

=> probability of winning = area shaded = 3/4

However, for n = 3, I'm kinda stuck. I've tried using the Expected number of draws that are less than the current xi to help make the guess. The way to calculate that is xi*(n-1) + number of xk < xi for k = 1 ~ i-1. If this expected number is 2, we can make our guess that ri = 2 + 1 = 3. But!!! this expected number is usually not an integer. I thought about rounding the expected number but couldn't really wrap my head around why we can use this method. Also, this is kinda hard to generalize to larger n. Any thoughts on how to approach this problem? My gut feeling tells me that there must be an easier way to deal with this, such as the geometric approach I used for n = 2.

Thanks in advance!