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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Large deviation theory is a branch of probability theory that is devoted to astudy of the "rate" at which empirical estimates of various quantities convergeto their true values. The object of study in this paper is the rate at whichestimates of the doublet frequencies of a Markov chain over a finite alphabetconverge to their true values. In case the Markov process is actually ani.i.d.\ process, the rate function turns out to be the relative entropy (orKullback-Leibler divergence) between the true and the estimated probabilityvectors. This result is a special case of a very general result known asSanov's theorem and dates back to 1957. Moreover, since the introduction of the"method of types" by Csisz\'{a}r and his co-workers during the 1980s, the proofof this version of Sanov's theorem has been "elementary," using somecombinatorial arguments. However, when the i.i.d.\ process is replaced by aMarkov process, the available proofs are far more complex. The main objectiveof this paper is therefore to present a first-principles derivation of the LDPfor finite state Markov chains, using only simple combinatorial arguments(e.g.\ the method of types), thus gathering in one place various arguments andestimates that are scattered over the literature.

An Elementary Derivation of the Large Deviation Rate Function for Finite State Markov Chains