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 $[ϵ(1)\cdots ϵ(r)]$ because somewhere in $x$ one can find the sequence $ϵ(1)\cdots ϵ(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 $[ϵ(1)\cdots ϵ(r)]$ because somewhere in $x$ one can find the sequence $ϵ(1)\cdots ϵ(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)<c(2)<\cdots$ in $\mathbb{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 \mathrm{\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 {\displaystyle \frac{1}{2^n}}$$ and this converges to zero because $$\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{p_{n+1}}{2^{n+1}}}/{\displaystyle \frac{p_n}{2^n}}={\displaystyle \frac{1}{2}}\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{p_{n+1}}{p_n}}={\displaystyle \frac{\varphi }{2}}<1$$ where $\varphi$ 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 \mathbb{N}$ with $x(n)x(n+1)=1$ which is not possible in $Y$.
   5. $\nu ={\delta }_0$
4. Define $f:\{0,1{\}}^{\mathbb{N}}\to [0,1]$ by $$f(x)=\sum _{n=1}^{\mathrm{\infty }}{\displaystyle \frac{x(n)}{2^n}}$$ for all $x\in \{0,1{\}}^{\mathbb{N}}$.
   1. The function $X_n(x)=x(n)$ is a measurable function from $X$ to $\mathbb{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}(\varnothing )=\varnothing$ we have $\nu (\varnothing )=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 $$\{x\in \{0,1{\}}^{\mathbb{N}}:\underset{N\to \mathrm{\infty }}{lim}{\displaystyle \frac{1}{N}}\sum _{n=1}^{N}1-x(x)={\displaystyle \frac{1}{2}}\}$$ has a measure of 1 with respect to the fair coin measure. Given $y\in [0,1]$ the sequence $$n\mapsto 1_{[0,\frac{1}{2}]}(2^{n}ymod1)$$ is equal to the sequence $$n\mapsto 1-x(n)$$ where $x\in \{0,1{\}}^{\mathbb{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(\{y\in [0,1]:\underset{N\to \mathrm{\infty }}{lim}{\displaystyle \frac{1}{N}}\sum _{n=1}^N{1}_{[0,\frac{1}{2}]}(2^{n}ymod1)={\displaystyle \frac{1}{2}}\}\right)$$ and therefore $\nu$ almost-every point in $[0,1]$ has the property that the limit in question is equal to $\frac{1}{2}$.