Dyadic Martingales

Setting for this page

Throughout this section we will restrict our attention to the probability space $(\Omega ,\Sigma ,\mathbb{P})=([0,1],\mathcal{B}([0,1]),\lambda ),$ where $\mathcal{B}([0,1])$ is the Borel sigma-algebra and $\lambda$ is the Lebesgue measure. For $k\in \mathbb{N}$, define ${\mathcal{D}}_k:=\left\{\left[\frac{i}{2^k},\frac{i+1}{2^k}\right):i=0,\dots ,2^k-1\right\},$ and ${\mathcal{F}}_k:=\sigma ({\mathcal{D}}_k).$ The sets in ${\mathcal{D}}_k$ are called the dyadic intervals of $[0,1]$ at scale $k$. They have the properties that the cubes in ${\mathcal{D}}_k$ partition $[0,1]$ and each dyadic interval in ${\mathcal{D}}_k$ uniquely contains two dyadic “children” in ${\mathcal{D}}_{k+1}$.

Proposition

For $f\in L^2([0,1))$, define $M_k(f):=\mathbb{E}(f\mid {\mathcal{F}}_k)$ for $k\in \mathbb{N}$.

1. $(M_k(f){)}_{k\in \mathbb{N}}$ is a martingale.
2. For any $k\in \mathbb{N}$, $M_k(f)$ can be expressed as $M_k(f)={\sum }_{i=0}^{2^k-1}{1}_{\left[\frac{i}{2^k},\frac{i+1}{2^k}\right)}{2}^k{\int }_{\frac{i}{2^k}}^{\frac{i+1}{2^k}}f(s)ds.$
3. For any $t\in [0,1)$, $M_k(f)(t)=\frac{1}{|I_t|}{\int }_{I_t}f(s)ds,$ where $I_t$ is the unique interval in ${\mathcal{D}}_k$ that contains $t$.
4. There exists $M_{\infty }(f)\in L^2([0,1))$ such that $M_k(f)\to M_{\infty }(f)$ almost surely and in $L^2([0,1))$ as $k\to \infty$.
5. For any $g\in C([0,1))$, $M_{\infty }(g)=g$.

Proof. (i) This is a consequence of the tower property,

$$\begin{array}{rl}\mathbb{E}(M_{k+1}(f)\mid {\mathcal{F}}_k)& =\mathbb{E}(\mathbb{E}(f\mid {\mathcal{F}}_{k+1})\mid {\mathcal{F}}_k)\\ & =\mathbb{E}(f\mid {\mathcal{F}}_k)\\ & =M_k(f).\end{array}$$

(ii) The sigma-algebra ${\mathcal{F}}_k$ is generated by the dyadic intervals

$$I_i^k:=\left[\frac{i}{2^k},\frac{i+1}{2^k}\right),i=0,\dots ,2^k-1.$$

It is then sufficient to demonstrate that the right-hand side of $M_k(f)={\sum }_{i=0}^{2^k-1}{1}_{\left[\frac{i}{2^k},\frac{i+1}{2^k}\right)}{2}^k{\int }_{\frac{i}{2^k}}^{\frac{i+1}{2^k}}f(s)ds.$ satisfies the conditional expectation defining property for $I_j^k$ for some fixed $j=0,\dots ,2^k-1.$ We have

$$\begin{array}{rl}{\int }_{I_j^k}\left(\sum _{i=0}^{2^k-1}{1}_{\left[\frac{i}{2^k},\frac{i+1}{2^k}\right)}(x)2^k{\int }_{I_i^k}f(s)ds\right)dx& ={\int }_{I_j^k}{2}^k{\int }_{I_j^k}f(s)dsdx\\ & ={\int }_{I_j^k}f(s)ds.\end{array}$$

(iii) This is equivalent to statement (ii). (iv) This follows immediately from the martingale convergence theorem. (v) Fix $g\in C([0,1])$ and $t\in [0,1)$. Then

$$\begin{array}{rl}\left|\mathbb{E}(g\mid {\mathcal{F}}_k)(t)-g(t)\right|& \le \underset{s\in I_t}{\sup }|g(s)-g(t)|\\ & \le \underset{\begin{array}{c}s,s^{\prime }\in [0,1]\\ |s-s^{\prime }|\le 2^{-k}\end{array}}{\sup }|g(s)-g(s^{\prime })|,\end{array}$$

which will converge to zero as $k\to \infty$. This demonstrates that $M_{\infty }(g)=g.$

Lebesgue's Differentiation Theorem

For any $f\in L^2([0,1))$, $M_{\infty }(f)=f.$

