5.2. Случайная цепь для решения алгебраической системы.
Очевидно, все методы Монте-Карло, приведенные в § 2, применимы для оценки решений уравнения (57) и дают нам возможность оценить решение системы (55). Однако специфика уравнения (57) позволяет упростить эти методы и дать им иную интерпретацию.
Так как
постоянны при
, то естественно выбирать плотности
также постоянными
Величины
очевидно, должны быть неотрицательными и удовлетворять условиям нормировки
Правила (59) можно интерпретировать как равномерное распределение случайной точки внутри соответственно
или
. Можно, однако, совсем отказаться от фиксации положения этой точки и говорить только об отрезке, в котором эта точка расположена. Тогда
— это вероятность того, что начальная точка траектории попадет в
вероятность того, что случайная точка из
перейдет в
. При такой интерпретации вместо траектории
случайной точки достаточно рассмотреть последовательность случайных номеров
тех отрезков
в которые эта точка попадет.
Итак, для решения системы (55) мы будем строить цепь случайных номеров (61), каждый из которых может принимать значения
Правила построения цепи (61):
где начальные вероятности
и вероятности переходов
должны удовлетворять условиям нормировки (60).
В теории вероятностей такие цепи называются цепями Маркова с конечным числом
состояний [71]. Веса
вдоль цепи (61) вычисляются по формуле
или по рекуррентной формуле
Формулы эти — следствие (4) и (5).
Условимся говорить, что распределение вероятностей
допустимо по отношению к вектору
если для тех а, для которых
значение
Аналогично распределение
допустимо по отношению к матрице
если
для тех пар
для которых
Как известно, из теории матриц, для того чтобы
ряд
сходился для любого вектора
необходимо
и достаточно, чтобы все собственные значения
матрицы А, представляющие собой корни уравнения
лежали внутри единичного круга (на комплексной плоскости):
при
. Достаточным условием может служить неравенство
Сформулируем для системы (55) теорему, вытекающую из теоремы
. Пусть бесконечная цепь
строится по правилам (62), где
допустимы по отношению к
соответственно, и рассмотрим случайную величину
Теорема 8. Если все собственные значения
матрицы
по абсолютной величине меньше единицы, то математическое ожидание случайной величины
равно
Повторим доказательство со стр. 177 применительно к рассматриваемому случаю. Так как
то, принимая во внимание (63), получим, что
Затем
причем существование этого математического ожидания обеспечивается условиями теоремы
Если какие-нибудь из элементов матрицы
равны нулю, то обычно целесообразно выбрать соответствующие вероятности перехода
(ср. п. 3.2.1 гл. 3). В противном случае, если в цепи окажется переход
которому отвечает
то из (63) видно, что все
можно считать, что цепь, попав в
останавливается: любые дальнейшие переходы
значения величины
не изменят.
Если матрица А содержит целую строку из нулей:
, то, конечно, нельзя все соответствующие вероятности выбрать нулевыми: это противоречило бы условию (60). Тогда можно положить
при
, так что