Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources

Shota Saito; Nozomi Miya; Toshiyasu Matsushima

doi:10.1109/ISIT.2015.7282803

Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources

Shota Saito, Nozomi Miya, Toshiyasu Matsushima

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

This paper considers universal lossless variable-length source coding problem and deals with one of the fundamental limits and pointwise asymptotics of the Bayes code for stationary ergodic finite order Markov sources. As investigation of the fundamental limits, we show upper and lower bounds of the minimum rate such that the probability which exceeds it is less than ϵ ϵ (0, 1). Furthermore, we prove that the codeword length ovf the Bayes code satisfies the asymptotic normality (pointwise equation asymptotics) and the law of the iterated logarithm (pointwise equation asymptotics), where n represents length of a source sequence and 'log' is the natural logarithm.

Original language	English
Title of host publication	IEEE International Symposium on Information Theory - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1986-1990
Number of pages	5
Volume	2015-June
ISBN (Print)	9781467377041
DOIs	https://doi.org/10.1109/ISIT.2015.7282803
Publication status	Published - 2015 Sept 28
Event	IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: 2015 Jun 14 → 2015 Jun 19

Other

Other	IEEE International Symposium on Information Theory, ISIT 2015
Country/Territory	Hong Kong
City	Hong Kong
Period	15/6/14 → 15/6/19

ASJC Scopus subject areas

Applied Mathematics
Modelling and Simulation
Theoretical Computer Science
Information Systems

Access to Document

10.1109/ISIT.2015.7282803

Cite this

Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources. / Saito, Shota; Miya, Nozomi; Matsushima, Toshiyasu.
IEEE International Symposium on Information Theory - Proceedings. Vol. 2015-June Institute of Electrical and Electronics Engineers Inc., 2015. p. 1986-1990 7282803.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Saito, S, Miya, N & Matsushima, T 2015, Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources. in IEEE International Symposium on Information Theory - Proceedings. vol. 2015-June, 7282803, Institute of Electrical and Electronics Engineers Inc., pp. 1986-1990, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 15/6/14. https://doi.org/10.1109/ISIT.2015.7282803

@inproceedings{626fa78c0559401aa362f60593898514,

title = "Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources",

abstract = "This paper considers universal lossless variable-length source coding problem and deals with one of the fundamental limits and pointwise asymptotics of the Bayes code for stationary ergodic finite order Markov sources. As investigation of the fundamental limits, we show upper and lower bounds of the minimum rate such that the probability which exceeds it is less than ϵ ϵ (0, 1). Furthermore, we prove that the codeword length ovf the Bayes code satisfies the asymptotic normality (pointwise equation asymptotics) and the law of the iterated logarithm (pointwise equation asymptotics), where n represents length of a source sequence and 'log' is the natural logarithm.",

author = "Shota Saito and Nozomi Miya and Toshiyasu Matsushima",

year = "2015",

month = sep,

day = "28",

doi = "10.1109/ISIT.2015.7282803",

language = "English",

isbn = "9781467377041",

volume = "2015-June",

pages = "1986--1990",

booktitle = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "IEEE International Symposium on Information Theory, ISIT 2015 ; Conference date: 14-06-2015 Through 19-06-2015",

}

TY - GEN

T1 - Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources

AU - Saito, Shota

AU - Miya, Nozomi

AU - Matsushima, Toshiyasu

PY - 2015/9/28

Y1 - 2015/9/28

N2 - This paper considers universal lossless variable-length source coding problem and deals with one of the fundamental limits and pointwise asymptotics of the Bayes code for stationary ergodic finite order Markov sources. As investigation of the fundamental limits, we show upper and lower bounds of the minimum rate such that the probability which exceeds it is less than ϵ ϵ (0, 1). Furthermore, we prove that the codeword length ovf the Bayes code satisfies the asymptotic normality (pointwise equation asymptotics) and the law of the iterated logarithm (pointwise equation asymptotics), where n represents length of a source sequence and 'log' is the natural logarithm.

AB - This paper considers universal lossless variable-length source coding problem and deals with one of the fundamental limits and pointwise asymptotics of the Bayes code for stationary ergodic finite order Markov sources. As investigation of the fundamental limits, we show upper and lower bounds of the minimum rate such that the probability which exceeds it is less than ϵ ϵ (0, 1). Furthermore, we prove that the codeword length ovf the Bayes code satisfies the asymptotic normality (pointwise equation asymptotics) and the law of the iterated logarithm (pointwise equation asymptotics), where n represents length of a source sequence and 'log' is the natural logarithm.

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

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

U2 - 10.1109/ISIT.2015.7282803

DO - 10.1109/ISIT.2015.7282803

M3 - Conference contribution

AN - SCOPUS:84969801339

SN - 9781467377041

VL - 2015-June

SP - 1986

EP - 1990

BT - IEEE International Symposium on Information Theory - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -

Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this