Abstract | ||
---|---|---|
It has been proved that for all stationary and ergodic processes the average Kolmogorov complexity of the first n observations converges almost surely to its Shannon's conditional entropy. This paper studies the convergence rate of this asymptotic result. In particular, we show that if the process satisfies certain mixing conditions, then a central limit theorem will be respected. Furthermore, we ... |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/TIT.2019.2934454 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
Complexity theory,Convergence,Entropy,Markov processes,Random variables,Turing machines,Indexes | Journal | 66 |
Issue | ISSN | Citations |
2 | 0018-9448 | 0 |
PageRank | References | Authors |
0.34 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Morgane Austern | 1 | 13 | 1.53 |
Arian Maleki | 2 | 803 | 57.52 |