\documentclass[amsart,notheorems,compress,14pt]{beamer}
\usepackage{CJK}
%\usepackage{graphicx}
\usepackage{xy}
\usepackage{amsfonts, bbm}
%\usepackage{mathrsfs}
\DeclareGraphicsRule{*}{mps}{*}{}
%\usepackage{subfigure}
\usepackage{xmpmulti}
\usepackage{colortbl,dcolumn}
\usepackage[english]{babel}
\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps}
%\usepackage{amsmath,amssymb}
%\usepackage[latin1]{inputenc}
\usepackage{times}
%\usepackage[T1]{fontenc}
\usefonttheme{serif}
\usepackage{graphicx}
\usepackage{latexsym}
%\usepackage{amsfonts}
\usepackage{mathrsfs}
 \usepackage{times,amsmath,amssymb,mathrsfs}


\setbeamerfont{frametitle}{size=\large,series=\bfseries}

\mode<presentation> {
  %\usetheme{Warsaw}
  \usetheme{Madrid}
  %\usetheme{Darmstadt}
\usefonttheme{structurebold}
  \setbeamercovered{transparent}
}

\colorlet{redshaded}{red!3!bg}
\colorlet{shaded}{black!5!bg}
\colorlet{shadedshaded}{black!5!bg}
\colorlet{blackshaded}{black!5!bg}
\colorlet{darkred}{red!5!black}
\colorlet{darkblue}{blue!20!black}
\colorlet{darkgreen}{green!20!black}

\def\red{\color{red}}
\def\green{\color{green}}
\def\blue{\color{blue}}
\def\brown{\color{brown}}
\def\pink{\color{pink}}
\def\cyan{\color{cyan}}
\def\orange{\color{orange}}
\def\gray{\color{gray}}

\def\black{\color{black}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{hypothesis}{Hypothesis}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{example}{Example}[section]
\newtheorem{question}{Question}[section]

\setbeamercolor{title}{fg=white, bg=blue!70!black}
\setbeamercolor{block title}{fg=white, bg=green!50!black}
\setbeamercolor{frametitle}{fg=white, bg=blue!70!black}

 \def\bhypothesis{\begin{hypothesis}\sl{}\def\ehypothesis{\end{hypothesis}}}
 \def\bdefinition{\begin{definition}\sl{}\def\edefinition{\end{definition}}}
 \def\blemma{\begin{lemma}\sl{}\def\elemma{\end{lemma}}}
 \def\bproposition{\begin{proposition}\sl{}\def\eproposition{\end{proposition}}}
 \def\btheorem{\begin{theorem}\sl{}\def\etheorem{\end{theorem}}}
 \def\bcorollary{\begin{corollary}\sl{}\def\ecorollary{\end{corollary}}}
 \def\bremark{\begin{Remark}\rm{}\def\eremark{\end{Remark}}}
 \def\bexample{\begin{example}\rm{}\def\eexample{\end{example}}}

 \def\beqlb{\begin{eqnarray}}\def\eeqlb{\end{eqnarray}}
 \def\beqnn{\begin{eqnarray*}}\def\eeqnn{\end{eqnarray*}}

%\newtheorem{dingli}[theorem]{\CJKfamily{hei}定理}
%\newtheorem{mingti}[theorem]{\CJKfamily{hei}命题}
%\newtheorem{yinli}[theorem]{\CJKfamily{hei}引理}
%\newtheorem{tuilun}[theorem]{\CJKfamily{hei}推论}
%\newtheorem{wenti}[theorem]{\CJKfamily{hei}问题}
 \def\wi{\widetilde}
 %\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
%\renewcommand{\labelenumi}{[\arabic{enumi}]}
\def\ar{\!\!\!&}

 \def\mcr{\mathscr}
 \def\mbb{\mathbb}
 \def\term{\it}
\def\rf{\ref}
 \def\az{\alpha}
\def\bz{\beta}
\def\gz{\gamma}
\def\sz{\sigma}
\def\dz{\delta}
\def\ez{\epsilon}
\def\lz{\lambda}
\def\oz{\omega}
\def\vz{\varphi}
\def\wz{\wedge}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\g{G}
\def\H{\mathcal {H}}
\def\K{{\cal K}}
\def\U{{\cal U}}
\def\V{{\cal V}}
\def\W{{\cal W}}
\def\M{{\cal M}}
\def\I{{\cal I}}
\def\J{{\cal J}}
\def\L{{\cal L}}
\def\R{{\cal R}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\N{{\cal N}}
\def\S{{\cal S}}
\def\T{{\overline{T}}}
\def\l{\underline{l}}
\def\n{{\underline{n}}}
\def\m{{\underline{m}}}
\def\e{\underline{e}}
\def\nn{{\n\times\n}}
\def\mm{{\m\times\m}}
\def\tt{{t\times t}}
\def\KM{(\K,\M)}
\def\rad{\mbox{rad}}
\def\ud{\underline}
\def\wt{\widetilde}
\def\lra{\longrightarrow}
\def\lla{\longleftarrow}
\def\ra{\rangle}
\def\la{\langle}
\def\rar{\rightarrow}
\def\lar{\leftarrow}
\def\Hom{\mbox{Hom}}
\def\diag{\mbox{diag}}
\def\op{\mbox{op}}
\def\Ext{\mbox{Ext}}
\def\End{\mbox{End}}
\def\dim{\mbox{dim}}
\def\mod{\mbox{mod}}
\def\ind{\mbox{ind}}
\def\Im{\mbox{Im}}
\def\Ker{\mbox{Ker}}
\def\Coker{\mbox{Coker}}
\def\add{\mbox{add}}
\def\Supp{\mbox{Supp}}
\def\top{\mbox{top}}
\def\soc{\mbox{soc}}
\def\rank{\mbox{rank}}
\def\mf{\mathfrak}

 \def\beqlb{\begin{eqnarray}}\def\eeqlb{\end{eqnarray}}
 \def\beqnn{\begin{eqnarray*}}\def\eeqnn{\end{eqnarray*}}

 \newcommand{\bcen}{\begin{center}}
 \newcommand{\ecen}{\end{center}}
 \newcommand{\bgeqn}{\begin{equation}}
 \newcommand{\edeqn}{\end{equation}}


 \def\mcr{\mathscr}\def\mbb{\mathbb}
 \def\mbf{\mathbf}\def\mrm{\mathrm}

\renewcommand{\raggedright}{\leftskip=0pt \rightskip=0pt plus 0cm}
\raggedright

\def\hilite<#1>{%
\temporal<#1>{\color{blue!25}}{\color{magenta}}%
{\color{blue!55}}}

%\newcolumntype{H}{>{\columncolor{blue!20}}c!{\vrule}}
%\newcolumntype{H}{>{\columncolor{blue!20}}c}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%重定义字体、字号命令 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\songti}{\CJKfamily{song}}        % 宋体
\newcommand{\fangsong}{\CJKfamily{fs}}        % 仿宋体
\newcommand{\kaishu}{\CJKfamily{kai}}         % 楷体
\newcommand{\heiti}{\CJKfamily{hei}}          % 黑体
\newcommand{\lishu}{\CJKfamily{li}}           % 隶书
\newcommand{\youyuan}{\CJKfamily{you}}       % 幼圆
\newcommand{\sihao}{\fontsize{14pt}{\baselineskip}\selectfont}      % 字号设置
\newcommand{\xiaosihao}{\fontsize{12pt}{\baselineskip}\selectfont}  % 字号设置
\newcommand{\wuhao}{\fontsize{10.5pt}{\baselineskip}\selectfont}    % 字号设置
\newcommand{\xiaowuhao}{\fontsize{9pt}{\baselineskip}\selectfont}   % 字号设置
\newcommand{\liuhao}{\fontsize{7.875pt}{\baselineskip}\selectfont}  % 字号设置
\newcommand{\qihao}{\fontsize{5.25pt}{\baselineskip}\selectfont}    % 字号设置
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\begin{CJK*}{GBK}{kai}


