\documentclass[12pt]{article}

\usepackage{hyperref}
\hypersetup{
  linkcolor  = blue,
  citecolor  = green,
  urlcolor   = orange,
  colorlinks = true,
}

\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amsthm}
\usepackage{bbold}
\usepackage{bm}
\usepackage{colonequals}
\usepackage[dvips,letterpaper,margin=1in]{geometry}
\let\digamma\relax
\usepackage[lucidasmallscale=true]{lucimatx}
\usepackage{tikz}

\definecolor{clightgray}{rgb}{0.6,0.6,0.6}
\newcommand{\hint}[1]{\textcolor{clightgray}{(\textsc{\textbf{Hint:}} #1)}}

\theoremstyle{definition}
\newtheorem{outproblem}{Problem}[]
\theoremstyle{plain}

\renewcommand{\AA}{\mathbb{A}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\renewcommand{\SS}{\mathbb{S}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\ZZ}{\mathbb{Z}}
\DeclareSymbolFont{bbold}{U}{bbold}{m}{n}
\DeclareSymbolFontAlphabet{\mathbbold}{bbold}
\newcommand{\One}{\mathbbold{1}}

\newcommand{\RP}{\RR\mathrm{P}}
\newcommand{\CP}{\CC\mathrm{P}}

\newcommand{\ba}{\bm a}
\newcommand{\bb}{\bm b}
\newcommand{\bc}{\bm c}
\newcommand{\bd}{\bm d}
\newcommand{\be}{\bm e}
\newcommand{\bg}{\bm g}
\newcommand{\bh}{\bm h}
\newcommand{\bi}{\bm i}
\newcommand{\bj}{\bm j}
\newcommand{\bk}{\bm k}
\newcommand{\bbm}{\bm m}
\newcommand{\bp}{\bm p}
\newcommand{\bq}{\bm q}
\newcommand{\br}{\bm r}
\newcommand{\bs}{\bm s}
\newcommand{\bt}{\bm t}
\newcommand{\bu}{\bm u}
\newcommand{\bv}{\bm v}
\newcommand{\bw}{\bm w}
\newcommand{\bx}{\bm x}
\newcommand{\by}{\bm y}
\newcommand{\bz}{\bm z}

\newcommand{\bA}{\bm A}
\newcommand{\bB}{\bm B}
\newcommand{\bC}{\bm C}
\newcommand{\bD}{\bm D}
\newcommand{\bE}{\bm E}
\newcommand{\bF}{\bm F}
\newcommand{\bG}{\bm G}
\newcommand{\bH}{\bm H}
\newcommand{\bI}{\bm I}
\newcommand{\bJ}{\bm J}
\newcommand{\bL}{\bm L}
\newcommand{\bM}{\bm M}
\newcommand{\bN}{\bm N}
\newcommand{\bP}{\bm P}
\newcommand{\bQ}{\bm Q}
\newcommand{\bR}{\bm R}
\newcommand{\bS}{\bm S}
\newcommand{\bT}{\bm T}
\newcommand{\bU}{\bm U}
\newcommand{\bV}{\bm V}
\newcommand{\bW}{\bm W}
\newcommand{\bX}{\bm X}
\newcommand{\bY}{\bm Y}
\newcommand{\bZ}{\bm Z}

\newcommand{\zero}{\bm{0}}
\newcommand{\one}{\bm{1}}

\newcommand{\balpha}{\boldsymbol{\alpha}}
\newcommand{\bbeta}{\boldsymbol{\beta}}
\newcommand{\bdelta}{\boldsymbol{\delta}}
\newcommand{\bepsilon}{\boldsymbol{\eps}}
\newcommand{\blambda}{\boldsymbol{\lambda}}
\newcommand{\bomega}{\boldsymbol{\omega}}
\newcommand{\bpi}{\boldsymbol{\pi}}
\newcommand{\bmmu}{\boldsymbol{\mu}}
\newcommand{\bmu}{\bm\mu}
\newcommand{\bnu}{\boldsymbol{\nu}}
\newcommand{\bphi}{\boldsymbol{\phi}}
\newcommand{\bvphi}{\boldsymbol{\varphi}}
\newcommand{\bpsi}{\boldsymbol{\psi}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\btheta}{\boldsymbol{\theta}}
\newcommand{\bzeta}{\boldsymbol{\zeta}}
\newcommand{\bxi}{\boldsymbol{\xi}}

\newcommand{\bDelta}{\boldsymbol{\Delta}}
\newcommand{\bLambda}{\boldsymbol{\Lambda}}
\newcommand{\bOmega}{\boldsymbol{\Omega}}
\newcommand{\bPi}{\boldsymbol{\Pi}}
\newcommand{\bPhi}{\boldsymbol{\Phi}}
\newcommand{\bPsi}{\boldsymbol{\Psi}}
\newcommand{\bSigma}{\boldsymbol{\Sigma}}
\newcommand{\bTheta}{\boldsymbol{\Theta}}
\newcommand{\bXi}{\boldsymbol{\Xi}}

\newcommand{\sA}{\mathcal{A}}
\newcommand{\sB}{\mathcal{B}}
\newcommand{\sC}{\mathcal{C}}
\newcommand{\sD}{\mathcal{D}}
\newcommand{\sE}{\mathcal{E}}
\newcommand{\sF}{\mathcal{F}}
\newcommand{\sG}{\mathcal{G}}
\newcommand{\sH}{\mathcal{H}}
\newcommand{\sI}{\mathcal{I}}
\newcommand{\sJ}{\mathcal{J}}
\newcommand{\sK}{\mathcal{K}}
\newcommand{\sL}{\mathcal{L}}
\newcommand{\sM}{\mathcal{M}}
\newcommand{\sN}{\mathcal{N}}
\newcommand{\sO}{\mathcal{O}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\sQ}{\mathcal{Q}}
\newcommand{\sR}{\mathcal{R}}
\newcommand{\sS}{\mathcal{S}}
\newcommand{\sT}{\mathcal{T}}
\newcommand{\sU}{\mathcal{U}}
\newcommand{\sV}{\mathcal{V}}
\newcommand{\sX}{\mathcal{X}}
\newcommand{\sY}{\mathcal{Y}}

\newcommand{\fB}{\mathscr{B}}
\newcommand{\fC}{\mathscr{C}}
\newcommand{\fE}{\mathscr{E}}
\newcommand{\fH}{\mathscr{H}}
\newcommand{\fI}{\mathscr{I}}
\newcommand{\fP}{\mathscr{P}}
\newcommand{\fS}{\mathscr{S}}
\newcommand{\fV}{\mathscr{V}}

\newcommand{\fp}{\mathfrak{p}}
\newcommand{\fq}{\mathfrak{q}}
\newcommand{\fg}{\mathfrak{g}}
\newcommand{\fh}{\mathfrak{h}}
\newcommand{\fa}{\mathfrak{a}}
\newcommand{\fb}{\mathfrak{b}}
\newcommand{\fc}{\mathfrak{c}}
\newcommand{\fm}{\mathfrak{m}}
\renewcommand{\sl}{\mathfrak{sl}}
\newcommand{\so}{\mathfrak{so}}
\newcommand{\gl}{\mathfrak{gl}}
\renewcommand{\sp}{\mathfrak{sp}}

\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\softmax}{soft\,max}
\DeclareMathOperator{\Gram}{Gram}
\DeclareMathOperator{\GOE}{GOE}
\DeclareMathOperator{\sym}{sym}
\DeclareMathOperator{\Part}{Part}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\sech}{sech}
\DeclareMathOperator{\img}{img}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\Irr}{Irr}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Der}{Der}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Ind}{Ind}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\Rad}{Rad}
\DeclareMathOperator{\Unif}{Unif}
\DeclareMathOperator{\Ad}{Ad}
\DeclareMathOperator{\ad}{ad}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\supp}{supp}
\renewcommand\Re{\operatorname{Re}}
\renewcommand\Im{\operatorname{Im}}
\newcommand{\Px}{\mathop{\mathbb{P}}}
\newcommand{\Ex}{\mathop{\mathbb{E}}}
\newcommand{\Varx}{\mathop{\mathsf{Var}}}

