\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{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 1}
\author{Probability Theory II \\ (EN.553.721, Spring 2025)}
\date{Assigned: January 29, 2025 \,\,\,\,\, Due: 11:59pm EST, February 10, 2025}

\begin{document}

\maketitle

\noindent
\textbf{Solve any three out of the four problems.} If you solve more, we will grade the first three 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
A few problems below involve the \emph{exponential} probability measure.
This, denoted $\Exp(\lambda)$, is the measure with density $\rho(x) = \One\{x \geq 0\} \lambda \exp(-\lambda x)$.
We will see it soon in lecture.

\vspace{1.5em}

\begin{outproblem}[Law of large numbers]
    This problem clarifies some details surrounding the weak law of large numbers (WLLN) as well as convergence in probability more generally.
    \begin{enumerate}
    \item Call a probability measure $\mu$ on $\RR$ (endowed with the Borel $\sigma$-algebra) \emph{deterministic} if, for all measurable $A$, we have $\mu(A) \in \{0, 1\}$.
        Show that $\mu$ is deterministic if and only if $\mu = \delta_x$ for some $x \in \RR$, i.e., if and only if $\mu(A) = \One\{x \in A\}$ for all measurable $A$.
    \item Let $X_1, X_2, \ldots \in \RR$ be random variables and $c \in \RR$ a constant.
        Show that $X_n \to c$ in probability if and only if $X_n \Rightarrow c$ in distribution.
    \item Let $\mu$ be the probability measure on $\RR$ with density $\rho(x) = \One\{x \geq 0\} \frac{2}{\pi(1 + x^2)}$.
        Show that, if $X_1, X_2, \ldots \sim \mu$ are i.i.d., then $\EE|X_i| = \infty$, and also that $\liminf_{n \to \infty} \PP[\frac{1}{n}\sum_{i = 1}^n X_i > K] > 0$ for any fixed $K > 0$.
        Conclude that the WLLN does not apply to these random variables, in the sense that $\frac{1}{n}\sum_{i = 1}^n X_i$ does not converge in probability to any deterministic $c \in \RR$.

        \hint{Consider the probability that one of the $X_i$ is greater than $Kn$.}
    \item Let $Z \colonequals \sum_{k = 2}^{\infty} \frac{1}{k^2\log k} < \infty$.
        Let $\mu$ be the probability measure on $\ZZ$ assigning probability masses $\mu(\{(-1)^k k\}) = \frac{1}{Z} \cdot \frac{1}{k^2\log k}$ for each $k \geq 2$ and $\mu(\{\ell\}) = 0$ for all other $\ell \in \ZZ$ not of the form $(-1)^k k$ for some $k \geq 2$.
        Let $X_1, X_2, \ldots \sim \mu$ be i.i.d.
        Prove that $\EE|X_i| = \infty$, and yet that there is a constant $c \in \RR$ such that $\frac{1}{n}\sum_{i = 1}^n X_i \to c$ in probability, whereby the assumption $\EE|X_i| < \infty$ in the WLLN is not always necessary.

        \hint{You may either follow the truncation proof of the WLLN, or use characteristic functions and Part 2. In the latter case, you may use the Taylor series estimate on the function $t \mapsto \exp(it)$ given in Klenke, Lemma 15.31, and you should expand the characteristic function of $X_i$ as a series in $k$ and truncate it appropriately.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Stirling's asymptotic]
    In this problem, you will show that the central limit theorem (CLT) implies Stirling's approximation for the factorial (a purely deterministic statement!).
    Let $X_1, \dots, X_n \sim \Exp(1)$ be i.i.d.\ and let $S_n \colonequals \sum_{i = 1}^n X_i$.
    \begin{enumerate}
    \item Show that $\EE X_i = 1$.
    \item Show that, for each $n \geq 1$, $S_n$ has density
        \[ \rho_n(x) = \One\{x \geq 0\} \frac{1}{(n - 1)!} x^{n - 1} \exp(-x) . \]
        \hint{Use induction to compute the integrals involved.}
    \item Show that
        \[ \EE \left|\frac{S_n - n}{\sqrt{n}}\right| = \frac{2\exp(-n) n^{n + 1/2}}{n!}. \]
        \hint{Use the density of $S_n$ from Part 2 to write the expectation as an integral. Split the integral into two parts to handle the absolute value appearing. Then, use integration by parts. You should be able to avoid actually computing any complicated-looking integrals.}
    \item Use the CLT applied to the $X_i$ to conclude that
        \[ \lim_{n \to \infty} \frac{n!}{\sqrt{2\pi}\exp(-n) n^{n + 1/2}} = 1. \]
      You may use without proof that, in this situation, the CLT implies that $\EE |\frac{S_n - n}{\sqrt{n}}| \to \EE_{N \sim \sN(0, 1)} |N|$, even though \emph{a priori} the test function $f(x) = |x|$ cannot be used in the CLT. We will soon see some concentration inequalities that make this easy to deduce from the kind of CLT we have seen so far.
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Central limit theorems]
    This problem clarifies a few details concerning the CLT we have seen in class.
    \begin{enumerate}
    \item Suppose $X_1, X_2, \ldots$ are i.i.d.\ satisfying $\EE X_i = 0$ and $\EE X_i^2 = 1$.
        Show that there does not exist a random variable $Z$ such that $\what{S}_n \colonequals \frac{1}{\sqrt{n}} \sum_{i = 1}^n X_i \to Z$ in probability.
        Explain why this does not contradict the CLT.

        \hint{Show that, if this convergence did happen, then $\what{S}_{2n} - \what{S}_n \to 0$ in probability. Derive a contradiction by showing that this expression must instead converge in distribution to a (non-trivial) Gaussian random variable.}
    \item Show that there exists $c > 0$ such that the following holds for arbitrarily large $n$.
        Let $X_1, \dots, X_n \sim \Unif(\{\pm 1\})$ and $N \sim \sN(0, 1)$.
        Then,
        \[ \left|\PP\left[\frac{1}{\sqrt{n}}\sum_{i = 1}^n X_i \leq 0\right] - \PP[N \leq 0]\right| \geq \frac{c}{\sqrt{n}}. \]
        This shows that the error bound of the Berry-Ess\'{e}en theorem is tight in general.
        You may use Stirling's asymptotic from Problem 2 even if you did not choose that problem to solve.

        \hint{Consider even $n$.}
    \item Construct a triangular array $(X_{i, n})_{1 \leq i \leq n}$ of independent but not identically distributed random variables with $\EE X_{i, n} = 0$, $\EE X_{i, n}^2 = 1$, and yet such that $\frac{1}{\sqrt{n}}\sum_{i = 1}^n X_{i, n}$ does not converge in distribution to $\sN(0, 1)$.
        Your example shows that some further condition (such as Lindeberg's condition) is needed in a statement like the Lindeberg CLT.

        \hint{Use the Poisson limit theorem.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Extreme value theory]
    Let $X_1, X_2, \ldots$ be i.i.d.\ random variables (with law specified in the parts below)
    and write $M_n \colonequals \max_{i = 1}^n X_i$.
    As a general hint, in all cases, look for a formula for $\PP[M_n \leq t]$.
    \begin{enumerate}
    \item Suppose $X_i \sim \Unif([0, 1])$.
        Show that $n (1 - M_n) \Rightarrow M$, where $\Law(M) = \Exp(1)$.
    \item Suppose $X_i \sim \Exp(1)$.
        Show that $(M_n - \log n) \Rightarrow M$, where $M$ is a random variable with density $\exp(-x - \exp(-x))$ (the nested exponential is not a typo, and the density is over all $x \in \RR$, not just non-negative $x$).
    \item This problem is in a different setting, preparing for the last part. Show that, if $N \sim \sN(0, 1)$, then, for any $t \geq 0$,
        \[ \PP[N \geq t] \leq \frac{1}{2}\exp\left(-\frac{t^2}{2}\right). \]
        \hint{Write out the integral, change variables to make it an integral from $0$ to $\infty$, and expand the square.}
    \item Suppose in the original setting that $X_i \sim \sN(0, 1)$. Using Part 3, show that, for any $\epsilon > 0$,
        \[ \lim_{n \to \infty}\PP[M_n \leq \sqrt{(2 + \epsilon) \log n}] = 1. \]
        You do not need to prove the other side here, but you should know and remember forever that, in this case, $M_n / \sqrt{2\log n} \to 1$ in probability.
    \end{enumerate}
\end{outproblem}

\end{document}
