§1. Физические датчики: откуда берут живую случайность

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

Договоримся о главном герое. Пусть $\eta_1, \eta_2, \dots$ — координаты точек, взятых наудачу из отрезка $[0,1]$: независимые и равномерно распределённые (помнишь равномерное из первой главы — «тычешь пальцем, не глядя»). Вот такой ровный поток «наугад из $[0,1]$» нам и нужен как сырьё.

Проблема. Как построить числовую последовательность $y_1, y_2, \dots$, которую можно было бы считать реализацией случайных величин $\eta_1, \eta_2, \dots$?

Числа такой последовательности называют псевдослучайными, а устройства или алгоритмы, которые их выдают, — датчиками (ещё говорят «генераторы»). По-нашему: датчик — это станок, который штампует случайность на поток. В этом параграфе — про станки железные, физические.

Рулетка — самый честный станок

Простейший физический датчик — это, считай, рулетка. Представь стрелку, которая крутится вокруг оси почти без трения, а её конец бегает по окружности длиной ровно 1. Раскрутил от души — стрелка покрутилась и встала где попало. Запиши, в каком месте окружности застыл кончик (отмеряя от нуля по кругу) — вот тебе и число $y \in [0,1)$.

Почему это честно? Потому что у хорошо раскрученной стрелки нет любимого места — ей всё равно, где останавливаться. Любой кусочек окружности она ловит с шансом, равным длине этого кусочка. А это ровно и есть определение равномерного распределения на $[0,1]$. Крутани барабан на районе — где шарик ляжет, там и ляжет, блата нет.

Монетка строит число по битам

Рулетка — красиво, но есть способ получить случайное число вообще из одной кривой монеты. И тут всплывает важное утверждение, ради которого стоит потерпеть одну формулу.

Любое число $\eta$ из $[0,1]$ можно записать в двоичном виде — как сумму половинок, четвертинок, восьмушек и так далее:

где каждый $\zeta_i$ — это $0$ или $1$ (двоичный разряд). Разберём по кирпичикам, тут всё просто:

• $2^{-i}$ — это $\tfrac12, \tfrac14, \tfrac18, \dots$ — вес $i$-го разряда. Первый бит стоит половину, второй — четверть, и дальше всё мельче.
• $\zeta_i$ — включён разряд или нет: $1$ — прибавляем его вес, $0$ — пропускаем.
• $\sum$ — складываем все включённые веса. Получается число где-то в $[0,1]$.

По-дворовому: представь, что набираешь сумму монетами разного номинала — рубль, полтинник, четвертак… только тут номиналы $\tfrac12, \tfrac14, \tfrac18$. Каждый бит решает, кладём эту «монетку» в кучу или нет.

А теперь сам факт: число $\eta$ будет равномерным на $[0,1]$ тогда и только тогда, когда его биты $\zeta_1, \zeta_2, \dots$ — это схема Бернулли с $p = 1/2$ (независимые, и каждый с шансом $1/2$ оказаться единицей). Схему Бернулли мы как раз разобрали в первой главе — «выгорело/спалился» с честной монетой.

Отсюда рецепт в лоб: хочешь псевдослучайное число — подбрось симметричную монету $n$ раз. Выпал герб на $i$-м броске — прибавь $2^{-i}$. Получишь число с точностью до $2^{-n}$ (чем больше бросков, тем больше знаков после запятой). Пощупаем руками — вот этот рецепт в коде, жми Run:

Среднее липнет к $0{,}5$ — ровно как положено равномерному на $[0,1]$. Монетка и правда работает датчиком, просто медленно.

Шум в проводах — случайность из помех

Монету подбрасывать долго. Поэтому физики ловят случайность прямо из электрического шума — тех самых помех, что всегда гуляют в проводах.

Берём шумящий сигнал и порог — уровень $C$. Нас интересуют моменты $T_1, T_2, \dots$, когда шум пересекает этот порог (снизу вверх или сверху вниз). А бит $\zeta_i$ назначаем так: внутри каждого такта электронных часов (длины $\Delta t$) смотрим, в первую половину такта случилось пересечение или во вторую — пишем $0$ или $1$. Если такт короче, чем среднее время между пересечениями, биты получаются честные.

По-нашему: помеха скачет как бешеная, предсказать её ты не можешь — вот и снимаем с неё случайные нули-единицы, как подслушиваешь обрывки чужого базара на районе: когда именно долетит слово — заранее не угадаешь.

Почему физику в итоге задвинули

Железные датчики честные, но для работы с компьютером у них три жирных минуса:

1. Нужно спецоборудование — рулетка, шумовая схема, да ещё и настраивать её аккуратно. Не у каждого под рукой.
2. Невоспроизводимость. Прокрутил серию — и всё, ту же самую последовательность $y_1, y_2, \dots$ ты уже не повторишь. А для отладки симуляции это беда: хочется прогнать тот же расклад ещё раз и сравнить. Тот вечер уже не отмотаешь назад.
3. Медленно и несовместимо с компом. Пока железка намотает свои числа, процессор успел бы посчитать миллион. Скорости несоизмеримы.

Из-за этих минусов от чистой физики в вычислениях почти ушли. На замену пришли таблицы случайных чисел (следующий параграф) и, главное, математические датчики — алгоритмы, которые гонят псевдослучайность прямо в процессоре (§3). Там-то и начнётся самое интересное — включая историю про то, как один знаменитый датчик с треском опозорился.

Проверь себя