English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the following learning problem with dependent data: Observing atrajectory of length $n$ from a stationary Markov chain with $k$ states, thegoal is to predict the next state. For $3 \leq k \leq O(\sqrt{n})$, usingtechniques from universal compression, the optimal prediction risk inKullback-Leibler divergence is shown to be $\Theta(\frac{k^2}{n}\log\frac{n}{k^2})$, in contrast to the optimal rate of $\Theta(\frac{\log \logn}{n})$ for $k=2$ previously shown in Falahatgar et al. (2016). These rates,slower than the parametric rate of $O(\frac{k^2}{n})$, can be attributed to thememory in the data, as the spectral gap of the Markov chain can be arbitrarilysmall. To quantify the memory effect, we study irreducible reversible chainswith a prescribed spectral gap. In addition to characterizing the optimalprediction risk for two states, we show that, as long as the spectral gap isnot excessively small, the prediction risk in the Markov model is$O(\frac{k^2}{n})$, which coincides with that of an iid model with the samenumber of parameters. Extensions to higher-order Markov chains are alsoobtained.

Optimal prediction of Markov chains with and without spectral gap