Problems of robustness for universal coding schemes
| dc.creator | V'yugin, V. V. | |
| dc.date | 2008-06-27 | |
| dc.date.accessioned | 2026-07-07T09:47:13Z | |
| dc.date.available | 2026-07-07T09:47:13Z | |
| dc.description | The Lempel-Ziv universal coding scheme is asymptotically optimal for the class of all stationary ergodic sources. A problem of robustness of this property under small violations of ergodicity is studied. A notion of deficiency of algorithmic randomness is used as a measure of disagreement between data sequence and probability measure. We prove that universal compressing schemes from a large class are non-robust in the following sense: if the randomness deficiency grows arbitrarily slowly on initial fragments of an infinite sequence then the property of asymptotic optimality of any universal compressing algorithm can be violated. Lempel-Ziv compressing algorithms are robust on infinite sequences generated by ergodic Markov chains when the randomness deficiency of its initial fragments of length $n$ grows as $o(n)$. | |
| dc.description | 23 pages | |
| dc.identifier | https://arxiv.org/abs/0806.4572 | |
| dc.identifier | http://arxiv.org/abs/0806.4572 | |
| dc.identifier | Problems of Information Transmission, 39 (2003), pp. 32-46 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163797 | |
| dc.subject | Information Theory | |
| dc.subject | Other Computer Science | |
| dc.subject | F.2 | |
| dc.title | Problems of robustness for universal coding schemes | |
| dc.type | text |