Week 7 Worksheet Solutions

Home | Assessment | Notes | Worksheets | Tutorials

1. 1. Take $x$ to be a concatenation of all possible finite strings of zeroes and ones. For example \[ x = \mathtt{0100011011000001010011100101110111} \cdots \] and note that the orbit of $x$ intersects every cylinder set $[\epsilon(1) \cdots \epsilon(r)]$ because somewhere in $x$ one can find the sequence $\epsilon(1) \cdots \epsilon(r)$.
   2. Take $x$ to be a concatenation of all possible finite strings of zeroes and ones and twos. For example \[ x = \mathtt{012000102101112202122} \cdots \] and note that the orbit of $x$ intersects every cylinder set $[\epsilon(1) \cdots \epsilon(r)]$ because somewhere in $x$ one can find the sequence $\epsilon(1) \cdots \epsilon(r)$.
2. 1. $x = \mathtt{01010101010101010101010101010101}\cdots$
   2. $x = \mathtt{00010001000100010001000100010001}\cdots$
   3. $x = \mathtt{001001001001001001001001001001001}\cdots$
   4. Fix a sequence $p_n/q_n$ of rational numbers converging to $1/\sqrt{2}$. Given $c(1) \l c(2) \l \cdots$ in $\N$ define $x$ as follows: repeat $c(1)$ times the pattern of $p_1$ ones followed by $q_1 - p_1$ zeroes. Then repeat $c(2)$ times the pattern of $p_2$ ones followed by $q_2 - p_2$ zeroes. Continue by induction. If $c(n) \to \infty$ fast enough then the desired limit statement will be true.
   5. Define $x$ to be 0 on all sets of the form $\{ 2^{2n+1} + 1, \dots, 2^{2n} \}$ and to be 1 on all sets of the form $\{ 2^{2n} + 1, \dots, 2^{2n+1} \}$.
3. 1. The sequence $x$ belongs to $Y$ if and only if every occurrence of 1 in $x$ is immediately followed by a zero.
   2. Let $p_n$ be the number of strings on $n$ zeroes and ones in which 11 does not occur. We have \[ p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 8, p_5 = 13, p_6 = 18 \] and one can prove that $p_n = p_{n-1} + p_{n-2}$ for all $n \ge 3$. Now $p_n$ is precisely the number of cylinders of length $n$ that we need to cover $Y$. Each such cylinder has measure $2^{-n}$ with respect to the fair coin measure. We must therefore have \[ \mu(Y) \le p_n \cdot \dfrac{1}{2^n} \] and this converges to zero because \[ \lim_{n \to \infty} \dfrac{p_{n+1}}{2^{n+1}} \Bigg/ \dfrac{p_n}{2^n} = \dfrac{1}{2} \lim_{n \to \infty} \dfrac{p_{n+1}}{p_n} = \dfrac{\phi}{2} \l 1 \] where $\phi$ is the golden ratio.
   3. Yes, the point \[ x = \mathtt{01010101010101010101010101010101}\cdots \] belongs to $Y$.
   4. No: if the limit is positive for some $x \in Y$ then there is $n \in \N$ with $x(n) x(n+1) = 1$ which is not possible in $Y$.
   5. $\nu = \delta_0$
4. Define $f : \{0,1\}^\N \to [0,1]$ by \[ f(x) = \sum_{n=1}^\infty \dfrac{x(n)}{2^n} \] for all $x \in \{0,1\}^\N$.
   1. The function $X_n(x) = x(n)$ is a measurable function from $X$ to $\R$. Indeed $\{ x \in X : x(n) = 1 \}$ is a Borel set. As linear combinations of measurable functions are measurable, and as pointwise limits of Borel measurable functions are measurable, the function $f$ is itself measurable.
   2. Since $f^{-1}(\emptyset) = \emptyset$ we have $\nu(\emptyset) = 0$. Fix $B_1,B_2,\dots$ a sequence of pairwise disjoint Borel subsets of $[0,1]$. The sequence \[ f^{-1}(B_1),f^{-1}(B_2),\dots \] is pairwise disjoint so the measure is countably additive.
   3. The strong law of large numbers tells us that \[ \left\{ x \in \{0,1\}^\N : \lim_{N \to \infty} \dfrac{1}{N} \sum_{n=1}^N 1 - x(x) = \dfrac{1}{2} \right\} \] has a measure of 1 with respect to the fair coin measure. Given $y \in [0,1]$ the sequence \[ n \mapsto 1_{[0,\tfrac{1}{2}]}(2^n y \bmod 1) \] is equal to the sequence \[ n \mapsto 1 - x(n) \] where $x \in \{0,1\}^\N$ is mapped by $f$ to $x$. We therefore have, up to a countable set of points where $f$ is not injective, that the above set is equal to \[ f^{-1} \left( \left\{ y \in [0,1] : \lim_{N \to \infty} \dfrac{1}{N} \sum_{n=1}^N 1_{[0,\tfrac{1}{2}]}(2^n y \bmod 1) = \dfrac{1}{2} \right\} \right) \] and therefore $\nu$ almost-every point in $[0,1]$ has the property that the limit in question is equal to $\tfrac{1}{2}$.