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

Estimating the entropy based on data is one of the prototypical problems indistribution property testing and estimation. For estimating the Shannonentropy 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 ispossible if and only if the sample size $n$ far exceeds $\frac{S}{\log S}$. Inthis paper we consider the problem of estimating the entropy rate of astationary 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 relaxationtime is at most $O(\frac{S}{\ln^3 S})$, consistent estimation is achievablewhen $n \gg \frac{S^2}{\log S}$.  (2) As long as the Markov chain has some slight dependency, i.e., therelaxation time is at least $1+\Omega(\frac{\ln^2 S}{\sqrt{S}})$, consistentestimation 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 raterequires at least $\Omega(S^2)$ samples to be consistent, even when the Markovchain is memoryless. In addition to synthetic experiments, we also apply theestimators that achieve the optimal sample complexity to estimate the entropyrate of the English language in the Penn Treebank and the Google One BillionWords corpora, which provides a natural benchmark for language modeling andrelates it directly to the widely used perplexity measure.

Entropy Rate Estimation for Markov Chains with Large State Space