============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

  Manhã de Combinatória Extremal e Métodos Probabilísticos
============================================================

Título:      Tight inequalities among set hitting times in 
             Markov chains 
            
Palestrante: Simon Griffiths
             Instituto de Matemática Pura e Aplicada

Hora e Data: 10h50m, quarta-feira, 31 de outubro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

Given an irreducible discrete-time  Markov chain on a finite
state space,  we consider the largest  expected hitting time
T(\alpha) of a set of  stationary measure at least \alpha,
0 < \alpha < 1.  We describe tight relationships between the
values  of T(\alpha)  for  different choices  of \alpha.  In
particular we prove for all  \alpha < 1/2 that 

      T(\alpha) \le T(1/2)/\alpha.  

A corollary is  that, if the chain is  reversible, T(1/2) is
equivalent to the total  variation mixing time of the chain,
answering a question of Peres.

Based  on  joint  work  with Ross  Kang,  Roberto  Imbuzeiro
Oliveira and Viresh Patel.