%\textcolor[rgb]{0.00,0.55,0.50}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            题页            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Separation cutoff]{Explicit criteria on separation cutoff for birth and death chains}

\author[Yu-Hui Zhang]{Yu-Hui Zhang}

\date[April 23, 2014]{\wuhao (April 23, 2014, National Chiao Tung University) \\
$ $\\ This talk is based on the joint work with Yong-Hua Mao and Chi Zhang.}

\institute[BNU]{\sihao Beijing Normal Univesity}

\frame{\titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            目录            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section*{目录}
  %  \frame{\frametitle{目录}\tableofcontents}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%         背景及问题        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\large
%----------------------------------------------------------------------------------------2

\frame{
 \frametitle{Outline}\small
\begin{enumerate}
\item Background
\item A general condition for separation cutoff
\item FSST of birth-death chains
\item Explicit criteria for BD chains
\begin{itemize}
\item Eigenvalues
\item Duality
\item Stochastic monotonicity
\end{itemize}
\item Applications
\item FSST of single birth chains
\item Explicit criterion for SB chains -Duality
\item Explicit criterion for SB chains -Stochastic monotonicity
\end{enumerate}
}
%----------------------------------------------------------------------------------------3
\frame{ \frametitle{1. Background}\small
\begin{itemize}
\item What is separation cutoff?
\end{itemize}
Cutoff is referred to a family of ergodic Markov chains shows a sharp transition when converging to their stationary
distributions. Let $P^{(n)}(t)$ be the distribution of an finite ergodic Markov chains $X_t$ at time $t$, its
stationary distribution is $\pi^{(n)}$. Then
$$ \lim_{t\to\infty}D(P^{(n)}(t),\pi^{(n)})=0$$
holds for each $n$.

However involving $n$, it may happen that
$$\lim_{n\to\infty}D(P^{(n)}(ct_n),\pi^{(n)})=\begin{cases}0 & \hbox{for $c>1$};\\ 1 & \hbox{for $c<1$.}\end{cases}$$
}
%----------------------------------------------------------------------------------------4
\frame{ \frametitle{1. Background}\small

This is called ($D$-)cutoff phenomenon by Persi Diaconis (1996). The ``distance'' $D$ usually can be chosen to be
\begin{itemize}
\item separation (Diaconis \& Saloff-Coste (2006))
\item total variance (Ding et al(2010))
\item $\max-L^2$ distance (Chen \& Saloff-Coste(2010))
\end{itemize}
}
%----------------------------------------------------------------------------------------5
\frame{ \frametitle{1. Background}\small

For two probability measures $\mu$ and $\nu$, the separation is defined as
$$\text{sep}(\mu,\nu)=\max_{i}(1-\mu_i/\nu_i).$$

Aldous \& Diaconis (1987). separation is not a distance.

For a finite Markov chain, let $P(t)$ be the distribution at $t$,
there exists a so-called {\red fastest strong stationary time (FSST)} $\tau$ such that
$$\text{sep}(P(t),\pi)=\mathbb P[\tau>t], \ t\ge0.$$

Aldous \& Diaconis (1987), Fill(1991).

($X_\tau\sim^\text{d}\pi$, $X_\tau$ and $\tau$ are independent.)

\vskip0.2cm
Diaconis \& Saloff-Coste(2006) first gave the criteria for birth and death chains, these criteria involves all the eigenvalues of each chain.
}
%----------------------------------------------------------------------------------------6
\frame{ \frametitle{1. Background}\small

We give the explicit criteria, which depend only on the one-step transition probability
in the discrete time case, and on the birth and death rates in the continuous time case.

\vskip0.2cm
Since the birth and death chain is symmetric, its eigenvalues are real. But for a general skip-free chains, eigenvalues may be
complex.

\vskip0.2cm
Fill(2009) obtained the distribution of the FSST for upward skip-free chains (single birth chain). So we will study the separation cutoff for the upward skip-free chains.

\vskip0.2cm
To get the FSST, the upward skip-free chain is assumed to have the stochastically monotone time-reversal.
}
%----------------------------------------------------------------------------------------7
\frame{ \frametitle{2. A general condition for separation cutoff}\small
\begin{block}{Proposition(Diaconis \& Saloff-Coste(2006)} Let $\tau^{(n)}$ be FSST's for a family of Markov chains. Assume that there is $C<\infty$ such that
$$\mathbb E(\tau^{(n)})^3\le C(\mathbb E\tau^{(n)})^3\ \text{for all}\ n.$$
Then there is a separation cutoff with $t_n=\mathbb E\tau^{(n)}$ iff
$$\frac{(\mathbb E\tau^{(n)})^2}{\text{Var}(\tau^{(n)})}\to \infty,\ \text{or, equivalently}\
\frac{(\mathbb E\tau^{(n)})^2}{\mathbb E(\tau^{(n)})^2}\to 1.$$
\end{block}

Set $\xi^{(n)}=\tau^{(n)}/\mathbb E\tau^{(n)}$. Separation cutoff is equivalent to that $\xi^{(n)}$ converges to $1$ in probability.
}
%----------------------------------------------------------------------------------------8
\frame{ \frametitle{3. FSST of birth-death chains}\small
\begin{block}{Theorem(Diaconis \& Fill(1990))}
For an ergodic continuous-time birth-death chain on the state space $\{0,\dots, N\}$ started at $0$, let $Q$ be the generator. Then there exists a fastest strong stationary time (FSST) $\tau$ such that
$$\text{sep}(P(t),\pi)=\mathbb P[\tau>t]$$
and the distribution of $\tau$ is given in Laplace transformation:
$$
\mathbb E e^{-\lambda \tau}=\prod_{\nu=1}^N\frac{\lambda_\nu}{\lambda+\lambda_\nu},\ \lambda\ge0,
$$
where $\lambda_1<\cdots<\lambda_N$ are positive eigenvalues of the matrix $-Q$.
\end{block}
}

%----------------------------------------------------------------------------------------9
\frame{ \small
Let $X_t^{(n)}$ be a sequence of birth and death process
on $E_n=\{0,1,\dots,m_n\}$ with generator matrix $Q^{(n)}$.
Let $\pi^{(n)}$ be the corresponding stationary distribution and $P^{(n)}(t)$ be the distribution $X_t^{(n)}$ starting from state $0$.
Let $0=\lambda_0^{(n)}<\lambda_1^{(n)}<\cdots<\lambda_{m_n}^{(n)}$ be the eigenvalues of $-Q^{(n)}$.

$$
\mathbb E\tau^{(n)}=T^{(n)}=\sum_{\nu=1}^{m_n}\frac1{\lambda^{(n)}_\nu},\  \text{Var}(\tau^{(n)})=\sum_{\nu=1}^{m_n}\bigg(\frac1{\lambda^{(n)}_\nu}\bigg)^2.
$$

$$
\bigg(\frac1{\lambda^{(n)}_1}\bigg)^2\le\text{Var}(\tau^{(n)})\le\frac{T^{(n)}}{\lambda^{(n)}_1},
$$

$$
\Longrightarrow \lambda_1^{(n)}T^{(n)}\le\frac{(\mathbb E\tau^{(n)})^2}{\text{Var}(\tau^{(n)})}\le\big[\lambda_1^{(n)}T^{(n)}\big]^2.
$$
\begin{block}{Theorem(Diaconis \& Saloff-Coste(2006))}
There is a separation cutoff with $t_n=T^{(n)}$ iff $\lim_{n\to\infty}\lambda_1^{(n)}T^{(n)}=\infty$.
\end{block}
}

%----------------------------------------------------------------------------------------10
\frame{ \frametitle{4. Explicit criteria for BD chains -Eigenvalues}\small
The formula for $T^{(n)}$  comes from the so-called eigentime identity, appearing first in Aldous \& Fill(2003).
Let $\lambda_\nu^{(n)},\nu\ge1$ be the non-zero eigenvalues of $-Q^{(n)}$, then it holds that
$$
\sum_{\nu=1}^{m_n}\frac{1}{\lambda_\nu^{(n)}}=\sum_{i,j=0}^{m_n}\pi_i^{(n)}\pi_j^{(n)}\mathbb E_i\tau_j^{(n)}=
\sum_{j=0}^{m_n}\pi_j^{(n)}\mathbb E_i\tau_j^{(n)}\quad \text{for all}\quad i.
$$
According to Mao(2004), for birth and death chains, we have
$$
T^{(n)}=\sum_{\nu=1}^{m_n}\frac{1}{\lambda_\nu^{(n)}}=
\sum_{i=0}^{m_n-1}\frac{1}{\pi_i^{(n)}b_i^{(n)}}\sum_{j=i+1}^{m_n}\pi_j^{(n)}\sum_{j=0}^i\pi_j^{(n)}.
$$
}
%----------------------------------------------------------------------------------------11
\frame{ \frametitle{4. Explicit criteria for BD chains -Eigenvalues}\small
M.F. Chen(2010) gives an elegant estimate of spectral gap for ergodic birth and death chains.
Let
$$
\kappa^{(n)}=\min_{0\le\ell<m\le m_n}\bigg[\bigg(\sum_{i=0}^\ell \pi_i^{(n)}\bigg)^{-1}+\bigg(\sum_{i=m}^{m_n} \pi_i^{(n)}\bigg)^{-1}\bigg]
\bigg(\sum_{i=\ell}^{m-1}\frac 1{\pi_i^{(n)}b_i^{(n)}}\bigg)^{-1}.
$$
Then
$$
\frac14\kappa^{(n)}\le \lambda_1^{(n)}\le \kappa^{(n)}.
$$

\begin{block}{Theorem 1} Separation cutoff occurs iff
$$\lim_{n\to\infty}\kappa^{(n)}T^{(n)}=\infty.
$$
\end{block}
}
%----------------------------------------------------------------------------------------12
\frame{ \frametitle{4. Explicit criteria for BD chains -Duality}\small

Fill(1992) constructed a dual absorbing birth-death process, whose absorption time $\tau^*$ has the same
distribution as $\tau$ the FSST.

Set for $0\le i\le m, H_i=\sum_{j\le i}\pi_j$ and for $i\le m-1$
$$
a_i^*=\frac{H_{i-1}}{H_i}b_i,\quad b_i^*=\frac{H_{i+1}}{H_i}a_{i+1},\quad a_m^*=b_m^*=0.
$$
Let
$$\pi_i^*=b_0H_i^2/(\pi_ib_i).$$
Let $a_i^* (1\le i\le m), b_i^* (0\le i\le m)$ be the birth and death rates for
a dual process $X^*(t)$. So $m$ is an absorbing state for $X^*(t)$. Assume both $X(t)$ and $X^*(t)$ start at $0$.
Then the absorption time (hitting time to $m$) of $X^*(t)$  has the same distribution as the FSST $\tau$ of $X(t)$.

$$Q^*\Lambda=\Lambda Q,\ \Lambda=(\Lambda_{ij}), \Lambda_{ij}=\frac{H_j}{H_i}\mathbf 1_{[j\le i]}.$$
}
%----------------------------------------------------------------------------------------13
\frame{ \small

$$\aligned
\mathbb E\tau&=\mathbb E\tau^*=\sum_{i=0}^{m-1}\frac{1}{\pi^*_{i}b^*_{i}}\sum_{j=0}^{i}\pi^*_{j},\\
\mathbb E\tau^2&=\mathbb E(\tau^*)^2=2(\mathbb E\tau)^2-2\sum_{i=0}^{m-1}\frac{1}{\pi^*_{i}b^*_{i}}\sum_{j=0}^{i}\pi^*_{j}
 \sum_{k=0}^{j-1}\frac{1}{\pi^*_{k}b^*_{k}}\sum_{l=0}^{j}\pi^*_{l},
 \endaligned
 $$
Denote
$$
S= (\mathbb E\tau)^2-\frac 12\mathbb E\tau^2=\sum_{i=0}^{m-1}\frac{1}{\pi^*_{i}b^*_{i}}\sum_{j=0}^{i}\pi^*_{j}
 \sum_{k=0}^{j-1}\frac{1}{\pi^*_{k}b^*_{k}}\sum_{l=0}^{j}\pi^*_{l}.
$$
}
%----------------------------------------------------------------------------------------14
\frame{ \small
$$
\mathbb E\tau=\sum_{j=0}^{m-1}\frac{1}{\pi_jb_j}H_j(1-H_j)=T.
$$

$$
S=\sum_{j=0}^{m-1}\frac{1-H_j}{\pi_jb_j}\sum_{k=0}^{j-1}\frac{H_k(H_j-H_k)}{\pi_kb_k}.
$$

Since
$$
\frac{\mathbb E\tau^2}{(\mathbb E\tau)^2}=2-2\frac {S}{(\mathbb E\tau)^2}=2-2\frac {S}{T^2},
$$

\begin{block}{Theorem 2} Separation cut-off occurs iff
$$
\lim_{n\to\infty}\frac{S^{(n)}}{[T^{(n)}]^2}=\frac12.
$$
\end{block}
}
%----------------------------------------------------------------------------------------15
\frame{ \frametitle{4. Explicit criteria for BD chains -Stochastic monotonicity}\small

We will obtain the distribution of FSST for the birth and death process via the halting state.
This method can be used to deal with general stochastically monotone Markov
processes.

Levin et al(2008): $i\in E$ is called a halting state for the FSST $\tau$ if for all $t\ge0$
$$
\mathbb P[\tau>t]=1-P_i(t)/\pi_i=\text{sep}(P(t),\pi).
$$
Since
$$
\max_{j}(1-P_j(t)/\pi_j)=\text{sep}(P(t),\pi),
$$
 $i$ is the halting state if and only if for $t\ge0$,
$$
P_i(t)/\pi_i=\min_{j}P_j(t)/\pi_j.
$$
}
%----------------------------------------------------------------------------------------16
\frame{\small

\begin{block}{Lemma} For the continuous time birth and death process chain on state space $E=\{0,1,\cdots, m\}$,
starting at $0$, state $m$ is a halting state for the FSST $\tau$.
\end{block}

$$
\frac{P_m(t)}{\pi_m}=\frac{p_{0m}(t)}{\pi_m}=\frac{p_{m0}(t)}{\pi_0}=\min_{i}\frac{p_{i0}(t)}{\pi_0}=\min_i \frac{p_{0i}(t)}{\pi_i}=\min_{i}\frac{P_i(t)}{\pi_i}.
$$

\begin{block}{Theorem}
Let $\tau$ be the FSST for a continuous time birth and death process on $\{0,1,\dots,m\}$, starting at $0$.
Define $\psi_m(\lambda)=\int_0^\infty e^{-\lambda t}\mathbb P[X_t=m]dt$. Then
$$\mathbb E e^{-\lambda \tau}=\frac{\lambda\psi_m(\lambda)}{\pi_m},\quad \lambda \ge0.$$
\end{block}
}
%----------------------------------------------------------------------------------------17
\frame{\small

Let $\tau_{k}$ be the hitting time of state $k$.

\begin{block}{Lemma(Y. Gong, Y.H. Mao \& C. Zhang(2012))}For the continuous time birth death process $X_t$, let
$$
\phi_{im}(\lambda)=0,\ \phi_{ij}(\lambda)=\int_0^\infty e^{-\lambda t}\mathbb P[X_t=j,t<\tau_m|X_0=i]dt$$
for $0\le i,j<m$ and
$$
\psi_{ij}(\lambda)=\int_0^\infty e^{-\lambda t}\mathbb P[X_t=j|X_0=i]dt
$$
for $0\le i,j\le m$. It holds that for $0\le i,j\le m$
$$
\psi_{ij}(\lambda)=\phi_{ij}(\lambda)+\frac{ \xi_i(\lambda)\pi_j \xi_j(\lambda)}{\lambda\sum_{i=0}^m\pi_i \xi_i(\lambda)},
$$
where $\xi_i(\lambda)=\mathbb E[e^{-\lambda\tau_m}|X_0=i]$.
\end{block}
}
%----------------------------------------------------------------------------------------18
\frame{\small

\begin{block}{Theorem} For the continuous-time birth and death process starting at $0$,
$$
\mathbb E e^{-\lambda \tau}=\bigg(\pi_0+\sum_{k=1}^n\pi_k\bigg(\mathbb E e^{-\lambda\tau_k}\bigg)^{-1}\bigg)^{-1},\ \lambda \ge0.
$$
\end{block}

$$
\mathbb E\tau=\sum_{i=0}^m\pi_i\mathbb E\tau_i,\
\mathbb E\tau^2=2(\mathbb E\tau)^2+\sum_{i=0}^m\pi_i\mathbb E\tau_i^2-2\sum_{i=0}^m\pi_i(\mathbb E\tau_i)^2.
$$
$$
\mathbb E\tau_i=\sum_{j=0}^{i-1}\frac1{\pi_jb_j}\sum_{k=0}^j\pi_k,\
\mathbb E\tau_i^2=2(\mathbb E\tau_i)^2-2\sum_{j=0}^{i-1}\frac 1{\pi_jb_j}\sum_{k=0}^j\pi_k\mathbb E\tau_k.
$$
$$
\mathbb E\tau=\sum_{i=0}^m\frac 1{\pi_ib_i}\sum_{j=0}^i\pi_j\sum_{j=i+1}^m\pi_j,
\mathbb E\tau^2=2(\mathbb E\tau)^2-2\sum_{i=0}^m\pi_i\sum_{j=0}^{i-1}\frac 1{\pi_jb_j}\sum_{k=0}^j\pi_k\mathbb E\tau_k.
$$
}
%----------------------------------------------------------------------------------------19
\frame{\small

Let
$$
S=(\mathbb E\tau)^2-\frac 12\mathbb E\tau^2=\sum_{i=0}^m\pi_i\sum_{j=0}^{i-1}\frac1{\pi_jb_j}\sum_{k=0}^j\pi_k
\sum_{u=0}^{k-1}\frac 1{\pi_ub_u}\sum_{v=0}^u\pi_v.
$$
and exchange the first summation and the second one, then exchange the third one and the forth one.
}
%----------------------------------------------------------------------------------------20
\frame{\frametitle{5. Applications -Restricted chains}\small

Let $a_i (i\ge1), b_i (i\ge 0)$ be the death and birth rates respectively for the continuous time
birth and death processes on $\{0,1,\dots\}$. For each $n=1,2,\dots$, a restricted process $X_t^{(n)}$ on $\{0,1,\dots, n\}$
 is referred to a birth and death process with birth rates $b_i^{(n)}=b_i$ for $0\le i\le n-1$ and $b_n^{(n)}=0$,
 and death rates $a_i^{(n)}= a_i$ for $1\le i\le n$. Then $X_t^{(n)}$ is ergodic with reflecting boundary at $n$.

\begin{block}{Corollary 1}
Assume that $X_t$ is exponential ergodic. Then $X_t^{(n)}$ has separation cutoff if and only if $X_t$ is not strong ergodic.
\end{block}
}
%----------------------------------------------------------------------------------------21
\frame{\small

Proof Let $\lambda_1$ be the spectral gap for $X_t$ and $\lambda_1>0$ by exponential ergodicity. Let $\lambda_1^{(n)}$ as before. Then
$\lim_{n\to\infty}\lambda_1^{(n)}=\lambda_1$.

$$\aligned
\sum_{i=0}^\infty\frac 1{\pi_ib_i}\sum_{j=i+1}^\infty\pi_j&\ge
\lim_{n\to\infty}T^{(n)}=T=\sum_{i=0}^\infty\frac 1{\pi_ib_i}\sum_{j=0}^i\pi_j\sum_{j=i+1}^\infty\pi_j\\
&\ge\pi_0\sum_{i=0}^\infty\frac1{\pi_ib_i}\sum_{j=i+1}^\infty\pi_j.
\endaligned$$
But the birth and death process is not strongly ergodic if and only if
$$
\sum_{i=0}^\infty\frac1{\pi_ib_i}\sum_{j=i+1}^\infty\pi_j=\infty.
$$
Therefore, the non-strong ergodicity is equivalent to  $\lim_{n\to\infty}\lambda_1^{(n)}T^{(n)}=\infty$.  Diaconis \& Saloff-Coste(2006).
}
%----------------------------------------------------------------------------------------22
\frame{\small
\begin{block}{Example 1}

Let $a_i=a,b_i=b$.

(1) If $a>b>0$, then $\lambda_1=(\sqrt a-\sqrt b)^2$. Thus this process is exponentially ergodic, but not strongly ergodic,
so that by Corollary 1 there is separation cutoff for the restricted chains.

(2) If $b\ge a>0$, the process is transient. In this case, we cannot apply Corollary 1. Instead, we apply
Theorem 2. For $\beta:=b/a>1$, we have
$$
Z=\frac{\beta^{m+1}-1}{\beta-1},\ \pi_i=\frac{\beta^i}{Z};
$$
A direct and tedious calculation implies the separation cutoff occurs.

(3) For $a=b$, we have $\pi_i=1/m$. Again an easy calculation shows that there is no separation cutoff.
\end{block}
}
%----------------------------------------------------------------------------------------23
\frame{\small
\begin{block}{Example 2}

Let $a_i=ai^\gamma, b_i=b$ with $\gamma\ge0, a,b>0$. Then
there is separation cutoff for the restricted chains if and only if $\gamma\in [0,1]$.
\end{block}
}

%----------------------------------------------------------------------------------------24
\frame{\frametitle{5. Applications -Metropolis algorithm}\small
For each $m=1,2,\dots$, a Metropolis chain on $\{0,1,\dots,m\}$ is formulated as follows:
for $1\le i\le m$, $a_i=1/2$ when $\pi_{i-1}/\pi_i\ge1$, $a_i=\pi_{i-1}/\pi_i$ when $\pi_{i-1}/\pi_i<1$;
for $0\le i\le m-1$, $b_i=1/2$ when $\pi_{i+1}/\pi_i\ge1$,
$b_i=\pi_{i+1}/\pi_i$ when $\pi_{i+1}/\pi_i<1$.

\begin{block}{Corollary 2}
Let $\pi_i=(i+1)^d/Z$ with $d\in\mathbb R$, where $Z$ makes $\pi$ a probability measure. For
a family of Metropolis chains on  $\{0,1,\dots,m\}$ defined as above, there is no separation cutoff.
\end{block}

\begin{block}{Corollary 3}
Let $\pi_i=\beta^i/Z$ with $\beta>0$, where $Z$ makes $\pi$ a probability measure. For
a family of Metropolis chains on $\{0,1,\dots,m\}$ defined as above, there is separation cutoff except $\beta=1$.
\end{block}
}
%----------------------------------------------------------------------------------------25
\frame{ \frametitle{6. FSST of single birth chains}\small

Since the birth and death chain is symmetric, its eigenvalues are real. But for a general skip-free chains, eigenvalues may be
complex.

\begin{block}{Theorem(Fill(2009))}
For an ergodic continuous-time single birth chain on the state space $\{0,\dots, N\}$ started at $0$ with stochastically
monotone time-reversal, let $Q$ be the generator. Then a fastest strong stationary time $\tau$ has the distribution
$$
\mathbb E e^{-\lambda \tau}=\prod_{\nu=1}^N\frac{\lambda_\nu}{\lambda+\lambda_\nu},\ \lambda\ge0,
$$
\end{block}
}
%----------------------------------------------------------------------------------------26
\frame{ \frametitle{7. Explicit criteria for SB chains -Duality}\small


Set for $0\le i\le m, H_i=\sum_{j\le i}\pi_j$ and for $i\le m-1$
$$
\tilde q_{ij}=\frac{\pi_jq_{ji}}{\pi_i},$$
$$q_{ij}^*=\frac{H_j}{H_i}\sum_{k\le i}(\tilde q_{jk}-\tilde q_{j+1,k}), \ i\le m-1; q_{mm}^*=0.$$
Let $Q^*$ be a single birth $Q$-matrix with an absorbing state $m$. Assume both $X(t)$ and $X^*(t)$ start at $0$.
Then the absorption time (hitting time to $m$) of $X^*(t)$  has the same distribution as the FSST $\tau$ of $X(t)$.

$$Q^*\Lambda=\Lambda Q,\ \Lambda=(\Lambda_{ij}), \Lambda_{ij}=\frac{H_j}{H_i}\mathbf 1_{[j\le i]}.$$
}
%----------------------------------------------------------------------------------------27
\frame{ \frametitle{8. Explicit criteria for SB chains -Stochastic monotonicity}\small

\begin{block}{Theorem} Assume the single birth chain on the state space  $E=\{0,1,\dots, N\}$, started at $0$, has the stochastically monotone
time-reversal. Let $\tau$ be a FSST and $P(t)=(P_i(t))$ be the distribution of $X_t$. Then

(1) $\mathbb P[\tau>t]=1-P_N(t)/\pi_N$;

(2)
$$ \mathbb E e^{-\lambda \tau}=\frac{\lambda}{\pi_N}\int_0^\infty e^{-\lambda t}P_N(t)dt,\ \lambda \ge0.$$
\end{block}

$$
p_{0N}(t)/\pi_N=p_{N0}^*(t)/\pi_0=\min_{i}p_{i0}^*(t)/\pi_0=\min_i p_{0i}(t)/\pi_i.
$$

$$
1-P_N(t)/\pi_N=\max_{j}(1-P_j(t)/\pi_j)=\text{sep}(P(t),\pi)=\mathbb P[\tau>t].
$$
}
%----------------------------------------------------------------------------------------28
\frame{\small

Let $\tau_{k}$ be the hitting time of state $k$.

\begin{block}{Lemma}For the continuous time single birth process $X_t$ on $\{0,1,\dots,N\}$, let
$$
\phi_{iN}(\lambda)=0,\ \phi_{ij}(\lambda)=\int_0^\infty e^{-\lambda t}\mathbb P_i[X_t=j,t<\tau_N]dt$$
for $0\le i,j<N$ and
$$
\psi_{ij}(\lambda)=\int_0^\infty e^{-\lambda t}\mathbb P_i[X_t=j]dt
$$
for $0\le i,j\le N$. It holds that for $0\le i,j\le N$
$$
\psi_{ij}(\lambda)=\phi_{ij}(\lambda)+\frac{ \xi_i(\lambda)\eta_j(\lambda)}{\lambda\sum_{j=0}^N\eta_j(\lambda)},
$$
where $\xi_i(\lambda)=1-\lambda\sum_{k=0}^{N-1}\phi_{ik}(\lambda), \eta_j(\lambda)=\pi_j-\lambda\sum_{k=0}^{N-1}\pi_k\phi_{kj}(\lambda)$.
\end{block}
}
%----------------------------------------------------------------------------------------29
\frame{\small

\begin{block}{Theorem} For the continuous-time single birth process with the stochastically monotone time-reversal, started at $0$,
$$
\mathbb E e^{-\lambda \tau}=\bigg(\pi_0+\sum_{k=1}^n\pi_k\bigg(\mathbb E_0 e^{-\lambda\tau_k}\bigg)^{-1}\bigg)^{-1},\ \lambda \ge0.
$$
\end{block}

$$
\mathbb E\tau=\sum_{i=0}^m\pi_i\mathbb E\tau_i,\
\mathbb E\tau^2=2(\mathbb E\tau)^2+\sum_{i=0}^m\pi_i\mathbb E_0\tau_i^2-2\sum_{i=0}^m\pi_i(\mathbb E_0\tau_i)^2.
$$
}
%----------------------------------------------------------------------------------------30
\frame{\small
For $0\le k<i\le N$, define
$q_i^{(k)}=\sum_{j=0}^kq_{ij}$, and
$$
F_i^{(i)}=1,\ F_i^{(k)}=\sum_{j=k+1}^{i}\frac{F_i^{(j)}q_{j}^{(k)}}{q_{j,j+1}}.
$$
$$
m_i=\sum_{k=0}^i\frac{F_i^{(k)}}{q_{k,k+1}}, \ 0\le i\le N.
$$
Here we set $q_{N,N+1}=1$ for saving notations and convenience. By induction, it is easy to check that
$$
F_i^{(k)}=\frac 1{q_{i,i+1}}\sum_{j=k}^{i-1}q_i^{(j)}F_j^{(k)}, \ 0\le k<i\le N;
$$
and
$$
m_i=\frac 1{q_{i,i+1}}\left(1+\sum_{0\le j\le i-1}q_i^{(j)}m_j\right), \ 0\le i\le N.
$$
}
%----------------------------------------------------------------------------------------31
\frame{\small
\begin{block}{Theorem} For $j<i$, we have
$$
\mathbb E_j\tau_i=\sum_{k=j}^{i-1}m_k, \
\mathbb E_j\tau_i^2=2\sum_{k=j}^{i-1}\sum_{\ell=0}^k\frac{F_k^{(\ell)}}{q_{\ell,\ell+1}}\mathbb E_\ell\tau_i.
$$
$$
\mathbb E_0\tau_i=\sum_{k=0}^{i-1}m_k, \
\mathbb E_0\tau_i^2=2(\mathbb E_0\tau_i)^2-2\sum_{k=0}^{i-1}\sum_{\ell=0}^k\frac{F_k^{(\ell)}}{q_{\ell,\ell+1}}\mathbb E_0\tau_\ell.
$$
For $i<j\le N$, we have
$$\mathbb E_j\tau_i=\sum_{k=i}^{j-1}\left(\frac{m_N}{F_N^{(i)}}F_k^{(i)}-m_k\right),$$
$$\mathbb E_j\tau_i^2=2\sum_{k=i}^{j-1}\left(\frac{F_k^{(i)}}{F_N^{(i)}}\sum_{\ell=0}^N\frac{F_N^{(\ell)}}{q_{\ell,\ell+1}}
\mathbb E_\ell\tau_i-\sum_{\ell=0}^k\frac{F_k^{(\ell)}}{q_{\ell,\ell+1}}\mathbb E_\ell\tau_i\right).
$$
\end{block}
}
%----------------------------------------------------------------------------------------32
\frame{\small

$$\pi_i=\frac{F_N^{(i)}}{q_{i,i+1}m_N}, \ 0\le i\le N.$$

\begin{block}{Proposition}
The time-reversal $\tilde Q$ is stochastically monotone iff
$$
\sum_{k\ge j}\frac{F_N^{(k)}q_{ki}}{q_{k,k+1}}\le \frac{q_{i+1,i+2}F_N^{(i)}}{q_{i,i+1}F_N^{(i+1)}}\sum_{k\ge j}
\frac{F_N^{(k)}q_{k,i+1}}{q_{k,k+1}},\  i+1<j\le N.
$$
\end{block}
\begin{block}{Corollary}
Assume that $q_{i,i+1}\equiv 1$. If $F_N^{(i)}\ge F_N^{(i+1)}$ for all $i< N-1$ and $q_{ki}\le q_{k,i+1}$ for all $k>i+1$,
then the time-reversal is stochastically monotone.
\end{block}
}

%----------------------------------------------------------------------------------------33
\frame{\small
$$
\mathbb E\tau^2=2(\mathbb E\tau)^2-2\sum_{i=0}^N\pi_i\sum_{j=0}^{i-1}\sum_{k=0}^j\frac{F_j^{(k)}}{q_{k,k+1}}\mathbb E_0\tau_k.
$$
Let
$$T=\mathbb E\tau=\sum_{i=0}^N\pi_i\sum_{j=0}^{i-1}m_j,\
S=\sum_{i=0}^N\pi_i\sum_{j=0}^{i-1}\sum_{k=0}^j\frac{F_j^{(k)}}{q_{k,k+1}}\mathbb E_0\tau_k.
$$
We have
$$
\frac{\mathbb E\tau^2}{(\mathbb E\tau)^2}=2-2\frac{S}{(\mathbb E\tau)^2}=2-2\frac{S}{T^2}.
$$
}
%----------------------------------------------------------------------------------------34
\frame{\small
\begin{block}{Theorem}
For each $n$, assume the skip-free chain on $\{0,1,\dots,N_n\}$ started at $0$, with the stochastically
monotone time-reversal and  $T^{(n)}$ and $S^{(n)}$ defined similarly (with $N_n$ in the place of $N$).
Then there is a separation cutoff with $t_n=T^{(n)}$  iff
$$
\lim_{n\to\infty}\frac{S^{(n)}}{[T^{(n)}]^2}=\frac12.
$$
\end{block}
\begin{block}{Corollary}
For each $n=1,2,\dots$, let $Q^{(n)}=(q_{ij}^{(n)})$ be the generator for a
 single birth chains on $\{0,1,\dots,N_n\}$ stared at $0$. Assume that
$q_{i,i+1}^{(n)}=1$ for $1\le i\le N_n-1$ and $q_{ki}^{(n)}\le q_{k,i+1}^{(n)}$ for $k> i+1$.
If there is $C>0$ and $\beta>1$ such that $F_i^{(j)}\sim C\beta^{i-j}$ as $i-j\to\infty$, then
 there is a separation cutoff.
\end{block}
}
%----------------------------------------------------------------------------------------35
\frame{ \small

\begin{block}{Examples}
(1) Let $q_{i,i+1}=q_{i,i-1}= q_{i,i-2}=1$. Then the chain exhibits the separation cutoff.

$$F_{i}^{(j)}\sim C(\sqrt 2+1)^{i-j}.$$

(2) Let $q_{i,i+1}=1, q_{ij}=1/i$ for $0\le j<i$. Then the chain exhibits the separation cutoff.
$$F_i^{(j)}\sim 2^{i-j-1}.$$

(3) Let $q_{i,i+1}=1, q_{ij}=(1-p)p^{i-j-1} (1\le j<i), q_{i0}=p^i$ for $i\ge0$. Then the chain exhibits the separation cutoff
if $0<p\le (\sqrt 5-1)/2$.

$$F_i^{(j)}=(1+p)^{i-j-1}.$$
\end{block}
}
%----------------------------------------------------------------------------------------35
\frame{ \small
\begin{itemize}
\item Y.H. Mao, Y.H. Zhang. Explicit criteria for separation cutoff of birth and death chains. Frontiers of Mathematics in China, 2014.
\item Y.H. Mao, C. Zhang, Y.H. Zhang. Separation cutoff for upward skip-free chains.
\end{itemize}
}
%----------------------------------------------------83
\frame{


\centerline{ \emph{\textbf{\color{blue} Thank you for your attention!}}}
\vskip0.5cm
\centerline{Homepage: http://math.bnu.edu.cn/${}^\sim$zhangyh/}

}

\end{CJK*}

\end{document}
