\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}\CJKfamily{hei}
\sf\boldmath


%\textcolor[rgb]{0.00,0.55,0.50}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            题页            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Separation cutoff]{Separation cutoff for skip-free upwardly chains}

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

\date[June 19, 2015]{\wuhao (June 19, 2015, Moscow State Lemonosov University) \\
$ $\\ This talk is based on the joint work with Yong-Hua Mao \& 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 Our main results
\item Finite skip-free upwardly chains
\item A general condition for separation cutoff
\item Proof on explicit criterion
\item References
\end{enumerate}
}
%----------------------------------------------------------------------------------------1-1
\frame{ \frametitle{1. Background}\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 for any ``distance'' $D$ between probability measures,
$$ \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}$$
}
%----------------------------------------------------------------------------------------1-2
\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.

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

However separation is easily handled and powerful in the following sense.
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.$$

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

\vskip0.2cm
Aldous \& Diaconis (1987) for the definitions and properties for FSST and Fill(1991) for the existence of FSST.

\vskip0.2cm
Diaconis \& Saloff-Coste(2006) first gave the criteria for
the continuous time or discrete time birth and death chains, these criteria involves all the
eigenvalues of each chain.

\vskip0.2cm
Mao \& Z.(2014) 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.
}


%----------------------------------------------------------------------------------------2-1
\frame{ \frametitle{2. Our main results}\small


In this talk, we study the separation cutoff for the skip-free upwardly chains (or single birth processes). Birth and death chains are special
cases of the skip-free chains.

$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)$$
}
%----------------------------------------------------------------------------------------2-2
\frame{ %\frametitle{2. Our main results}
\small

Let us first recall some basics for the skip-free upwardly chains.

On the finite state space $\{0,1,\dots,N\}$,
let $Q=(q_{ij})$ be the generator of an irreducible and conservative upward skip-free chain.
That is, for $0\le i<N$ and $j>i+1$, $q_{i,i+1}>0, q_{ij}=0$;
and for $0\le i\le N, q_{i}:=-q_{ii}=\sum_{j\ne i}q_{ij}<\infty$.
For $0\le k<i\le N$, define
$
q_i^{(k)}=\sum_{j=0}^kq_{ij}
$, and
$$
F_i^{(i)}=1,\quad F_i^{(k)}=\sum_{j=k+1}^{i}\frac{F_i^{(j)}q_{j}^{(k)}}{q_{j,j+1}}.
$$
Then define
$$
m_i=\sum_{k=0}^i\frac{F_i^{(k)}}{q_{k,k+1}}, \quad 0\le i\le N.
$$

Z.(2013) gives the stationary distribution as follows
$$
\pi_i=\frac{F_N^{(i)}}{q_{i,i+1}m_N}, \quad 0\le i\le N.
$$
}

%----------------------------------------------------------------------------------------2-3
\frame{ \frametitle{2. Our main results}\small

Define
$$
T=\sum_{i=0}^N\pi_i\sum_{j=0}^{i-1}m_j,\quad
S=\sum_{i=0}^N\pi_i\sum_{j=0}^{i-1}\sum_{k=0}^j\frac{F_j^{(k)}}{q_{k,k+1}}\sum_{\ell=0}^{k-1}m_\ell.
$$

\begin{block}{Theorem}
For each $n$, assume that $X_t^{(n)}$ is an upward skip-free chain on $\{0,1,\dots,N_n\}$, started at $0$
and with the stochastically monotone time-reversal.
Define $T^{(n)}$ and $S^{(n)}$ with $N$ replaced by $N_n$.
Then there exists the separation cutoff with $t_n=T^{(n)}$ if and only if
$$
\lim_{n\to\infty}\frac{S^{(n)}}{[T^{(n)}]^2}=\frac12.
$$
\end{block}
}
%----------------------------------------------------------------------------------------2-4
\frame{ \frametitle{2. Our main results}\small

The following corollary gives a useful sufficient condition for separation cutoff.
\begin{block}{Corollary}
For each $n=1,2,\dots$, let $Q^{(n)}=(q_{ij}^{(n)})$ be the generator for a
 skip-free upwardly chains on $\{0,1,\dots,N_n\}$, where
$q_{i,i+1}^{(n)}=1$ for $1\le i< N_n$, 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
the separation cutoff occurs.
\end{block}

$$
m_i\sim \beta^{i+1}/(\beta-1),\quad \pi_i=F_N^{(i)}/m_N\sim(\beta-1)\beta^{-i-1}.
$$

$$
T\sim\frac{N}{\beta-1},\quad S\sim\frac{N^2}{2(\beta-1)^2}.
$$

}