Proof. Fix $\alpha >0$. It will be shown that

$$\mathbb{P}\left(\underset{k\to \infty }{\mathrm{limsup}}\left|\mathbb{E}(f\mid {\mathcal{F}}_k)-f\right|>3\alpha \right)=0.$$

Fix $\epsilon >0$. As the continuous functions are dense in $L^2([0,1])$, there must exist some $g\in C([0,1])$ with $\Vert g-f{\Vert }_2<\epsilon .$ By monotonicity of the conditional expectation,

$$\begin{array}{rl}\left|\mathbb{E}(f\mid {\mathcal{F}}_k)(t)-f(t)\right|& \le \left|\mathbb{E}(g\mid {\mathcal{F}}_k)(t)-g(t)\right|+\left|\mathbb{E}(f-g\mid {\mathcal{F}}_k)(t)\right|+|f(t)-g(t)|\\ & \le |M_k(g)(t)-g(t)|+\underset{k\in \mathbb{N}}{\sup }\mathbb{E}(|f-g|\mid {\mathcal{F}}_k)+|f(t)-g(t)|,\end{array}$$

for almost every $t\in [0,1)$. $\begin{array}{rl}& \left\{\underset{k}{\mathrm{limsup}}|\mathbb{E}(f\mid {\mathcal{F}}_k)-f|>3\alpha \right\}\\ & \subseteq \left\{\underset{k}{\mathrm{limsup}}|M_k(g)-g|>\alpha \right\}\cup \left\{\underset{k}{\sup }\mathbb{E}(|f-g|\mid {\mathcal{F}}_k)>\alpha \right\}\\ & \cup \{|f-g|>\alpha \}.\end{array}$ Then, through an application of Doob’s maximal inequality and the above proposition, $g\in C([0,1))$, $M_{\infty }(g)=g$.

$$\begin{array}{rl}& \mathbb{P}\left(\underset{k\to \infty }{\mathrm{limsup}}\left|\mathbb{E}(f\mid {\mathcal{F}}_k)-f\right|>3\alpha \right)\\ & \le \mathbb{P}\left(\underset{k\to \infty }{\mathrm{limsup}}|M_k(g)-g|>\alpha \right)+\mathbb{P}\left(\underset{k\in \mathbb{N}}{\sup }\mathbb{E}(|f-g|\mid {\mathcal{F}}_k)>\alpha \right)+\frac{1}{\alpha }\Vert f-g{\Vert }_1\\ & \le \frac{1}{\alpha }\underset{k\in \mathbb{N}}{\sup }\mathbb{E}\left(\mathbb{E}(|f-g|\mid {\mathcal{F}}_k)\right)+\frac{1}{\alpha }\Vert f-g{\Vert }_1\\ & =\frac{2}{\alpha }\Vert f-g{\Vert }_1\\ & \le \frac{2}{\alpha }\Vert f-g{\Vert }_2\\ & \le \frac{2}{\alpha }\epsilon .\end{array}$$

This demonstrates $\mathbb{P}\left({\mathrm{limsup}}_{k\to \infty }\left|\mathbb{E}(f\mid {\mathcal{F}}_k)-f\right|>3\alpha \right)=0.$ Then

$$\begin{array}{rl}\mathbb{P}\left(\underset{k\to \infty }{\mathrm{limsup}}\left|\mathbb{E}(f\mid {\mathcal{F}}_k)-f\right|>0\right)& =\mathbb{P}\left(\bigcup _{N\in \mathbb{N}}\left\{\underset{k\to \infty }{\mathrm{limsup}}\left|\mathbb{E}(f\mid {\mathcal{F}}_k)-f\right|>\frac{1}{N}\right\}\right)\\ & \le \sum _{N\in \mathbb{N}}\mathbb{P}\left(\underset{k\to \infty }{\mathrm{limsup}}\left|\mathbb{E}(f\mid {\mathcal{F}}_k)-f\right|>\frac{1}{N}\right)\\ & =0.\end{array}$$

Corollary

For any $f\in L^2([0,1))$, ${\Vert \mathbb{E}(f\mid {\mathcal{F}}_k)-f\Vert }_2\to 0\text{as }k\to \infty .$

Haar Function

