Iterated Weighted Arithmetic Means

This isn’t a novel idea, but I was looking for an iterative method for easing between two values. In this post, I describe and analyze the method of iterating a weighted arithmetic mean. I’m going to examine the effect of changing the weight factor and the rate at which the limiting value is approached as iterations increase. The end goal of this is to provide an alternative easing method to the standard parametric methods that use easing functions such as smoothstep or logistics. This allows the animation variable to be discrete (for instance, in $\mathbb{Z}$), making it simple to ease between a finite set of discrete nodes.

I originally started writing this as a paper, so it might be uncharacteristically formal for this site.

Define the $n^{\text{th}}$ iterated arithmetic mean of $(x_0, y_0)$ to be

$$g_n((x_0,y_0))=f(f(f(\cdots f(x_0) \cdots)))$$

where $f(x)=px+(1-p)y_0$ and $p\in (0,1)$ is the “easing factor”.

Lemma 1.

$$g_n((x_0,y_0))=p^nx_0+(1-p)y_0\sum_{k=0}^{n-1}p^k\quad \forall n\in\mathbb{Z}^{+}$$

Proof. Proceed by induction. Let $P(n)$ denote that the formula holds for $n$. Consider the base case, $n=1$.

$$\begin{aligned}
g_1((x_0,y_0))&=f(x_0)\\
&= px_0+(1-p)y_0\\
&= p^1x_0+(1-p)y_0\sum_{k=0}^0p^k
\end{aligned}$$

So the base case $P(1)$ holds. Now suppose the formula holds for some $n$. Consider:

$$\begin{aligned}
g_{n+1}((x_0,y_0))&=f(g_n((x_0,y_0)))\\
&= f\left(p^nx_0+(1-p)y_0\sum_{k=0}^{n-1}p^k\right)\\
&= p\left(p^nx_0+(1-p)y_0\sum_{k=0}^{n-1}p^k\right)+(1-p)y_0\\
&= p^{n+1}x_0+p(1-p)y_0\sum_{k=0}^{n-1}p^k+(1-p)y_0\\
&= p^{n+1}x_0+(1-p)y_0\left(\sum_{k=0}^{n-1}p^{k+1}+1\right)\\
&= p^{n+1}x_0+(1-p)y_0\left(1+\sum_{k=1}^{n}p^k\right)\\
&= p^{n+1}x_0+(1-p)y_0\sum_{k=0}^{n}p^k
\end{aligned}$$

So $P(n)\implies P(n+1)$ therefore $P(n)\ \forall n\in\mathbb{N}$. $$\tag*{$\blacksquare$}$$

Note that by using this definition, we get

$$g_0(x_0,y_0)=p^0x_0+(1-p)y_0\sum_{k=0}^{-1}p^k=x_0$$

as expected. So $g_n$ is defined $\forall n\in\mathbb{N}$ by this definition.

We might be interested in the long-term behavior of this function; that is, what value it approaches upon many iterations. To be useful, it should approach $y_0$, be strictly monotonic, and never leave the interval $[x_0,y_0]$. Consider

$$\begin{aligned}
\lim_{n\to\infty}\left( g_n((x_0,y_0)) \right) &= \lim_{n\to\infty}\left( p^nx_0+(1-p)y_0\sum_{k=0}^{n-1}p^k \right)\\
&= \lim_{n\to\infty}\left( p^nx_0 \right) + (1-p)y_0 \lim_{n\to\infty}\left( \sum_{k=0}^{n-1}p^k \right)\\
&= (1-p)y_0\lim_{n\to\infty}\left( \sum_{k=0}^{n-1}p^k \right)\end{aligned}$$

Note this is a geometric series with common ratio $p$. Since $p\in(0,1)$,

$$\lim_{n\to\infty}\sum_{k=0}^{n-1}p^k=\sum_{k=0}^{\infty}p^k=\frac{1}{1-p}$$

so

$$\lim_{n\to\infty}\left( g_n((x_0,y_0)) \right) = (1-p)y_0\left(\frac{1}{1-p}\right)=y_0$$

as desired.

