9
$\begingroup$

I have a question about switching the order of summation in this probability question. I'll give the probability background, but it's not necessary to understand my question. We have a random variable X that takes on nonnegative integer values. We want to show that:

$\operatorname{E}[X]=\sum\limits_{i=1}^\infty P(X\geq i)$

We start off by noting that:

$\sum\limits_{i=1}^\infty P(X\geq i) = \sum\limits_{i=1}^\infty \sum\limits_{j=i}^\infty P(X = j). $

My question comes in at this next part: $\begin{align} \sum\limits_{i=1}^\infty \sum\limits_{j=i}^\infty P(X = j) &=\sum\limits_{j=1}^\infty \sum\limits_{i=1}^j P(X = j)\\ \end{align}$

If I explicitly write out the first several terms of the left hand side, I can convince myself that these two double sums are indeed the same. But is there an intuitive, heuristic way to see that these two sums are equivalent without explicitly writing out any terms?

Thanks!

Note: If you need more background, you can read about this problem on the Wiki page: http://en.wikipedia.org/wiki/Expected_value#Discrete_distribution_taking_only_non-negative_integer_values

$\endgroup$
1
  • $\begingroup$ fix an index $j$ and see that the term $P(X=j)$ appears on both sides the same number of times. That is $j$ times. $\endgroup$ Commented Sep 11, 2013 at 17:18

2 Answers 2

21
$\begingroup$

For these things, I often find it helpful to think of the direction of the summation.

Think of it as a matrix, where $i$ denotes the row and $j$ the column. The first sum says that: in the first row, when $i=1$, we sum the entries in columns 1 to infinity. That is, we sum the entire (infinite...) row starting at 1. Then, we move to the second row, such that $i=2$, and sum the entire row from 2 and upwards. This pattern continues - in row $i$, we sum all entries from column number $i$ and to the right of it. Thus, we are doing horizontal summation.

It is, however, possible to do the summation vertically as well. To sum the exact same entries but in this way instead, we start with column $j=1$. Here, we want the entry in the first row only. Then, we move to $j=2$ and sum elements 1 and 2. When $j=3$, we sum elements 1, 2, and 3 since we want everything to the right of, and including, the main diagonal. Thus, the pattern that we find is that $i\leq j$. Hence, having $j$ as the outer sum we let it go to infinity to get the entire upper triangular part of the matrix and let the sum for $i$ stop at $j$.

Here's a picture too:

enter image description here

$\endgroup$
1
  • $\begingroup$ To that, I would add that actually drawing the matrix helps a lot $\endgroup$ Commented Sep 11, 2013 at 17:04
5
$\begingroup$

Instead of directly switching the sums, you can use an intermediate step with only one sum, for example:

$$\sum_{i=1}^{n}\sum_{j=1}^{i}f\left(\left(i,j\right)\right)\\ = \sum_{t\in\left\{ \left(i,j\right)\mid j\le i\le n\right\} }f\left(t\right)\\ = \sum_{j=1}^{n}\sum_{i=j}^{n}f\left(\left(i,j\right)\right)$$

This has the advantage that it works with pretty much arbitrary amounts of nested summations and it's also easier when you don't want to draw the matrix suggested by @hejseb.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .