З
Задача двух генералов»
Две армии, каждая руководимая своим генералом, готовятся к штурму города. Лагеря этих армий располагаются на двух холмах, разделённых долиной. Единственным способом связи между генералами является отправка посыльных с сообщениями через долину. Но долина занята противником и любой из посыльных может быть перехвачен. Проблема заключается в том, что, генералы заранее (пока была связь) приняли принципиальное решение о штурме, но не согласовали точное время штурма.
Для успешного штурма генералы должны атаковать город одновременно. Штурм, предпринятый только одной армией, приведет к катастрофическим последствиям для атакующих. Требуется найти алгоритм обмена сообщениями, после которого каждый генерал был бы уверен, что они оба атакуют в указанное время.
Отметим, что достичь такого соглашения (в случае надёжного канала связи) очень просто — достаточно одного сообщения с временем начала штурма и одного сообщения, подтверждающего согласие. Сложность задачи заключается в невозможности разработать алгоритм гарантированного обмена этими сообщениями.
Предположим, первый генерал отправляет второму сообщение «Атакуем завтра в девять часов утра». Отправив посыльного, первый генерал не знает, добрался ли посыльный до второго генерала. Не зная, поддержит ли второй генерал его действия, первый может отложить штурм. Зная это, второй генерал может отправить подтверждающее сообщение «Я получил Ваше сообщение и атакую завтра в девять часов утра». Но это сообщение также может быть перехвачено противником. Зная, что первый генерал не начнет штурм без подтверждения, второй генерал также может отложить атаку. Первый генерал может отправить сообщение «Я получил Ваше подтверждение о времени начала штурма», но оно также может быть перехвачено. Быстро становится очевидным, что, сколько бы ни было циклов обмена сообщениями, нет способа гарантированно уведомить обоих генералов о том, что их сообщения получены. Таким образом, задача не имеет решения.
Предположим, что есть некоторая последовательность сообщений, доставленных или перехваченных, которая позволяет обоим генералам гарантированно согласовать время начала штурма. В таком случае существует некоторое минимальное подмножество таких сообщений. Рассмотрим последнее сообщение в этой минимальной последовательности. Так же, как и любое другое сообщение, оно может быть перехвачено. Если оно не будет доставлено, то условие согласованности действий не выполнится, и один из генералов (вероятнее всего, получатель) отложит свою атаку. С точки зрения другого генерала, алгоритм обмена будет соблюден, и он начнет штурм в полной уверенности, что будет поддержан. Таким образом, при использовании заведомо правильного алгоритма, создается ситуация, в которой один генерал штурмует город, а другой — нет. Это противоречит нашему допущению о существовании алгоритма решения задачи.
Прагматичный подход к решению задачи предполагает не полное устранение ненадежности канала, а её сведение к допустимому уровню. Например, первый генерал может отправить сразу 100 посыльных с сообщением, считая, что вероятность перехвата сразу всех посыльных чрезвычайно низка, и затем, не дожидаясь подтверждения, атаковать в указанное время. Однако такой способ, конечно же, не обеспечивает строгой гарантии согласованности действий генералов.
Парадокс лжеца
Парадокс Кантора
Парадоксы в теории вероятности — различного рода парадоксы, возникающие в теории вероятности из-за несовершенства аксиоматики, в частности из-за определения вероятности через вероятность, неопределённости понятия «равновероятные события» и иных пробелов в основаниях данного раздела математики.
Основания возникновения парадоксов
В теории вероятности парадоксы бывают двух типов: первый — когда существует строгое решение в рамках аксиоматики, просто оно не очевидно, и условия задачи таковы, что ведут интуитивное понимание условий в ошибочном ключе, примерами таких парадоксов являются — Петербургский парадокс, Парадокс закона больших чисел Бернулли, Парадокс дней рождения; второй тип — парадоксы, которые основываются на неоднозначной интерпретации аксиоматики теории вероятности, её недоопределённости, их и можно назвать истинными парадоксами. Примеры истинных парадоксов: Проблема Монти Холла, Парадокс двух конвертов, Парадокс Хемпеля, Парадокс Бертрана. Ценность обоих типов парадоксов в том, что они помогают лучше понять суть теории, область её ограничения, глубже понять основания теории, и иногда исследование парадоксов вело к созданию отдельных разделов математики.
Петербургский парадокс
Впервыеэтот парадокс был изложенв «Мемуаре», который знаменитый математик Даниил Бернулли представил Санкт-Петербургской Академии. Предположим, что я бросаю монету и согласен уплатить вам доллар, если выпадет орел. В случае же выпадения решки я бросаю монету второй раз и плачу вам два доллара, если при втором подбрасывании выпадет орел. Если же снова выпадет решка, я бросаю монету в третий раз и плачу вам четыре доллара, если при третьем подбрасывании выпадает орел. Короче говоря, с каждым разом я удваиваю выплачиваемую сумму. Бросать монету я продолжаю до тех пор, пока вы не остановите игру и не предложите мне расплатиться. Какую сумму вы должны заплатить мне, чтобы я согласился играть с вами в эту «одностороннюю игру», а вы не остались в убытке?
В ответ трудно поверить: сколько бы вы мне ни платили за каждую партию, пусть даже по миллиону долларов, вы все равно сможете с лихвой окупить свои расходы. В каждой отдельно взятой партии вероятность того, что вы выиграете один доллар, равна 1/2, вероятность выиграть два доллара равна 1/4, четыре доллара — 1/8 и т.д. В итоге вы можете рассчитывать на выигрыш в сумме (1 x 1/2) + (2 x 1/4) + (4 x 1/8) … Этот бесконечный ряд расходится: его сумма равна бесконечности. Следовательно, независимо от того, какую сумму вы будете выплачивать мне перед каждой партией, проведя достаточно длинный матч, вы непременно окажетесь в выигрыше. Делая такое заключение, мы предполагаем, что мой капитал неограничен и мы можем проводить любое число партий. Разумеется, если вы заплатили за право сыграть одну партию, например 1000 долларов, то с весьма высокой вероятностью вы эту партию проиграете, но ожидание проигрыша с лихвой компенсируется шансом, хотя и небольшим, выиграть астрономическую сумму при выпадении длинной серии из одних лишь орлов. Если же мой капитал, как это имеет место в действительности, ограничен, то и разумная плата за право сыграть партию также должна иметь верхний предел. Петербургский парадокс возникает в любой азартной игре с удваивающимися ставками. Подробный анализ этого парадокса приводит ко всякого рода тонким вопросам обоснования теории вероятностей.
Парадокс дней рождения
Выберем наугад 24 человека. Какова, по вашему мнению, вероятность того, что двое или большее число из них родились в один и тот же день одного и того же месяца (но, быть может, в разные годы)? Интуитивно чувствуется, что вероятность такого события должна быть очень мала. На самом же деле она оказывается равной 27/50, то есть чуть выше 50%!
Вероятность того, что дни рождения любых двух людей не совпадают, очевидно, равна 364/365 (поскольку лишь в одном случае из 365 возможных дни рождения совпадают). Вероятность несовпадения дня рождения третьего человека с днем рождения любых двух других членов отобранной группы составляет 363/365. Для четвертого человека вероятность того, что его день рождения отличается от дней рождения любых трех людей, равна 362/365 и т. д. Дойдя до двадцать четвертого участника эксперимента, мы увидим, что вероятность несовпадения его дня рождения с днями рождения остальных двадцати трех участников равна 342/365. Таким образом, мы получаем набор из 23 дробей. Перемножив их, мы найдем вероятность того, что все 24 дня рождения различны. Сократив числитель и знаменатель произведения двадцати четырех дробей, мы получим дробь 23/50. Иначе говоря, заключая пари на то, что среди 24 по крайней мере двое родились в один и тот же день, вы будете выигрывать в 27 и проигрывать в 23 случаях из 50. (Проведенный нами подсчет вероятности не совсем точен, он не учитывает того, что год может быть високосным — то есть в феврале может быть 29 дней — и что дни рождения чаще приходятся на одни месяцы и реже на другие. Первое обстоятельство уменьшает вероятность интересующего нас события, второе — увеличивает.)
Приведенные цифры настолько неожиданны, что экспериментальная проверка их в классе или среди сослуживцев может явиться отличным развлечением. Если присутствует более 23 человек, попросите каждого написать на листке бумаги его день рождения. Соберите и сложите листки. Скорее всего по крайней мере две даты совпадут, что обычно вызывает невероятное удивление даже у людей, знакомых друг с другом в течение многих лет. Результат не изменится, если кто-нибудь схитрит, написав неправильную дату. Вероятность совпадения остается и в этом случае.
Прекрасной иллюстрацией парадокса могут служить даты рождения и смерти 33 президентов Соединенных Штатов. В каждом случае вероятность совпадения (33 даты рождения, 30 дат смерти) близка к 75%. И действительно, Полк и Хардинг родились 2 ноября, а три президента — Джефферсон, Адаме и Монро — умерли 4 июля.
Парадокс Монти Холла или Дилемма игрока
Вы участвуете в игре. Вам выносят 3 черных ящичка, в одном из них лежат ключи от машины/квартиры/дачи/сейфа, в двух других пусто. Первый этап, вы указываете на ящик. Тогда ведущий игры открывает один из двух невыбранных вами ящиков, причем обязательно пустой, и показывает, что он пуст, после чего предлагает снова выбрать уже из двух: остаться при прежнем мнении или указать на второй ящик.
Игрок уверен в себе и мнения не меняет, выбирая всегда тот же ящик, что и вначале. Но зря. Почему так? На первый взгляд, при первом выборе вероятность попасть в цель 1/3, а при втором среди оставшихся ящиков — 1/2, так что выбор можно делать произвольно.
На самом деле, когда вы делаете первый выбор, вероятность не попасть в цель 2/3, то есть вдвое выше. А потом ничего не меняется, только ведущий нам помогает и убирает лишний пустой ящик. А это значит, что ключи лежат в выбранном ящике с вероятностью все еще 1/3, а в последнем из двух невыбранных — все еще 2/3. Конечно, есть вероятность, а есть уверенность в правильном выборе, но, играя во что-то, нужно стремиться повысить свою вероятность, поэтому в описанной игре нужно отказываться от своего мнения и выбирать второй закрытый ящик.
Парадокс двух конвертов
В различных формулировках парадокс известен с 1930 года, вариант с двумя конвертами, который и получил большую популярность, описан в конце 1980-х. Условия парадокса следующие — существует два конверта с деньгами, сумма в одном конверте в два раза больше суммы в другом, предлагается выбранный конверт открыть, и в случае желания выбрать другой конверт. Если в первом (открытом) конверте была сумма А, во втором может находиться 0,5•(2•А) + 0,5•(0,5•А) = 1,25•А, что больше А. При таких условиях целесообразнее отказаться от первого конверта и выбрать второй, однако, все те же рассуждения справедливы при выборе второго конверта — бóльшую привлекательность приобретает первый, и наоборот, до бесконечности. Различные варианты разрешения парадокса предлагаются до сих пор.
В случае, если будет найдено приемлемое решение, разрешающее парадокс, это поможет найти решения в различных теоретических и прикладных областях: наглядное понимание некоторых парадоксов термодинамики, оптимизация работы технических систем, улучшение электронных схем, составление выигрышной стратегии игры на фондовом рынке.
Парадокс Бертрана
С какой вероятностью сторона вписанного в окружность правильного треугольника окажется меньше случайно выбранной хорды в этой окружности?
1) Любая точка круга (кроме центральной) однозначно задаёт хорду, серединой которой является. И эта хорда окажется длиннее стороны нашего правильного треугольника тогда и только тогда, когда её середина лежит внутри круга, вписанного в треугольник. Радиус этого круга равен половине радиуса исходной окружности. Это значит, что площадь маленького круга в четыре раза меньше площади большого. Поэтому вероятность того, что случайная точка окажется внутри вписанного круга, равна 1/4. Другими словами, ответ 1/4.
2) Мы всегда можем так «довернуть» воображаемый вписанный треугольник, чтобы одна из его вершин совпала с одним из концов хорды. Соответственно, координаты второго конца хорды однозначно задают всю хорду. Вершины треугольника делят окружность на три равные дуги, поэтому второй конец хорды с равными вероятностями попадает на каждую из них. Но хорда оказывается длиннее стороны треугольника только в том случае, если пересекает его сторону (т.е. ровно в одном случае из трёх). Получается, что хорда окажется длиннее стороны треугольника в 1/3 случаев.
3) Хорду в окружности можно однозначно задать точкой на радиусе, если проводить её через выбранную точку и перпендикулярно этому радиусу. Какой из радиусов брать? Годится любой вектор из центра до окружности, так как при повороте конструкции ничего не поменяется. Тогда получается, что случайная хорда длиннее стороны вписанного треугольника, если случайная точка радиуса попадёт на ту половину радиуса, которая ближе к центру окружности. Выходит, ровно в половине случаев случайная хорда будет больше стороны вписанного треугольника.
Поучительная история про математика, проигравшего велосипед
Это известная история, предостерегающая чересчур увлекаться числами. Была она на самом деле или нет, неизвестно, но в учебниках по теории вероятности этот пример приводят стабильно.
Однажды математик по профессии поспорил со случайным встречным: оппонент говорил, что следующие 100 человек, прошедшие мимо них, будут мужчинами, математик же утверждал, что этого не будет. Причем математик ставил на кон велосипед против всего 1 рубля своего оппонента.
Логика математика была очень проста: есть всего 1 шанс из около 1267 октиллионов (октиллион — единица с 27-ю нулями), то есть, по его мнению, он ничем не рисковал. Логика оппонента была тоже по-своему безупречна: рубль — невелика потеря, а вот возможность, пусть призрачная, выиграть велосипед, того стоит.
Спор решился не в пользу математика, потому что как раз в этот момент по их улице прошел батальон солдат. Так что не стоит забывать, что кроме вероятности и достоверности, есть еще обстоятельства, имеющие привычку образовываться в неподходящий момент.