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:

  1. Generate $A_1\sim Beta(n,1)$ - a variable that has the same distribution as $X_{(1)}$.
  2. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.