9/2. Недетерминированное преобразование. Если передача должна продолжаться в течение неопределенно долгого времени, то разнообразие должно беспрерывно поддерживаться и, следовательно, мы имеем случай, отличный от изученного в  8/11, где передача разнообразия Т останавливалась после первого шага 1. Но никакая детерминированная система конечной величины не может иметь бесконечно длинной траектории ( 4/5). Поэтому мы должны рассмотреть более общую форму машины и преобразования - недетерминированную.

1 Ср. подстрочное примечание на стр. 219. - Прим. ред.

До сих пор все наши преобразования были однозначными и изображали, таким образом, детерминированные машины. Некоторое расширение этого было указано в  2/10, и мы можем теперь исследовать возможности, которые нам открываются в случае, когда операнд имеет более чем один образ. Здесь, однако, требуются дополнительные ограничения, чтобы удерживать эти возможности внутри определенных границ, подчиненными некоторому закону. Они не должны становиться совершенно хаотичными. Многочисленные применения находит случай, в котором каждый операнд, вместо того чтобы преобразовываться в определенное новое состояние, может перейти в одно из ряда возможных состояний, причем выбор конкретного состояния осуществляется некоторым способом или процессом, придающим каждому состоянию постоянную вероятность стать образом. Именно неизменность вероятности и обеспечивает ту закономерность или упорядоченность, на которой могут основываться точные высказывания.

Таково, например, преобразование где значение a находится бросанием монеты по правилу: если герб, то a=1, если решетка, то  a = 0. Например, если начальное состояние х равно 4 и бросание монеты дает последовательность РРГГГРГРРГ, то траектория будет иметь вид 4,4,4, 5, 6, 7,7, 8, 8,8, 9. А если бросание монеты даст ГРГГРРРГРР, то траектория будет иметь вид 4,5, 5,6, 7,7,7,7, 8,8,8. Таким образом, недостаточно знать преобразование и начальное состояние, чтобы определить однозначно траекторию, как это было в  2/17; они определяют только некоторое множество траекторий. Данное здесь определение дополнено указаниями, полученными при бросании монеты (ср.  4/19), в результате чего мы и приходим к единственной траектории.

Это преобразование может быть представлено (по образцу ранее употреблявшихся представлений) в следующем виде:

И т.д.
где 1/2 означает, что из состояния 3 система перейдет с вероятностью 1/2  в состояние 3 и с вероятностью 1/2 в состояние 4.

Такое преобразование, и особенно множество траекторий, которое оно может произвести, называют <стохастическим>, чтобы отличить его от однозначного и детерминированного преобразования.

Если из каждого состояния возможно много переходов, такое представление скоро становится неудобным. Более удобным и в основном довольно подходящим представлением является матрица, подобная матрице из  2/10. Матрица строится выписыванием возможных операндов в строку наверху и возможных образов в столбец слева; затем на пересечении столбца i со строкой j записывается вероятность того, что система из состояния i перейдет в состояние j.

В качестве примера рассмотрим только что описанное преобразование. Если система находилась в состоянии 4, а вероятность выпасть гербу при бросании монеты равна 1/2, то вероятность перехода системы в состояние 5 равна  1/2 такова же будет вероятность того, что система останется в состоянии 4:

Все другие переходы имеют вероятность, равную нулю. Так, клетка за клеткой, и строится эта матрица.

Описанная матрица называется матрицей переходных вероятностей, т. е. вероятностей перехода. (Читателю следует иметь в виду, что в литературе более обычна транспонированная форма, при которой строки и столбцы меняются местами; но данная форма имеет существенные преимущества - см., например, упр. 12/8/4, - помимо того, что она соответствует принятым в нашей книге обозначениям.)

Здесь мы обязаны совершенно ясно представлять себе, что мы понимаем под <вероятностью> (см. также  7/4). Мы не только должны ясно представлять себе смысл этого слова, но сам смысл должен быть сформулирован в виде практического, операционального критерия. (Субъективные ощущения <степени уверенности> здесь неприменимы.) Итак, если два наблюдателя несогласны в том, имеет ли нечто <постоянную вероятность>, то какое испытание может разрешить эту трудность?

Вероятность есть частота 1 <"Вероятное" событие есть

1      Такая формулировка является, конечно, грубым упрощением. При большом числе испытаний частота появления какого-либо собы-тия, имеющего заданную вероятность, лишь (и то только как правило) мало отличается от этой вероятности. См. по этому поводу статью А. Н. Колмогорова <Вероятность> в Большой Советской Энциклопедии.- Прим. ред.