\documentclass[11pt]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%  PACKAGES %%%%%%%%%%%%%%%%%%%%%
\usepackage{amsthm,amssymb,amsfonts,amsmath}
\usepackage{amscd} %Commutative diagrams. 
\usepackage{mathrsfs}
\usepackage[numbers, sort&compress]{natbib}
\usepackage{subfigure, graphicx}
\usepackage{vmargin}
\usepackage{setspace}
\usepackage{paralist}
\usepackage[pagebackref=true]{hyperref}
\usepackage{color}
\usepackage[normalem]{ulem}
\usepackage{stmaryrd} %for \bbr
\usepackage[notcite,notref]{showkeys} % shows labels 
\usepackage[refpage,noprefix,intoc]{nomencl} %for list of notation.


%%%%%%%%%%%%%%%%%%%%%%% NATURAL NUMBERS, INTEGERS, ETC. %%%%%%%%%%%%%%%%
\providecommand{\R}{}
\providecommand{\Z}{}
\providecommand{\N}{}
\providecommand{\C}{}
\providecommand{\Q}{}
\providecommand{\G}{}
\providecommand{\Lt}{}
\renewcommand{\R}{\mathbb{R}}
\renewcommand{\Z}{\mathbb{Z}}
\renewcommand{\N}{{\mathbb N}}
\renewcommand{\C}{\mathbb{C}}
\renewcommand{\Q}{\mathbb{Q}}
\renewcommand{\G}{\mathbb{G}}
\renewcommand{\Lt}{\mathbb{L}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%% BASIC PROBABILITY %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\E}[1]{{\mathbf E}\left[#1\right]}										
\newcommand{\e}{{\mathbf E}}
\newcommand{\V}[1]{{\mathbf{Var}}\left\{#1\right\}}
\newcommand{\va}{{\mathbf{Var}}}
\newcommand{\p}[1]{{\mathbf P}\left\{#1\right\}}
\newcommand{\psub}[2]{{\mathbf P}_{#1}\left\{#2\right\}}
\newcommand{\psup}[2]{{\mathbf P}^{#1}\left\{#2\right\}}
\newcommand{\I}[1]{{\mathbf 1}_{[#1]}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
% \Cprob Bases bracket size on term before conditioning; \probC on term after conditioning
\newcommand{\Cprob}[2]{\mathbf{P}\set{\left. #1 \; \right| \; #2}} 
\newcommand{\probC}[2]{\mathbf{P}\set{#1 \; \left|  \; #2 \right. }}
\newcommand{\phat}[1]{\ensuremath{\hat{\mathbf P}}\left\{#1\right\}}
\newcommand{\Ehat}[1]{\ensuremath{\hat{\mathbf E}}\left[#1\right]}
\newcommand{\ehat}{\ensuremath{\hat{\mathbf E}}}
\newcommand{\Esup}[2]{{\mathbf E^{#1}}\left\{#2\right\}}
\newcommand{\esup}[1]{{\mathbf E^{#1}}}
\newcommand{\Esub}[2]{{\mathbf E_{#1}}\left\{#2\right\}}
\newcommand{\esub}[1]{{\mathbf E_{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SETS %%%%%%%%%%%%%%%%%%%%%
\newcommand\cA{\mathcal A}
\newcommand\cB{\mathcal B}
\newcommand\cC{\mathcal C}
\newcommand\cD{\mathcal D}
\newcommand\cE{\mathcal E}
\newcommand\cF{\mathcal F}
\newcommand\cG{\mathcal G}
\newcommand\cH{\mathcal H}
\newcommand\cI{\mathcal I}
\newcommand\cJ{\mathcal J}
\newcommand\cK{\mathcal K}
\newcommand\cL{{\mathcal L}}
\newcommand\cM{\mathcal M}
\newcommand\cN{\mathcal N}
\newcommand\cO{\mathcal O}
\newcommand\cP{\mathcal P}
\newcommand\cQ{\mathcal Q}
\newcommand\cR{{\mathcal R}}
\newcommand\cS{{\mathcal S}}
\newcommand\cT{{\mathcal T}}
\newcommand\cU{{\mathcal U}}
\newcommand\cV{\mathcal V}
\newcommand\cW{\mathcal W}
\newcommand\cX{{\mathcal X}}
\newcommand\cY{{\mathcal Y}}
\newcommand\cZ{{\mathcal Z}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%%%%%%%%%%%%%%% PROBABILISTIC CONVERGENCE/EQUALITY %%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\eqdist}{\ensuremath{\stackrel{\mathrm{d}}{=}}}
\newcommand{\convdist}{\ensuremath{\stackrel{\mathrm{d}}{\rightarrow}}}
\newcommand{\convas}{\ensuremath{\stackrel{\mathrm{a.s.}}{\rightarrow}}}
\newcommand{\aseq}{\ensuremath{\stackrel{\mathrm{a.s.}}{=}}}

%%%%%%%%%%%%%%%%%%%%%%%% OTHER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\pran}[1]{\left(#1\right)}
\providecommand{\eps}{}
\renewcommand{\eps}{\epsilon}
\providecommand{\ora}[1]{}
\renewcommand{\ora}[1]{\overrightarrow{#1}}
\newcommand\urladdrx[1]{{\urladdr{\def~{{\tiny$\sim$}}#1}}} % For title
\DeclareRobustCommand{\SkipTocEntry}[5]{} %For table of contents when using AMS styles. Change 5 to 4 if not using hyperref. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%% FOR MARGINAL AND OTHER COMMENTS, AND COLOR TEXT %%%%%%%%%%%%%%%
\reversemarginpar
\marginparwidth 1.1in
\newcommand\marginal[1]{\marginpar{\raggedright\parindent=0pt\tiny #1}}
\newcommand\LAB{\marginal{LAB}}
\newcommand\REM[1]{{\raggedright\texttt{[#1]}\par\marginal{XXX}}}
\newcommand\rem[1]{{\raggedright\texttt{[#1]}\marginal{XXX}}}
\definecolor{clou}{rgb}{0.8,0.25,0.5125}
\newcommand{\lou}[1]{\textcolor{clou}{#1}}
\newcommand{\lmar}[1]{\textcolor{clou}{\marginal{#1 \\ LAB}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%% Theorem types %%%%%%%%%%%%%%%%%
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{conj}{Conjecture}
\newtheorem{ex}{Exercise}[section]
\newtheorem{example}[thm]{Example}
\newtheorem{fact}[thm]{Fact}
\newtheorem{claim}[thm]{Claim}
\newtheorem{cla}[thm]{Claim}
\numberwithin{thm}{section}
%\numberwithin{equation}{section}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{color}

\begin{document}

\title{Math 589 -- Winter 2020 -- Assignment 3}
\author{Assigned on February 14, 2020. \\Due on February 24, 2020 at 2 PM (by email or in my office)}
\date{}
\maketitle

{\color{blue} 
}
\begin{enumerate}

\item {\color{red} [How many leaves does a tree have?]} 
For a node $v$ of a tree $t$, say that $v$ is a {\em leaf} of $t$ if $c(v;t)=0$. Fix an offspring distribution $\mu$ and write $\alpha = \sum_{i \ge 0} i \mu(i)$. Then let $T$ be a $\mathrm{GW}_\mu$-distributed random tree, and for $n \ge 0$ let $L_n = |\{v \in T_n: v\mbox{ is a leaf of }T\}|$. 

Suppose that $\mu(0)>0$. 

\begin{itemize}
\item[(a)] Prove that as $n \to \infty$, 
\[
\frac{L_n}{|T_{n}|}\I{M \ne 0} \convas \mu(0)\I{M\ne 0}\, ,
\]
where $M:=\limsup M_n$ is the almost sure limit of the martingale $M_n=|T_n|/\alpha^n$. 
Interpret the ratio as zero if $|T_{n}|=0$. 

\item[(b)] Prove that as $n \to \infty$, 
\[
\frac{L_n}{\alpha^{n}}\I{M\ne 0} \convas M\mu(0)\, .
\]
where $M:=\limsup M_n$ is the almost sure limit of the martingale $M_n=|T_n|/\alpha^n$. 
\end{itemize}


\item~{\color{red} [Moment generating function examples]}

\begin{itemize}
\item[(a)] Let $E$ be an Exponential$(\alpha)$ random variable; this means $E$ is non-negative and has density $\alpha e^{-\alpha x}$ on $(0,\infty)$. Show that 
\[
G_E(s) = \sum_{k=0}^\infty \frac{s^k}{\alpha^k}\, ,
\]
for $s \in (-\infty,\alpha)$. 
\item[(b)] Let $X$ be Gamma$(\alpha,u)$-distributed; this means $X$ is non-negative and has density 
\[
\frac{\alpha^u}{\Gamma(u)} x^{u-1}e^{-\alpha x}
\]
on $(0,\infty)$. Show that $G_X(s) = (1-s/\alpha)^{-u}$ for $s \in (-\infty,\alpha)$, and deduce that $\E{X^k} = u(u+1)\cdot\ldots\cdot(u+k-1)/\alpha^k$. (Notice the relation with part (a).)
\end{itemize}

\item~{\color{red} [Characteristic function facts]}\\ %Chaumont and Yor 2.4

In class and in the notes you have seen that for any a real random variable $X$, for all $n \ge 0$, if $\E{|X|^n}<\infty$ then 
\begin{equation}\label{eq:error_bound}
\left|\varphi_X(t) - \sum_{k=0}^n \frac{(it)^k}{k!} \E{X^k} \right|
\le \e \min\pran{\frac{|tX|^{n+1}}{(n+1)!},\frac{2|tX|^n}{n!}}\, .
\end{equation}
Use this bound to prove the following. 
\begin{enumerate}
\item[(a)] {\color{red} [The characteristic function of simple random walk.]} Let $(X_i,i \ge 1)$ be independent fair coin tosses, i.e., $\p{X_i=1}=\p{X_i=-1}=1/2$, and let $S_n=n^{-1/2}\sum_{i=1}^n X_i$. 
Prove that for all $t \in \R$, $\varphi_{S_n}(t) \to e^{-t^2/2}$. 

\item[(b)] {\color{red} [Finite moment generating function gives Taylor expansion of characteristic function.} Let $X$ be any random variable. Suppose that the moment generating function $G_X$ is finite: $G_X(s) \in \R$ for all $s \in \R$. Prove that 
\[
\varphi_X(t) = \sum_{k=0}^\infty \frac{(it)^k}{k!} \E{X^k}\, 
\]
for all $t \in \R$. (Hint: use the assumption to show the error term
in (\ref{eq:error_bound}) tends to zero as $n \to \infty$.) 
\end{enumerate}

\item~{\color{red} Characteristic functions and densities}

Let $X$ be a real random variable. Show that if $X$ has a density with respect to Lebesgue measure then $|\varphi_X(t)| \to 0$ as $t \to \infty$. Also show that if $\int_\R |\varphi_X(t)|<\infty$ then the function defined by 
\[
f(x) = \frac{1}{2\pi} \int_\R e^{-itx} \varphi_X(t)\mathrm{d} t
\]
is a continuous density for $X$.
% You may use the inversion theorem for characteristic functions in proving these results. 

{\color{red} The next two questions are about periodicity and characteristic functions.}

\item Let $X$ be a real random variable with characteristic function $\varphi=\varphi_X$, and fix $r > 0$ Prove that the following statements are equivalent. 
\begin{itemize}
\item[(i)] $\varphi(r)=1$
\item[(ii)] $\varphi(t+r)=\varphi(t)$ for all $t \in \R$.
\item[(iii)] $\p{rX/(2\pi) \in \Z}=1$. 
\end{itemize}
Hint: what does (i) imply about the probability $\p{\cos(rX)<1}$?

\item Let $X$ be a real random variable with characteristic function $\varphi=\varphi_X$. Prove that one of the following three conditions must occur.
\begin{itemize}
\item[(i)] $\varphi(t)=1$ for all $t \in \R$. 
\item[(ii)] $|\varphi(t)|<1$ for $t \ne 0$. 
\item[(iii)] There is $r > 0$ such that $|\varphi(t)|<1$ for $0 < t < r$, and $\varphi(t)=\varphi(t+r)$ for all $t \in \R$. 
\end{itemize}

\end{enumerate}

\end{document}