What is the limit of the average value of the first $n$ terms of $(1, 2, 1, 1, 1, 2, 1, 1, 2, 1, ...)$ as $n\to\infty$?

We establish the convergence of the limit.

Step 1. Designate $(1,2)$ as the $1$-st stage and let $L_n$ be the length of the sequence at the $n$-th stage. Also, let $S_n = \sum_{k=1}^{n} a_k$ and $T_n = S_{L_n}$. Then

$$ L_{n+1} = \begin{cases} 2L_n - 1, & \text{if } a_{L_n} = 1 \\ 3L_n - 2, & \text{if } a_{L_n} = 2 \end{cases}, \qquad T_{n+1} = \begin{cases} 2T_n - 1, & \text{if } a_{L_n} = 1 \\ 3T_n - 4, & \text{if } a_{L_n} = 2 \end{cases} $$

With this at our hands, we claim the following:

Claim. $T_n/L_n$ converges to some $\alpha \in [1, 2]$, and in fact, we have $\left|\frac{T_n}{L_n} - \alpha \right| \leq \frac{4}{L_n} $.

Notice that $L_{n+1} - 1 \geq 2(L_n - 1)$ for all $n \geq 1$. Inductively applying this inequality, it follows that

$$L_{n+k} \geq 1 + 2^k (L_n - 1) \qquad \forall n, k \geq 1.$$

Moreover, from the above recurrence relation we read out that

$$ \left| \frac{T_{n+1}}{L_{n+1}} - \frac{T_n}{L_n} \right| = \left\{ \begin{array}{ll} \dfrac{\left| T_n - L_n \right|}{L_n(2L_n - 1)}, & \text{if } a_{L_n} = 1 \\ \dfrac{2\left| 2L_n - T_n \right|}{L_n(3L_n - 2)}, & \text{if } a_{L_n} = 2 \end{array} \right\} \leq \frac{1}{L_n}$$

So by the comparison test applied to $\frac{T_n}{L_n} = \frac{T_1}{L_1} + \sum_{k=1}^{n-1} \left( \frac{T_{k+1}}{L_{k+1}} - \frac{T_k}{L_k} \right)$, it follows that $T_n/L_n$ converges. Let $\alpha$ denote the limit. Then $1 \leq a_k \leq 2$ tells that $1 \leq \alpha \leq 2$ as well. Finally, applying both of the previous inequalities, we get

\begin{align*} \left| \frac{T_n}{L_n} - \alpha \right| &\leq \sum_{k=n}^{\infty} \left| \frac{T_{k+1}}{L_{k+1}} - \frac{T_k}{L_k} \right| \leq \frac{1}{L_n} \sum_{k=0}^{\infty} \frac{L_n}{L_{n+k}} \\ &\leq \frac{1}{L_n} \sum_{k=0}^{\infty} \frac{L_n}{1 + 2^k (L_n - 1)} \leq \frac{1}{L_n} \sum_{k=0}^{\infty} \frac{1}{2^{k-1}} = \frac{4}{L_n} \end{align*}

Therefore the claim follows. ////

Step 2. Now we want to show that $S_m/m$ converges to $\alpha$ as $m\to\infty$. To this end, we define

$$ \epsilon_{A} := \sup\left\{ \left| \frac{S_m}{m} - \alpha \right| : m \in A \cap \mathbb{Z} \right\} $$

(with the convention $\sup \varnothing = 0$, though this is irrelevant to the argument.) Our goal is to estimate $\epsilon_{[L_n, \infty)}$ and conclude that this converges to $0$ as $n\to\infty$, which is equivalent to the showing that $S_m/m \to \alpha$ as $m\to\infty$. It turns out that the following almost-repeating structure plays the key role:

Observation. Let $m \in (L_n, L_{n+1}]\cap\mathbb{Z}$. Then

