# How to find the expectation of the maximum of independent exponential variables?

Suppose $$x_1, x_2, ......, x_n$$ are i.i.d. random variable of exponential distribution $$Exp(1)$$, i.e., $$f(x)=e^{-x}, x\gt0$$.

Given the order statistics $$x_{(1)} \le x_{(2)} \le......\le x_{(n)}$$, it is easy to find out that $$F_{x(1)}(x)= 1 - \Big[1-F_{x}(x)\Big]^n = 1- \Big[1-(1-e^{-x})\Big]^n=1-e^{-nx}$$ $$F_{x(n)}(x) = \Big[F_{x}(x)\Big]^n = (1-e^{-x})^n$$ Taking the derivative, $$f_{x(1)}(x) = ne^{-nx}$$ $$f_{x(n)}(x) = n(1-e^{-x})^{n-1}e^{-x}$$

Taking the integral, we have the expectation: $$E(x_{(1)}) = \int_0^\infty xne^{-nx}dx = \int_0^\infty xn d\Big(-\frac{e^{-nx}}{n}\Big) = \Big[-xe^{-nx}\Big]_0^\infty + \int_0^\infty e^{-nx}dx=\frac{1}{n}$$

But how could I obtain the $$E(x_{(n)})$$, the expectation of the largest order statistic?

• The full answer is on StackExchange, one Google click away... Commented Jan 21, 2018 at 16:41
• I was trying to perform this, but the integral is $\int_0^\infty x n (1-e^{-x})^{n-1}e^{-x}dx$, and by Taylor expansion, $1-e^{-x} = x - \frac{x^2}{2}+ \frac{x^3}{6} - \frac{x^4}{24} +......$, which is not obvious that its n-1th power is an explicit term. Commented Jan 21, 2018 at 16:49
• Following the answer on the link I gave above$$\mathbb{E}[X_{(n)}]=\sum_{i=1}^n \dfrac{1}{i}$$ Commented Jan 21, 2018 at 16:51
• Given that the expectation quoted by @Xi'an is correct, you're just going to have to live with it. It's senseless to ask for a different answer just because the right answer isn't expressed in a way you like! If you prefer, you may write it as $H(n)$, which has a closed analytic expression.
– whuber
Commented Jan 21, 2018 at 17:49
• Wolfram can calculate Integrate[x*n*(1 - Exp[-x])^(n - 1) Exp[-x], {x, 0, [Infinity]}, Assumptions -> {n > 1}]. The answer is HarmonicNumber[n] and this is the same as @Xi'an said Commented Jan 22, 2018 at 15:26

The answer referenced in the comments is great, because it is based on straightforward probabilistic thinking. But it is possible to obtain the answer through elementary means, beginning from definitions.

Because $$x_{(n)}$$ is the largest of $$n$$ independent variables, the event $$x_{(n)}\le x$$ is the event that all the $$x_i \le x.$$ Stipulating the $$x_i$$ have Exponential$$(1)$$ distributions says that for $$x\gt 0,$$ these have common probability $$1 - e^{-x}$$ (and otherwise have zero probability).

Since probabilities of independent events multiply,

$$\Pr(x_{(n)} \le x) = \left(1 - e^{-x}\right)^n.$$

One well-known formula for the expectation of a positive random variable with distribution function $$F$$ is the integral of $$1-F$$ from $$0$$ to $$\infty.$$ (Take the usual integral for the expectation and integrate by parts.) We are looking, then, to compute

$$E_n = E\left[x_{(n)}\right] = \int_0^\infty 1 - \left(1 - e^{-x}\right)^n\,\mathrm{d}x$$

for $$n=1, 2, 3, \ldots.$$

That initial "$$1$$" in the integrand is thorny, because its integral diverges, so we cannot separate it out. However, the differences between these quantities are considerably simpler to compute because the $$1$$'s cancel:

$$E_{n} - E_{n-1} = \int_0^\infty 1 - \left(1 - e^{-x}\right)^n - \left[1 - \left(1 - e^{-x}\right)^{n-1}\right]\,\mathrm{d}x = \int_0^\infty \left(1 - e^{-x}\right)^{n-1}e^{-x}\,\mathrm{d}x.$$

This is a textbook case for integration by substitution: the natural form to try is $$u = 1-e^{-x},$$ reducing the integral to

$$E_{n} - E_{n-1} = -\int_1^0 u^{n-1}\,\mathrm{d}u = \frac{1}{n}.$$

Beginning with $$E_0=\int (1-1)\mathrm{d}x = 0,$$ we obtain recursively

\begin{aligned}E_n &= E_0 + (E_1 - E_0) + (E_2 - E_1) + \cdots + (E_n - E_{n-1}) \\&= 0 + \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n} = H(n), \end{aligned}

the $$n^\text{th}$$ harmonic number.

Method of Moments approach

Given a set of $$n$$ exponentially distributed i.i.d variables $$X_i \sim EXP(1)$$ the expected value of an ordered statistic $$X_{i:n}$$ is found in a straighforward fashion with the method of moments which gives the expected value as,

