Independent relative ranks of a uniform random permutation ($R_i\sim \mathrm{Unif}\{1,\dots ,i\}$)

For a uniform random permutation $a_1,\dots ,a_n$, define $R_i$ as the rank of $a_i$ among $a_1,\dots ,a_i$, with rank one assigned to the smallest value. Each sequence $r_i\in \{1,\dots ,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,\dots ,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.

The indicators $Y_i=1_{\{R_i=1\}}$ of successively smaller records are independent and have Bernoulli distributions of parameters $1/i$. Successively larger records use $R_i=i$ and have the same laws. For $K_n={\sum }_{i=1}^n{Y}_i$, expectation and variance additivity for independent random variables give $E{K}_n={\sum }_{i=1}^{n}1/i$ and $\mathrm{Var}{K}_n={\sum }_{i=1}^n(1/i-1/i^2)$.