Week 11 Worksheet Solutions

Home | Assessment | Notes | Worksheets | Tutorials

1. The partition $\xi = ( [0], [1], [2])$ is generating for the shift map so we may just compute \[ \begin{align*} \ent(T) &{} = \ent(T, \xi) = \lim_{N \to \infty} \dfrac{1}{N} \ent( \xi \vee T^{-1} \xi \vee \cdots \vee T^{-(N-1)} \xi) \\ &{} = \lim_{N \to \infty} \dfrac{1}{N} 3^N \cdot \dfrac{1}{3^N} \log (3^N) \end{align*} \] giving an entropy of $\log 3$.
2. With respect to normalized counting measure, every partition of $\Z/p$ has entropy at most $\log p$ and therefore, for any partition $\xi$ we have \[ \ent(T,\xi) \le \lim_{N \to \infty} \dfrac{\log p}{N} \] which is zero.
3. It is directly verified that $0$, $1$ and \[ 00 \quad 01 \quad 10 \] are the only string of lengths 1 and 2 respectively that do not contain consecutive ones. Fix $n \ge 3$ and let $s_1 \cdots s_r$ be a string of zeroes and ones with no consecutive ones. If $s_1 = 0$ then there are $w_{n-1}$ possibilities for the repaining strings as any string of length $n-1$ not containing consecutive ones can appear. If $s_1 = 1$ then $s_2 = 0$ but then there are $w_{n-2}$ possibilities for the remaining $n-2$ strings. Thus $w_n = w_{n-1} + w_{n-2}$.
4. Fix $0 \l p \le 1$ and let $\mu$ be the $(1-p,p)$ fair coin measure. As $T$ is ergodic for $\mu$ we can deduce that \[ \lim_{N \to \infty} \dfrac{1}{N} \sum_{n=0}^{N-1} 1_{[11]}(T^n x) = \int 1_{[11]} \intd \mu = p^2 \] for $\mu$ almost every $x \in \{0,1\}^\N$. But no sequence in $Y$ has consecutive ones in it, so we must have $\mu(Y) = 0$.
5. The $(1-p,p)$ coin measure on $\{0,1\}^\N$ has entropy \[ -p \log p - (1-p) \log(1-p) \] which, for every $0 \le p \le 1$ is less than $\log 3$. As isomorphic systems have the same entropy, no coin measure on $\{0,1\}^\N$ gives a system isomorphic to the fair coin measure on $\{0,1,2\}^\N$.
6. The corresponding transition matrix is \[ B = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} \] and since all entries of $B^2$ are positive we may apply Parry's theorem to calculate the entropy. The eigenvalues of B are \[ 1 - \sqrt{3}, 0, 1 + \sqrt{3} \] and we set $\lambda = 1 + \sqrt{3}$. The entropy is $\log(1 + \sqrt{3})$.
   
   The vectors \[ U = \begin{bmatrix} \lambda & 2 & \lambda \end{bmatrix} \qquad V = \begin{bmatrix} \lambda \\ 2 \\ \lambda \end{bmatrix} \] are left and right eigenvectors respectively of $B$ with eigenvalue $\lambda$. Parry's theorem tells us to take \[ Q = \begin{bmatrix} \dfrac{1}{\lambda} & \dfrac{2}{\lambda^2} & \dfrac{1}{\lambda} \\ \dfrac{1}{2} & 0 & \dfrac{1}{2} \\ \dfrac{1}{\lambda} & \dfrac{2}{\lambda^2} & \dfrac{1}{\lambda} \end{bmatrix} \] and \[ p = \begin{bmatrix} \dfrac{\lambda^2}{4+2 \lambda^2} & \dfrac{4}{4+2 \lambda^2} & \dfrac{\lambda^2}{4+2 \lambda^2} \end{bmatrix} \]