Prefixes and the entropy rate for long-range sources

Ioannis Kontoyiannis; Yurii M. Suhov

Prefixes and the entropy rate for long-range sources

Ioannis Kontoyiannis, Yurii M. Suhov

Mathematics

Research output: Contribution to conference › Paper › peer-review

1 Scopus citations

Abstract

The asymptotic a.s.-relation H = lim_n→∞ n log n ÷ Σ_i=1ⁿ L_iⁿ (X) is derived for any finite-valued stationary ergodic process X = (X_n, n ∈ Z) that satisfies a Doeblin-type condition: there exists r ≥ 1 such that ess_xinf P(X_n+r | x_-∞,n) ≥ α > 0. Here, H is the entropy rate of the process X, and L_iⁿ(X) is the length of a shortest prefix in X which is initiated at time i and is not repeated among the prefixes initiated at times j, 1 ≤ i ≠ j ≤ n. The validity of this limiting result was established by Shields in 1989 for i.i.d. processes and also for irreducible aperiodic Markov chains. Under our new condition, we prove that this holds for a wider class of processes, that may have infinite memory.

Original language	English (US)
State	Published - 1994
Event	Proceedings of the 1994 IEEE International Symposium on Information Theory - Trodheim, Norw Duration: Jun 27 1994 → Jul 1 1994

Other

Other	Proceedings of the 1994 IEEE International Symposium on Information Theory
City	Trodheim, Norw
Period	6/27/94 → 7/1/94

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Cite this

@conference{e297990e58964807b2f648ed43b63973,

title = "Prefixes and the entropy rate for long-range sources",

abstract = "The asymptotic a.s.-relation H = limn→∞ n log n ÷ Σi=1n Lin (X) is derived for any finite-valued stationary ergodic process X = (Xn, n ∈ Z) that satisfies a Doeblin-type condition: there exists r ≥ 1 such that essxinf P(Xn+r | x-∞,n) ≥ α > 0. Here, H is the entropy rate of the process X, and Lin(X) is the length of a shortest prefix in X which is initiated at time i and is not repeated among the prefixes initiated at times j, 1 ≤ i ≠ j ≤ n. The validity of this limiting result was established by Shields in 1989 for i.i.d. processes and also for irreducible aperiodic Markov chains. Under our new condition, we prove that this holds for a wider class of processes, that may have infinite memory.",

author = "Ioannis Kontoyiannis and Suhov, {Yurii M.}",

year = "1994",

language = "English (US)",

note = "Proceedings of the 1994 IEEE International Symposium on Information Theory ; Conference date: 27-06-1994 Through 01-07-1994",

}

TY - CONF

T1 - Prefixes and the entropy rate for long-range sources

AU - Kontoyiannis, Ioannis

AU - Suhov, Yurii M.

PY - 1994

Y1 - 1994

N2 - The asymptotic a.s.-relation H = limn→∞ n log n ÷ Σi=1n Lin (X) is derived for any finite-valued stationary ergodic process X = (Xn, n ∈ Z) that satisfies a Doeblin-type condition: there exists r ≥ 1 such that essxinf P(Xn+r | x-∞,n) ≥ α > 0. Here, H is the entropy rate of the process X, and Lin(X) is the length of a shortest prefix in X which is initiated at time i and is not repeated among the prefixes initiated at times j, 1 ≤ i ≠ j ≤ n. The validity of this limiting result was established by Shields in 1989 for i.i.d. processes and also for irreducible aperiodic Markov chains. Under our new condition, we prove that this holds for a wider class of processes, that may have infinite memory.

AB - The asymptotic a.s.-relation H = limn→∞ n log n ÷ Σi=1n Lin (X) is derived for any finite-valued stationary ergodic process X = (Xn, n ∈ Z) that satisfies a Doeblin-type condition: there exists r ≥ 1 such that essxinf P(Xn+r | x-∞,n) ≥ α > 0. Here, H is the entropy rate of the process X, and Lin(X) is the length of a shortest prefix in X which is initiated at time i and is not repeated among the prefixes initiated at times j, 1 ≤ i ≠ j ≤ n. The validity of this limiting result was established by Shields in 1989 for i.i.d. processes and also for irreducible aperiodic Markov chains. Under our new condition, we prove that this holds for a wider class of processes, that may have infinite memory.

UR - http://www.scopus.com/inward/record.url?scp=0028715134&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028715134&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0028715134

T2 - Proceedings of the 1994 IEEE International Symposium on Information Theory

Y2 - 27 June 1994 through 1 July 1994

ER -

Prefixes and the entropy rate for long-range sources

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Cite this