\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]{Separation cutoff: from birth and death chains to single birth processes}

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

\date[May 14, 2014]{\wuhao (May 14, 2014, National University of Kaohsiung) \\
$ $\\ 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 processes
\item Explicit criterion for SBP -Duality
\item Explicit criterion for SBP -Stochastic monotonicity
\end{enumerate}
}
%----------------------------------------------------------------------------------------3-1
\frame{ \frametitle{1. Background}\small

$$\mathbb P_i[X(t)=j]=p_{ij}(t)=\begin{cases} q_{ij}t+o(t),&\text{if}\ j\ne i\\
1-q_it+o(t),&\text{if}\ j=i
\end{cases}\quad \text{as}\quad t\to 0.$$
$$\sum_{j\ne i}q_{ij}\le q_i:=-q_{ii}.
$$

$$\mathbb P_i[\text{the first jump time}\ \eta_1> t]=\text{e}^{-q_it},$$
$$\mathbb P_i[X(\eta_1)=j]=\frac{q_{ij}}{q_i},\quad j\ne i\ \text{if}\ q_i\ne 0.$$

birth and death chain
$$ b_i=q_{i,i+1},\qquad a_i=q_{i,i-1}.$$
}
%----------------------------------------------------------------------------------------3-2
\frame{ \frametitle{1. Background}\small


[ http://jupiter.math.nctu.edu.tw/~gychen/]

所謂的cutoff現象是Aldous和Diaconis在八零年代初期的一項重要發現, 是馬氏過程的一種相變行為:
馬氏過程的機率分佈與其穩定分佈之間的距離,在某個時間點之前會保持在幾乎是最大值的情形,接著在該時間點後距離函數會急速遞減.
一個cutoff現象的典型例子就是洗牌模型.Diaconis和Bayer在1992年針對鴿尾式洗牌法(散射洗牌法)的研究報告中指出,一副撲克牌(52張)的全變量在前五次的洗牌中大致上會保持在1(最大值),
接著在第七次的洗牌後會快速遞減至1/2.這說明了以鴿尾式洗牌法將牌洗至均勻,七次是必需的.
}
%----------------------------------------------------------------------------------------3-3
\frame{\small

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^{(n)}$ at time $t$, its
stationary distribution is $\pi^{(n)}$. Then
$$ \lim_{t\to\infty}D(P^{(n)}(t),\pi^{(n)})=0$$
holds for every $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}

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.

}
%----------------------------------------------------------------------------------------5
\frame{ \frametitle{1. Background}\small

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.$$

\vskip0.2cm
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.

\vskip0.2cm
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.

}
%----------------------------------------------------------------------------------------6
\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}

Let $\xi^{(n)}=\tau^{(n)}/\mathbb E\tau^{(n)}$. Separation cutoff implies that $\xi^{(n)}$ converges to $1$ in probability.
$\lim_{n\to\infty}\mathbb E|\xi^{(n)}-1|^2=0$.
$$
\lim_{n\to\infty}\frac{(\mathbb E\tau^{(n)})^2}{\mathbb E(\tau^{(n)})^2}=\lim_{n\to\infty}\frac{(\mathbb E\xi^{(n)})^2}{\mathbb E(\xi^{(n)})^2}=1.
$$
}
%----------------------------------------------------------------------------------------7-2
\frame{ \frametitle{2. A general condition for separation cutoff}\small

The following Chebyshev type inequality (Feller 1971).
For a non-negative $\xi$ with mean $\mathbb E\xi$ and variance $\text{Var}(\xi)$, we have for any $\epsilon >0$,
$$
\mathbb P[\xi\ge \mathbb E\xi+\epsilon\sqrt{\text{Var}(\xi)}]\le\frac 1{1+\epsilon^2},\ \mathbb P[\xi\le \mathbb E\xi-\epsilon\sqrt{\text{Var}(\xi)}]\le\frac 1{1+\epsilon^2}.$$
Apply this Chebyshev inequality to the sequence of fastest strong stationary times $\tau^{(n)}$ to get that
$$\aligned
\mathbb P[\tau^{(n)}\ge (1+\epsilon )\mathbb E\tau^{(n)}]&=\mathbb P[\tau^{(n)}\ge \mathbb E\tau^{(n)}+
\frac{\epsilon\mathbb E\tau^{(n)}}{\sqrt{\text{Var}(\tau^{(n)})}}\sqrt{\text{Var}(\tau^{(n)})}]\\
&\le \frac 1{1+\epsilon^2\frac{[\mathbb E\tau^{(n)}]^2}{\text{Var}(\tau^{(n)})}}\to 0
\endaligned
$$
and similarly
$$
\mathbb P[\tau^{(n)}\le (1-\epsilon) \mathbb E\tau^{(n)}]\to 0.
$$
}
%----------------------------------------------------------------------------------------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> 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}
}
%----------------------------------------------------------------------------------------5
\frame{\frametitle{6. FSST of single birth processes }\small
Single birth process. 

$Q=(q_{ij}:i,j\ge 0)$: $q_{i,i+1}>0,\ q_{i,i+j}=0,\ i\ge 0,j\ge 2$.
%\vspace{0.3cm}
\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(11,2)
\put(4.9,-0.5){$i$}
\put(3.55,-0.5){$i-1$}
\put(5.55,-0.5){$i+1$}
\put(6.55,0.5){$i+2$}
\put(-0.15,-0.5){$0$}
\put(0.85,-0.5){$1$}
\put(0,0){\line(1,0){11}}
\qbezier(1,0)(3,2)(5,0)
\qbezier(0,0)(2.5,2)(5,0)
\qbezier(4,0)(4.5,2)(5,0)
\qbezier(6,0)(5.5,2)(5,0)
\put(0.15,0.12){\vector(-1,-1){0.1}}
\put(1.12,0.12){\vector(-1,-1){0.1}}
\put(4.1,0.25){\vector(-1,-2){0.1}}
\put(5.9,0.25){\vector(1,-2){0.1}}
\put(0,0){\circle*{0.2}}
\put(1,0){\circle*{0.2}}
\put(4,0){\circle*{0.2}}
\put(5,0){\circle*{0.2}}
\put(6,0){\circle*{0.2}}
\put(7,0){\circle*{0.2}}
\put(9,0){\circle*{0.2}}
\put(10,0){\circle*{0.2}}
\end{picture}
\end{center}

\vskip0.3cm
$$Q=\left(%
\begin{array}{ccccc}
  - & + & 0 & 0 & \cdots \\
  * & - & + & 0 & \cdots \\
  * & * & - & + & \cdots\\
  \vdots & \vdots & \vdots & \vdots & \ddots \\
  \end{array}%
\right)$$
}

%----------------------------------------------------------------------------------------25-1
\frame{ \small

Since the birth and death chain is symmetric, its eigenvalues are real. But for single birth process, eigenvalues may be
complex.

\vskip0.2cm
Fill(2009) obtained the distribution of the FSST for single birth processes (upward skip-free process). 

\vskip0.2cm
To get the FSST, the single birth process is assumed to have the stochastically monotone time-reversal.

$$\hat p_{ij}(t):=\frac{\pi_j p_{ji}(t)}{\pi_i}.$$

$$\sum_{j\ge k}\hat p_{ij}(t)\uparrow\ \text{w.r.t.}\ i\ \text{for all}\ t\ge 0, k.$$
}
%----------------------------------------------------------------------------------------25-2
\frame{ \frametitle{6. FSST of single birth processes}\small

\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 SBP -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 SBP -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}