\renewcommand{\bar}{\overline}
\newcommand{\what}{\widehat}
\newcommand{\wtil}{\widetilde}
\newcommand{\lvec}{\overrightarrow}
\newcommand{\ra}{\rangle}
\newcommand{\la}{\langle}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\veq}{\mathrel{\rotatebox{90}{$=$}}}

\newcommand{\Law}{\mathsf{Law}}
\newcommand{\Exp}{\mathsf{Exp}}



\title{Assignment 2}
\author{Probability Theory II \\ (EN.553.721, Spring 2025)}
\date{Assigned: February 14, 2025 \,\,\,\,\, Due: 11:59pm EST, February 28, 2025}

\begin{document}

\maketitle

\noindent
\textbf{Solve any four out of the five problems.} If you solve more, we will grade the first four solutions you include. Each problem is worth an equal amount towards your grade.

\vspace{1em}

\noindent
Submit solutions in \LaTeX. Write in complete sentences. Include and justify all steps of your arguments, but avoid writing excessive explanation that is not contributing to your solution.

\vspace{1em}

\noindent
Keep in mind the late submission policy: you may use a total of five late days for homework submissions over the course of the semester without penalty. If you need an extension beyond these, \emph{you must ask me 48 hours before the due date of the homework} and have an excellent reason. After you have used up these late days, further late assignments will be penalized by 20\% per day they are late.

