Проблемы устойчивости универсальных схем сжатия информации

Универсальная схема сжатия информации Зива–Лемпеля является асимптотически оптимальной для произвольных стационарных эргодических источников. Исследуется вопрос устойчивости этого свойства при нарушениях эргодичности источника. В качестве количественной меры согласованности последовательности исходов и вероятностной меры используется понятие дефекта алгоритмической случайности. Доказано, что универсальные алгоритмы сжатия из достаточно широкого класса неустойчивы в том смысле, что достаточно допустить любой небольшой рост дефекта случайности на начальных фрагментах бесконечной последовательности, как свойство асимптотической оптимальности такого алгоритма может нарушиться. Для эргодических марковских цепей конечного порядка схема сжатия Зива–Лемпеля асимптотически устойчива даже при росте дефекта случайности начального фрагмента последовательности длины $n$ порядка $o(n)$.