\begin{equation*} \begin{aligned}[b] E[X] = \left[\frac{\partial}{\partial t}\int e^{xt}f(x) \right]_{t=0}= \int xf(x) \end{aligned} \end{equation*}

Now, for the sake of rigor and clarity, consider the full pdf of the ordered statistic for a general integer $$i ; 1;

\begin{equation*} \begin{aligned}[b] f(x_i) &= \frac{n!}{(i-1)!(n-i)!}[F(x_i)]^{i-1}[1-F(x_i)]^{n-i}f(x_i) \\ &=\frac{n!}{(i-1)!(n-i)!}[1-e^{-x_i}]^{i-1}[e^{-x_i}]^{(n-i+1)x_i} \end{aligned} \end{equation*}

Applying the method of moments gives,

\begin{equation*} \begin{aligned}[b] E[X] &= \frac{n!}{(i-1)!(n-i)!}\left[\frac{\partial}{\partial t}\int [1-e^{-x_i}]^{i-1}[e^{-x_i}]^{(n-i+1-t)x_i}\right]_{t=0}\\ & = \frac{n!}{(i-1)!(n-i)!}\left[ \frac{(i-1)!(n-i)!}{n!} \sum_{k=1}^i \frac{1}{n-k-t+1} \right]_{t=0}\\ & = \sum_{k=1}^i \frac{1}{n-t+1} \end{aligned} \end{equation*}

If I recall correctly in my messing around I found this method works well for the variance too, but I ran into difficulties in attempting to make it work for the covariance, e.g. $$\frac{\partial^2}{\partial t_1\partial t_2}e^{x_{i:n}t_1 + x_{j:n}t_2}f(x_{i:n},x_{j:n})$$, but to no avail. There might be some esoteric covariance formula for ordered statistics which makes it work though.

Substitution approach

Following a paper entitled ORDER STATISTICS OF UNIFORM, LOGISTIC AND EXPONENTIAL DISTRIBUTIONS by Okoyo Collins and Omondi (see page 100-102) an alternative is to make a clever substitution;

\begin{equation*} \begin{aligned}[b] Z_i = (n-i+1)(X_i - X_{i-1}) \qquad \longrightarrow \qquad X_i = \frac{Z_i}{n-i+1} + X_{i-1} \end{aligned} \end{equation*}

which can be used to show that,

\begin{equation*} \begin{aligned}[b] X_i \sim \frac{Z_1}{n} + \frac{Z_2}{n-1} +...+ \frac{Z_i}{n-i+1} \end{aligned} \end{equation*}

The Jacobian of the transformation turns out to be $$n!$$ (see pg 101 of referenced paper). Also, we conveniently have,

\begin{equation*} \begin{aligned}[b] \sum_{i=1}^n x_i = \sum_{i=1}^n z_i \end{aligned} \end{equation*}

(Convince yourself of this). The joint pdf then transforms as,

\begin{equation*} \begin{aligned}[b] f_{X_1,X_2,...,X_n} = n!e^{-\sum_{i=1}^n x_i } \quad \longrightarrow \quad e^{-\sum_{i=1}^n z_i } \end{aligned} \end{equation*}

Writing the subscripts out in full ordered notation, we now have,

\begin{equation*} \begin{aligned}[b] E[X_{i:n}] &= E\left[\frac{Z_{1:n}}{n} + \frac{Z_{2:n}}{n-1} +...+ \frac{Z_{i:n}}{n-i+1}\right] &= \sum_{k=1}^i \frac{1}{n-t+1} \end{aligned} \end{equation*}

Because $$Z_{i:n} \sim EXP(1)$$ as well (?). This warrants additional justification, but I've taken it as far as needed for my purposes which was applied to a different problem.

• +1 Thank you for sharing these answers. The "method of moments" usually refers to a procedure for estimating distributions based on sample moments. The first method you give is usually known as the "moment generating function" approach.
– whuber
Commented Dec 28, 2021 at 20:30

A different approach is that we can view the order statistic as a sum statistic. An explanation is given here: https://math.stackexchange.com/a/4283180

If $$X_k \sim Exp(1)$$ then

$$max(X_1, X_2, \dots , X_n) \qquad \sim \qquad \sum_{k=1}^n Y_k$$

with $$Y_k \sim Exp(n+1-k)$$.

And then you can compute the expectation value as

$$E\left[max(X_1, X_2, \dots , X_n)\right] = E\left[\sum_{k=1}^n Y_k\right] = \sum_{k=1}^n E\left[Y_k\right] = \sum_{k=1}^n \frac{1}{n+1-k} = \sum_{k=1}^n \frac{1}{k}$$

In general you get for the $$m$$-th order statistic (of $$n$$ exponential distributed variables) the expectation:

$$E[X_{(k)}] = \sum_{k=1}^m \frac{1}{n+1-k}$$