ChapterZero

Quick and easy route to concentration inequalities for order statistics

I’m reading Barvinok’s paper Approximating Orthogonal Matrices by Permutation Matrices. To achieve his goal, he uses some results about the concentration of order statistics. Given i.i.d. real random variables $\xi_i$ , define the -th order statistic $\omega_k$ to be the value of the -smallest $\xi_i$ . So $\omega_1$ is the smallest of the values, and $\omega_n$ is the largest.

He proves the following lemma:

Suppose that the cumulative distribution function of $\xi_i$ is continuous and strictly increasing. Let be an integer, $1 \leq k \leq n.$

Let $\alpha$ be a number such that $F(\alpha) < k/n < 2F(\alpha).$ Then

$\displaystyle \mathbb{P}(\omega_k < \alpha) \leq \exp\left(-\frac{n}{3F(\alpha)}\left(\frac{k}{n}-F(\alpha)\right)^2\right).$

Let $\alpha$ be a number such that $F(\alpha) > k/n.$ Then

$\displaystyle \mathbb{P}(\omega_k > \alpha) \leq \exp\left(-\frac{n}{2F(\alpha)}\left(\frac{k}{n}-F(\alpha)\right)^2\right).$

The result looks complicated, but the proof is quite simple. I’ll explain the first case; the second is analogous. Simply note that if we define $\chi_i = \boldsymbol{1}_{\xi_i < \alpha}$ and $\chi = \chi_1 + \cdots + \chi_n,$ then $\omega_k > \alpha$ iff $\chi > k$ . Then one applies a Chernoff bound: $\mathbb{P}(\chi \geq pn(1+\epsilon)) \leq \exp\left(-\frac{\epsilon^2pn}{3}\right)$ with $p = \mathbb{P}(\chi_i = 1) = F(\alpha)$ and $\epsilon = \frac{k}{F(\alpha)n}-1 \in (0,1)$ .

Possibly relevant posts:

Comparing products of gaussian moments with one gaussian moment (8/13/2010)
Notes from the underbelly (11/26/2007)
Sharpness of Moment bounds, exponential example (7/29/2010)

Tags: concentration, random

Quick and easy route to concentration inequalities for order statistics

Possibly relevant posts:

Leave a comment

Archives

intelligently designed

light and not filling

Tags