Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Entropy Rate Estimation for Markov Chains with Large State Space   Estimating the entropy based on data is one of the prototypical problems in
distribution property testing and estimation. For estimating the Shannon
entropy of a distribution on $S$ elements with independent samples,
[Paninski2004] showed that the sample complexity is sublinear in $S$, and
[Valiant--Valiant2011] showed that consistent estimation of Shannon entropy is
possible if and only if the sample size $n$ far exceeds $\frac{S}{\log S}$. In
this paper we consider the problem of estimating the entropy rate of a
stationary reversible Markov chain with $S$ states from a sample path of $n$
observations. We show that:
  (1) As long as the Markov chain mixes not too slowly, i.e., the relaxation
time is at most $O(\frac{S}{\ln^3 S})$, consistent estimation is achievable
when $n \gg \frac{S^2}{\log S}$.
  (2) As long as the Markov chain has some slight dependency, i.e., the
relaxation time is at least $1+\Omega(\frac{\ln^2 S}{\sqrt{S}})$, consistent
estimation is impossible when $n \lesssim \frac{S^2}{\log S}$.
  Under both assumptions, the optimal estimation accuracy is shown to be
$\Theta(\frac{S^2}{n \log S})$. In comparison, the empirical entropy rate
requires at least $\Omega(S^2)$ samples to be consistent, even when the Markov
chain is memoryless. In addition to synthetic experiments, we also apply the
estimators that achieve the optimal sample complexity to estimate the entropy
rate of the English language in the Penn Treebank and the Google One Billion
Words corpora, which provides a natural benchmark for language modeling and
relates it directly to the widely used perplexity measure.

7
The categories of this paper are: hep-th
10
The categories of this paper are: q-bio
3
The categories of this paper are: physics
0
The categories of this paper are: hep-ph
21
The categories of this paper are: adap-org
31
The categories of this paper are: ao-sci
29
The categories of this paper are: funct-an
35
The categories of this paper are: mtrl-th
17
The categories of this paper are: q-fin
27
The categories of this paper are: comp-gas
23
The categories of this paper are: solv-int
20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
19
The categories of this paper are: eess
26
The categories of this paper are: bayes-an
22
The categories of this paper are: chao-dyn