Lemma 2. If $x_0<y_0$, $g_n$ is monotonically increasing with respect to $n$. If $x_0=y_0$, $g_i=x_0 \ \forall n \in \mathbb{N}$. If $x_0>y_0$, $g_n$ is monotonically decreasing with respect to $n$.

Proof. Consider:

$$\begin{aligned}
g_{n+1}-g_n&=p^{n+1}x_0+(1-p)y_0\sum_{k=0}^{n}p^k-p^nx_0-(1-p)y_0\sum_{k=0}^{n-1}p^k\\
&= x_0p^n(p-1)+(1-p)y_0\left( \sum_{k=0}^{n}p^k-\sum_{k=0}^{n-1}p^k \right)\\
&= p^nx_0(p-1)+(1-p)y_0p^n\\
&= p^nx_0(p-1)-(p-1)y_0p^n\\
&= p^n(p-1)(x_0-y_0)
\end{aligned}$$

Note $p^n(p-1)<0$ since $p\in (0,1)$. So:

$$x_0<y_0 \implies x_0-y_0<0 \implies g_{n+1}-g_n>0 \implies g_n \text{ increasing}.$$

$$x_0=y_0 \implies x_0-y_0=0 \implies g_{n+1}-g_n=0 \implies g_n \text{ constant}.$$

$$x_0>y_0 \implies x_0-y_0>0 \implies g_{n+1}-g_n<0 \implies g_n \text{ decreasing}.\tag*{$\blacksquare$}$$

We are only interested in the cases where $x_0\neq y_0$ ; the $x_0=y_0$ case is trivial. The natural next question is: how quickly does $g_n$ converge to $y_0$ as a function of $p$ and $n$. Consider the difference quotient

$$\frac{y_0-g_n((x_0,y_0))}{y_0-x_0}$$

This gives some measure of the proportion of the way $g_n((x_0,y_0))$ is from $x_0$ towards $y_0$ at a given $n$; note the numerator is the difference between the value of $g_n$ and the target $y_0$, and the denominator is the length of the range of values $g_n$ can take on. This measure makes sense because $g_n$ is monotonic and bounded on $[x_0,y_0]$ by Lemma 2. Note also by Lemma 2 the numerator and denominator have the same sign, so the difference quotient is non-negative with values in $[0,1)$. Now:

$$\begin{aligned}
\frac{y_0-g_n((x_0,y_0))}{y_0-x_0}&=\frac{y_0-(1-p)y_0\sum_{k=0}^{n-1}p^k}{y_0-x_0}\\\\
&= \frac{y_0\left( 1-(1-p)\sum_{k=0}^{n-1}p^k \right) – p^nx_0}{y_0-x_0}\\\\
&= \frac{y_0\left( 1+(p-1)\sum_{k=0}^{n-1}p^k \right) – p^nx_0}{y_0-x_0}\\\\
&= \frac{y_0\left( 1+\sum_{k=0}^{n-1}p^{k+1}-\sum_{k=0}^{n-1}p^k \right)-p^nx_0}{y_0-x_0}\\\\
&= \frac{y_0\left( 1+\sum_{k=1}^{n}p^{k+1}-\sum_{k=0}^{n-1}p^k \right)-p^nx_0}{y_0-x_0}\\\\
&= \frac{y_0\left(\sum_{k=0}^{n}p^{k+1}-\sum_{k=0}^{n-1}p^k \right)-p^nx_0}{y_0-x_0}\\\\
&= \frac{p^n(y_0-x_0)}{y_0-x_0}\\\\
&= p^n, \qquad y_0 \neq x_0
\end{aligned}$$

In words, $g_n$ is $100(1-p^n)$% of the way to $y_0$ at the $n_{\text{th}}$ step. Define

$$\Delta_n = 1-p^n$$

and consider the finite difference

$$\begin{aligned}
\Delta_{n+1}-\Delta_n &= 1-p^{n+1}-(1-p^n)\\
&= p^n-p^{n+1}\\
&= p^n(1-p) > 0
\end{aligned}$$

In other words, $g_n$ grows exponentially closer to $y_0$ as $n$ increases, with $p$ as the base.

Here is an example of the method in action (https://www.desmos.com/calculator/gzoqpwzchn):

Thanks for reading!