%----------------------------------------------------------------------------------------2-4
\frame{ \frametitle{2. Our main results}\small

Next we would like to present some examples.
We will focus on the restricted chains of a skip-free upwardly chain $X_t$ with generator $Q=(q_{ij})$ on $E=\{0,1,2,\dots\}$.

For an increasing sequence $\{N_n\}$ with limit $\infty$ as $n\to\infty$,
we define a sequence of ergodic chains $\{X_t^{(n)}\}$ as below.
For each $X_t^{(n)}$, let $Q^{(n)}=(q_{ij}^{(n)})$ be its generator satisfying
$q_{ij}^{(n)}=q_{ij}$ ($0\le i\le N_n, 0\le j\le N_n$) except for $q_{N_n,N_n}^{(n)}=-\sum_{j=0}^{N_n-1}q_{N_n,j}$.
Then $X_t^{(n)}$ is a restricted chain of $X_t$ on $\{0,1,\dots,N_n\}$ .

We say that $X_t$ exhibits the separation cutoff if it occurs for the family of restricted chains $\{X_t^{(n)}\}$.
Obviously, the choice of the increasing sequence $\{N_n\}$ going to infinity has no impact on
the occurrence of the separation cutoff for $X_t$.
}

%----------------------------------------------------------------------------------------2-5
\frame{ %\frametitle{2. Our main results}
\small

\begin{block}{Examples}
(1) Let $q_{01}=q_{10}=q_{12}=1$ and $q_{i,i+1}=q_{i,i-1}= q_{i,i-2}=1$, $q_{ii}=-3$ $(i\ge2)$.
Then the skip-free chain exhibits the separation cutoff.

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

(2) Let $q_{i,i+1}=1$ $(i\ge0)$ and $q_{ij}=1/i$ $(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_{i0}=p^i$ $(i\ge0)$, and $q_{ij}=(1-p)p^{i-j-1}$ $(1\le j<i)$.
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}
}
%----------------------------------------------------------------------------------------3-1
\frame{ \frametitle{3. Finite skip-free upwardly chains}\small

Define the time-reversal $\widetilde Q=(\tilde q_{ij})$ of
$Q$ as
$$
\tilde q_{ij}=\frac{\pi_j}{\pi_i}q_{ji}.
$$

\begin{block}{Proposition}
The time-reversal chain of $Q$ is stochastically monotone if and only if
$$
\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}},\quad  i+1<j\le N.
$$
\end{block}
\begin{block}{Corollary}
Assume that $q_{i,i+1}\equiv 1(i\ge 0)$. 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 chain is stochastically monotone.
\end{block}
}
%----------------------------------------------------------------------------------------3-2
\frame{ \frametitle{3. Finite skip-free upwardly chains}\small
Under the assumption that the time-reversal chain is stochastically monotone,
Fill(2009) obtained the following theorem

\begin{block}{Theorem A}
For an ergodic continuous-time skip-free upwardly chain in the state space $\{0,\dots, N\}$ started at $0$ and with stochastically
monotone time-reversal, let $Q$ be the generator. Then the fastest strong stationary time $\tau$ has the distribution
$$
\mathbb E e^{-\lambda \tau}=\prod_{\nu=1}^N\frac{\lambda_\nu}{\lambda+\lambda_\nu},\quad \lambda>0,
$$
where $\lambda_1,\dots,\lambda_N$ are the nonzero eigenvalues of $-Q$.
\end{block}
}
%----------------------------------------------------------------------------------------3-2
\frame{ %\frametitle{3. Finite skip-free upwardly chains}
\small

Define the hitting time of state $k$ as $\tau_k=\inf\{t\ge0: X_t=k\}$.

\begin{block}{Lemma} For the ergodic continuous time upward skip-free chain $X_t$ on $\{0,1,\dots,N\}$, for $0\le i,j<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$$
$$
\psi_{ij}(\lambda)=\int_0^\infty e^{-\lambda t}\mathbb P_i[X_t=j]dt,\quad 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}
}

%----------------------------------------------------------------------------------------4-1
\frame{ \frametitle{4. A general condition for separation cutoff}\small

To use Theorem A(Fill) to derive the criterion, we need the following result.
This result was originated in Diaconis \& Saloff-Coste (2006) and completed recently in Mao \& Z.(2014).

\begin{block}{Proposition B} For each $n$, let $\tau^{(n)}$ be a FSST of the ergodic Markov chains $X_t^{(n)}$. 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 exists the separation cutoff with $t_n=\mathbb E\tau^{(n)}$ if and only if
$$\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\ \text{as}\ n\to\infty.$$
\end{block}

}
%----------------------------------------------------------------------------------------4-2
\frame{ \frametitle{4. A general condition for separation cutoff}\small

We remark that the integrability condition is natural for Markov chains.
For example, if $X_t^{(n)}$ is a family of upward skip-free chains started at $0$ and
with stochastically monotone time-reversals, then we can easily get from Theorem A that
$$
\mathbb E(\tau^{(n)})^k\le k!(\mathbb E\tau^{(n)})^k, \quad k=1,2,\dots.
$$
}
%----------------------------------------------------------------------------------------5-1
\frame{ \frametitle{5. Proof on explicit criterion}\small
We will obtain the explicit criterion for the separation cutoff of  skip-free upwardly chains
by deriving the explicit expressions of $\mathbb E\tau^{(n)}$ and $\mathbb E(\tau^{(n)})^2$ in Proposition B.


Firstly, we study the distribution of the FSST in the following theorem.

\begin{block}{Theorem} Assume that $X_t$ is an ergodic skip-free upwardly chain on $\{0,1,\dots, N\}$, started at $0$ and with the stochastically monotone
time-reversal. Let $\tau$ be a FSST and $P_i(t)=\mathbb P_0[X_t=i]$ for $0\le i\le N$. 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}

}