1. If $m \in (L_n, 2L_n - 1]$, then $S_m = T_n + S_{m-L_n}$.
2. If $a_{L_n} = 2$ and $m \in [2L_n, 3L_n-2]$, then $S_m = 2T_n - 2 + S_{m-2L_n + 1}$.

Both are direct consequences of the construction. Now we temporarily fix $p \geq 1$ and let $n > p$. Then for $m \in (L_n, L_{n+1}] \cap \mathbb{Z}$,

• Case 1. Assume that $m \in [L_n, L_n+L_p) $. Using the fact that $\left| \frac{S_{m-L_n}}{m - L_n} - \alpha \right| \leq 1$, we obtain

  \begin{align*} \left| \frac{S_{m}}{m} - \alpha \right| &\leq \frac{L_n}{m} \cdot\left| \frac{T_n}{L_n} - \alpha \right| + \frac{m-L_n}{m} \left| \frac{S_{m - L_n}}{m - L_n} - \alpha \right| \\ &\leq \frac{L_n}{m} \cdot \frac{4}{L_n} + \frac{m-L_n}{m} \\ &\leq \frac{4}{L_n} + \frac{L_p}{L_p + L_n}. \end{align*}

• Case 2. Assume that $m \in [L_n + L_p, 2L_n - 1]$. Using the fact that $m - L_n \geq L_p$, it follows that

  \begin{align*} \left| \frac{S_{m}}{m} - \alpha \right| &\leq \frac{L_n}{m} \cdot\left| \frac{T_n}{L_n} - \alpha \right| + \frac{m-L_n}{m} \left| \frac{S_{m - L_n}}{m - L_n} - \alpha \right| \\ &\leq \frac{L_n}{m} \cdot \frac{4}{L_n} + \frac{m-L_n}{m} \epsilon_{[L_p, \infty)} \\ &\leq \frac{4}{L_n} + \frac{1}{2} \epsilon_{[L_p, \infty)}. \end{align*}

• Case 3. Let $m \in [2L_n, 2L_n+L_p) $. This case is possible only when $a_{L_n} = 2$ and hence we assume so. By mimicking the previous claim, we find that $\left| \frac{2T_n - 2}{2L_n - 1} - \alpha \right| \leq \frac{C}{2L_n - 1}$ holds for all $n \geq 1$ for some constant $C > 0$ which is independent of $n$. Using this and mimicking Claim 1,

  \begin{align*} \left| \frac{S_{m}}{m} - \alpha \right| &\leq \frac{2L_n - 1}{m} \left| \frac{2T_n - 2}{2L_n - 1} - \alpha \right| + \frac{m - 2L_n + 1}{m} \left| \frac{S_{m-2L_n+1}}{m - 2L_n + 1} - \alpha \right| \\ &\leq \frac{C}{L_n} + \frac{L_p}{L_p + L_n}. \end{align*}

• Case 4. Let $m \in [2L_n+L_p, L_{n-1}) $. Adopting the techniques in Case 2 and Case 3, we obtain

  $$ \left| \frac{S_{m}}{m} - \alpha \right| \leq \frac{C}{L_n} + \frac{2}{3}\epsilon_{[L_p, \infty)}. $$

Combining altogether, with $C' = 4+C$ the following holds:

$$ \epsilon_{(L_n, L_{n+1}]} \leq \frac{C'}{L_n} + \max\left\{ \frac{L_p}{L_p + L_n}, \frac{2}{3}\epsilon_{[L_p, \infty)} \right\}. $$

Then it follows that $ \limsup_{n\to\infty} \epsilon_{(L_n, L_{n+1}]} \leq \frac{2}{3}\epsilon_{[L_p, \infty)} $. Then $\limsup_{n\to\infty} \epsilon_{[L_n, \infty)} \leq \frac{2}{3}\epsilon_{[L_p, \infty)}$ holds as well, and then it is easy to conclude that

$$\limsup_{n\to\infty} \epsilon_{[L_n, \infty)} = 0.$$

This implies the desired convergence.