Swap sums, change of indices

Question

there are two equations I don't understand.

1. (Probability Theory): $$\sum_{k=1}^{\infty} P(X \ge k) = \sum_{k=1}^{\infty} \sum_{n=k}^{\infty} P(X=n) = \sum_{n=1}^{\infty} \sum_{k=1}^{n} P(X=n) = \dots$$ I really don't get the second equation. I know that you can swap sums if all the addends are non-negative. But why do you change the indices like that?

2. Markov Chains: $$\dots \sum_{n=1}^{\infty} \sum_{k=1}^{n} f_{ij}^{k} \Pi^{n-k}(j,j) = \sum_{k=1}^{\infty} \sum_{m=0}^{\infty} f_{ij}^{k} \Pi^m (j,j) = \dots $$ where $\Pi$ is the transition matrix. This time I know that you replace $n-k$ by $m$, but why is the first sum from 1 to infinity?

Thank you for all your help.

Answer 1

Those two problems are basically the same, one is the inverse of the other.

It's just the matter of the order in which you take the numbers $n$ and $k$. Let's represent the pairs $(n,k)$ that are included in the sum in a table (a bullet indicates that we include $(n,k)$ in the sum):

So in $\sum\limits_{k=1}^{\infty} \sum\limits_{n=k}^{\infty}$ we sum by columns, i.e. we take the sum of each column (for each fixed $k$) and then add all those sums.

On the other hand, in $\sum\limits_{n=1}^{\infty} \sum\limits_{k=1}^{n}$ we sum by rows, i.e. take the sum in each row and add them all together.

In both cases we're using the same set of pairs $(n,k)$, so the sum is the same (of course, given that we can do the swap, which we can, as you noted, because all addends are positive).

The second problem is similar. Let's denote $f_{ij}^{k} \Pi^{m}(j,j) = a_{m,k}$. Then the second problem becomes:

$$\sum\limits_{n=1}^{\infty} \sum\limits_{k=1}^{n} a_{n-k,k}=\sum\limits_{k=1}^{\infty} \sum\limits_{n=k}^{\infty} a_{n-k,k}=\sum\limits_{k=1}^{\infty} \sum\limits_{m=0}^{\infty} a_{m,k},$$ where the first equation follows from what we said earlier, and the second equation just takes $m=n-k$.

Answer 2

In the first sum, omitting the infinite upper bounds,

$$\begin{cases}1\le k,\\k\le n\end{cases}$$ or $$1\le k\le n.$$

You can transform this system of inequations in the equivalent

$$\begin{cases}1\le n,\\1\le k\le n.\end{cases}$$

(The range of $n$ is clearly $n\ge1$, and for a given $n$, the range of $k$ is $1\le k\le n$.)

Hence

$$\sum_{k=1}^\infty\sum_{n=k}^\infty e_{kn}\equiv\sum_{n=1}^\infty\sum_{k=1}^n e_{kn}.$$

---

For the second, $$1\le k\le n$$

(the range of $k$ is clearly $k\ge1$, and for a given $k$, $n\ge k$)

or, by the change of variable $m:= n-k$,

$$\begin{cases}1\le k,\\0\le m\end{cases}.$$

$$\sum_{n=1}^\infty\sum_{k=1}^n e_{k,n-k}\equiv\sum_{k=1}^\infty\sum_{m=0}^\infty e_{km}.$$

---

The general approach is

• find the range of the first summation index,

• for a given value of the first summation index, find the range of the second summation index,

• for a given value of the first and second summation indexes, find the range of the third summation index, and so on.

• simple changes of variables can be useful.

Answer 3

The following representation could also be helpful.

In the first case we can write \begin{align*} \sum_{k=1}^\infty\sum_{n=k}^\infty P(X=n) =\color{blue}{\sum_{1\leq k \leq n<\infty} P(X=n)} =\sum_{n=1}^\infty \sum_{k=1}^n P(X=n) \end{align*}

$$ $$

In the second case we obtain similarly

\begin{align*} \sum_{n=1}^\infty\sum_{k=1}^n f_{ij}^k\prod^{n-k}(j,j) &=\color{blue}{\sum_{1\leq k\leq n<\infty} f_{ij}^k\prod^{n-k}(j,j)}\\ &=\sum_{k=1}^\infty\sum_{n=k}^\infty f_{ij}^k\prod^{n-k}(j,j)\\ &=\sum_{k=1}^\infty\sum_{n=0}^\infty f_{ij}^k\prod^{n}(j,j) \end{align*} In the last line we shift the inner index $n$ to start from $n=0$.