Дискретно-непрерывная математика (стр. 56 )

где F — подмножество номеров столбцов матрицы а с — положительная величина, зависящая от матрицы

IV. Существует натуральное l2 такое, что любая матрица А(р) для является стягивающей матрицей.

Доказательство. Предположим, что выполнено I. Во всякой матрице А(р) найдется столбец, в котором имеется эле­мент, не меньший чем Выберем t такое, что

(22.8.4)

для всех словПусть j — номер столбца матрицы А(р), в котором содержится элемент, не меньший 1/п. Согласно (22.8.4) j-й столбец матрицы А(р) будет состоять только из положитель­ных элементов. Итак, из I следует II. Пусть для некоторого l2 любая матрица удовлетворяет условию III.

Докажем, что матрица А(р) в этом случае будет стягивающей. Предположим обратное. Тогда существует пара строк с номерами i и j такая, что у любого столбца на пересечении с этими строка­ми находятся элементы, один из которых неположительный. В силу этого имеем

где F' — множество всех номеров столбцов, на пересечении кото­рых с i-й строкой находятся ненулевые элементы. Иначе это означает для двух строк ai(p) и аj(р) матрицы что противоречит условию III. Наоборот, если А(р) — стягивающая матрица, то для нее выполнено условие III. Пусть i и j — произвольные строки матрицы А(р). Поскольку А(р) — стягивающая матрица, то найдется столбец с номером k такой, что Пусть F — произвольное подмножество номеров столбцов Тогда либо либо В обоих случаях имеем строгое неравенство

с той разницей, что в первом случае обе суммы заведомо равны нулю, а во втором случае обе суммы заведомо строго меньше единицы. Ввиду конечности порядка матрицы А(р) число различных пар строк i и j и число различных подмножеств F конечно. Следовательно, найдется положительное фигурирующее в условии III. Итак, условия III и IV эквивалентны.

Очевидно, что из условия II вытекает условие IV, следова­тельно, и III.

Пусть выполнено условие IV,Для пары строк столбцов с указанным свойством может оказаться несколько.

Положим

где F — множество номеров таких столбцов, и

Если В — произвольная матрица, для которой определено произведение то

(22.8.5)

Действительно, пусть и

Очевидно, что

Пусть r —номер столбца, на пересечении которого со строками i и j находится элементТогда для общего элемента матрицы получим

Аналогично

Переходя к оценкам, будем иметь

Для произвольных двух строк t1 и t2 и произвольного столбца получим поэтому формула (22.8.5) доказана.

Пусть теперь Тогда любую матрицу можно представить в виде произведения матриц

(22.8.6)

гдеозначает наибольшее

целое число, не превосходящее и каждая матрица

является стягивающей.

Число матриц вида конечно. Поэтому, если обо­значитьто, применяя к (22.8.6) раз соотноше­ние (22.8.5), получим Следовательно, т. е. из условия IV следует условие I.

Пусть — общий элемент матрицы переходов ВА

Определение 22.8.3. ВА А называется эргодическим, если для любой пары строк матрицы переходов и произвольной после­довательности слов возрастающей длины имеет ме­сто соотношепие

Содержательно выполнение эргодического принципа для си­стемы матриц вероятностей переходов ВА означает, что вероят­ность того, что автомат будет находиться в состоянии а после подачи на вход слова р, прине зависит от начального состояния. Более того, эта вероятность не зависит даже от на­чального вектора состояний.

Теорема 22.8.2. Для того чтобы ВА А был эргодическим, необходимо и достаточно, чтобы каждая матрица, вероятностей переходов принадлежала классу регулярных стохастических матриц.

Доказательство. Действительно, предположим противное, тогда существует некоторая матрица которая является иррегулярной. Тогда, очевидно, и матрица является иррегулярной для любогоПоследнее противоречит условию II теоремы 22.8.1. Полученное противоречие доказывает необходи­мость условий теоремы.

Пусть теперь каждая матрица принадлежит классу регулярных стохастических матриц.

Обозначим черезсистему булевских шаблонов матриц вероятностей переходов автомата А и через В(х) — булевский шаблон матрицы А(х). Замыкание системы матриц В относительно булевской операции умножения содержит конечное число матриц. В систему матриц В входят матрицы, содержащие по крайней мере по одному положительному столбцу (из еди­ниц). Обозначим множество таких матриц через М. Пусть, далее, k есть число различных с точностью до перестановки строк матриц из разности

Для завершения доказательства теоремы достаточно показать, что любая матрица принадлежит множеству М.

Очевидно, если для некоторого принадлежит

множеству М, то и будет принадлежать М. Пред-