Q:

Suppose that $X$ is a discrete random variable taking values in $\{0,1,2,...\}$. Show that $E[X]=\sum^{\infty}_{k=0}{P(X>k)}$

Suppose that $X$ is a discrete random variable taking values in $\{0,1,2,...\}$. Show that $E[X]=\sum^{\infty}_{k=0}{P(X>k)}$

Absolutely lost. From my notes, we define $E[X]$ as follows
$E[X]=\sum^{\infty}_{k=1}{xP(X=k)}$
I am also unsure how to explictly write $\sum^{\infty}_{k=0}{P(X>k)}$. My intuitive understanding of $P(X>k)=\{$ probability of the event not occuring consequetively until $X=k\}$, i.e.
$P(X>k)=(1-P(0))(1-P(1))(1-P(2)) \dots (1-P(k-1))$
Or is it
$P(X>k)=1-[P(X=0)P(X=1) \dots P(X=k-1)$

A:

Write 
$$\begin{align}
\mathbb{E} X &= \sum_{k=0}^\infty k \mathbb{P}\{ X = k\}
= \sum_{k=1}^\infty k \mathbb{P}\{ X = k\}
= \sum_{k=1}^\infty \sum_{j=1}^k \mathbb{P}\{ X = k\} \\
&= \sum_{j=1}^\infty \sum_{k=j}^\infty  \mathbb{P}\{ X = k\}
= \sum_{j=1}^\infty \sum_{k=j}^\infty  \mathbb{P}\{ X = k\}
= \sum_{j=1}^\infty  \mathbb{P}\big\{ \bigcup_{k=j}^\infty X = k\big\} \\
&= \sum_{j=1}^\infty \mathbb{P}\{ X > j- 1\}
= \sum_{i=0}^\infty \mathbb{P}\{ X > i\}.
\end{align}$$
For the record, the third equality may look like a magic "trick", and hard to figure out; the whole thing is more intuitive and easier to figure out starting from $\sum_{i=0}^\infty \mathbb{P}\{ X > i\}$ and trying to get back to $\sum_{k=0}^\infty k \mathbb{P}\{ X = k\}$.

