ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
Том 58
2022
Вып. 2
УДК 621.391 : 517.938 : 519.722
© 2022 г.
Г.Д. Дворкин
ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЭНТРОПИИ ДЛЯ СИСТЕМ ДИКА
Рассматривается связь метрической энтропии с локальной скоростью дефор-
мации границ (ЛСДГ) в символическом случае. Показывается равенство ЛСДГ
как предела в среднем и энтропии для широкого класса мер на системах Дика.
Ключевые слова: метрическая энтропия, локальная скорость деформации гра-
ниц, символическая система, несинхронизованная система, инвариантная эрго-
дическая мера, правильная скобочная последовательность, система Дика.
DOI: 10.31857/S0555292322020041, EDN: DZCGLF
§ 1. Введение
Будем рассматривать энтропию Колмогорова - Синая как предел некоторой ве-
личины (скорости деформации границ), имеющей простой геометрический смысл.
Такое представление энтропии будем называть геометрической интерпретацией.
Этот подход был предложен физиком Г.М. Заславским [1], который в 1984 г. вы-
двинул гипотезу (точнее, сформулировал утверждение), что объем границы множе-
ства в фазовом пространстве растет экспоненциально по времени с показателем, рав-
ным метрической энтропии. Первый математический результат в этом направлении
был получен Б.М. Гуревичем [2] для символических марковских систем и совмест-
но с С.А. Комечем [3,4] обобщен на существенно более широкий класс символических
систем, а также на некоторые гладкие (системы Аносова). В настоящей статье пока-
зывается возможность геометрической интерпретации энтропии для важного класса
несинхронизованных систем, называемого системами (сдвигами) Дика.
Статья является продолжением работы автора [5], в которой рассматривалась
геометрическая интерпретация энтропии для систем Дика, но лишь в контексте
одной конкретной меры. Здесь же показывается возможность такого подхода для
широкого класса мер на сдвигах Дика. Вместе с тем, результаты из [5] и настоящей
статьи независимы (см. замечание 2).
§ 2. Определения и обозначения
Пусть A - конечное множество, и пусть AZ - пространство бесконечных двусто-
ронних последовательностей символов из A.
Множество A будем называть алфавитом, а любую конечную последовательность
символов (букв) из A - (конечным) словом этого алфавита. Количество букв в сло-
ве w называют его длиной и обозначают |w|. Слово нулевой длины называют пустым.
Элементы AZ будем называть бесконечными словами, при этом в данной терми-
нологии бесконечные слова словами не являются.
Определение 1. Назовем полным сдвигом пару (AZ,T), где A - конечное мно-
жество, a T - сдвиг на шаг вправо в пространстве последовательностей AZ.
41
Для x ∈ AZ и целых a и b, таких что a ≤ b, обозначим слово (x(a), x(a + 1),
...,x(b)) через x[a;b]. Если слово w равно x[a;b] для некоторых a и b, то будем го-
ворить, что w является подсловом бесконечного слова x (аналогично определяется
подслово конечного слова). Вместо x[a;a] будем писать x[a].
Введем метрику d на AZ: примем d(x, x) = 0, а для несовпадающих точек x и y
положим d(x, y) = (1/2)m, где m = m(x, y) - целое неотрицательное число, равное
нулю, если x[0] = y[0], и удовлетворяющее условиям x[-(m-1);m-1] = y[-(m-1);m-1],
x[-m;m] = y[-m;m] в противном случае. Эта метрика порождает топологию, которая
далее считается фиксированной.
Определение 2. Будем называть символической системой пару (X,T), где
X - замкнутое T-инвариантное подмножество AZ с индуцированной топологией,
а также первый элемент этой пары, считая сдвиг и топологию заданными по умол-
чанию.
Пусть далее в этом параграфе X - символическая система.
Множество всех подслов всех x ∈ X называется языком символической систе-
мы X и обозначается W (X); кроме того, обозначим через Wn(X) множество всех
слов из языка длины n. Префикс слова - любое его подслово, начинающееся с начала
этого слова. Суффикс слова - любое его подслово, заканчивающееся в конце этого
слова.
Определение 3. Множество
{
}
{w}Xc :=
x∈X : x[c;c+|w|-1] =w
называется цилиндром в X с основанием w ∈ W (X). Всюду далее
{
}
{
}
{w}c := {w}Xc,
x[a;b]
:=
x[a;b]
a
Рассмотрим T -инвариантную борелевскую вероятностную меру μ на X. Под ме-
рой μ(w) слова w ∈ W (X) понимаем меру цилиндра {w}0 (из T -инвариантности
меры очевидно, что μ({w}a) = μ({w}0) для любого целого a).
Введем следующие обозначения:
k(ε) := max{ℓ ∈ Z : (1/2)(ℓ+1) ≤ ε} (часто будем писать просто k);
Oε(x) - открытая ε-окрестность точки x в рассматриваемом пространстве;
Oε(C) - открытая ε-окрестность множества C в рассматриваемом пространстве.
Определение 4. Метрическая энтропия (энтропия Колмогорова-Синая)
символической динамической системы (X, T ) с инвариантной мерой μ может быть
определена как средняя условная энтропия настоящего при условии прошлого (об-
щее определение для произвольной динамической системы см. в [6, 7]):
hμ(X, T) = lim
Hμ(x0 |x-1, x-2, . . . , x-n).
n→∞
Определение 5. Для x ∈ X определим локальную скорость деформации гра-
ниц (ЛСДГ):
(
)))
1
(μ(O
ε
Tn(ε)(Oε(x))
PX,T,μ(x) := lim
log
,
ε→0 n(ε)
μ(Oε(x))
где n(ε) - положительная целочисленная функция со свойствами
n(ε) → ∞ и n(ε) = o(| log(ε)|) = o(k(ε)) при ε → 0
(часто будем писать просто n). Такие функции n будем называть медленными. До-
предельное выражение будем обозначать через PεX,T,μ(x) и называть ε-ЛСДГ.
42
Определение 6. Символическая система X синхронизована, если она транзи-
тивна и существует w ∈ W (X), такое что для любых u, v ∈ W (X), если uw, wv ∈
∈ W(X), то и uwv ∈ W(X). Такое слово w называется волшебным или синхронизу-
ющим.
Определение 7. Слово w ∈ W(X) назовем n-синхронизующим, если для лю-
бых u, v ∈ Wn(X) условие uw ∈ W (X) и wv ∈ W (X) влечет uwv ∈ W (X).
Определение 8. Полная правильная скобочная последовательность (расста-
новка) - конечная последовательность скобок, приводящаяся к пустому слову путем
сокращения стоящих подряд открывающей и закрывающей скобок одного вида. На-
пример, в случае двух видов скобок сокращать можно только “( )” и “[ ]”. Здесь
и далее тип скобки - открывающая или закрывающая, вид - круглая, квадратная
и т.д.
Определение 9. Правильная скобочная последовательность (расстановка) -
конечная последовательность скобок, являющаяся подсловом некоторой полной пра-
вильной скобочной расстановки.
Определение 10. m-язык Дика - язык, состоящий из правильных скобочных
последовательностей скобок m видов.
Определение 11. Сдвиг Дика - символическая система, языком которой яв-
ляется язык Дика.
Эта система транзитивна, но несинхронизована (см. [8]).
Далее рассматриваем систему Дика с m ≥ 2 видами скобок.
Будем использовать для i-й открывающей скобки обозначение αi, а для i-й за-
крывающей - βi. Обозначим также множество всех открывающих скобок через α,
а закрывающих - через β. Кроме того, при наличии меры μ ∈ M0 на системе Дика
будем считать, что
∑
∑
μ(α) :=
μ(αi), μ(β) :=
μ(βi).
i=1
i=1
Понятно, что μ(α) + μ(β) = 1.
Пусть w - слово языка Дика. Скобка, сокращающаяся вместе с данной при опи-
санном выше процессе сокращения, называется парной к ней в этом слове. Скобка,
для которой нет парной в w, называется непарной в w. Положим
• n1 = n1(w) - количество открывающих скобок в слове w, для которых в этом
слове есть парная закрывающая;
• n2 = n2(w) - количество непарных скобок в w.
Очевидно, |w| = 2n1 + n2.
Приведенным видом слова w будем называть слово, получающееся из w сокраще-
нием всех парных скобок. Более подробно, алгоритм получения приведенного вида
слова w = a1a2 . . . an, где каждое ai ∈ α ∪ β, следующий: на первом шаге из w уда-
ляются все пары последовательных скобок ai, ai+1 такие, что ai = αj и ai+1 = βj
для некоторого j. После удаления получается новое слово w1, для которого повто-
ряется то же действие, и так далее. Процесс завершается, когда после некоторого
шага с номером s пар скобок для удаления не остается. Полученное на этом шаге
слово ws и называется приведенным видом слова w.
Из алгоритма ясно, что приведенный вид всегда является конкатенацией слова,
состоящего только из закрывающих скобок, и слова, состоящего только из открыва-
ющих. Например: )]]]) + [[[[(([ или ))]]]] + ((((((, где символ + формально обозначает
конкатенацию. Также полезно заметить, что приведенный вид слова w является
пустым словом тогда и только тогда, когда само слово w - полная правильная ско-
бочная последовательность.
43
Через H(w) обозначим разность количества открывающих и закрывающих ско-
бок в слове w, т.е.
∑∑
H (w) :=
(δαj ,wi - δβj ,wi ),
i=1 j=1
где δx,y - символ Кронекера, т.е. функция, равная 1, если x = y, и 0 в противном
случае.
Через Hj(w) обозначим такую же разность, но только по j-му виду скобок:
∑
Hj(w) := (δαj,wi - δβj,wi ).
i=1
§ 3. Обзор основных результатов
Пусть M(X) - некоторый подкласс класса борелевских вероятностных инвари-
антных эргодических мер на символической динамической системе (X, T ) (весь этот
класс будем обозначать через M0(X)). Во всех случаях, когда из контекста будет
ясно, что такое X, будем писать просто M и M0.
Связь между энтропией и ЛСДГ в разных системах может быть различной и мо-
жет формально выражаться одним из следующих утверждений.
Точечная гипотеза (ТГ). PX,T,μ(x) = h(μ,X,T) для всех μ ∈ M(X), любой
медленной функции n(ε), любого x ∈ X.
Обобщенная точечная гипотеза (ОТГ). PX,T,μ(x) = h(μ,X,T) для всех
μ ∈ M(X), любой медленной функции n(ε), μ-почти любого x ∈ X.
Основная гипотеза (ОГ). PX,T,μ(x) = h(μ,X,T) для всех μ ∈ M(X), любой
медленной функции n(ε), где выражение в левой части понимается как предел
в L1(X, μ).
ТГ очевидным образом влечет ОТГ и ОГ, при этом ОТГ и ОГ, вообще говоря,
друг из друга не вытекают и не влекут ТГ.
Точечная и обобщенная точечная гипотезы верны для многих важных систем
(ТГ, например, выполняется для автоморфизмов тора с мерой Лебега, а утвержде-
ния, близкие к ОТГ, верны для существенно более общих диффеоморфизмов Ано-
сова с мерой Синая - Рюэлля - Боуэна; подробнее cм. в [4]), но, как показано в [5],
неверны даже для класса бернуллиевских мер на полном сдвиге (контрпримером
может служить любая несимметричная бернуллиевская мера при достаточно мед-
ленном росте функции n(ε)).
Основная гипотеза, в отличие от двух других, подтверждается для многих сим-
волических систем. Наиболее сильный результат в этом направлении получен в [5]:
Теорема 1. Пусть символическая динамическая система (X,T) и борелевская
T-инвариантная эргодическая вероятностная мера μ на X удовлетворяют сле-
дующему условию: в X имеется синхронизованный подсдвиг L (T -инвариантное
замкнутое подмножество) полной меры, обладающий хотя бы одним волшебным
словом положительной меры. Тогда для X и μ верна основная гипотеза.
В [5] также показано, что условия теоремы 1 не являются необходимыми для
выполнения основной гипотезы. Это продемонстрировано на примере конкретной
меры на сдвиге Дика. При этом возникает общий вопрос о возможности геометри-
ческой интерпретации энтропии для произвольной меры μ ∈ M0 на системе Дика.
Этот вопрос и изучается ниже.
44
§4. Основная теорема для систем Дика
Теорема 2. Пусть (X,T,μ) - сдвиг Дика с борелевской вероятностной T-ин-
вариантной эргодической мерой μ, для которой μ(α) = μ(β). Тогда для этой си-
стемы верна основная гипотеза.
Доказательство. Здесь, как и в [5], будем пользоваться достаточным усло-
вием выполнения основной гипотезы для борелевских вероятностных инвариантных
эргодических мер на символических системах (доказано Комечем в [3]), а именно:
для справедливости основной гипотезы достаточно, чтобы для k = k(ε) и для любой
медленной функции n = n(ε) было выполнено
μ(Eε) ---→ 1,
(1)
ε→0
где
{
(
)
{
}}
Eε = x ∈ X : Oε
Tn(Oε(x))
=
Tnx[-k+n;k]
Зафиксируем x ∈ X и ε > 0. Заметим несколько важных фактов.
Во-первых, если x[-k;k-n] - n-синхронизующее слово, то x ∈ Eε. Действительно,
⋃
Oε(Tn(Oε(x))) =
{uTnx[-k+n;k]},
u
где объединение берется по всем словам u ∈ Wn(X), таким что ux[-k;k-n]x[k-n+1;k] ∈
∈ W(X), но так как слово x[-k;k-n] - n-синхронизующее, то это объединение всех
допустимых цилиндров вида {uTnx[-k+n;k]}, u ∈ Wn(X), которое, очевидно, равно
{Tnx[-k+n;k]}.
Во-вторых, любое слово w, приведенный вид которого содержит не менее n скобок
хотя бы одного типа (открывающие, закрывающие), является n-синхронизующим.
Действительно, если в приведенном виде не менее n открывающих скобок, то все
закрывающие скобки в любом слове v из определения n-синхронизованности будут
иметь пару в wv. Теперь предположим, что для некоторых u и v из определения
s := uwv запрещено. Это означает, что пару в s составили скобки разных видов
в том смысле, что после сокращения всех парных скобок по соседству оказались
открывающая и закрывающая скобка (именно в таком порядке), вид которых не
совпадает. Из разрешенности слов uw и wv следует, что внутри этих слов такая
пара образоваться не может, а значит, остается единственная возможность: откры-
вающая скобка лежит в u, а закрывающая - в v, но и такое невозможно, поскольку
все закрывающие скобки из v имеют пару в wv - противоречие, которое и показы-
вает, что слово w является n-синхронизующим. Случай, когда в приведенном виде
содержится не менее n закрывающих скобок, симметричен.
В-третьих, если |H(x[-k;k-n])| ≥ n, то приведенный вид x[-k;k-n] содержит не
меньше n скобок хотя бы одного типа - простое следствие того, что функция H не
меняется при парном сокращении скобок.
Из этих трех замечаний заключаем, что |H(x[-k;k-n])| ≥ n влечет x ∈ Eε.
Теперь воспользуемся эргодической теоремой для индикатора множества β. По-
лучим, что для почти каждого x ∈ X
∑
1
I(wi ∈ β) ---→ μ(β),
(2)
2k - n + 1
ε→0
i=-k
где w = x[-k;k-n].
45
Учтем очевидные равенства:
∑
∑
I(wi ∈ α) +
I(wi ∈ β) = 2k - n + 1
i=-k
i=-k
и
∑
∑
I(wi ∈ α) -
I(wi ∈ β) = H(w),
i=-k
i=-k
откуда
∑
1
I(wi ∈ β) =
(2k - n + 1 - H(w)),
2
i=-k
а значит,
(
)
∑
1
1
H (w)
I(wi ∈ β) =
1-
2k - n + 1
2
2k - n + 1
i=-k
Подставляя это в (2), получим
H (x[-k;k-n])
lim
= 1 - 2μ(β) := c.
ε→0
2k - n + 1
Из условий μ(α) + μ(β) = 1 и μ(α) = μ(β) следует, что 1 - 2μ(β) = μ(α) - μ(β) = 0,
т.е. c = 0. Также понятно, что c ∈ [-1; 1].
Воспользуемся очевидным фактом: если функция стремится к положительному
пределу κ в точке z, то для любого τ < 1 существует окрестность точки z, в которой
1
эта функция не меньше τκ, в частности, это верно для τ =
. Отсюда получаем,
2
что для почти любого x ∈ X существует положительное число γ(x), такое что для
всех ε ∈ (0; γ(x)] выполнено
(
)
1
≥
H
x[-k;k-n]
|c|(2k - n + 1) ≥ n.
(3)
2
Здесь учтено, что n мало относительно k, а значит, и относительно 2k - n + 1.
Согласно замеченному выше из неравенства (3) вытекает, что x ∈ Eε для всех
ε ∈ (0;γ(x)]. Обозначим множество полной меры, на котором корректно опреде-
лено γ(x), через S. Пусть Γε := {x ∈ S : ⋃(x) ≥ ε}. Понятно, что совокупность Γε
монотонно возрастает при убывании ε, а
Γε = S, значит,
ε>0
μ(Γε) ---→ 1.
ε→0
Кроме того, Γε ⊆ Eε, откуда
μ(Eε) ---→ 1,
ε→0
что и завершает доказательство. ▴
Замечание 1. Повторив рассуждения для функции Hj(w) вместо H(w), можно
ослабить дополнительное условие теоремы до μ(αj) = μ(βj) для некоторого j.
46
Замечание 2. Нетрудно понять, что меры, отвечающие условиям теоремы, суще-
ствуют и в некотором смысле составляют большинство среди борелевских вероят-
ностных T -инвариантных эргодических мер. В частности, обе меры максимальной
энтропии отвечают условиям теоремы.
С другой стороны, для важной меры, рассматриваемой автором в [5], не выполня-
ются даже ослабленные условия из замечания 1 (там все скобки имеют одинаковую
меру).
СПИСОК ЛИТЕРАТУРЫ
1. Заславский Г.М. Стохастичность динамических систем. М.: Наука, 1984.
2. Gurevich B.M. Geometric Interpretation of Entropy for Random Processes // Sinai’s Moscow
Seminar on Dynamical Systems. Providence, RI: Amer. Math. Soc., 1996. P. 81-87.
3. Комеч С.А. Скорость искажения границы в синхронизованных системах: геометриче-
ский смысл энтропии // Пробл. передачи информ. 2012. Т. 48. № 1. С. 15-25. http:
//mi.mathnet.ru/ppi2065
4. Гуревич Б.М., Комеч C.А. Скорость деформации границ в системах Аносова и близких
02011X
5. Дворкин Г.Д. Геометрическая интерпретация энтропии: новые результаты // Пробл.
030062
6. Синай Я.Г. О понятии энтропии динамической системы // ДАН СССР. 1959. Т. 124.
С. 768-771.
7. Корнфельд И.П., Синай Я.Г., Фомин С.В. Эргодическая теория. М.: Наука, 1980.
8. Meyerovitch T. Tail Invariant Measures of the Dyck-Shift and Non-sofic Systems. Master
Thesis. Tel-Aviv Univ., Israel, 2004.
Дворкин Григорий Дмитриевич
Поступила в редакцию
Московский государственный университет
13.09.2021
им. М.В. Ломоносова, механико-математический факультет,
После доработки
кафедра математической статистики и случайных процессов
25.11.2021
grisha230531415@gmail.com
Принята к публикации
26.11.2021
47