%----------------------------------------------------------------------------------------5-2
\frame{ \frametitle{5. Proof on explicit criterion}\small

Let $p_{ij}(t)=\mathbb P_i[X_t=j]$ and $X_t^*$ be the time-reversal chain of $X_t$. Then
$$
p_{ij}^*(t):=\mathbb P_i[X_t^*=j]=\frac{\pi_jp_{ji}(t)}{\pi_i}.
$$
Since $X_t^*$ is stochastically monotone, we have
$$
p_{0N}(t)/\pi_N=p_{N0}^*(t)/\pi_0=\min_{i}p_{i0}^*(t)/\pi_0=\min_i p_{0i}(t)/\pi_i.
$$
Thus,
$$1-P_N(t)/\pi_N=\max_{i}(1-p_{0i}(t)/\pi_i)=\mathbb P[\tau>t].$$
}

%----------------------------------------------------------------------------------------5-3
\frame{ \frametitle{5. Proof on explicit criterion}\small

To derive the explicit formulas for the moments of the FSST, we need the boundary theory below,
which establishes a relationship between the FSST and the hitting times.

\begin{block}{Theorem} For the chain $X_t$ defined in the theorem above, the Laplace transform of the FSST can be expressed as
$$
\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}
}

%----------------------------------------------------------------------------------------5-4
\frame{ \frametitle{5. Proof on explicit criterion}\small

Now we can deduce the explicit criteria of the separation cutoff.

For the chain $X_t$ in the theorem above, we can obtain the explicit expressions for the moments of the FSST $\tau$ from those of the hitting times $\{\tau_k\}.$

In fact, by taking derivatives twice, we get
$$
\mathbb E\tau=\sum_{i=0}^N\pi_i\mathbb E_0\tau_i,\
\mathbb E\tau^2=2(\mathbb E\tau)^2+\sum_{i=0}^N\pi_i\mathbb E_0\tau_i^2-2\sum_{i=0}^N\pi_i(\mathbb E_0\tau_i)^2.
$$

By Z.(2013),
$$
\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.
$$
}
%----------------------------------------------------------------------------------------5-6
\frame{ \frametitle{5. Proof on explicit criterion}\small
We can easily get that
$$
\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.
$$
Then we have
$$
\frac{\mathbb E\tau^2}{(\mathbb E\tau)^2}=2\bigg(1-\frac{S}{T^2}\bigg).
$$
Thus our criterion follows from Proposition B.
}
%----------------------------------------------------------------------------------------6
\frame{ \frametitle{6. References}\small
1. Aldous, David; Diaconis, Persi. Strong uniform times and finite random walks.
Adv. in Appl. Math. 8 (1987), no. 1, 69--97.

\vskip0.2cm
2. Chen, Guan-Yu; Saloff-Coste, Laurent. The $L^2$-cutoff for reversible Markov processes.
J. Funct. Anal. 258 (2010), no. 7, 2246--2315.

\vskip0.2cm
3. Diaconis, Persi. The cutoff phenomenon in finite Markov chains.
Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659--1664.

\vskip0.2cm
4. Diaconis, Persi; Saloff-Coste, Laurent. Separation cut-offs for birth and death chains.
Ann. Appl. Probab. 16 (2006), no. 4, 2098--2122.

\vskip0.2cm
5. Ding, Jian; Lubetzky, Eyal; Peres, Yuval. Total variation cutoff in birth-and-death chains.
Probab. Theory Related Fields 146 (2010), no. 1-2, 61--85.

}

%----------------------------------------------------------------------------------------6
\frame{ \frametitle{6. References}\small

6. Fill, James Allen. Time to stationarity for a continuous-time Markov chain.
Probab. Engrg. Inform. Sci. 5 (1991), no. 1, 61--76.

\vskip0.2cm
7. Fill, James Allen. On hitting times and fastest strong stationary times for skip-free and more general chains.
J. Theoret. Probab. 22 (2009), no. 3, 587--600.

\vskip0.2cm
8. Mao, Yong-Hua; Zhang, Yu-Hui. Explicit criteria on separation cutoff for birth and death chains.
Fron. Math. China 9 (2014), no. 4, 881--898.

\vskip0.2cm
9. Zhang, Yu-Hui. Expressions on moments of hitting time for single birth processes in infinite and finite spaces.
(Chinese) J. Beijing Normal Univ. 49 (2013), no. 5, 445--452.

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