BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Optimal prediction of Markov chains without mixing conditions - Yi
 hong Wu (Yale University)
DTSTART:20220513T150000Z
DTEND:20220513T160000Z
UID:TALK173321@talks.cam.ac.uk
CONTACT:Qingyuan Zhao
DESCRIPTION:Motivated by practical applications such as autocomplete and t
 ext generation\, we study the following statistical problem with dependent
  data: Observing a trajectory of length $n$ from a stationary first-order 
 Markov chain with $k$ states\, how to predict (the distribution of) the ne
 xt state? In contrast to the better-studied parameter estimation problem w
 hich relies on assumptions on the mixing time or the minimal probability o
 f the stationary distribution\, the prediction problem requires neither. T
 his allows for an assumption-free framework but also results in new techni
 cal challenges due to the lack of concentration for sample path statistics
 .\n\nFor $3 \\leq k \\leq O(\\sqrt{n})$\, using information-theoretic tech
 niques including\, in particular\, those rooted in universal compression\,
  we show that the optimal rate of Kullback-Leibler prediction risk is $\\f
 rac{k^2}{n}\\log \\frac{n}{k^2}$\, in contrast to the optimal rate of $\\f
 rac{\\log \\log n}{n}$ for $k=2$ previously shown by Falahatgar et al. The
 se rates\, slower than the parametric rate of $O(\\frac{k^2}{n})$\, can be
  attributed to the memory in the data. To quantify the memory effect\, we 
 give a lower bound on the spectral gap that ensures the prediction risk is
  parametric. Extensions to higher-order Markov chains and Hidden Markov Mo
 del will be discussed briefly.\n\nThis is based on joint work with Yanjun 
 Han and Soham Jana: https://arxiv.org/abs/2106.13947
LOCATION:MR12\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR