Итак, как обещал, начинаю знакомить вас с книгой Дэвида Хенда "Improbability Principle", со своими комментариями. Принцип невероятности --- это набор законов, в результате которых невероятные события, совпадения и т.п. так часто встречаются. О природе случайности и о том, как она работает (а как --- не работает) уже была предварительная заметка.
Закон Очень Больших Чисел (не путать с Законом Больших Чисел!) гласит, что если попыток достаточно много, то маловероятное событие становится вероятным, а то и почти неизбежным.
Удобна такая заготовка для оценок: если вероятность р события мала, а число попыток 1/р, то вероятность не увидеть событие ни одного раза есть (1-р)^(1/р) ~ 1/e ~ 1/3. Тогда вероятность увидеть событие хотя бы один раз где-то в районе 2/3, что уже довольно много. Если попыток вдвое больше, то первая вероятность уже порядка 1/e^2~0.1, а вторая ~0.9.
В этом некоторая проблема малых вероятностей. Скажем, вероятность 0.001 вроде мала, это примерно вероятность выкинуть десять раз монету одной и той же стороной. Вероятность 0.000001 еще меньше, это --- двадцать раз. Если мы увидим, как 20 раз монета падает орлом, мы начнем искать подвох. Да и если десять --- начнем.
Однако тысяча попыток --- это не так и много. Миллион попыток --- и то разумно. К примеру, вероятность попасть в авиакатастрофу --- 1 на миллион (это пример!), но за год совершается несколько миллионов рейсов --- вероятность хотя бы одной катастрофы получается очень велика. Раз мы не видим каждый год по авиакатастрфе, то шанс намного меньше 1 на миллион. И славно!
В чем проблема, спросите вы? Не получается отбросить "хвост". Вероятность вроде бы исчезающе мала, событие невозможно --- но "подожди (не)много", и оно почти неизбежно.
Вот, например, всего раскладов в бридже порядка 5е28 (5 на 10 в степени 28), а раскладов, при котором у одного из игроков все 13 карт одной масти --- порядка 8е16. Вероятность увидеть такой расклад --- около 1.5е-12 (обратная величина --- около 6е11). Вероятность увидеть расклад, при котором у всех четверых все карты одной масти (у каждого своей), составляет 1е-28. По правилам спортивного бриджа, за час играется восемь сдач. Если играет 10 миллионов человек (точнее, "столов", четверок) в течение 10 тысяч часов, то это больше, чем 6е11. Играть два часа в неделю --- это немного. Получается 5000 недель, или около ста лет. Вывод: вероятность, что за сто лет бриджа (возраст игры примерно такой) кому-то приходили все карты одной масти --- весьма велика, не меньше 0.5.
Предельным случаем ЗОЧБ является закон неизбежности: если перебрать все варианты, маловероятное событие неизбежно. Пример: лотерея. Если нет обмана, то скупка всех билетов гарантированно принесет выигрыш. Впрочем, зачем?
Хенд приводит пример, как в 1990-ых одна американская лотерея типа "6 из 44" имела вероятность джекпота 1 к 7`059`052. На скупку всех билетов нужно было порядка 7 миллионов долларов. 15 февраля 1992 джекпот достиг 27 миллионов. Более мелкие призы добавляли еще порядка 900 тысяч. (Как формируется призовой фонд --- я не знаю). Был создан консорциум из нескольких тысяч инвесторов, который скупил все оставшиеся билеты. Порядка двадцати агентов скупали билеты в течение недели. Удалось купить билетов на 5 миллионов --- еще два уже ушли в другие руки. Еще один риск был --- если у кого-то будут те же числа, джекпот придется делить. Кроме того, организаторы придрались к процедуре: по правилам, надо было оплачивать билет при покупке в автомате. Тем не менее, после некоторой нервотрепки, приз был выплачен.
ЗОЧБ для лотерей также справедлив. Шанс выиграть очень мал, верно; однако лотерей много, и играет в них много народу. Если шанс порядка 1 к десяти миллионам, но лотерей, допустим, сто --- то шанс, что кто-то сорвет джекпот, уже более обозрим. Если в каждую играет сто тысяч человек, то выигрыш уже не удивителен. А ведь это всего 10 миллионов человек! Если игроков больше, то и два выигрыша одним человеком уже должны быть зарегистрированы. И да, такие случаи известны. Хенд приводит пример Эвелин Мари Адамс, которая за 4 месяца 1985 дважды выигрывала в лотерею, и еще несколько случаев.
Если вероятность случайного зарождения жизни на планете 1 на миллиард миллиардов... это мало... но в галактике порядка сотен миллирдов звезд... а галактик в видимой Вселенной тоже сотни миллиардов... а за пределами видимой Вселенной, скорее всего, все так же...
Очень Большие Числа могут быть спрятаны в довольно компактных начальных данных. Это явление известно как экспоненциальный взрыв. В комбинаторике --- подсчете числа комбинаций --- число вариантов часто растет очень быстро. Я посвящу несколько заметок этой важной теме. Примером является парадокс дней рождения: вероятность того, что у двоих в компании совпадут дни рождения (день и месяц) выше 0.5, начиная всего с 23 человек. Классы в школе обычно такого размера, так что в половине, не меньше, классов должны найтись дети с одинаковым днем рождения.
Ещё пример экспоненциального взрыва --- число возможных групп из заданного числа человек. Пусть их тридцать --- учеников. Они могут работать по одному: 30 вариантов. По двое: 435 пар. То трое: 4060 троек. И так далее, вплоть до полной команды из 30 человек, которая одна. Полное число вариантов выбрать команду довольно велико: 1`073`741`823 --- более милларда! Для ста человек это число превысит 10^30.
Ну, и линейное программирование: поиск максимума линейной функции при линеных ограничениях. Принципиально все просто: линейные неравенства --- это полупространства, их пересечение --- это многогранник (с натяжкой). Максимум всегда в вершине --- перебор и успех. Но число вершин растет очень быстро. Так быстро, что полный перебор для размерности задачи около нескольких десятков уже невозможен. Есть, впрочем, другие методы...
...Продолжение следует...