Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Minimax redundancy for Markov chains with large state space   For any Markov source, there exist universal codes whose normalized
codelength approaches the Shannon limit asymptotically as the number of samples
goes to infinity. This paper investigates how fast the gap between the
normalized codelength of the "best" universal compressor and the Shannon limit
(i.e. the compression redundancy) vanishes non-asymptotically in terms of the
alphabet size and mixing time of the Markov source. We show that, for Markov
sources whose relaxation time is at least $1 + \frac{(2+c)}{\sqrt{k}}$, where
$k$ is the state space size (and $c>0$ is a constant), the phase transition for
the number of samples required to achieve vanishing compression redundancy is
precisely $\Theta(k^2)$.

26
The categories of this paper are: bayes-an
16
The categories of this paper are: stat
11
The categories of this paper are: hep-lat
22
The categories of this paper are: chao-dyn
17
The categories of this paper are: q-fin
9
The categories of this paper are: nlin
7
The categories of this paper are: hep-th
30
The categories of this paper are: q-alg
24
The categories of this paper are: dg-ga
28
The categories of this paper are: alg-geom
37
The categories of this paper are: supr-con
29
The categories of this paper are: funct-an
3
The categories of this paper are: physics
35
The categories of this paper are: mtrl-th
31
The categories of this paper are: ao-sci
34
The categories of this paper are: chem-ph