(js, cit, HRT, Jump..)QR interview problem Guessing order of draws from iid U(0,1)

[wakuwaku]

This is for QR at two well know trading firms (think jane street, HRT, Citadel, Jump ...)(not BB bank).

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!

 

[redtruck]

Here's my solution:

So for some x1, probability of it being rank k out of n is [imath]P(k_1|x_1) = {n \choose k_1-1}(1-x_1)^{n-k_1}*x_1^{k_1-1}[/imath]. Essentially you are trying to figure out the probability of k-1 numbers being smaller than x1 and n-k numbers on the right. You calculate this for all possible k, and pick the one with the highest probability. Lets call this k1

Since we already made a guess for x1, we proceed with the assumption that it is the correct guess for x2. If x2<x1, we are trying to guess what rank j x2 will be out of the k-1 numbers that will be smaller than x1. If x2>x1, we are guessing rank k2 out of n-k numbers. It essentially becomes the same problem as the first part. If we assume x2<x1, [imath]P(k_2|x_2 < x_1) = {k_1-1 \choose k_2-1}(\frac{1-x_2}{x_1})^{k_1-1-k_2}*(\frac{x_2}{x_1})^{k_2-1}[/imath]. Similar thing if x2>x1. Rinse and repeat.

To calculate probability of winning for n = 2, we first find the transition point p1 where we would switch guess for k1. This segments the plane in to 2 pieces and we can integrate [imath]P(k_1|x_1)[/imath] at each segment and sum them to get the probability of winning [imath]P(W|2)[/imath]. For n = 3, we get 3 pieces. First piece's integrand will be [imath]P(k_1|x_1) * P(W|2)[/imath], second piece will be [imath]P(W|1)*P(k_1|x_1)*P(W|1)[/imath], third will be [imath]P(k_1|x_1) * P(W|2)[/imath]. Sum of these three integrals will be [imath]P(W|3)[/imath]. We can proceed from here iteratively for any n.

 

[binomial-torrent]

[redacted]

 

[TheCheshireCat]

Think of it as generating intervals on [0,1] every time an xi is drawn. So when x1 is drawn, it generates the intervals [0, x1] and [x1, 1]. You should then pick the widest interval. So before xi is drawn, you should find the widest interval, say for example [r_k, r_{k+1}] for some k < i (which is also wider than [0, r_1] and [r_{i-1}, 1]), and give your answer as k+1.