Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Это называется линейностью математического ожидания, и это, вероятно, второй по полезности факт во всей теоретической информатике после границы объединения. Опять же самое важное здесь — что любые зависимости между X и Y не имеют значения.

Может быть, выполнятся также и соотношение

E [ XY ] = E[ X ] E[ Y ]?

Разумеется, не выполняется! Впрочем, выполняется, если X и Y независимы, но не в общем случае.

Еще один важный факт — неравенство Маркова (или скорее одно из его многочисленных неравенств): если X ≥ 0 есть неотрицательная случайная переменная, то для любого k

Pr[X≥kE[X]] ≤ 1/k.

Почему? Ну, если бы X слишком часто имело значение, слишком во много раз превосходящее его математическое ожидание, то даже если бы все остальное время X было равно 0, этого все равно было бы недостаточно, чтобы скомпенсировать отклонение матожидания.

Неравенство Маркова сразу же ведет к третьему полезнейшему факту теоретической информатики, известному как граница Чернова. Граница Чернова, по сути, означает, что если вы бросили монетку 1000 раз и при этом 900 раз выпал орел, то очень велики шансы на то, что монетка неправильная. Именно на эту теорему неявно опираются менеджеры казино, когда решают, посылать ли своих горилл ломать ноги игроку после крупного выигрыша.

Теоретически пусть h — число выпадений орла при бросании правильной монетки n раз. Тогда один из способов определить границу Чернова — это

где c — постоянная, которую вы можете уточнить, если не помните. (Ну хорошо, хорошо: c = 2 годится.)

Как мы можем доказать границу Чернова? Ну, есть такой простой фокус: пусть xi = 1, если i-я монетка падает орлом, и xi = 0, если решкой. Рассмотрим математическое ожидание, не самой суммы x1 + … + xn, а ее экспоненты exp (x1 + … + xn). Поскольку броски монетки, по идее, не должны коррелировать между собой, мы имеем

Теперь мы можем просто воспользоваться неравенством Маркова, а затем взять логарифмы обеих сторон, чтобы получить границу Чернова. Я избавлю вас от скучных вычислений (или, скорее, себя избавлю).

Для чего нам нужна случайность?

Даже великие древние — Тьюринг, Шеннон и фон Нейман — понимали, что источник случайных чисел может оказаться полезен при написании программ. Так, к примеру, еще в 1940-е и 1950-е гг. физики придумали метод математического моделирования, названный методом Монте-Карло, для изучения какого-то странного вопроса, который им был в тот момент интересен и который был как-то связан с имплозией, или направленным внутрь взрывом, полых плутониевых шаров. Метод Монте-Карло означает просто сбор информации о типичном или среднем поведении возможно сложной динамической системы не путем явного вычисления средних значений различных интересующих вас величин, а просто путем моделирования системы много раз с различными случайными начальными состояниями и сбора статистических данных. Статистическая выборка — скажем, различных способов, которыми полый плутониевый шар может сделать Большой Бабах, — это совершенно законное использование случайности.

Существует великое множество причин, по которым вам может потребоваться случайность: помешать перехвату шифрованных сообщений, избежать блокировки при работе проколов связи и т. п. Но в пределах теории вычислительной сложности обычное назначение случайности — «размазать ошибку», то есть взять алгоритм, который работает на большинстве входных данных, и превратить его в алгоритм, который работает на всех входных данных большую часть времени.

Посмотрим пример рандомизированного алгоритма (алгоритма с элементом случайности). Предположим, я описываю вам число следующим образом: начинаю с 1 и затем многократно добавляю, вычитаю или умножаю два числа, которые уже были упомянуты ранее (как в карточной игре «24»). Примерно так: