§ 27. Сохраняющий двоичный шум

Предположим, что у нас есть эксперимент Exp(s) = ááa1, ..., amñ, I(M)I(X(S))sñ и вероятность для детерминированного случая Dμ. Определим шумы, задающие случайное преобразование F : E ® E. Предположим, что каждое атомарное высказывание, значение которого получается в эксперименте, подвергается воздействию независимой и одинаково распределенной двузначной случайной величины L, принимающей значение 1 с вероятностью l > 0.5 и 0 с вероятностью 1-l. Если значения эксперимента представить как двоичный вектор á1, 1, 0, ..., 0, 1ñ, где 1 – истина, а             0 – ложь, то преобразование F : E ® E примет вид:

á1, 1, 0, ..., 0,1ñ Þ ál11, l21, l30, ...,  ln-10, ln1ñ,

где l1, l2, ..., ln – различные независимые случайные величины с распределением L. Эксперимент с преобразованными значениями атомарных высказываний обозначим через FExp(s). Пусть Sμ – вероятность (определение 16) для случайно преобразованного эксперимента.

Теорема 8. Множества вероятностных законов для эксперимента Exp(s) с вероятностью Dμ и эксперимента FExp(s) с вероятностью Sμ равны.

Доказательство. Нужно доказать, что правило C = (A1& ... &Ak Þ A0) является вероятностным законом для эксперимента Exp(s) тогда и только тогда, когда оно является вероятностным законом для эксперимента FExp(s). В стохастическом эксперименте FExp(s) правило l*C примет вид (l1*A1& ... &lk*Ak Þ l0*A0), где l1*, ..., lk*, l0* – случайные величины вида l1 l2 , ..., ln, если литера A1, ..., Ak, A0 не содержит отрицания, или случайные величины вида 1 - l1, 1 - l2 , ..., 1 - ln,  если литера содержит отрицание.

Надо доказать, что правила C = (A1& ... &Ak Þ A0) и l*C = (l1*A1& ... &lk*Ak Þ l0*A0) одновременно либо являются, либо не являются вероятностными законами. Докажем это последовательностью эквивалентных преобразований. Пусть правило l*C является вероятностным законом. Тогда

η(l0*A0 / l1*A1& ... & lk*Ak) > η(l0*A0 / l2*A2& ... & lk*Ak),                                      (1)

для подправила вида 2 (теорема 4) (l2*A2& ... &lk*Ak Þ l0*A0).

Распишем это неравенство:

η(l0*A0 / l1*A1& ... & lk*Ak) = η(l0*A0&l1*A1& ... & lk*Ak) / η(l1*A1& ... & lk*Ak) >

η(l0*A0 / l2*A2& ... & lk*Ak) = η(l0*A0&l2*A2& ... & lk*Ak) / η(l2*A2& ... & lk*Ak).

Рассматривая значения литер A0, A1, ..., Ak, как точку в двоичном кубе, мы можем заменить операцию конъюнкции на умножение. Тогда получим следующее эквивалентное неравенство:

η(l0*A0 · l1*A1 ·...· lk*Ak) / η(l1*A1 ·...· lk*Ak) > η(l0*A0 · l2*A2 ·...· lk*Ak) / η(l2*A2 ·...· lk*Ak).

Это неравенство легко преобразуется эквивалентным образом в силу независимости случайных величин l как между собой так и относительно литер A1, ..., Ak, A0:

η(l0*A0·l1*A1·...·lk*Ak) / η(l1*A1·...·lk*Ak) = η(l0*·l1*·…·lk*·A0·A1·…·Ak) / η(l1*·…·lk*·A1·…·Ak) >

η(l0*A0·l2*A2·...·lk*Ak) / η(l2*A2·...·lk*Ak) = η(l0*·l2*·…·lk*·A0·A2·…·Ak) / η(l2*·…·lk*·A2·…·Ak).

Если два события A, B независимы, то η(A&B) = η(A)η(B). Так как операция · является конъюнкцией, то η(A · B) = η(A)η(B). Отсюда получаем следующее эквивалентное преобразование неравенства:

l0*·l1*·…·lk* η(A0·A1·…·Ak) / l1*·…·lk* η(A1·…·Ak) > l0*·l2*·…·lk* η(A0·A2·…·Ak) / l2*·…·lk* η(A2·…·Ak) Û

η(A0·A1·…·Ak) / η(A1·…·Ak) > η(A0·A2·…·Ak) / η(A2·…·Ak)

Но последнее неравенство и есть то, что нам требуется доказать, а именно вероятностное неравенство, аналогичное неравенству (22), но только относительно правила C, а не правила l*C. Так как последнее неравенство было получено эквивалентными преобразованиями, то обратное так же верно, т. е. если неравенство (22) выполнено для правила C, то оно будет выполнено и для правила l*C. Справедливость аналогичного неравенства относительно других подправил вида 2 (теорема 4) доказывается аналогично. Таким образом справедливость теоремы относительно подправил вида 2 доказана.

Для завершения доказательства теоремы необходимо доказать аналогичное неравенство для подправил вида 1 (теорема 4).

Рассмотрим неравенство

η(l0*A0 / l1*A1 & ... & lk*Ak) > η(Øl1*A1 / l2*A2 & ... & lk*Ak)

Распишем его аналогичным образом. Отрицание Øl1*A1 равно (1-l1*)A1. Но поскольку сама случайная функция l1* есть либо l1, либо 1-l1 в зависимости от наличия либо отсутствия отрицания у атома A1, то обозначение случайной величины Øl1* можно оставить тем же самым, а именно l1*. Поэтому мы получим неравенства

η(l0*A0 / l1*A1 & ... & lk*Ak) = η(l0*A0 & l1*A1 & ... & lk*Ak) / η(l1*A1 & ... & lk*Ak) >

η(l1*A1 / l2*A2 & ... & lk*Ak) = η(l1*A1 & l2*A2 & ... & lk*Ak) / η(l2*A2 & ... & lk*Ak).

Заменим операцию конъюнкции на операцию умножения.

η(l0*A0·l1*A1·...·lk*Ak) / η(l1*A1·...·lk*Ak) > η(l1*A1·l2*A2·...·lk*Ak) / η(l2*A2·...·lk*Ak).

Проведем серию эквивалентных преобразований.

η(l0*A0·l1*A1·...·lk*Ak) / η(l1*A1·...·lk*Ak) = η(l0*·l1*·…·lk*·A0·A1·…·Ak) / η(l1*·…·lk*·A1·…·Ak) >

η(l1*A1·l2*A2·...·lk*Ak) / η(l2*A2·...·lk*Ak) = η(l1*·l2*·…·lk*·A1·A2·…·Ak) / η(l2*·…·lk*·A2·…·Ak).

Отсюда получаем следующие эквивалентные преобразования.

l0*·l1*·…·lk* η(A0·A1·…·Ak) / l1*·…·lk* η(A1·…·Ak) > l1*·l2*·…·lk* η(A1·A2·…·Ak) / l2*·…·lk* η(A2·…·Ak) Û

l0* η(A0·A1·…·Ak) / η(A1·…·Ak) > l1*η(A0·A2·…·Ak) / η(A2·…·Ak)

Так как l0* = l1* = l, то мы получаем требуемое неравенство, так как последнее неравенство и есть то, что нам требуется доказать. Аналогичное доказательство проводится для остальных подправил вида 1 (теорема 4).