2
$\begingroup$

Suppose $X_1,X_2,...,X_m$ are iid uniform on ${0,1/n,2/n,...,1}.$ Let $S_l$ be the $l$ th highest among all $X_1,...,X_m$. I want to show that Pr(S_l > S_{l+1}) goes to $0$ at the rate $1/m.$ Please advise. Also I would like to know how can I generalize the result for a more general non-uniform distributions.

  • 0
    If $l$ is fixed, then $l/m$ is going to zero as $m$ grows, and eventually the top $l+1$ variables will all be equal to $1$ with probability very nearly $1$ (with error decaying exponentially). So this won't be right. On the other hand, the expected value of Pr(S_l > S_{l+1}) taken over all $l$ does go to zero as $1/m$.2012-07-20

1 Answers 1

1

The rate $1/m$ is unlikely. Consider for example that, for every $1\leqslant k\leqslant n$, $[S_1=k/n\gt S_2]$ is realized as follows: one chooses a rank $i$ amongst $m$, then one decides that $X_i=k/n$ and that $X_j\lt k/n$ for every $j\ne i$. Hence, $ \mathrm P\left(S_1=\frac{k}n\gt S_2\right)=m\cdot\frac1{n+1}\left(\frac{k}{n+1}\right)^{m-1}. $ Summing this yields $ \mathrm P(S_1\gt S_2)=\frac{m}{(n+1)^m}\sum_{k=1}^nk^{m-1}. $ Introduce $\varrho_n=\frac{n}{n+1}\lt1$. Then, for every fixed $n\geqslant1$, when $m\to\infty$, $ \mathrm P(S_1\gt S_2)\sim\frac{m\varrho_n^m}{n}, $ that is, $\mathrm P(S_1\gt S_2)\to0$ geometrically fast.