\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 3}
\author{Probability Theory II \\ (EN.553.721, Spring 2025)}
\date{Assigned: March 6, 2025 \,\,\,\,\, Due: 11:59pm EST, March 17, 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
For some of these problems, you might find it useful to watch the recorded lectures on martingales if you haven't yet.

\vspace{1.5em}

\begin{outproblem}[Martingales for random walks]
    Let $X_i \sim \Unif(\{\pm 1\})$ be i.i.d., and let $S_n = \sum_{i = 1}^n X_i$ with $S_0 = 0$ be the usual simple random walk.
    \begin{enumerate}
    \item Let $T \colonequals \min\{n: S_n = a\}$ be the hitting time of some $a > 0$. Using the optional stopping theorem, show that $\EE T = \infty$.
    \item Using Doob's martingale convergence theorem, show that $T < \infty$ almost surely.

        \hint{Rephrase this conclusion as the convergence almost surely of a suitable martingale.}
    \item Let $\lambda \in \RR$ and
        \[ M_n \colonequals \frac{\exp(\lambda S_n)}{\cosh(\lambda)^n}. \]
        Show that $M_n$ is a martingale.
    \item Using the optional stopping theorem, derive a formula for $f(z) = \EE z^{T}$ valid for all $0 \leq z \leq 1$.
        Note that, by our recent discussion in class, the Taylor series expansion of this function contains the values of $\PP[T = k]$ for all $k \geq 0$.
        (You are not required to derive these.)
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Time to observe a sequence]
    Let $a_1, \dots, a_N \in \{0, 1\}$ be fixed, and let $X_1, X_2, \ldots \sim \Unif(\{0, 1\})$ be i.i.d.\ random variables.
    In this problem, you will study the time required to see the sequence $(a_1, \dots, a_N)$ in the random sequence $(X_1, X_2, \dots)$:
    \[ T \colonequals \min\{n: n \geq N, X_n = a_N, X_{n - 1} = a_{N - 1}, \dots, X_{n - N + 1} = a_1\}. \]
    Consider a Casino where a countable number of Gamblers $1, 2, \dots$ bet on the outcome of the $X_n$ at each time $n$.
    Gambler $i$ bets $B_{i, n, 0}$ on the outcome being $X_n = 0$ at time $n$, and $B_{i, n, 1}$ on the outcome being $X_n = 1$ at time $n$.
    At each time $n$, almost surely only a finite number of the Gamblers make a non-zero bet.
    If $X_n = 0$, then the Casino's fortune increases by $B_{i, n, 1}$ for each $i$ and decreases by $B_{i,n, 0}$ for each $i$, and Gambler $i$'s fortune increases by $B_{i, n, 0}$ and decreases by $B_{i, n, 1}$; if $X_n = 1$, the same happens with 0 and 1 switched.
    Write $(G_{i, n})_{n \geq 0}$ for the fortune of Gambler $i$ at each time.
    \begin{enumerate}
    \item
        Suppose that the processes $(B_{i, n, s})_{n}$ for each $i \geq 1$, $s \in \{0, 1\}$ are predictable with respect to the $\sigma$-algebra $\sF_n = \sigma(X_1, \dots, X_n)$.
        Define the net profit of the Casino from the bets made at time $n$ as:
        \begin{align*}
          Y_0 &\colonequals 0, \\
          Y_n &\colonequals \sum_{i \geq 1} \One\{X_n = 0\} (B_{i, n, 1} - B_{i, n, 0}) + \sum_{i \geq 1} \One\{X_n = 1\} (B_{i, n, 0} - B_{i, n, 1}).
        \end{align*}
        Define the net profit up to time $n$ as:
        \[ M_n \colonequals \sum_{j = 1}^n Y_j. \]
        Show that $M_n$ is a martingale.
    \item The Gamblers play strategies similar to but slightly different from the martingale betting strategy from class.
        Each Gambler starts with a fortune of $G_{i, 0} = 1$.
        Gambler 1 bets all of their money on $X_i = a_i$, until either losing and stopping or leaving with a fortune of $2^N$:
        \[ B_{1, n, s} \colonequals \One\{1 \leq n \leq N, X_1 = a_1, \dots, X_{n - 1} = a_{n - 1}, s = a_n\} \cdot 2^{n - 1}. \]
        The other Gamblers $j \geq 2$ play the same strategy, but starting at time $j$:
        \[ B_{j, n, s} \colonequals \One\{j \leq n \leq N + j - 1, X_{j} = a_1, \dots, X_{j + n - 2} = a_{n - 1}, s = a_n\} \cdot 2^{n - j}. \]
        Suppose that $N = 2$ and $(a_1, a_2) = (0, 1)$.
        Give a formula for the value of $M_T$ in terms of $T$ for each $T \geq 2$.
        Compute $\EE[M_T]$ using the optional stopping theorem.
        Use that to compute $\EE[T]$.
    \item Repeat Part 2 for $N = 6$ and $(a_1, a_2, a_3, a_4, a_5, a_6) = (1, 1, 0, 0, 1, 1)$.
    \item Describe a general formula for $\EE[T]$ in terms of $(a_1, \dots, a_N)$. For a given length $N$, find a sequence that makes $\EE[T]$ as large as possible and another that makes $\EE[T]$ as small as possible.
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Product martingales]
    Let $X_1, X_2, \dots$ be independent random variables such that $X_i \geq 0$ almost surely and $\EE X_i = 1$ for all $i$.
    We have seen that
    \begin{align*}
      M_0 &\colonequals 1, \\
      M_n &\colonequals \prod_{i = 1}^n X_i \text{ for } n \geq 1
    \end{align*}
    defines a martingale.
    Define $s_i \colonequals \EE \sqrt{X_i}$.
    \begin{enumerate}
    \item Show that $0 < s_i \leq 1$ for all $i$.
    \item Show that there exists a random variable $M_{\infty} \geq 0$ such that $M_n \to M_{\infty}$ almost surely.
    \item Show that if $\prod_{i = 1}^{\infty} s_i = 0$, then $M_{\infty} = 0$ almost surely.

        \hint{Consider another martingale formed by suitably normalizing $\prod_{i = 1}^n \sqrt{X_i}$.}
    \item Show that if $\prod_{i = 1}^{\infty} s_i > 0$, then $M_n \to M_{\infty}$ in $L^1$, and therefore $\EE M_{\infty} = 1$ and it is not the case that $M_{\infty} = 0$ almost surely.

        \hint{Use the same martingale from Part 3 and a suitable martingale maximal inequality to establish that $\sup_n M_n < \infty$ almost surely. Then, apply dominated convergence.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Sums of random length]
    Let $X_1, X_2, \dots$ be i.i.d.\ random variables with $\EE |X_i| < \infty$ and let $S_n \colonequals \sum_{i = 1}^n X_i$.
    Let $N \in \NN$ be a random variable independent of the $X_i$ having $\EE N < \infty$.
    \begin{enumerate}
    \item Show that $\EE S_N = \EE\sum_{i = 1}^{N} X_i = \EE N  \cdot \EE X_1$.

        \hint{Write $S_N = \sum_{i = 1}^{\infty} X_i \One\{i \leq N\}$. Handle the case $X_i \geq 0$ first.}
    \item Show that if further $X_i \geq 0$ almost surely, $X_i$ is not almost surely zero, and $\EE N = \infty$, then the above identity still holds, in the sense that $\EE S_N = \infty$.
    \item Show that, if $\EE X_i^2 < \infty$, then $\EE(S_N - N \EE X_1)^2 = \EE N \cdot \Var[X_1]$ and conclude that, if also $\EE N^2 < \infty$, then $\EE S_N^2 = \EE N \cdot \EE X_1^2 + \EE[N(N - 1)] \cdot (\EE X_1)^2$.

        \hint{Reduce to the case $\EE X_1 = 0$. Use the $L^2$ martingale convergence theorem.}
    \item Calculate the mean and variance of the sum of the rolls of a six-sided die made until a 6 is rolled.
    \end{enumerate}
\end{outproblem}

\end{document}
