This paper considers universal lossless variable-length source coding problem and investigates the Bayes code from viewpoints of the distribution of its codeword lengths. First, we show that the codeword lengths of the Bayes code satisfy the asymptotic normality. This study can be seen as the investigation on the asymptotic shape of the distribution of codeword lengths. Second, we show that the codeword lengths of the Bayes code satisfy the law of the iterated logarithm. This study can be seen as the investigation on the asymptotic end points of the distribution of codeword lengths. Moreover, the overflow probability, which represents the bottom of the distribution of codeword lengths, is studied for the Bayes code. We derive upper and lower bounds of the infimum of a threshold on the overflow probability under the condition that the overflow probability does not exceed ε∈(0,1). We also analyze the necessary and sufficient condition on a threshold for the overflow probability of the Bayes code to approach zero asymptotically.
Shota SAITO
Waseda University
Nozomi MIYA
Waseda University
Toshiyasu MATSUSHIMA
Waseda University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Shota SAITO, Nozomi MIYA, Toshiyasu MATSUSHIMA, "Evaluation of the Bayes Code from Viewpoints of the Distribution of Its Codeword Lengths" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 12, pp. 2407-2414, December 2015, doi: 10.1587/transfun.E98.A.2407.
Abstract: This paper considers universal lossless variable-length source coding problem and investigates the Bayes code from viewpoints of the distribution of its codeword lengths. First, we show that the codeword lengths of the Bayes code satisfy the asymptotic normality. This study can be seen as the investigation on the asymptotic shape of the distribution of codeword lengths. Second, we show that the codeword lengths of the Bayes code satisfy the law of the iterated logarithm. This study can be seen as the investigation on the asymptotic end points of the distribution of codeword lengths. Moreover, the overflow probability, which represents the bottom of the distribution of codeword lengths, is studied for the Bayes code. We derive upper and lower bounds of the infimum of a threshold on the overflow probability under the condition that the overflow probability does not exceed ε∈(0,1). We also analyze the necessary and sufficient condition on a threshold for the overflow probability of the Bayes code to approach zero asymptotically.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.2407/_p
Copy
@ARTICLE{e98-a_12_2407,
author={Shota SAITO, Nozomi MIYA, Toshiyasu MATSUSHIMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Evaluation of the Bayes Code from Viewpoints of the Distribution of Its Codeword Lengths},
year={2015},
volume={E98-A},
number={12},
pages={2407-2414},
abstract={This paper considers universal lossless variable-length source coding problem and investigates the Bayes code from viewpoints of the distribution of its codeword lengths. First, we show that the codeword lengths of the Bayes code satisfy the asymptotic normality. This study can be seen as the investigation on the asymptotic shape of the distribution of codeword lengths. Second, we show that the codeword lengths of the Bayes code satisfy the law of the iterated logarithm. This study can be seen as the investigation on the asymptotic end points of the distribution of codeword lengths. Moreover, the overflow probability, which represents the bottom of the distribution of codeword lengths, is studied for the Bayes code. We derive upper and lower bounds of the infimum of a threshold on the overflow probability under the condition that the overflow probability does not exceed ε∈(0,1). We also analyze the necessary and sufficient condition on a threshold for the overflow probability of the Bayes code to approach zero asymptotically.},
keywords={},
doi={10.1587/transfun.E98.A.2407},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Evaluation of the Bayes Code from Viewpoints of the Distribution of Its Codeword Lengths
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2407
EP - 2414
AU - Shota SAITO
AU - Nozomi MIYA
AU - Toshiyasu MATSUSHIMA
PY - 2015
DO - 10.1587/transfun.E98.A.2407
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2015
AB - This paper considers universal lossless variable-length source coding problem and investigates the Bayes code from viewpoints of the distribution of its codeword lengths. First, we show that the codeword lengths of the Bayes code satisfy the asymptotic normality. This study can be seen as the investigation on the asymptotic shape of the distribution of codeword lengths. Second, we show that the codeword lengths of the Bayes code satisfy the law of the iterated logarithm. This study can be seen as the investigation on the asymptotic end points of the distribution of codeword lengths. Moreover, the overflow probability, which represents the bottom of the distribution of codeword lengths, is studied for the Bayes code. We derive upper and lower bounds of the infimum of a threshold on the overflow probability under the condition that the overflow probability does not exceed ε∈(0,1). We also analyze the necessary and sufficient condition on a threshold for the overflow probability of the Bayes code to approach zero asymptotically.
ER -