Entropy rate of a finite repetition

Solution 1:

Sketch:

In general, $n$ can be written as $$n = 3 m + r $$ where $m,r$ are non-negative integers and $r \in \{1,2, 3\}$ is the remainder of $n$ divided by $3$, plus one.

Then $$H_n = (m +1)H(X) = \left(\frac{n+3-r}{3}\right) H(X)$$

Can you go on from here?

Solution 2:

$X_i^{1} \sim U(\{1,2,\ldots 26\})$, i.i.d., s.t., $H(X_i^{1})=\log_2{26}$, where the r.v. represents the first symbol of the $i^{th}$ group $X_i$. All the groups (except possibly the last one) contain (at most) 3 variables, with the $1^{st}$ being random, the others being completely deterministic.

There can be 3 cases:

1. $n \equiv 0 (\text{mod } 3)$: there are $\frac{n}{3}$ groups for which the first one is randomly (uniformly) chosen from $26$ symbols, the other two are fully determined, hence total entropy $H(X)=\sum\limits_{i=1}^{\frac{n}{3}}H(X_i^{1})=\frac{n}{3}\log{26}$.

2. $n \equiv 1 (\text{mod } 3)$: there are $\frac{n-1}{3}$ groups for which the first one is randomly (uniformly) chosen from $26$ symbols, the other two are fully determined, additionally there is one single symbol in the group $X_{\frac{n-1}{3}+1}$, hence total entropy $=\sum\limits_{i=1}^{\frac{n-1}{3}}H(X_i^{1})+H\left(X_{\frac{n-1}{3}+1}^{1}\right)=\frac{n-1}{3}\log{26}+\log{26}=\frac{n+2}{3}\log{26}$.

3. $n \equiv 2 (\text{mod } 3)$: there are $\frac{n-2}{3}$ groups for which the first one is randomly (uniformly) chosen from $26$ symbols, the other two are fully determined, additionally there is a last group with two symbols in the group $X_{\frac{n-2}{3}+1}$, hence total entropy $=\sum\limits_{i=1}^{\frac{n-2}{3}}H(X_i^{1})+H\left(X_{\frac{n-2}{3}+1}^{1}\right)=\frac{n-2}{3}\log{26}+\log{26}=\frac{n+1}{3}\log{26}$.

Hence, $\frac{n}{3}\log{26}\leq H(X) \leq \frac{n+2}{3}\log{26}$.