Let $X_1,\ldots,X_n\sim U[0,1]$ be independent uniform variables, and let $X_{(1)}, X_{(2)},\ldots,X_{(n)}$ be their order statistics (i.e., $X_{(i)}$ is the $i$'th smallest among $X_1,\ldots,X_n\sim U[0,1]$).
Given some parameter $k\in\{1,2,\ldots,n\}$, I want to generate values for $X_{(1)}, X_{(2)},\ldots,X_{(k)}$. A simple solution would be to generate all $n$ variables and find the smallest $k$; however, this would take $O(n)$ time which seems wasteful if $k\ll n$.
As an alternative, we can do the following:
- Generate $A_1\sim Beta(n,1)$ - a variable that has the same distribution as $X_{(1)}$.
- For $i=2,\ldots,k$, generate $B_i\sim Beta(n-i+1,1)$ and set $A_i = A_{i-1}+B_i (1-A_{i-1})$.
Intuitively, this should produce $A_1,\ldots,A_k$ from the same distribution as $X_{(1)},\ldots,X_{(k)}$, but require just $O(k)$ time.
I'm interested in formalizing this argument. It seems that $A_1$ has the same distribution as $X_{(1)}$ and that given $A_1,\ldots,A_i = X_{(1)},\ldots,X_{(i)}$, $A_{i+1}$ should be distributed similarly to $X_{(i+1)}$ as the remaining of the $X_i$'s are distributed i.i.d, uniformly, on $[X_{(i)},1]$.
How to formally prove that the $A_i$'s produced by this process have the same distribution as $X_{(1)},\ldots,X_{(k)}$?
An alternative algorithm was published by Lurie and Hartley.