Small fact related to generating functions

Question

As part of a demonstration involving coin flipping, I saw this passage: \begin{equation} \sum_{n=0}^{\infty}s^n\mathbb{P}(W>n)=\frac{1-\mathbb{E}(s^W)}{1-s}. \end{equation} I tried to use the facts that \begin{equation}\mathbb{E}(s^W)=\sum_{n=0}^{\infty}s^n\mathbb{P}(W=n)\end{equation} and \begin{equation}\mathbb{P}(W>n)=\sum_{k=n+1}^{\infty}\mathbb{P}(W=k)\end{equation} but still could not proof the equation above. Might it be that I need some assumption that I'm missing?

Answer 1

You have the right formulae, it's just a question of combining them in the correct way. We have $$ \sum_{n=0}^{\infty} s^n\mathbb{P}(W>n) = \sum_{n=0}^{\infty} s^n \sum_{k=n+1}^{\infty} \mathbb{P}(W=k). $$ Now we need to change the order of summation. The sum can be written as over the region $0 \leq n < k < \infty$, so we find that $\sum_{n=0}^{\infty} \sum_{k=n+1}^{\infty} = \sum_{k=0}^{\infty} \sum_{n=0}^{k-1} $. Thus $$ \sum_{n=0}^{\infty} s^n\mathbb{P}(W>n) = \sum_{k=0}^{\infty} \sum_{n=0}^{k-1} s^n \mathbb{P}(W=k) = \sum_{k=0}^{\infty} \mathbb{P}(W=k) \frac{1-s^k}{1-s} = \frac{1}{1-s} \sum_{k=0}^{\infty} \mathbb{P}(W=k) (1-s^k). $$ Then the remaining sum is $\mathbb{E}(1-s^W) = 1-\mathbb{E}(s^W)$ by linearity.