How to show: $\sum_{k=1}^{\infty}\sum_{n=1}^{k}P(X=k)=\sum_{n=1}^{\infty}\sum_{k=n}^{\infty}P(X=k)$

Can anyone explain why this equation is true.

$$\sum_{k=1}^{\infty}\sum_{n=1}^{k}P(X=k)=\sum_{n=1}^{\infty}\sum_{k=n}^{\infty}P(X=k).$$

• Both are sums over pairs $(k,n)$ with $1\leq n\leq k$ of the same expression. Since $P(X=k)\geq 0$, if either side is convergent, you can rearrange the sums freely. – Thomas Andrews Aug 4 '14 at 21:30
• Okay, so it's Tonnellis Theorem which is applied ? – New_to_this Aug 4 '14 at 21:32
• @New_to_this: Yes, you can interpret it this way. – PhoemueX Aug 4 '14 at 21:44
• Tonelli's theorem certain can be cited here. So can Fubini's theorem. Fubini's theorem applies in the case when the sum of all absolute values of the terms is finite. Tonelli's theorem applies when all terms are non-negative, regardless of whether their sum is finite. – Michael Hardy Aug 4 '14 at 22:10

Let $a_{k,n}=P(X=k)$ if $k\geq n$ and $a_{k,n}=0$ otherwise. Then we need to show:

$$\sum_{k=1}^\infty\sum_{n=1}^k P(X=k) = \sum_{k=1}^\infty \sum_{n=1}^\infty a_{k,n}\stackrel{?}{=} \sum_{n=1}^\infty\sum_{k=1}^\infty a_{k,n} = \sum_{n=1}^\infty \sum_{k=n}^\infty a_{k,n}$$

That interior switch is, as you say, a result of Tonelli's theorem for summations, since $a_{k,n}\geq 0$.

• This was my final conclusion aswell. Thank you. – New_to_this Aug 5 '14 at 5:49

I've posted answers to this here before.

$$\sum_{k=1}^\infty \sum_{n=1}^k P(X=k)=\sum_{n=1}^\infty \sum_{k=n}^\infty P(X=k).$$ $$\begin{array}{c|ccccccccccccccccc} & n=1 & n=2 & n=3 & n=4 & \cdots \\ \hline k=1 & \bullet \\ k=2 & \bullet & \bullet \\ k=3 & \bullet & \bullet & \bullet \\ k=4 & \bullet & \bullet & \bullet & \bullet \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$ The sum $\sum_{n=1}^k$ goes along the $k$th horizontal row (and is a finite sum).

The sum $\sum_{k=1}^\infty \sum_{n=1}^k$ then adds those up.

The sum $\sum_{k=n}^\infty$ goes down the $n$th vertical column (and is thus an infinite sum, and starts at $n$, not at $0$).

The sum $\sum_{n=1}^\infty \sum_{k=n}^\infty$ then adds those up.

• That doesn't explain why you can swap the sums, of course. The key is that $P(X=k)\geq 0$. – Thomas Andrews Aug 5 '14 at 10:58