Welcome to Randal Douc's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
{{page>:defs}}

====== Approximation Lemma ======

Let $(\Xset^{\mathbb{N}},\Xsigma^{\otimes\mathbb{N}},\mathbb{P})$ be a probability space.  
For each $k\in\mathbb{N}$, define
$$
\mathcal{F}_k=\sigma(X_{1:k}),
$$
where $X_i$ denotes the coordinate projection on the $i$-th component, that is,
$X_i(\omega)=\omega_i$ for $\omega\in\Xset^{\mathbb{N}}$.

<WRAP center round tip 80%>
**Lemma (Approximation Lemma).**  
Any set $A\in\mathcal{X}^{\otimes\mathbb{N}}$ satisfies the **approximation property**:

For every $\delta>0$, there exist an integer $k\in\mathbb{N}$ and a set $B\in\mathcal{F}_k$ such that
$$
\mathbb{E}\big[|\mathbb{1}_A-\mathbb{1}_B|\big]\leq\delta.
$$
</WRAP>

===== Proof =====

The proof is a classical application of the **monotone class theorem**.

Let $\mathcal{M}$ denote the collection of all sets $A\in\mathcal{X}^{\otimes\mathbb{N}}$ that satisfy the approximation property stated in the lemma.  
We show that $\mathcal{M}$ is a monotone class.

  * **Stability under set differences.**  
Let $A_0,A_1\in\mathcal{M}$ with $A_0\subset A_1$. We claim that $A_1\setminus A_0\in\mathcal{M}$.

For arbitrary sets $A_0,A_1,B_0,B_1$, the following identity holds:
$$
\mathbb{1}_{A_1\setminus A_0}-\mathbb{1}_{B_1\setminus B_0}
=\mathbb{1}_{A_1}\mathbb{1}_{A_0^c}-\mathbb{1}_{B_1}\mathbb{1}_{B_0^c}
=\mathbb{1}_{A_1}(\mathbb{1}_{A_0^c}-\mathbb{1}_{B_0^c})
+(\mathbb{1}_{A_1}-\mathbb{1}_{B_1})\mathbb{1}_{B_0^c}.
$$

Taking absolute values and expectations yields
$$
\mathbb{E}\big[|\mathbb{1}_{A_1\setminus A_0}-\mathbb{1}_{B_1\setminus B_0}|\big]
\leq
\mathbb{E}\big[|\mathbb{1}_{A_0}-\mathbb{1}_{B_0}|\big]
+
\mathbb{E}\big[|\mathbb{1}_{A_1}-\mathbb{1}_{B_1}|\big].
$$

Since $A_0,A_1\in\mathcal{M}$, both terms on the right-hand side can be made arbitrarily small. Hence, the approximation property holds for $A_1\setminus A_0$.

  * **Stability under increasing limits.**  
Let $(A_n)_{n\geq0}$ be an increasing sequence of sets in $\mathcal{M}$, and define
$$
A=\bigcup_{n\geq0}A_n.
$$

For any set $B$, the triangle inequality gives
$$
\mathbb{E}\big[|\mathbb{1}_A-\mathbb{1}_B|\big]
\leq
\mathbb{E}\big[|\mathbb{1}_A-\mathbb{1}_{A_n}|\big]
+
\mathbb{E}\big[|\mathbb{1}_{A_n}-\mathbb{1}_B|\big].
$$

Since $\mathbb{1}_{A_n}\uparrow\mathbb{1}_A$ pointwise, the first term converges to zero, while the second term can be made arbitrarily small because $A_n\in\mathcal{M}$. Therefore, $A\in\mathcal{M}$.

Finally, $\mathcal{M}$ is a monotone class containing all $\mathcal{F}_k$. By the monotone class theorem, it contains
$$
\sigma\Big(\bigcup_{k\geq0}\mathcal{F}_k\Big)=\mathcal{X}^{\otimes\mathbb{N}}.
$$
This completes the proof.
Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools
