This section provides a short recap of things that should be known from the lecture on stochastic. \subsection{Notions of Convergence} \begin{definition}+ \label{def:convergence} Fix a probability space $(\Omega,\cF,\bP)$. Let $X, X_1, X_2,\ldots$ be random variables. \begin{itemize} \item We say that $X_n$ converges to $X$ \vocab[Convergence!almost surely]{almost surely} ($X_n \xrightarrow{\text{a.s.}} X$) iff \[ \bP(\{\omega | X_n(\omega) \to X(\omega)\}) = 1. \] \item We say that $X_n$ converges to $X$ \vocab[Convergence!in probability]{in probability} ($X_n \xrightarrow{\bP} X$) iff \[ \lim_{n \to \infty}\bP[|X_n - X| > \epsilon] = 0 \] for all $\epsilon > 0$. \item We say that $X_n$ converges to $X$ \vocab[Convergence!in mean]{in the $p$-th mean} ($X_n \xrightarrow{L^p} X$ ) iff \[ \bE[|X_n - X|^p] \xrightarrow{n \to \infty} 0. \] \item We say that $X_n$ converges to $X$ \vocab[Convergence!in distribution]{in distribution}% \footnote{ This notion of convergence was actually defined during the course of the lecture, but has been added here for completeness; see \yaref{def:weakconvergence}. } ($X_n \xrightarrow{\text{d}} X$) iff for every continuous, bounded $f: \R \to \R$ \[ \bE[f(X_n)] \xrightarrow{n \to \infty} \bE[f(X)]. \] \end{itemize} \end{definition} % TODO Connect to AnaIII \pagebreak \begin{theorem}+ % \footnote{see exercise 3.4} \label{thm:convergenceimplications} \vspace{10pt} Let $X$ be a random variable and $X_n, n \in \N$ a sequence of random variables. Let $1 \le p < q < \infty$. Then \begin{figure}[H] \centering \begin{tikzpicture} \node at (0,1.5) (as) { $X_n \xrightarrow{\text{a.s.}} X$}; \node at (1.5,0) (p) { $X_n \xrightarrow{\bP} X$}; \node at (1.5,-1.5) (w) { $X_n \xrightarrow{\text{d}} X$}; %\node at (3,1.5) (L1) { $X_n \xrightarrow{L^1} X$}; \node at (3,1.5) (Lp) { $X_n \xrightarrow{L^p} X$}; \node at (3,3) (Lq) { $X_n \xrightarrow{L^q} X$}; \draw[double equal sign distance, -implies] (as) -- (p); \draw[double equal sign distance, -implies] (p) -- (w); % \draw[double equal sign distance, -implies] (L1) -- (p); % \draw[double equal sign distance, -implies] (Lp) -- (L1); \draw[double equal sign distance, -implies] (Lp) -- (p); \draw[double equal sign distance, -implies] (Lq) -- (Lp); \end{tikzpicture} \end{figure} and none of the other implications hold (apart from the transitive closure). \end{theorem} \begin{refproof}{thm:convergenceimplications} \begin{claim} $X_n \xrightarrow{\text{a.s.}} X \implies X_n \xrightarrow{\bP} X$. \end{claim} \begin{subproof} Let $\Omega_0 \coloneqq \{\omega \in \Omega : \lim_{n\to \infty} X_n(\omega) = X(\omega)\}$. Fix some $\epsilon > 0$ and consider $A_n \coloneqq \bigcup_{m \ge n} \{\omega \in \Omega: |X_m(\omega) - X(\omega)| > \epsilon\}$. Then $A_n \supseteq A_{n+1} \supseteq \ldots$ Define $A \coloneqq \bigcap_{n \in \N} A_n$. Then $\bP[A_n] \xrightarrow{n\to \infty} \bP[A]$. Since $X_n \xrightarrow{a.s.} X$ we have that \[\forall \omega \in \Omega_0 .~ \exists n \in \N .~ \forall m \ge n.~ |X_m(\omega) - X(\omega)| < \epsilon.\] We have $A \subseteq \Omega_0^{c}$, hence $\bP[A_n] \to 0$. Thus \[ \bP[\{\omega \in \Omega | ~|X_n(\omega) - X(\omega)| > \epsilon\}] < \bP[A_n] \to 0. \] \end{subproof} \begin{claim} Let $1 \le p < q < \infty$. Then $X_n \xrightarrow{L^q} X \implies X_n \xrightarrow{L^p} X$. \end{claim} \begin{subproof} Take $r$ such that $\frac{1}{p} = \frac{1}{q} + \frac{1}{r}$. We have \begin{IEEEeqnarray*}{rCl} \|X_n - X\|_{L^p} &=& \|1 \cdot (X_n - X)\|_{L^p}\\ &\overset{\text{Hölder}}{\le}& \|1\|_{L^r} \|X_n - X\|_{L^q}\\ &=& \|X_n - X\|_{L^q} \end{IEEEeqnarray*} Hence $\bE[|X_n - X|^q] \xrightarrow{n\to \infty} 0 \implies \bE[|X_n - X|^p] \xrightarrow{n\to \infty} 0$. \end{subproof} \begin{claim} \label{claim:convimpll1p} $X_n \xrightarrow{L^1} X \implies X_n\xrightarrow{\bP} X$. \end{claim} \begin{subproof} Suppose $\bE[|X_n - X|] \to 0$. Then for every $\epsilon > 0$ \begin{IEEEeqnarray*}{rCl} \bP[|X_n - X| \ge \epsilon] &\overset{\text{Markov}}{\le}& \frac{\bE[|X_n - X|]}{\epsilon}\\ &\xrightarrow{n \to \infty} & 0, \end{IEEEeqnarray*} hence $X_n \xrightarrow{\bP} X$. \end{subproof} \begin{claim} %+ $X_n \xrightarrow{\bP} X \implies X_n \xrightarrow{\text{d}} X$. \end{claim} \begin{subproof} Let $F$ be the distribution function of $X$ and $(F_n)_n$ the distribution functions of $(X_n)_n$. By \yaref{lec10_thm1} it suffices to show that $F_n(t) \to F(t)$ for all continuity points $t$ of $F$. Let $t$ be a continuity point of $F$. Take some $\epsilon > 0$. Then there exists $\delta > 0$ such that $|F(t) - F(t')| < \frac{\epsilon}{2}$ for all $t'$ with $|t - t'| \le \delta$. For all $n$ large enough, we have $\bP[|X_n - X| > \delta] < \frac{\epsilon}{2}$. It is \begin{IEEEeqnarray*}{rCl} |F_n(t) - F(t)| &=& |\bP[X_n \le t] - F(t)|\\ &\le& \max(|\frac{\epsilon}{2} + \bP[X \le t + \delta] - F(t)|, |\bP[X \le t -\delta] - F(t)|)\\ &\le& \max(|\frac{\epsilon}{2} + F(t + \delta) - F(t)|, |F(t-\delta) -F(t)|)\\ &\le& \epsilon, \end{IEEEeqnarray*} hence $F_n(t) \to F(t)$. \end{subproof} \begin{claim} \label{claim:convimplpl1} $X_n \xrightarrow{\bP} X \notimplies X_n\xrightarrow{L^1} X$.% \footnote{Note that the implication holds under certain assumptions, see \yaref{thm:l1iffuip}.} \end{claim} \begin{subproof} Take $([0,1], \cB([0,1 ]), \lambda)$ and define $X_n \coloneqq n \One_{[0, \frac{1}{n}]}$. We have $\bP[|X_n| > \epsilon] = \frac{1}{n}$ for $n$ large enough. However $\bE[|X_n|] = 1$. \end{subproof} \begin{claim} $X_n \xrightarrow{\text{a.s.}} X \notimplies X_n\xrightarrow{L^1} X$. \end{claim} \begin{subproof} We can use the same counterexample as in \yaref{claim:convimplpl1} $\bP[\lim_{n \to \infty} X_n = 0] \ge \bP[X_n = 0] = 1 - \frac{1}{n} \to 0$. We have already seen, that $X_n$ does not converge in $L_1$. \end{subproof} \begin{claim} $X_n \xrightarrow{L^1} X \notimplies X_n\xrightarrow{\text{a.s.}} X$. \end{claim} \begin{subproof} Take $\Omega = [0,1], \cF = \cB([0,1]), \bP = \lambda$. Define $A_n \coloneqq [j 2^{-k}, (j+1) 2^{-k}]$ where $n = 2^k + j$. We have \[ \bE[|X_n|] = \int_{\Omega}|X_n| \dif\bP = \frac{1}{2^k} \to 0. \] However $X_n$ does not converge a.s.~as for all $\omega \in [0,1]$ the sequence $X_n(\omega)$ takes the values $0$ and $1$ infinitely often. \end{subproof} \begin{claim} $X_n \xrightarrow{\text{d}} X \notimplies X_n \xrightarrow{\bP} X$. \end{claim} \begin{subproof} Note that $X_n \xrightarrow{\text{d}} X$ only makes a statement about the distributions of $X$ and $X_1,X_2,\ldots$ For example, take some $p \in (0,1)$ and let $X$, $X_1, X_2,\ldots$ be i.i.d.~with $X \sim \Bin(1,p)$. Trivially $X_n \xrightarrow{\text{d}} X$. However \[ \bP[|X_n - X| = 1] = \bP[X_n = 0]\bP[X = 1] + \bP[X_n = 1]\bP[X = 0] = 2p(1-p). \] \end{subproof} \begin{claim} Let $1 \le p < q < \infty$. Then $X_n \xrightarrow{L^p} X \notimplies X_n \xrightarrow{L^q} X$. \end{claim} \begin{subproof} Consider $\Omega = [0,1]$, $\cF = \cB([0,1])$, $\bP = \lambda\upharpoonright [0,1]$ and $X_n(\omega) = \frac{1}{n \sqrt[q]{\omega}}$. Then $\|X_0(\omega)\|_{L^p} < \infty$, since $p < q$. Thus $X_n \xrightarrow{L_p} 0$. However $\|X_n(\omega)\|_{L^q} = \infty$ for all $n$. \end{subproof} \end{refproof} \begin{theorem}[Bounded convergence theorem] \yalabel{Bounded Convergence Theorem}{Bounded convergence}{thm:boundedconvergence} Suppose that $X_n \xrightarrow{\bP} X$ and there exists some $K$ such that $|X_n| \le K$ for all $n$. Then $X_n \xrightarrow{L^1} X$. \end{theorem} \begin{proof} Note that $|X| \le K$ a.s.~since \[\bP[|X| \ge K + \epsilon] \le \bP[|X_n - X| > \epsilon] \xrightarrow{n \to \infty} 0.\] Hence \begin{IEEEeqnarray*}{rCl} \int |X_n - X| \dif \bP &\le& \int_{|X_n - X| \ge \epsilon} |X_n - X| \dif \bP + \epsilon\\ &\le &2K\bP[|X_n - X| \ge \epsilon] +\epsilon. \end{IEEEeqnarray*} \end{proof} \subsection{Some Facts from Measure Theory} \begin{fact}+[Finite measures are {\vocab[Measure]{regular}}, Exercise 3.1] Let $\mu$ be a finite measure on $(\R, \cB(\R))$. Then for all $\epsilon > 0$, there exists a compact set $K \in \cB(\R)$ such that $\mu(K) > \mu(\R) - \epsilon$. \end{fact} \begin{proof} We have $[-k,k] \uparrow \R$, hence $\mu([-k,k]) \uparrow \mu(\R)$. \end{proof} \begin{theorem}+[Change of variables formula] Let $X$ be a random variable with a continuous density $f$, and let $g: \R \to \R$ be continuous such that $g(X)$ is integrable. Then \[ \bE[g(X)] = \int g \circ X \dif \bP = \int_{-\infty}^\infty g(y) f(y) \lambda(\dif y) = \int_{-\infty}^\infty g(y) f(y) \dif y. \] \end{theorem} \begin{theorem}+[Riemann-Lebesgue] %\footnote{see exercise 3.3} \yalabel{Riemann-Lebesgue}{Riemann-Lebesgue}{riemann-lebesgue} Let $f: \R \to \R$ be integrable. Then \[ \lim_{n \to \infty} \int_{\R} f(x) \cos(n x) \lambda(\dif x) = 0. \] \end{theorem} \begin{theorem}+[Fubini-Tonelli] \yalabel{Fubuni-Tonelli}{Fubini}{thm:fubini} %\footnote{exercise sheet 1} Let $(\Omega_{i}, \cF_i, \bP_i), i \in \{0,1\}$ be probability spaces and $\Omega \coloneqq \Omega_0 \otimes \Omega_1$, $\cF \coloneqq \cF_1 \otimes\cF_2$, $\bP \coloneqq \bP_0 \otimes \bP_1$. Let $f \ge 0$ be $(\Omega, \cF)$-measurable, then \[ \Omega_0 \ni x \mapsto \int_{\Omega_{2}} f(x,y) \bP_2(\dif y) \] and \[ \Omega_1 \ni y \mapsto \int_{\Omega_1} f(x,y) \bP_1(\dif x) \] are measurable, and \[ \int f \dif \bP = \int_{\Omega_1} \int_{\Omega_2} f(x,y) \bP_2(\dif y) \bP_1(\dif x)(\dif x) = \int_{\Omega_2} \int_{\Omega_1} f(x,y) \bP_1(\dif x) \bP_2(\dif y). \] \end{theorem} \subsection{Inequalities} This is taken from section 6.1 of the notes on Stochastik. \begin{theorem}[Markov's inequality] \yalabel{Markov's Inequality}{Markov}{thm:markov} Let $X$ be a random variable and $a > 0$. Then \[ \bP[|X| \ge a] \le \frac{\bE[|X|]}{a}. \] \end{theorem} \begin{proof} We have \begin{IEEEeqnarray*}{rCl} \bE[|X|] &\ge & \int_{|X| \ge a} |X| \dif \bP\\ &=& a \int_{|X| \ge a} \dif \bP = a\bP[|X| \ge a]. \end{IEEEeqnarray*} \end{proof} \begin{theorem}[Chebyshev's inequality] \yalabel{Chebyshev's Inequality}{Chebyshev}{thm:chebyshev} Let $X$ be a random variable and $a > 0$. Then \[ \bP[|X - \bE(X)| \ge a] \le \frac{\Var(X)}{a^2}. \] \end{theorem} \begin{proof} We have \begin{IEEEeqnarray*}{rCl} \bP[|X-\bE(X)| \ge a] &=& \bP[|X - \bE(X)|^2 \ge a^2]\\ &\overset{\yaref{thm:markov}}{\le}& \frac{\bE[|X - \bE(X)|^2]}{a^2}. \end{IEEEeqnarray*} \end{proof} How do we prove that something happens almost surely? The first thing that should come to mind is: \begin{lemma}[Borel-Cantelli] \yalabel{Borel-Cantelli}{Borel-Cantelli}{thm:borelcantelli} If we have a sequence of events $(A_n)_{n \ge 1}$ such that $\sum_{n \ge 1} \bP(A_n) < \infty$, then $\bP[ A_n \text{for infinitely many $n$}] = 0$ (more precisely: $\bP[\limsup_{n \to \infty} A_n] = 0$). For independent events $A_n$ the converse holds as well. \end{lemma}