Probability with Martingales - Ryan McCorvie's solutions

\[ \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\Z}{\mathbb Z} \newcommand{\N}{\mathbb N} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\Norm}[1]{\left \lVert #1 \right \rVert} \newcommand{\Abs}[1]{\left \lvert #1 \right \rvert} \newcommand{\pind}{\bot \!\!\! \bot} \newcommand{\probto}{\buildrel P\over \to} \newcommand{\vect}[1]{\boldsymbol #1} \DeclareMathOperator{\EE}{\mathbb E} \DeclareMathOperator{\PP}{\mathbb P} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\dnorm}{\mathcal N} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\Cov}{Cov} \DeclareMathOperator{\Leb}{Leb} \DeclareMathOperator{\Bin}{Bin} \newcommand{\wto}{\buildrel w\over \to} \]

Problem 14.1 Hunt's lemma

Suppose that \((X_n)\) is a sequence of RV's such that \(X = \lim X_n\) exists a.s. and that \((X_n)\) is dominated by \(Y\) in \((L^1)^+\).

\[ \begin{equation} \abs{X_n(\omega)} \leq Y(\omega), \qquad \forall(n,\omega), \qquad \text{and}\qquad \E(Y)<\infty \end{equation} \]

Let \(\{\mathcal F_n\}\) be any filtration. Prove that

\[ \begin{equation} \E(X_n \mid \mathcal F_n) \to \E( X\mid \mathcal F_\infty)\qquad \text{a.s.} \end{equation} \]

\[ \begin{equation} \lim_n X_n = X \qquad \Rightarrow \qquad \lim_n \abs{X_n-X} = 0 \qquad \Rightarrow \qquad \limsup_n \abs{X_n-X} = 0 \end{equation} \]

The last limit is the same as \(\lim_m Z_m= 0\). Furthermore \(Z_m \to 0\) in \(L^1\) by dominated convergence. Note \(\abs{X} = \lim_n \abs{X_n} \leq Y\), so \(\abs{Z_m}\leq \sup_{r\geq m} \abs{X_r-X}\leq 2Y\) and is dominated by an \(L^1\) function. Therefore \(\E Z_m \to 0\).

\[ \begin{equation} \begin{split} \Abs{\E(X_n \mid \mathcal F_n) - \E( X\mid \mathcal F_\infty)} \leq& \Abs{\E(X \mid \mathcal F_n) - \E(X\mid \mathcal F_\infty)} + \Abs{\E(X_n \mid \mathcal F_n) - \E(X \mid \mathcal F_n)} \\ \leq& \Abs{\E(X \mid \mathcal F_n) - \E(X\mid \mathcal F_\infty)} + \E(\abs{X_n-X} \mid \mathcal F_n)\\ \leq& \Abs{\E(X \mid \mathcal F_n) - \E(X\mid \mathcal F_\infty)} + \E(Z_m \mid \mathcal F_n) \\ \leq& \Abs{\E(X \mid \mathcal F_n) - \E(X\mid \mathcal F_\infty)} \\ & \qquad + \Abs{\E(Z_m \mid \mathcal F_n)- \E(Z_m \mid \mathcal F_\infty) } + \E( Z_m \mid \mathcal F_\infty) \end{split} \end{equation} \]

By Doob's upward convergence theorem, \(\E(X \mid \mathcal F_n) \to \E(X \mid \mathcal F_\infty)\) and \(\E(Z_m \mid \mathcal F_n) \to \E(Z_m \mid \mathcal F_\infty)\) in \(L^1\) and almost surely. By the tower property and positivity,

\[ \begin{equation} \E \abs{\E( Z_m \mid \mathcal F_\infty)} = \E Z_m \to 0 \end{equation} \]

so the last term converges to 0 in \(L^1\). Furthermore by conditional dominated convergence, \(\E(Z_m\mid \mathcal F_\infty) \to \E(0\mid \mathcal F_\infty)=0\), so the last term converges to 0 almost surely. Therefore \(\E(X_n \mid \mathcal F_n) \to \E( X\mid \mathcal F_\infty)\) in \(L^1\) and almost surely.

Problem 14.2 Azuma-Hoeffding

Show that if \(Y\) is a RV with values in \([-c,c]\) and \(\E Y = 0\) then for \(\theta \in \R\)

\[ \begin{equation} \E e^{\theta Y} \leq \cosh \theta c \leq \exp\left( \frac 1 2 \theta^2 c^2 \right) \end{equation} \]

Prove that if \(M\) is a positive martingale null at 0 such that for some sequence \((c_n : n\in \N)\) of positive constants

\[ \begin{equation} \abs{M_n-M_{n-1}} \leq c_n, \qquad \forall n \end{equation} \]

then, for \(x>0\),

\[ \begin{equation} \Pr\left(\sup_{k\leq n} M_k \geq x \right) \leq \exp \left( {\frac 1 2 x^2} \bigg/ \sum_{k=1}^n c^2_k \right) \end{equation} \]

\[ \begin{equation} \alpha = \frac{ Y+c} {2c} \qquad \Rightarrow \qquad Y = c \alpha -c (1-\alpha) \end{equation} \]

Since \(\abs{Y}\leq c\) we have \(\alpha \in [0,1]\). By Jensen's inequality since \(\E \alpha = \frac 1 2\)

\[ \begin{equation} \E e^{\theta Y} = \E e^{\theta c \alpha - \theta c (1-\alpha)} \leq e^{\theta c} \E \alpha + e^{-\theta c} \E(1-\alpha) = \frac 1 2 (e^{\theta c} + e^{-\theta c}) = \cosh \theta c \end{equation} \]

\[ \begin{equation} \cosh x = \sum_k \frac{x^{2k}}{(2k)!} \qquad \exp\left( \frac 1 2 x^2 \right) = \sum_k \frac{x^{2k}}{2^k k!} \end{equation} \]

For \(x\geq 0\), we see \(\exp( \frac 1 2 x^2 )\) dominates \(\cosh x\) term by term since the product on the RHS below contains only the even terms

\[ \begin{equation} (2k)! = 2k\cdot (2k-1)\cdots 2\cdot1 \geq 2k\cdot(2k-2) \cdots 2 = 2^k k! \end{equation} \]

Thus we get the second inequality \(\cosh \theta c \leq e^{\frac 1 2 \theta^2 c^2}\).

\[ \begin{equation} \Pr\left( \sup_{k\leq n} e^{\theta M_k} \geq e^{\theta x} \right) \leq e^{-\theta x} \E e^{\theta M_n} \label{eq:azume hoeffding from doob} \end{equation} \]

\[ \begin{equation} \E e^{\theta M_n} = \E( \E( e^{M_n-M_{n-1} } e^{M_{n-1}} \mid \mathcal F_{n-1}) ) = e^{-\frac 1 2 \theta^2 c_n^2} \E e^{\theta M_{n-1}} \end{equation} \]

Thus by induction \(\E e^{\theta M_n} = e^{\frac 1 2 \theta^2 ( c_n^2+ c_{n-1}^2 +\dots +c_1^2)} \E e^{M_0}= \exp(\frac 1 2 \theta^2 \sum_k c^2_k)\). If we choose \(\theta\) to minimize \(\exp( -\theta x + \frac 1 2 \theta^2 \sum_k c^2_k)\) we get \(\theta = x/(\sum_k c_k^2)\). Plugging this into eqref{eq:azume hoeffding from doob}, where we can rewrite the LHS because \(e^{\theta x}\) is monotonically increasing

\[ \begin{equation} \Pr\left( \sup_{k\leq n} M_k \geq x \right) \leq \exp \left( -\frac 1 2 x \bigg/ \sum_k c_k^2 \right) \end{equation} \]

Probability with Martingales by David Williams

Contact