$\sum\limits_{j=1}^{\infty}\sum\limits_{k=1}^{j}P(N=j)=\sum\limits_{k=1}^{\infty}P(N\geq k)$

Question

So I'm currently learning about Markov chains and in one proof there was the following step:

$N(y)$ is the number of visits to the state $y$.

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

I don't really understand how you can eliminate the inner sum on the left side by switching the indices etc...

Answer 1

The left side is $$\sum_{j=1}^\infty jP(N=j)=p_1+2p_2+3p_3+\cdots$$ where $p_j=P(N=j)$. This equals $$(p_1+p_2+p_3+\cdots)+(p_2+p_3+\cdots)+(p_3+\cdots)+\cdots =P(N\ge1)+P(N\ge2)+P(N\ge3)+\cdots.$$

Answer 2

I think it's a change in the order of summation. You may consider the 2-D Cartesian plane with the $x$ and $y$ axes becoming the $k-$axis and $j-$axis, respectively. So the main diagonal is the line $k=j$.

In the LHS sum: $\displaystyle\sum_{j=1}^{\infty}\sum_{k=1}^j P(N=j)$, we are summing over all positive integral pairs from the $k-$axis up to the line $j=k$. We can look at this sum the other way, i.e., from the line $k=j$, then "to the right".

Hence, we can write $$ \displaystyle \sum_{j=1}^{\infty}\sum_{k=1}^j P(N=j) = \sum_{k=1}^{\infty}\sum_{j=k}^{\infty} P(N=j). $$ And on the RHS, we can write the inner sum simply as $P(N\ge k)$. Then you have the needed equality.