\vspace{1em}

\noindent
We use the notation $X \in L^p$ to denote that $\EE|X|^p < \infty$ below.

\vspace{1.5em}

\begin{outproblem}[Poisson point process]
    This problem elaborates on some properties of the Poisson point process.
    All processes discussed below are in continuous time.
    \begin{enumerate}
    \item \emph{Brownian motion} is a continuous-time stochastic process $(B(t))_{t \geq 0}$ with $B(0) = 0$ almost surely and with finite distributions described in terms of their increments by, for all $0 < t_1 < \cdots < t_k$, having
        \begin{align*}
          &\Law\bigg(\big(B(t_1), B(t_2) - B(t_1), \dots, B(t_k) - B(t_{k - 1})\big)\bigg) \\
          &\hspace{1cm} = \sN(0, t_1) \otimes \sN(0, t_2 - t_1) \otimes \cdots \otimes \sN(0, t_k - t_{k - 1}).
        \end{align*}
        Take the existence of such a process for granted for this problem.
        Let $F_{\lambda} \sim \mathsf{PPP}(\lambda)$ be a sequence of Poisson processes.
        Prove that the sequence of processes $\what{F}_{\lambda}(t) \colonequals (F_{\lambda}(t) - \lambda t) / \sqrt{\lambda}$ converges in finite distributions to the Brownian motion $B(t)$ as $\lambda \to \infty$.
    \item Prove the following generalized version of the Poisson limit theorem from class.
        Let $(X_{i, n})_{1 \leq i \leq n}$ be independent random variables such that $X_{1, n}, \dots, X_{n, n}$ are i.i.d.\ for each $n$ (but not for different $n$).
        Suppose that $n \cdot \PP[X_{1, n} \notin \{0, 1\}] \to 0$ as $n \to \infty$, and that $n \cdot \PP[X_{1, n} = 1] \to \lambda \in (0, \infty)$.
        Show that $S_n \colonequals \sum_{i = 1}^n X_{i, n} \Rightarrow \mathsf{Pois}(\lambda)$.

        \hint{Argue that this may be reduced to the version from class.}
    \item Suppose that $(F(t))_{t \geq 0}$ is a counting process satisfying the following properties:
        \begin{itemize}
        \item \emph{Initial Condition:} $F(0) = 0$ almost surely.
        \item \emph{Stationarity:} For any $\delta > 0$, the law of $F(t + \delta) - F(t)$ is the same for all $t \geq 0$.
        \item \emph{Independence:} For any $0 < t_1 < \cdots < t_k$, the random variables $F(t_1), F(t_2) - F(t_1), \dots, F(t_k) - F(t_{k - 1})$ are mutually independent.
        \item \emph{Rate of Events:} $\lim_{\delta \to 0^+} \frac{1}{\delta} \PP[F(\delta) = 1] = \lambda \in (0, \infty)$.
        \item \emph{Isolation of Events:} $\lim_{\delta \to 0^+}\frac{1}{\delta}\PP[F(\delta) \geq 2] = 0$.
        \end{itemize}
        Show that $F(t)$ has the law $\mathsf{PPP}(\lambda)$ as a stochastic process (i.e., has the same finite distributions as $\mathsf{PPP}(\lambda)$, as discussed in lecture).

        \hint{Use Part 2.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Conditional expectation]
    This problem will derive some further properties of the conditional expectation and parallels with the ordinary expectation.
    We always assume $\sG \subseteq \sF$ are $\sigma$-algebras.
    \begin{enumerate}
    \item Let $X$ be a random variable measurable with respect to $\sF$.
        Write
        \[ \Var[X \mid \sG] \colonequals \EE[(X - \EE[X \mid \sG])^2 \mid \sG]. \]
        Note that $\Var[X] = \Var[X \mid \{\emptyset, \Omega\}]$ is just the usual variance.
        Show that
        \[ \Var[X] = \EE[\Var[X \mid \sG]] + \Var[\EE[X \mid \sG]]. \]
        Make sure you are clear on why both terms on the right-hand side are well-defined scalars.
    \item For any $\sigma$-algebras $\sG_1 \subseteq \sG_2 \subseteq \sF$, show that
        \[ \EE[\Var[X \mid \sG_1]] \geq \EE[\Var[X \mid \sG_2]]. \]
    \item Show that, if $X \in L^2$ is an $\sF$-measurable random variable and $Y \in L^2$ is any $\sG$-measurable random variable, then
        \[ \EE \big(X - Y\big)^2 \geq \EE \big(X - \EE[X \mid \sG]\big)^2. \]
        Thus $Y^{*} = \EE[X \mid \sG]$ is a minimizer of the left-hand side among $\sG$-measurable random variables $Y$, giving a precise sense in which the conditional expectation is an ``optimal estimator'' of a random variable under a measurability constraint.

        \hint{Add and subtract $\EE[X \mid \sG]$ inside the parentheses on the left-hand side.}
    \item Let $X$ be a $\sF$-measurable random variable with $X \geq 0$ almost surely and $Y$ be a $\sG$-measurable random variable with $Y > 0$ almost surely.
        Prove that
        \[ \PP[X > Y \mid \sG] \leq \frac{\EE[X \mid \sG]}{Y} \text{ almost surely}. \]
        Recall that the left-hand side is defined to equal $\EE[\One{\{X > Y\}} \mid \sG]$.
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Martingales]
    All stochastic processes referred to below are in discrete time.
    \begin{enumerate}
    \item Let $(M_n)_{n \geq 0}$ be a martingale.
        Prove that $M_n$ has \emph{uncorrelated increments}: for any $0 \leq a < b \leq c < d$,
        \[ \EE[ (M_d - M_c) (M_b - M_a) ] = 0. \]
    \item Let $(S_n)_{n \geq 0}$ be the simple random walk on the integers $\ZZ$, i.e., $S_0 = 0$ and $S_n = \sum_{i = 1}^n X_i$ for $X_i \sim \Unif(\{\pm 1\})$ drawn i.i.d.
        Let $f: \ZZ \to \RR$ satisfy, for all $k \in \ZZ$,
        \[ \frac{1}{2}\big(f(k + 1) + f(k - 1)\big) \geq f(k). \]
        Show that $(f(S_n))_{n \geq 0}$ is a supermartingale, a submartingale if the inequality above is reversed, and a martingale if the inequality is an equality.
        Describe the $f$ for which the inequality is an equality.
        Note that the directions of these inequalities match what you would expect from the terms ``sub-'' and ``super-'' here.
    \item Let $(Z_n)_{n \geq 0}$ be adapted to a filtration $(\sF_n)_{n \geq 0}$ and have $Z_n \in L^1$.
        Show that there exist $(M_n)_{n \geq 0}$ and $(H_n)_{n \geq 0}$ adapted to the same filtration such that $M_n$ is a martingale (with respect to that filtration), $H_n$ is predictable (with respect to that filtration), and $Z_n = M_n + H_n$ almost surely for all $n \geq 0$.
        Further show that if $Z_n$ is a submartingale, then we may take $H_n$ to be almost surely non-decreasing (i.e., for any $i \geq 0$, $H_{i + 1} - H_i \geq 0$ almost surely).
    \item Construct a martingale $(M_n)_{n \geq 0}$ such that $M_n \to +\infty$ almost surely.

        \hint{Consider a sum of independent but not i.i.d.\ random variables.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Distributional distances]
    This problem will show you a few different useful ways of measuring the distance between probability measures.
    In all cases, let $(\Omega, \sF)$ be a measurable space and $\mu, \nu$ and $\mu_m, \nu_n$ for $m, n \geq 1$ probability measures on it.
    \begin{enumerate}
    \item Let
        \[ d_1(\mu, \nu) \colonequals \sup_{A \in \sF} |\mu(A) - \nu(A)|. \]
        Show that $d_1$ is a metric on the set of probability measures on the measurable space above.
        Show also that if $d_1(\mu_n, \mu) \to 0$ as $n \to \infty$ then $\mu_n \to \mu$ weakly, but that the converse is not always true.
    \item Suppose that $\nu \ll \mu$, so that the Radon-Nikodym derivative $\frac{d\nu}{d\mu} \geq 0$ is defined.
        Show that
        \[ d_1(\mu, \nu) \leq \int \left|\frac{d\nu}{d\mu} - 1\right|d\mu. \]
    \item Again supposing $\nu \ll \mu$, let
        \[ d_2(\mu, \nu) \colonequals \sqrt{\int \left(\sqrt{\frac{d\nu}{d\mu}} - 1\right)^2d\mu}. \]
        Show that, for all $\nu \ll \mu$,
        \[ \frac{1}{2} d_2(\mu, \nu)^2 \leq d_1(\mu, \nu) \leq d_2(\mu, \nu). \]
    \item Show the following inequalities:
        \begin{align*}
          d_1(\mu_1 \otimes \mu_2, \nu_1 \otimes \nu_2) &\leq d_1(\mu_1, \nu_1) + d_1(\mu_2, \nu_2), \\
          d_2(\mu_1 \otimes \mu_2, \nu_1 \otimes \nu_2)^2 &\leq d_2(\mu_1, \nu_1)^2 + d_2(\mu_2, \nu_2)^2.
        \end{align*}
        \hint{Show the second inequality first.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Gaussian vectors]
    A \emph{Gaussian random vector} is, for $\bm\Sigma \in \RR^{d \times d}$ a positive definite symmetric matrix and $\bm\mu \in \RR^d$ a vector, the random vector $\bX = (X_1, \dots, X_d)$ whose density over $\RR^d$ is given by
    \[ \rho(\bx) = \frac{1}{\sqrt{\det(2\pi \bm\Sigma)}} \exp\left(-\frac{1}{2} (\bx - \bm \mu)^{\top} \bm\Sigma^{-1}(\bx - \bm \mu)\right). \]
    There is also a sensible definition when $\bm\Sigma$ is only positive semidefinite and therefore not invertible, but we will omit that case here.
    You may assume all covariance matrices encountered below are invertible.
    You should already know and can use without proof the following properties of Gaussian random vectors:
    \begin{itemize}
    \item In the above setting, $\EE \bX = \bm\mu$ and $\Cov(\bX) \colonequals \EE (\bX - \bm\mu)(\bX - \bm\mu)^{\top} = \bm\Sigma$.
    \item If $\bX \sim \sN(\bm\mu, \bm\Sigma)$ and $\bX^{\prime} \sim \sN(\bm \mu^{\prime}, \bm\Sigma^{\prime})$ are independent Gaussian random vectors, then $\Law(\bX + \bX^{\prime}) = \sN(\bm\mu + \bm\mu^{\prime}, \bm\Sigma + \bm\Sigma^{\prime})$.
    \item If $\bX$ is as above and $\bM \in \RR^{d^{\prime} \times d}$, then $\Law(\bM\bX) = \sN(\bM\bm \mu, \bM\bm\Sigma \bM^{\top})$.
    \end{itemize}
    Using these results, show the following.
    \begin{enumerate}
    \item Suppose $(X_1, \dots, X_a, Y_1, \dots, Y_b) \sim \sN(\bm\mu, \bm\Sigma)$.
        Further, suppose that $\Cov(X_i, Y_j) = 0$ for all $i \in [a], j \in [b]$.
        Show that $(X_1, \dots, X_a)$ and $(Y_1, \dots, Y_b)$ are independent.
    \item In the above setting, let $\bX = (X_1, \dots, X_a)$ and $\bY = (Y_1, \dots, Y_b)$.
        Suppose that, according to this same partition, $\bm\Sigma$ has a block structure
        \[ \bm\Sigma = \left[\begin{array}{cc} \bA & \bB^{\top} \\ \bB & \bC \end{array}\right]. \]
        Describe, in terms only of $\bA, \bB, \bC$, a matrix $\bR$ such that $\bZ \colonequals \bX - \bR \bY$ is independent of $\bY$.
        This $\bZ$ is a Gaussian random vector; compute its mean and covariance.
    \item For a bounded measurable function $f: \RR \to \RR$, write an expression for the random variable $\EE[f(\bX) \mid \bY]$ that holds almost surely and only involves the function $f$, the matrices $\bA, \bB, \bC$, the vector $\bm\mu$, and the vector $\bY$.
    \item Consider the two-dimensional case $a = b = 1$, where $(X, Y) \sim \sN(\bm\mu, \bm\Sigma)$ with $\bm \mu \in \RR^2$ and $\bm\Sigma \in \RR^{2 \times 2}$ symmetric and positive definite.
        Show that the conditional variance $\Var[X \mid Y] = \EE[(X - \EE[X \mid Y])^2 \mid Y]$ is a constant (almost surely), not depending on $Y$.
        Give a formula for this constant in terms of $\bm \mu$ and $\bm\Sigma$.
    \end{enumerate}
\end{outproblem}

\end{document}
