\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 4}
\author{Probability Theory II \\ (EN.553.721, Spring 2025)}
\date{Assigned: March 31, 2025 \,\,\,\,\, Due: 11:59pm EST, April 14, 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{1.5em}

\begin{outproblem}[Harmonic analysis and Markov chains]
    Let $(Y_n)$ be a Markov chain taking values in a countable $S$ and initialized from some probability measure $\mu_0$ over $S$ with transition kernel $p: S \times S \to [0, 1]$.
    Suppose that $S$ is irreducible.
    \begin{enumerate}
    \item Let $f: S \to \RR$ satisfy, for all $y \in S$,
        \[ f(y) \geq \sum_{z \in S} p(y, z) f(z) = \Ex_{y} f(Y_1) \]
        and have that $f(Y_n)$ is integrable (i.e., in $L^1$) for all $n \geq 0$.
        Show that $(f(Y_n))_{n \geq 0}$ is a supermartingale, a submartingale if the inequality above is reversed, and a martingale if the inequality is an equality.
        (This generalizes part of Problem 3 from Homework 2.)
        In these cases, $f$ is called \emph{superharmonic}, \emph{subharmonic}, and \emph{harmonic}, respectively.
        For $U \subseteq S$, write $\partial U = \{y \notin U: p(x, y) > 0 \text{ for some } x \in U\}$.
        Then, $f: U \cup \partial U \to \RR$ is called \emph{super/sub/harmonic on $U$} if it satisfies the above for all $y \in U$ (a weaker condition than having these properties on all of $S$).
    \item Let $U \subseteq S$ be finite and non-empty.
        Suppose $f: U \cup \partial U \to \RR$ is harmonic on $U$.
        Show that
        \[ \max_{x \in U} f(x) \leq \sup_{x \in \partial U} f(x). \]
    \item Again, let $U \subseteq S$ be finite and non-empty.
        For any $f: \partial U \to \RR$, show that there is at most one $g: U \cup \partial U \to \RR$ that is harmonic on $U$ and that satisfies the ``boundary condition'' $g(x) = f(x)$ for all $x \in \partial U$.

        \hint{If $g$ and $h$ are two different such functions, consider using Part 2 on $g - h$ and $h - g$.}
    \item Once more, let $U \subseteq S$ be finite and non-empty.
        Let $T \colonequals \min\{n \geq 0: Y_n \notin U\}$ be the \emph{exit time} from $U$.
        Suppose that $f: \partial U \to \RR$ is bounded.
        Show that the function
        \[ g(x) \colonequals \Ex_{x} f(Y_T) \]
        is well-defined for $x \in U \cup \partial U$, is harmonic on $U$, and satisfies $g(x) = f(x)$ for all $x \in \partial U$.
        That is, averaging the value of $f$ at an exit time gives the unique solution of the associated boundary value problem from Part 3.
    \end{enumerate}
    If you are familiar with basic notions of continuous harmonic analysis and/or the Poisson partial differential equation, you should compare Parts 2 and 3 to the corresponding analytic principles.
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Recurrence and transience of trees]
    A tree is a simple connected graph with no cycles.
    All trees in this problem are \emph{locally finite}, meaning each vertex has finite degree (though the total number of vertices may be infinite).
    The \emph{simple random walk (SRW)} on a tree is the Markov chain taking values in the tree where each successive state is a uniformly random neighbor of the current state.
    \begin{enumerate}
    \item Let $G_d$ be the infinite $d$-regular tree, the infinite tree where every vertex has degree $d \geq 2$.
        (For example, $d = 2$ gives the integer graph $\ZZ$ we have discussed in class.)
        Fix some $x \in G_d$.
        Let $W_n$ be the number of closed walks in $G_d$ that start at $x$, follow an edge at every step, traverse a total of $n$ edges, and end back at $x$.
        Show that $W_n = 0$ if $n$ is odd.
        If $n$ is even, let $W_{n, k}$ be the number of such walks that visit $x$ exactly $k$ times (note that we must have $k \geq 2$).
        Show that $W_{n, k} \leq 2^{n - k + 1}d^{k - 1}(d - 1)^{n/2 - k + 1}$.

        \hint{Group the steps of a walk into three types: (1) steps from $x$ to one of its neighbors, (2) steps from vertices other than $x$ that increase the distance to $x$, and (3)~steps from vertices other than $x$ that decrease the distance to $x$. How many possible patterns of step types are there for a fixed $n$ and $k$, and how many walks are there with each pattern?}
    \item Derive that, if $d \geq 3$, then there is a constant $C_d > 0$ such that $W_n \leq C_d(2\sqrt{d - 1})^{n}$. Conclude that all $x \in G_d$ are transient for the SRW on $G_d$ for any $d \geq 3$.
        (In contrast, by P\'{o}lya's theorem from class, all $x \in G_2 = \ZZ$ are recurrent for the SRW on $G_2$.)
    \item Let $x \in G_d$ and pick some neighbor $y$ of $x$.
        If we remove the edge between $x$ and $y$, then $G_d$ is split into two trees, $H$ and $H^{\prime}$, whose vertices partition the vertices of $G_d$.
        Show that, if $d \geq 3$, then the SRW started from any $z \in G_d$ almost surely either visits $H$ only finitely many times or visits $H^{\prime}$ only finitely many times.
        (Of course, the SRW must visit one of the two infinitely many times, since all vertices belong to $H$ or $H^{\prime}$.)
    \item Consider $G_2 = \ZZ$.
        In class we showed that the SRW on $\ZZ$ is recurrent.
        Consider now picking some $\beta \in (\frac{1}{2}, 1)$, and taking a Markov chain on $\ZZ$ with the ``biased'' transition kernel
        \[ p(x, y) = \left\{\begin{array}{ll} \beta & \text{if } y = x + 1, \\ 1 - \beta & \text{if } y = x - 1, \\ 0 & \text{otherwise} \end{array}\right\}. \]
        Show that every $x \in \ZZ$ is transient for a Markov chain with this transition kernel with any initialization.
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[More on stationary measures]
    Let $(Y_n)$ be a Markov chain on a countable $S$ such that $S$ is irreducible and every $x \in S$ is recurrent.
    Recall that we studied the stationary measure $\mu_x(y) \colonequals \mathbb{E}_x[\sum_{n = 0}^{T_x - 1} \One\{Y_n = y\}]$, where $T_x \colonequals \min\{n \geq 1: Y_n = x\}$.
    \begin{enumerate}
    \item We say that a random variable $A$ \emph{stochastically dominates} a random variable $B$ if, for all $t \in \RR$, $\PP[A \geq t] \geq \PP[B \geq t]$.
        Write $A \succeq B$ for this relation (not to be confused with positive semidefiniteness of matrices).
        Show that, if $A \succeq B$, and $f: \RR \to \RR$ is strictly increasing, then $\EE f(A) \geq \EE f(B)$ provided that both expectations are well-defined.
    \item Show that, for all $x, y \in S$ distinct, $\PP_y[T_x < T_y] > 0$.
    \item Conclude that $\sum_{n = 0}^{T_x - 1} \One\{Y_n = y\}$ is stochastically dominated by a suitable geometric random variable, and therefore that $\mu_x(y) < \infty$ for all $x, y \in S$.
    \item Suppose $S = \{0, 1, \dots, M\}$ for some $M \geq 1$; in particular, $S$ is finite.
        Suppose that $p, q: S \times S \to [0, 1]$ are transition kernels such that, for all $x \in S$, $q(x, \cdot) \succeq p(x, \cdot)$ (note that both sides here, for each fixed $x \in S$, are probability measures).
        Let $\mu$ be the unique stationary probability measure of $p$ and $\nu$ that of $q$.
        Show that $\nu \succeq \mu$ (i.e., that stochastic domination of transition kernels implies stochastic domination of stationary distributions).

        \hint{Write $\nu^{(k)}(x) = \sum_y \nu(y) p^{(k)}(y, x)$. Show that $\nu \succeq \nu^{(k)}$ for all $k$, and use the convergence theorem from class.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[More on stationary probability measures]
    As in Problem 3, let $(Y_n)$ be a Markov chain on a countable $S$ such that $S$ is irreducible and every $x \in S$ is recurrent.
    The same $\mu_x$ and $T_x$ discussed there will appear below.
    \begin{enumerate}
    \item Suppose that, for some $x \in S$, $\EE_x[T_x] < \infty$.
        Show that then in fact $\EE_y[T_y] < \infty$ for all $y \in S$.
        Generally, such states in a Markov chain are called \emph{positive recurrent}, and positive recurrence, like recurrence, is ``contagious under accessibility'' (but you do not need to prove that beyond this special case).
        You may use the result of Problem 3 that the $\mu_x$ are measures on $S$.

        \hint{Use the uniqueness theorem for stationary measures, which shows that the various $\mu_x$ are the same up to constant rescaling.}
    \item Let $h(x, y) \colonequals \EE_x[T_y]$, the \emph{expected hitting time} of $y$ starting from $x$.
        Note that $h(x, x) = \EE_x[T_x]$ is the quantity appearing in Part 1.
        Show that, for all $x, y \in S$,
        \[ h(x, y) = 1 + \sum_{\substack{z \in S \\ z \neq y}} p(x, z) h(z, y). \]
    \item Deduce that, if $\pi$ is a stationary probability measure, then, for all $y \in S$,
        \[ \sum_{x \in S} \pi(x) h(x, y) = 1 + \sum_{\substack{x \in S \\ x \neq y}} \pi(x) h(x, y). \]
    \item Suppose that, as in Part 1, all states in $S$ are positive recurrent.
        Let $\mu_x$ be as in Problem~3.
        Recall that in this case, from the existence theorem from class,
        \[ \what{\mu}_x(y) \colonequals \frac{\mu_x(y)}{\mu_x(S)} = \frac{\mu_x(y)}{\EE_x[T_x]} \]
        is a stationary probability measure.
        Recall also that the uniqueness theorem for stationary measures implies that there is a unique stationary probability measure (since there is a unique stationary measure up to scaling, and the scaling is fixed by asking for a probability measure), so all $\what{\mu}_x$ must be equal.
        Show more concretely that, for all $x, y \in S$,
        \[ \what{\mu}_x(y) = \frac{1}{\EE_y[T_y]}, \]
        whereby also the unnormalized stationary measures are given by
        \[ \mu_x(y) = \frac{\EE_x[T_x]}{\EE_y[T_y]}. \]
        \hint{Use Part 3 to show that the first result holds for any stationary probability measure.}
    \end{enumerate}
\end{outproblem}

\vspace{1em}

\begin{outproblem}[Continuous state space]
    Consider a process $(Y_n)$ taking values in $S = \RR$ formed by $Y_0 = y_0$ for some (deterministic) $y_0 \in \RR$ and setting $Y_{n + 1} = \alpha Y_n + Z_{n + 1}$ for all $n \geq 0$, for some $\alpha \in \RR$, where $Z_1, Z_2, \ldots \sim \sN(0, 1)$ are i.i.d.
    \begin{enumerate}
    \item Show that $(Y_n)$ is a Markov chain.
        Describe its transition kernel (recall that in this setting this is a function $p: \RR \times \sB \to [0, 1]$ for $\sB$ the Borel $\sigma$-algebra of $\RR$).
    \item Show that this transition kernel has a stationary probability measure if and only if $|\alpha| < 1$.
        In this case, describe such a probability measure $\mu_{\alpha}$.
    \item If $|\alpha| < 1$, show that $\Law(Y_n)$ converges weakly to $\mu_{\alpha}$, for any initial $y_0$.
    \item If $|\alpha| < 1$ and $f: \RR \to \RR$ is smooth and bounded, show that, as $n \to \infty$, $\frac{1}{n}\sum_{i = 1}^n f(Y_i)$ converges to $\int fd\mu_{\alpha}$ in probability.
        Note that this statement, an ergodic theorem like we saw in class, is like a law of large numbers, except the $Y_i$ are not i.i.d.\ but rather arise from a Markov chain.

        \hint{Estimate the mean and variance.}
    \end{enumerate}
\end{outproblem}

\end{document}
