Order Statistics of Exponentials and Spacing Structure
Let $X_1, \ldots, X_n$ be i.i.d. $\text{Exp}(\lambda)$ random variables. Denote the order statistics $X_{(1)} \leq X_{(2)} \leq \cdots \leq X_{(n)}$, so $X_{(n)} = M_n = \max_i X_i$.
- Derive the CDF and PDF of $M_n$. Then compute $E[M_n]$.
- Compute the expected gap $E[M_n - M_{n-1}]$ between the top two order statistics.
- Define the spacings $D_k = X_{(k)} - X_{(k-1)}$ for $k = 1, \ldots, n$ (with $X_{(0)} = 0$). Show that $D_1, D_2, \ldots, D_n$ are independent, and identify the distribution of each $D_k$.
Hints
- The CDF of the maximum of independent random variables factors: write $P(M_n \leq t)$ as a product and substitute the exponential CDF.
- For the spacings, use the memoryless property: after the $k$-th smallest is observed, the remaining $n - k$ survivors each restart fresh, so the next gap is the minimum of $n - k$ independent exponentials. The top gap is the minimum of just one survivor, i.e. $\text{Exp}(\lambda)$.
- To get $E[M_n]$, use the spacing decomposition $M_n = \sum_{k=1}^n D_k$ with $E[D_k] = 1/((n-k+1)\lambda)$, which telescopes to the harmonic sum $H_n / \lambda$.
Worked Solution
How to Think About It: The maximum of $n$ exponentials is not itself exponential -- it has a more spread-out distribution with a heavier right tail. But the first thing to do is write down the CDF of the max: $P(M_n \leq t) = P(\text{all } X_i \leq t) = (1 - e^{-\lambda t})^n$ by independence. That is the whole CDF right there. Everything else -- the PDF, the expectation, the spacings -- flows from that one line.
The spacing result is the real gem. The intuition: when you have $k$ survivors all above some threshold, you are running a race to the next event with $k$ independent Exp($\lambda$) clocks. The minimum of $k$ exponentials is Exp($k\lambda$). That is why each spacing $D_k$ is exponential with rate $(n - k + 1)\lambda$.
Quick Estimate: Take $n = 4$, $\lambda = 1$. $E[M_4] = 1/4 + 1/3 + 1/2 + 1 = 3/12 + 4/12 + 6/12 + 12/12 = 25/12 \approx 2.08$. The expected gap between the top two is the last spacing $D_4 \sim \text{Exp}(1)$, so $E[M_4 - M_3] = E[D_4] = 1/\lambda = 1$. Rough sanity check: the maximum should be noticeably larger than the second-largest for small $n$, and indeed the gap is
Approach: Use the joint CDF factorization and the memoryless property of the exponential.
Formal Solution:
*Part 1: Distribution and expectation of $M_n$.*
By independence: $F_{M_n}(t) = P(M_n \leq t) = \prod_{i=1}^n P(X_i \leq t) = (1 - e^{-\lambda t})^n, \quad t \geq 0.$
Differentiating: $f_{M_n}(t) = n\lambda e^{-\lambda t}(1 - e^{-\lambda t})^{n-1}.$
For the expectation, expand $(1 - e^{-\lambda t})^{n-1}$ by the binomial theorem and integrate term by term, or use the order statistics identity directly. For order statistics of $\text{Exp}(\lambda)$: $E[X_{(k)}] = \frac{1}{\lambda} \sum_{j=n-k+1}^{n} \frac{1}{j}.$
For the maximum, $k = n$: $E[M_n] = E[X_{(n)}] = \frac{1}{\lambda} \sum_{j=1}^{n} \frac{1}{j} = \frac{H_n}{\lambda},$
where $H_n = 1 + 1/2 + \cdots + 1/n$ is the $n$-th harmonic number.
*Part 2: Expected gap $E[M_n - M_{n-1}]$.*
This is the last spacing $D_n = X_{(n)} - X_{(n-1)}$. Using the order statistics identity above, the second-largest ($k = n-1$) has $E[X_{(n-1)}] = \frac{1}{\lambda} \sum_{j=2}^{n} \frac{1}{j} = \frac{1}{\lambda}\left(H_n - 1\right) = \frac{H_n - 1}{\lambda},$ since the sum runs from $j = n-(n-1)+1 = 2$ up to $n$, i.e. it is $H_n$ with the $j=1$ term removed. Therefore $E[M_n - M_{n-1}] = E[X_{(n)}] - E[X_{(n-1)}] = \frac{H_n}{\lambda} - \frac{H_n - 1}{\lambda} = \frac{1}{\lambda}.$
The gap between the top two order statistics has expected value
*Part 3: Spacings are independent exponentials.*
Define $D_k = X_{(k)} - X_{(k-1)}$ for $k = 1, \ldots, n$ with $X_{(0)} = 0$. The key tool is the memoryless property.
Consider the first spacing $D_1 = X_{(1)} = \min_i X_i$. The minimum of $n$ i.i.d. $\text{Exp}(\lambda)$ is $\text{Exp}(n\lambda)$, so $D_1 \sim \text{Exp}(n\lambda)$.
Now condition on $X_{(1)} = t$. At time $t$, the minimum has been identified and is discarded. The remaining $n-1$ variables each satisfy $X_i > t$. By the memoryless property, each of those $n-1$ survivors is independently distributed as $t + \text{Exp}(\lambda)$. So $X_{(2)} - X_{(1)} = \min$ of $n-1$ independent $\text{Exp}(\lambda)$ variables, which is $\text{Exp}((n-1)\lambda)$, independent of $X_{(1)}$.
Repeating the argument at each stage: after the $k$-th smallest has been recorded, there are $n - k$ remaining survivors, each independently restarting at 0 (by memorylessness). The next spacing is the minimum of $n - k$ exponentials: $D_{k+1} \sim \text{Exp}((n-k)\lambda), \quad \text{independent of } D_1, \ldots, D_k.$
Summarizing: $D_k \sim \text{Exp}((n - k + 1)\lambda), \quad k = 1, \ldots, n,$ and $D_1, \ldots, D_n$ are mutually independent.
In particular the top gap is the last spacing $D_n \sim \text{Exp}((n-n+1)\lambda) = \text{Exp}(\lambda)$, so $E[M_n - M_{n-1}] = E[D_n] = 1/\lambda$, matching Part 2.
As a consistency check, $E[X_{(n)}] = \sum_{k=1}^n E[D_k] = \sum_{k=1}^n \frac{1}{(n-k+1)\lambda} = \frac{1}{\lambda}\sum_{j=1}^n \frac{1}{j} = \frac{H_n}{\lambda}$. Matches Part 1.
Answer: - $F_{M_n}(t) = (1 - e^{-\lambda t})^n$, $E[M_n] = H_n / \lambda$ where $H_n$ is the $n$-th harmonic number. - $E[M_n - M_{n-1}] = 1/\lambda$. - Spacings $D_k = X_{(k)} - X_{(k-1)}$ are independent with $D_k \sim \text{Exp}((n-k+1)\lambda)$; the top gap is $D_n \sim \text{Exp}(\lambda)$.
Intuition
The spacing result is one of the most elegant facts in probability and it comes up constantly in queuing theory, survival analysis, and order flow modeling. The reason it works is pure memorylessness: the exponential distribution is the only continuous distribution with the property that past survival gives you no information about future survival time. So when you have $k$ active exponential clocks and the first one fires, the remaining $k-1$ clocks do not remember how long they have already been running -- they reset. This lets you decompose the entire order statistics structure into a ladder of independent races, each with fewer competitors.
In practice, this structure shows up whenever you model the first arrival, second arrival, and so on from a pool of competing processes -- think of $n$ market makers each independently deciding when to cancel an order, or $n$ components in a reliability system failing at exponential rates. The harmonic sum $H_n / \lambda$ for the expected maximum grows logarithmically in $n$, which means adding more competitors has strongly diminishing returns on the expected time until the last one fires. This logarithmic growth is a direct consequence of the harmonic series and is worth memorizing as a benchmark.