Optimal Sequential Rank Guessing

HardProbability

Reported in interviews at Citadel Two Sigma

Problem statement

You observe $n$ random variables $x_1, x_2, \ldots, x_n$, drawn i.i.d. from $\text{Uniform}(0, 1)$, one at a time. After seeing each $x_i$ (and all previously observed values), you must immediately guess the overall rank of $x_i$ among all $n$ values -- that is, its position if the entire sequence were sorted.

You win if and only if every single guess is correct.

  1. What is the optimal strategy for guessing ranks?
  1. What is the probability of winning under this strategy? Compute it explicitly for small $n$ (say $n = 2$ and $n = 3$) and describe the general formula.
Show hint

Once you commit to a rank for a revealed value, what does that commitment say about where the unseen values must fall, and does the actual interval matter or only how many values are in it?

Relevant roles: Data Scientist, Applied Scientist and Research Scientist.

Related free problems