---
tag: 2A71TR7AV7
kind: proof
name: Proof of the tail sum formula for expectation by dyadic approximation
msc: [60A05]
proves: 0Y6QNF1J49
uses: [0DCT0QZVQ1, 0DKRR22AEQ, 0BVHZXWKCD, 0464Z0JP2E, 0VSB0XF4G7, GEA8H3228S, 0P7PTC8DDE, G2S6H789RG, 04YKAYDQPW, 05RCDKHZM6, 0MBWQKM8QR]
sources:
  - url: https://en.wikipedia.org/wiki/Expected_value
    locator: Tail-sum formula
---

## Proof

We write $X$ as a series of indicators and use monotone convergence. For the integral we compare with sums over a fine dyadic grid.

1. Let $X$ be a [[random variable|0DKRR22AEQ]] on $(\Omega, \mathcal{F}, P)$ with values in $[0, \infty)$. For $t \ge 0$ the set $(t, \infty)$ is open, hence a [[Borel set|0BVHZXWKCD]]. The set $[t, \infty)$ is the complement of the open set $(-\infty, t)$, so it is Borel too. So $\set{X > t}$ and $\set{X \ge t}$ are events.
2. We first prove a lemma. Let $A_1, A_2, \dots$ be events, let $c_1, c_2, \dots \ge 0$, and let $Z(\omega) = \sum_{n=1}^{\infty} c_n \mathbf{1}_{A_n}(\omega) \in [0, \infty]$. We claim $E[Z] = \sum_{n=1}^{\infty} c_n P(A_n)$.
3. An [[indicator|0VSB0XF4G7]] $\mathbf{1}_A$ is a simple function. By the [[integral of a non-negative function|GEA8H3228S]], $E[\mathbf{1}_A] = P(A) \le 1$, so $\mathbf{1}_A$ is integrable.
4. Let $S_N = \sum_{n=1}^{N} c_n \mathbf{1}_{A_n}$. By [[linearity of expectation|0P7PTC8DDE]] and induction on $N$, $S_N$ is integrable and $E[S_N] = \sum_{n=1}^{N} c_n P(A_n)$.
5. The functions $S_N$ are nonnegative and nondecreasing in $N$, with limit $Z$. By the [[monotone convergence theorem|G2S6H789RG]], $Z$ is measurable and $E[Z] = \lim_N E[S_N] = \sum_{n} c_n P(A_n)$.
6. Integer case. Let $X$ take values in $\set{0, 1, 2, \dots}$. For each $\omega$, the indices $n \ge 1$ with $X(\omega) \ge n$ are $1, \dots, X(\omega)$. So $\sum_{n \ge 1} \mathbf{1}_{\set{X \ge n}}(\omega) = X(\omega)$.
7. The lemma with $c_n = 1$ and $A_n = \set{X \ge n}$ gives $E[X] = \sum_{n=1}^{\infty} P(X \ge n)$.
8. General case. Let $G(t) = P(X > t)$ for $t \ge 0$. If $s \le t$, then $\set{X > t} \subseteq \set{X > s}$. By [[monotonicity of probability|0464Z0JP2E]], $G$ is nonincreasing, with values in $[0, 1]$.
9. By [[monotone functions are Riemann integrable|04YKAYDQPW]], $G$ is integrable on each $[0, T]$. We read $\int_0^\infty G(t) \, dt$ as $I = \lim_{T \to \infty} \int_0^T G(t) \, dt$.
10. This limit exists in $[0, \infty]$. By the [[additivity over intervals|05RCDKHZM6]] and the [[monotonicity of the integral|0MBWQKM8QR]], $\int_0^{T'} G = \int_0^T G + \int_T^{T'} G \ge \int_0^T G$ for $T < T'$.
11. Fix $m \ge 1$ and let $h = 2^{-m}$. Let $Z_m = \sum_{n=1}^{\infty} h \mathbf{1}_{\set{X > nh}}$. Then $Z_m(\omega) = h N_m(\omega)$, where $N_m(\omega)$ is the number of integers $n \ge 1$ with $nh < X(\omega)$.
12. We have $X - h \le Z_m \le X$. Let $N = N_m(\omega)$. Then $(N + 1) h \ge X(\omega)$, and $Nh < X(\omega)$ if $N \ge 1$, while $Z_m(\omega) = 0 \le X(\omega)$ if $N = 0$.
13. The sequence $Z_m$ is nondecreasing in $m$. If $nh < X(\omega)$, then $2n$ and $2n - 1$ satisfy $k \cdot h/2 < X(\omega)$. So $N_{m+1} \ge 2 N_m$, and $Z_{m+1} = (h/2) N_{m+1} \ge h N_m = Z_m$.
14. By steps 12 and 13, $Z_m$ increases to $X$. By the monotone convergence theorem, $E[Z_m] \to E[X]$ in $[0, \infty]$.
15. By the lemma of step 2, $E[Z_m] = \sum_{n=1}^{\infty} h \, G(nh)$.
16. Let $I_n = \int_{(n-1)h}^{nh} G(t) \, dt$. On $[(n-1)h, nh]$ we have $G(nh) \le G(t) \le G((n-1)h)$, by step 8.
17. By the monotonicity of the integral, comparing with constant functions, $h \, G(nh) \le I_n \le h \, G((n-1)h)$.
18. By additivity over intervals, $\int_0^{Nh} G = \sum_{n=1}^{N} I_n$. By step 10, letting $N \to \infty$ gives $I = \sum_{n=1}^{\infty} I_n$.
19. By steps 15, 17 and 18, $E[Z_m] = \sum_{n \ge 1} h \, G(nh) \le \sum_{n \ge 1} I_n = I$.
20. Also $I = \sum_{n \ge 1} I_n \le \sum_{n \ge 1} h \, G((n-1)h) = h \, G(0) + \sum_{n \ge 1} h \, G(nh) \le h + E[Z_m]$.
21. So $E[Z_m] \le I \le E[Z_m] + 2^{-m}$ for every $m \ge 1$.
22. If $E[X] = \infty$, then $E[Z_m] \to \infty$ by step 14, and step 21 gives $I = \infty = E[X]$.
23. If $E[X] < \infty$, let $m \to \infty$ in step 21. Both bounds tend to $E[X]$, so $I = E[X]$. Thus $E[X] = \int_0^\infty P(X > t) \, dt$ in all cases.

## Idea

A nonnegative integer $k$ equals the number of $n \ge 1$ with $k \ge n$, so $X = \sum_n \mathbf{1}_{\set{X \ge n}}$. Taking expectations term by term turns this into the tail sum. For a general $X$, the same count on the grid $2^{-m} \Z$ gives a staircase below $X$, and its expectation is a Riemann sum of $t \mapsto P(X > t)$. Refining the grid squeezes both sides together.