\documentclass[oneside,final,12pt]{book}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{xunicode}

\usepackage{hyperref}
\usepackage{xstring}
\def\rooturl{https://www.math.bgu.ac.il/}
\hyperbaseurl{\rooturl}
\let\hhref\href
\providecommand{\extrahref}[2][]{\LTRfootnote{\LR{\IfBeginWith*{#2}{http}{\nolinkurl{#2}}{\nolinkurl{\rooturl#2}}}}}
\renewcommand{\href}[2]{\IfBeginWith*{#1}{http}{\hhref{#1}{#2}}{\hhref{\rooturl#1}{#2}}\extrahref{#1}}

\usepackage{polyglossia}
\usepackage{longtable}
%% even in English, we sometimes have Hebrew (as in course hours), and we
%% can't add it in :preamble, since it comes after hyperref
%%\usepackage{bidi}
\setdefaultlanguage{english}
\setotherlanguage{hebrew}
%%\setmainfont[Ligatures=TeX]{Libertinus Serif}
\setmainfont[Script=Hebrew,Ligatures=TeX]{LibertinusSerif}[
  UprightFont = *-Regular,
  BoldFont = *-Bold,
  ItalicFont = *-Italic,
  BoldItalicFont = *-BoldItalic,
  Extension = .otf]

\SepMark{‭.}
\robustify\hebrewnumeral
\robustify\Hebrewnumeral
\robustify\Hebrewnumeralfinal

% vim: ft=eruby.tex:



\begin{document}
\pagestyle{empty}
\pagenumbering{gobble}

\begin{center}
\vspace*{\baselineskip}

{\Large Department of Mathematics, BGU}

\vspace*{\baselineskip}

\rule{\textwidth}{1.6pt}\vspace*{-\baselineskip}\vspace*{2pt}
\rule{\textwidth}{0.4pt}\\[\baselineskip]

{\Huge Probability and ergodic theory (PET)}\\[0.2\baselineskip]

\rule{\textwidth}{0.4pt}\vspace*{-\baselineskip}\vspace{3.2pt}
\rule{\textwidth}{1.6pt}\\[\baselineskip]

\textbf{On} \emph{Tuesday, June 13, 2017}
\bigskip

\textbf{At} \emph{10:50 -- 12:00}
\bigskip

\textbf{In} \emph{Math -101}

\vspace*{2\baselineskip}

{\large\scshape Aryeh Kontorovich 
  %
  (BGU)
}
\bigskip

will talk about
\bigskip

{\Large\bfseries Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path\par}
\bigskip

\end{center}
\vfill

\textsc{Abstract:}
We propose a procedure (the first of its kind) for computing a fully
data-dependent interval that traps the mixing time t\_mix of a finite
reversible ergodic Markov chain at a prescribed confidence level. The
interval is computed from a single finite-length sample path from the
Markov chain, and does not require the knowledge of any parameters of
the chain. This stands in contrast to previous approaches, which
either only provide point estimates, or require a reset mechanism, or
additional prior knowledge.

The interval is constructed around the relaxation time t\_relax, which
is strongly related to the mixing time, and the width of the interval
converges to zero roughly
at a sqrt\{n\} rate, where n is the length of the sample path. Upper and
lower bounds are given on the number of samples required to achieve
constant-factor multiplicative accuracy. The lower bounds indicate
that, unless further restrictions are placed on the chain, no
procedure can achieve this accuracy level before seeing each state at
least \textbackslash{}Omega(t\_relax) times on the average. Finally, future
directions of research are identified.

Join work with Daniel Hsu and Csaba Szepesvári








% vim: ft=eruby.tex:


\end{document}

% vim: ft=eruby.tex:
