= Independent relative ranks of a uniform random permutation
{title2=$R_i\sim\operatorname{Unif}\{1,\ldots,i\}$}
For a <uniform random permutation> $a_1,\ldots,a_n$, define $R_i$ as the rank of $a_i$ among $a_1,\ldots,a_i$, with rank one assigned to the smallest value. Each sequence $r_i\in\{1,\ldots,i\}$ corresponds to exactly one <permutation>: insert index $i$ in position $r_i$ of the current increasing-value list, then assign the final list the values $1,\ldots,n$. The $n!$ equally likely permutations therefore correspond to the $\prod_{i=1}^n i=n!$ equally likely rank sequences. Consequently the $R_i$ are <independent random variables>, each with the displayed <uniform distribution>.
Back to article page
