Exponentially weighted average, sum of weights

Question

I'm just wondering how to actually prove that the weights of an exponentially weighted average sum to 1, like

$(1-\alpha)^n + \displaystyle\sum_{i=1}^n \alpha (1-\alpha)^{n-i} = 1$

where $\alpha \in (0, 1]$

This is mentioned in Reinforcement Learning, Barto & Sutton, first sentence of p33. Intuitively it holds true but I'd like to understand the proof of it.

Answer 1

First of all you can put $\alpha$ and $(1-\alpha)^n$ in front of the sigma sign:

$$(1-\alpha)^n + (1-\alpha)^{n}\cdot \alpha\sum_{i=1}^n (1-\alpha)^{-i} $$

Factoring out $(1+\alpha)^n$

$$(1-\alpha)^n \left(1+\alpha\sum_{i=1}^n (1-\alpha)^{-i}\right) $$

That means, that the brackets must be $(1-\alpha)^{-n}$, since $(1-\alpha)^n\cdot (1-\alpha)^{-n}=1 \quad (\color{red}*)$

The sum is the partial sum of a $\color{grey}{\textrm{geometric series}}$, where $\sum\limits_{i=1}^n x^i=x\cdot \frac{x^n-1}{x-1}$. Thus

$$1+\alpha\sum_{i=1}^n \left(\frac1{1-\alpha}\right)^{i}=1+\frac{\alpha}{1-\alpha}\frac{\left(\frac1{1-\alpha}\right)^{n}-1}{\frac1{1-\alpha}-1}$$

$(1-a)\cdot \left( \frac1{1-\alpha}-1\right)=1-1+a=a$. Therefore the denominator is $\alpha$.

$$1+\alpha\frac{\left(\frac1{1-\alpha}\right)^{n}-1}{\alpha}=1+\left(\frac1{1-\alpha}\right)^{n}-1=\left(\frac1{1-\alpha}\right)^{n}=(1-\alpha)^{-n}$$

This is was we wanted at $(\color{red}*)$

Answer 2

Just use the binomial theorem to calculate the coefficient of $\alpha^t$:

The coefficient of $\alpha^t$ in $\alpha(1-\alpha)^{n-i}$ is equal to (clearly for $n-i\geqslant t-1$ and $t>0$) the coefficient of $\alpha^{t-1}$ in $(1-\alpha)^{n-i}$ which is equal to: $$(-1)^{t-1}\cdot\binom{n-i}{t-1}$$
So the coefficient of $\alpha^t$ in the whole thing is equal to:
$$(-1)^t\cdot\binom{n}{t}+(-1)^{t-1}\cdot\binom{n-1}{t-1}+(-1)^{t-1}\cdot\binom{n-2}{t-1}+\dotsb$$ $$=(-1)^t\Bigg(\binom{n}{t}-\binom{n-1}{t-1}-\binom{n-2}{t-1}+\dotsb\Bigg)$$ $$=(-1)^t\Bigg(\binom{n}{t}-\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}\Bigg)$$ Now one can prove that $\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}=\binom{n}{t}$ like the following:
Assume that we have $n$ people $p_1,p_2,\dotsb,p_n$ and their heights are $h_1<h_2<\dotsb<h_n$ and we put them in a row as the $i$-th person is $p_i$ and we want to choose $t$ people out of them. Casework on the tallest person we have chosen:
Since we're taking $t$ people, the tallest guy cannot be shorter that $h_t$. On the other hand if the tallest guy is to be $p_i$, the number of all ways to choose $t$ people so that the tallest one is $p_i$ is equal to $\binom{i-1}{t-1}$. So the number of all methods to choose $t$ people is $\displaystyle\sum_{\small{i=t-1}}^{n-1}\binom{i}{t-1}=\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}$. On the other hand the number of ways to choose $t$ people out of $n$ people is clearly $\binom{n}{t}$ so finally $\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}=\binom{n}{t}$.

Back to our problem, since we proved this identity, the coefficient of $\alpha^t$ in the whole expression ($\forall t\not=0$) is equal to zero. Hence it only has constant terms and we only have one constant term in the expression (which is in the $(1-\alpha)^n$ and it is equal to $1$. So the value of $(1-\alpha)^n + \displaystyle\sum_{i=1}^n \alpha (1-\alpha)^{n-i}$ is equal to $1$.