BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Statistics
SUMMARY:Optimal prediction of Markov chains without mixing
conditions - Yihong Wu (Yale University)
DTSTART;TZID=Europe/London:20220513T160000
DTEND;TZID=Europe/London:20220513T170000
UID:TALK173321AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/173321
DESCRIPTION:Motivated by practical applications such as autoco
mplete and text generation\, we study the followin
g statistical problem with dependent data: Observi
ng a trajectory of length $n$ from a stationary fi
rst-order Markov chain with $k$ states\, how to pr
edict (the distribution of) the next state? In con
trast to the better-studied parameter estimation p
roblem which relies on assumptions on the mixing t
ime or the minimal probability of the stationary d
istribution\, the prediction problem requires neit
her. This allows for an assumption-free framework
but also results in new technical challenges due t
o the lack of concentration for sample path statis
tics.\n\nFor $3 \\leq k \\leq O(\\sqrt{n})$\, usin
g information-theoretic techniques including\, in
particular\, those rooted in universal compression
\, we show that the optimal rate of Kullback-Leibl
er prediction risk is $\\frac{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. These rates\, slower than the
parametric rate of $O(\\frac{k^2}{n})$\, can be a
ttributed to the memory in the data. To quantify t
he memory effect\, we give a lower bound on the sp
ectral gap that ensures the prediction risk is par
ametric. Extensions to higher-order Markov chains
and Hidden Markov Model will be discussed briefly.
\n\nThis is based on joint work with Yanjun Han an
d Soham Jana: https://arxiv.org/abs/2106.13947
LOCATION:MR12\, Centre for Mathematical Sciences
CONTACT:Qingyuan Zhao
END:VEVENT
END:VCALENDAR