Do the order statistics give a good approximation of uniform random variables?

Question

Let $\{X_i\}_{i \geq 1}$ be a sequence of iid uniform random variables on $[0, 1]$. Define, for each $n$, the order statistic $O_n$ of $X_n$ by

$$O_n := \frac{1}{n}\#\{1 \leq k \leq n \, \, | \, X_k \leq X_n\},$$

where $\#$ denotes the cardinality of a set.

Question: Is it true that $|X_n - O_n| = O(1/n)$ almost surely as $n \to \infty$?

That is, does there exist a deterministic constant $C > 0$ such that for almost every $\omega$, there exists $N(\omega)$ such that for all $n \geq N(\omega)$, we have

$$|X_n (\omega) - O_n (\omega)| \leq C/n?$$

Answer 1

No.

Conditioned on $X_n$, the random variable $n O_n - 1$ is a Binomial random variable with parameters $(n-1, X_n)$. In particular, $O_n$ has fluctuations of order $\sqrt{X_n (1 - X_n)/n}$, so $|X_n - O_n| \gtrsim n^{-1/2}$ with constant probability.