Expectation of the Maximum Order Statistic of a Power Law Distribution

Didn’t know calculating expectation would take this long…

Consider $n$ i.i.d. random variables $X_i$ drawn from Power Law distribution with support lowerbound $x_\text{min} = 1$ and the shape parameter $\alpha > 2$—in other words, the pdf of $X_i$ being

$$ f_{X_i}(x) = (\alpha - 1) x^{-\alpha }, $$

and

$$ F_{X_i}(x) =1 - x^{-(\alpha - 1)} \quad \text{ for }x \ge 1. $$

Btw, for the heavy-tailed distribution family, it can be more comfortable (and general) to understand random variable $X$ as

$$ > \Pr[X > x] \sim x^{-\alpha}. > $$

see Ibragimov and Walden (MS'10)’s Section 3 “Heavy-Tailed Distributions” for a cooler, less intuitive way of seeing it.

Assume there are $n$ iid $X_i$ for $i = 1, \ldots, n$. Take $X_\text{(n)}:= \max_{i \in [n]}X_i$—the maximum order statistics of $[X_i]$ for $i\in [n]$ . $n$ is expected to go large. The expectation of $X_{(n)}$ can be calculated as

$$ \begin{align*} \mathbb E[X_{(n)}] & = \int_0^\infty \Pr[X_{(n)} > t]\, \text{d}t\cr (X_i \ge 1) \quad & = 1+ \int_1^\infty \Pr[X_{(n)} > t]\, \text{d}t\cr & = 1 + \int_1^\infty \left[1 - \Pr[X_{(n)} \le t]\right]\, \text{d}t\cr & = 1 + \int_1^\infty \left[1 - F^n_{X_i}(t)\right]\, \text{d}t\cr & = 1 + \int_1^\infty \left[1 - (1 - t^{-(\alpha - 1)})^n\right]\, \text{d}t \end{align*} $$

Notice that

$$ (1 - t^{-(\alpha - 1)})^n = 1 + \sum_{k = 1}^n {n\choose k} (-1)^k t^{-(\alpha - 1)k} $$

So the integral part above becomes

$$ \begin{align*} & \quad \quad \int_1^\infty \left[1 - (1 - t^{-(\alpha - 1)})^n\right]\, \text{d}t \cr & = -\int_1^\infty \left( \sum_{k = 1}^n {n\choose k} (-1)^k t^{-(\alpha - 1)k} \right)\, \text{d}t\cr \end{align*} $$

It’s legal to swap $\int$ and $\sum$ here cause absolute cause there’s absolute convergence—continuing:

$$ \begin{align*} & \quad \quad \int_1^\infty \left[1 - (1 - t^{-(\alpha - 1)})^n\right]\, \text{d}t \cr & = -\sum_{k= 1}^n \left(\int_1^\infty{n\choose k} (-1)^k t^{-(\alpha - 1)k}\, \text{d}t \right)\cr & = -\sum_{k= 1}^n {n\choose k} (-1)^k \left(\int_1^\infty t^{-(\alpha - 1)k}\, \text{d}t \right)\cr & = -\sum_{k= 1}^n {n\choose k} (-1)^k \frac1{(\alpha - 1)k - 1}. \quad \quad \text{(\*)}\cr \end{align*} $$

$\text{(\*)}$ becomes a bit nasty. Nevertheless, from binomial identity digged up in a really fancy math textbook:

$$ \sum_{k = 0}^n {n\choose k} (-1)^k\frac{1}{k+x} = \frac{n!}{x(x + 1)\cdots (x + n)}. $$

So as $n\to \infty$,

$$ \begin{align} \mathbb E[X_{(n)}] & = 1 -\sum_{k= 1}^n {n\choose k} (-1)^k \frac1{(\alpha - 1)k - 1}\cr & = 1 -\frac1{\alpha - 1}\sum_{k= 1}^n {n\choose k} (-1)^k \frac1{k - \frac1{\alpha - 1}}\cr & = -\frac1{\alpha - 1} \sum_{k = 0}^n {n\choose k} (-1)^k\frac{1}{k - \frac1{\alpha - 1}} + \underbrace{1 - \frac1{\alpha - 1}}_\text{just constants}\cr \end{align} $$

Let $x = -1/(\alpha - 1)$ just for notation convenience.

$$ \begin{align} & = - \frac1{\alpha - 1}\frac{n!}{x(x + 1)\cdots (x + n)} + 1 - \frac1{\alpha - 1}\cr & = - \frac1{\alpha - 1}\frac{n!\Gamma (x)}{\Gamma(n + x + 1)} + 1- \frac1{\alpha - 1}\cr & = \mathcal O(n^\frac{1}{\alpha - 1}) \end{align} $$

And we’re done.