Let $H:\mathbb{R}\to \mathbb{R}$ be the function $H(t):=\{\begin{array}{ll}1& \text{if }t\in [0,1/2)\\ -1& \text{if }t\in [1/2,1)\\ 0& \text{otherwise.}\end{array}$ The Haar functions are defined through $H_0(t):=1\forall t\in [0,1],$ and for any $k\in \mathbb{N}$ and $i=0,\dots ,2^k-1,$ $H_{2^k+i}(t):=2^{k/2}H(2^{k}t-i)\forall t\in [0,1].$

Lemma

For any $f\in L^2([0,1))$, the following statements are true.

1. For any $I=I_i^k=[i/2^k,(i+1)/2^k)$, where $k\in \mathbb{N}$ and $i\le 2^k-1$, $1_I\cdot (\mathbb{E}(f\mid {\mathcal{F}}_{k+1})-\mathbb{E}(f\mid {\mathcal{F}}_k))=\left({\int }_0^1{H}_{2^k+i}(s)f(s)ds\right)H_{2^k+i}=⟨H_{2^k+i},f⟩H_{2^k+i}.$
2. For any $k\in \mathbb{N}$, $\mathbb{E}(f\mid {\mathcal{F}}_k)={\sum }_{n=0}^{2^k-1}⟨f,H_n⟩H_n.$

Proof.

(i) Define the intervals

$$I_{+}:=\left[\frac{i+\frac{1}{2}}{2^k},\frac{i+1}{2^k}\right)\text{and}{I}_{-}:=\left[\frac{i}{2^k},\frac{i+\frac{1}{2}}{2^k}\right).$$

Then

$$\begin{array}{rl}{1}_{I_i^k}\cdot \left(\mathbb{E}(f\mid {\mathcal{F}}_{k+1})-\mathbb{E}(f\mid {\mathcal{F}}_k)\right)& =1_{I_i^k}\cdot \left(1_{I_{+}}\frac{2}{|I|}{\int }_{I_{+}}f+1_{I_{-}}\frac{2}{|I|}{\int }_{I_{-}}f\right)-\frac{1_I}{|I|}{\int }_{I}f\\ & =\frac{1_{I_{+}}}{|I|}\left({\int }_{I_{+}}f-{\int }_{I_{-}}f\right)+\frac{1_{I_{-}}}{|I|}\left({\int }_{I_{-}}f-{\int }_{I_{+}}f\right)\\ & =\frac{1}{|I|}\left(1_{I_{+}}-1_{I_{-}}\right)\left({\int }_{I_{+}}f-{\int }_{I_{-}}f\right)\\ & =⟨f,H_{2^k+i}⟩H_{2^k+i}.\end{array}$$

(ii) The statement is trivially true for $k=0$. So fix $k\in {\mathbb{N}}^{\ast }$. This can be deduced from part (i) through

$$\begin{array}{rl}\mathbb{E}(f\mid {\mathcal{F}}_k)-\mathbb{E}(f\mid {\mathcal{F}}_0)& =\sum _{l=0}^{k-1}\left(\mathbb{E}(f\mid {\mathcal{F}}_{l+1})-\mathbb{E}(f\mid {\mathcal{F}}_l)\right)\\ & =\sum _{l=0}^{k-1}\sum _{j=0}^{2^l-1}{1}_{[j/2^l,(j+1)/2^l)}\cdot \left(\mathbb{E}(f\mid {\mathcal{F}}_{l+1})-\mathbb{E}(f\mid {\mathcal{F}}_l)\right)\\ & =\sum _{l=0}^{k-1}\sum _{j=0}^{2^l-1}⟨H_{2^l+j},f⟩H_{2^l+j}\\ & =\sum _{n=1}^{2^k-1}⟨H_n,f⟩H_n.\end{array}$$

Which implies $\mathbb{E}(f\mid {\mathcal{F}}_k)={\sum }_{n=0}^{2^k-1}⟨f,H_n⟩H_n,$ since

$$\mathbb{E}(f\mid {\mathcal{F}}_0)=⟨f,H_0⟩H_0.$$

Haar basis

$(H_n{)}_{n\in \mathbb{N}}$ is an orthonormal basis for the Hilbert space $L^2([0,1))$. It is called the Haar basis.

Proof. On combining the Lebesgue differentiation theorem and the previous lemma we obtain

$$\begin{array}{rl}f& =\underset{k\to \infty }{\overset{L^2}{\lim }}\mathbb{E}(f\mid {\mathcal{F}}_k)\\ & =\underset{k\to \infty }{\overset{L^2}{\lim }}\sum _{n=0}^{2^k-1}⟨f,H_n⟩H_n\\ & =\sum _{n=0}^{\infty }⟨f,H_n⟩H_n,\end{array}$$

for any $f\in L^2([0,1))$. This demonstrates that the linear span of the Haar functions is dense in the space $L^2([0,1))$.