Глава 4. Показательные и нормальные датчики

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

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

Параграфы

• §1. Метод обратной функции — универсальный рецепт: $\xi = F^{-1}(\eta)$ превращает равномерное число в число с законом $F$.
• §2. Распределения экстремальных значений — как ведёт себя максимум выборки и почему пределов всего три типа.
• §3. Показательный датчик без логарифмов — показательный закон из нисходящих серий, вообще без вычисления логарифма.
• §4. Быстрый показательный датчик — один логарифм на целую пачку показательных чисел: гамма-распределение, порядковые статистики, спейсинги.
• §5. Нормальные случайные числа — три способа сварить колокол: формула Хамакера, «двенадцать минус шесть» и точный Бокс — Мюллер.
• §6. Наилучший выбор — задача о разборчивой царевне: пропусти примерно $n/e$ женихов и бери первого, кто лучше всех.

Практика

• Задачи с разборами
• Контрольные вопросы

Что уносим из главы

Любой закон получается из равномерного — вопрос только в цене. Метод обратной функции универсален, но требует считать $F^{-1}$, а это бывает дорого. Поэтому для самых ходовых законов, показательного и нормального, придуманы свои быстрые трюки.

Смысл по-пацански: равномерный датчик — это станок, а всё остальное — сменные штампы к нему. Хороший мастер знает не только как штамповать, но и сколько стоит каждый удар.