Limit of the running average of 3 numbers

Question

Take three numbers $x_1$, $x_2$, and $x_3$ and form the successive running averages $x_n = (x_{n-3} + x_{n-2} + x_{n-1})/3$ starting from $x_4$.

What is the limit as $n\to\infty$?

One approach to this problem is to form a Markov chain, as alluded to by this question: Markov chain, successive running average

However, I am wondering how to construct this as a Markov chain? What are the states? What is the transition matrix?

Answer 1

Can you show that the sequence converges? Once you have done that it is easy to find the limit.

Let's write down the recurrence in form $$3x_n=x_{n-1}+x_{n-2}+x_{n-3}$$ And further if we put $n=4,5, \dots $ we get the set of relations \begin{align} 3x_4&=x_3+x_2+x_1\notag\\ 3x_5&=x_4+x_3+x_2\notag\\ 3x_6&=x_5+x_4+x_3\notag\\ \dots&=\dots\notag\\ 3x_{n-2}&=x_{n-3}+x_{n-4}+x_{n-5}\notag\\ 3x_{n-1}&=x_{n-2}+x_{n-3}+x_{n-4}\notag\\ 3x_n&=x_{n-1}+x_{n-2}+x_{n-3}\notag \end{align} Adding these relations we can see that there will be a lot of cancellations from both sides and the final result will be $$3x_n+2x_{n-1}+x_{n-2}=x_1+2x_2+3x_3$$ Letting $n\to\infty $ we can see that the desired limit is $$\frac{x_1+2x_2+3x_3}{6}$$

---

For showing convergence the best technique is the one mentioned here. The result is easily generalized for the recurrence $$x_n=\frac{1}{k}\sum_{i=1}^{k}x_{n-i}$$ and the limit in this case is $$\frac {2}{k(k+1)}\sum_{i=1}^{k}ix_{i}$$

Answer 2

The naive, immediate approach would be this: any term in the sequence is a linear combination of $x_1,x_2$ and $x_3$. A state would be the coefficients of this linear combination, for the most recent three terms.

So, the initial state is thus $$ [1,0,0,0,1,0,0,0,1]^T $$ One step in the process is a two-step thing. We first append three entries to the right, and then we delete three entries on the left. The three entries we append on the right are the averages of every third element in this vector. In this case, the first entry we append will be the average of $1,0$ and $0$, which is $1/3$. The next one is the average of $0,1$ and $0$, which is $1/3$. The last one is the average of $0,0$ and $1$, which is $1/3$. Then we delete the leftmost three entries. This means the next state is $$ \left[0,1,0,0,0,1,\frac13,\frac13,\frac13\right]^T $$ and the next one after that is $$ \left[0,0,1,\frac13,\frac13,\frac13,\frac1{9},\frac4{9},\frac4{9}\right]^T $$ and so on.

The transition matrix is $$ \begin{bmatrix} 0&0&0&1&0&0&0&0&0\\ 0&0&0&0&1&0&0&0&0\\ 0&0&0&0&0&1&0&0&0\\ 0&0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&0&1\\ 1/3&0&0&1/3&0&0&1/3&0&0\\ 0&1/3&0&0&1/3&0&0&1/3&0\\ 0&0&1/3&0&0&1/3&0&0&1/3\\ \end{bmatrix} $$ So in this approach, we don't have a true Markov process in the conventional sense, as this matrix doesn't preserve the sum of the entries. But it's possible that a lot of the analysis can be carried over.

Also, with our particular initial position, the sum of the entries is actually preserved all the way through the process. One could, conceivably, find the subspace of $\Bbb R^9$ where the above matrix does preserve the sum of the entries, find a new basis on that space, then potentially do real Markov analysis there.

Answer 3

With $$ v_n:= \begin{pmatrix} x_{n}\\ x_{n-1}\\ x_{n-2}\\ \end{pmatrix} \qquad\text{and}\qquad M:=\frac13 \begin{pmatrix} 1&1&1\\ 3&0&0\\ 0&3&0\\ \end{pmatrix} $$ we can write: $$v_n = M v_{n-1} = M^{n-3}v_3 \;\text{ for }\; n \geqslant 4 $$ Then determine eigenvectors $e_i$ and eigenvalues $\lambda_i$, i.e. we have: $$Me_i = \lambda_i e_i \;\Rightarrow\; M^n e_i=\lambda^n_ie_i$$ and represent $v_3$ as linear combination of the 3 eigenvectors: Determine $c_i$ such that $$v_3=\sum_{i=1}^3 c_i e_i$$ which gets us an explicit representation of $v_n$: $$\begin{align} v_n&=M^{n-3}v_3\\ &=M^{n-3}\cdot\big(\sum_i c_i e_i\big)\\ &=\sum_i c_i M^{n-3} e_i\\ &=\sum_i c_i\lambda_i^{n-3} e_i\\ \end{align}$$

The route is exactly the same like can be taken to get an explicit representation for the Fibonacci numbers, see [1].

What is the limit as $n\to\infty$?

The characteristic polynomial of $M$ is $$\begin{align} p(\lambda)&=|M-\lambda E| = \left| \begin{matrix} 1/3-\lambda & 1/3 & 1/3 \\ 1 & -\lambda & 0 \\ 0 & 1 & -\lambda \\ \end{matrix} \right|\\ &= (-3\lambda^3 + \lambda^2+\lambda+1)/3\\ &= -(\lambda - 1)(3\lambda^2 + 2\lambda + 1)/3\\ \end{align}$$ with zeros $$\lambda_1=1,\; \lambda_{2,3}=-\frac13(1\pm\sqrt{2}i)$$ The absolute value of the complex roots is $1/\sqrt3\approx0.577$ thus $x_n$ is dominated by the constant term at $\lambda_1$ and eigenvector $e_1=(1~1~1)$: $$\lim_{n\to\infty}x_n = c_1$$ The eigenvectors for the complex eigenvalues are: $$e_{2,3}= \begin{pmatrix} \lambda^2_{2,3} \\ \lambda_{2,3}\\ 1\\ \end{pmatrix} $$ therefore we get the $c_i$ by means of $$ \begin{pmatrix} c_1\\ c_2\\ c_3\\ \end{pmatrix} =\begin{pmatrix} 1 & \lambda^2_2 & \lambda^2_3\\ 1 & \lambda_2 & \lambda_3\\ 1 & 1 & 1\\ \end{pmatrix}^{\!-1} \begin{pmatrix} x_3\\ x_2\\ x_1\\ \end{pmatrix} $$