Глава 19

Нетранзитивные игральные кости

[198]

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

Это все чепуха, забавная чепуха, но тем не менее. Среди прочего чепуха происходит от того, насколько субъективна методология оценки. Если определенный ресторан в вашем городе признан лучшим, это не обязательно ваш любимый ресторан. Ваши предпочтения могут отличаться от суждений ресторанных критиков, а их взгляды на один и тот же вопрос зачастую прямо противоположны.

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

Но, предположим, мы преодолели субъективность и достигли всеобщего соглашения относительно того, как сравнивать конкурентов. Попробуем выпарить идею ранжирования до ее математической сути. Улетучится ли тогда вся чепуха?

Две игральные кости

Сыграем в простую игру. Каждый бросит кубик, и у кого выпадет больше очков, тот выиграет. Если мы возьмем два обыкновенных кубика, где грани пронумерованы от одного до шести, то нет смысла говорить, что одна чем-то лучше другой. Они одинаковые.

Теперь сменим числа на гранях. Назовем наши игральные кости A и B.

Какая из них лучше, A или B? Какую вы предпочтете?

Для того чтобы ответить на этот вопрос, рассмотрим все вероятности: как могут выпасть игральные кости? Если игральная кость A выпала числом 2 вверх, то для сравнения есть шесть вариантов того, как может выпасть игральная кость B. Если выпало число 3, вариантов для сравнения опять-таки шесть. Таким образом, есть 6 + 6 + 6 + 6 + 6 + 6 = 6 × 6 = 36 возможностей, и все они равновероятны. Иногда побеждает обладатель игральной кости A, иногда – обладатель игральной кости B (все числа на гранях разные, поэтому нет варианта сыграть раунд вничью). Кто выигрывает чаще?

Составим схему, включающую все 36 возможных комбинаций, где отмечено, кто выигрывает в каждом отдельном случае, A или B.

Становится очевидно, что игральная кость B лучше. В борьбе один на один B одолевает A чаще, чем наоборот. На схеме видно, что A побеждает в 15 случаях из 36, в то время как B – в 21 случае из 36.

Профессиональные игроки скажут, что шансы на победу A равны 15 против 21, а шансы на победу B равны 21 против 15. Вероятность того, что выиграет A, равна 15/36 (или 42 %), вероятность того, что выиграет B, равна 21/36 (или 58 %).

Как ни назови это преимущество, но B явно лучше A.

Соперник

Добавим еще одну игральную кость. Внимание, появился новый соперник! Пусть на грани C нанесены числа, указанные на схеме.

C рьяно вызывает на бой B. Кости кидают, и побеждает та, где выпало наибольшее число. Какая из них лучше, B или C? Как и раньше, начертим схему и посмотрим, какая игральная кость имеет больше шансов на победу.

Мы видим, что C выигрывает гораздо чаще, чем B. Вероятность победы C равна 25/36 (около 69 %), в то время как B побеждает с вероятностью 11/36 (около 31 %).

В схватке один на один C лучше B, а B лучше A.

Значит, C лучше всех, верно?

Триумф неудачника

Казалось бы, среди трех игральных костей A слабее всех, а C сильнее всех. Что будет, если C сразится с A? Разумеется, C победит?

Начертим снова схему всех возможностей:

Посмотрите! A лучше C. Игральная кость A выигрывает с вероятностью 21/36 (около 58 %), а C – с вероятностью 15/36 (около 42 %).

Мы пришли к трем ошарашивающим выводам:

– B лучше A;

– C лучше B;

– A лучше C.

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

Сколько еще рейтингов в нашей жизни лишены смысла?

Другие примеры

Вот еще несколько игральных костей для изучения; эту задачу придумал Брэдли Эфрон, профессор статистики в Стэнфорде.

Сравним четыре игральные кости. Проработайте варианты, когда № 1 противостоит № 2, № 2 противостоит № 3, № 3 противостоит № 4, и № 4 противостоит № 1. Какая игральная кость лучше в каждой схватке? Как вы их проранжируете?

Ответы – в конце главы.

Вы играете в покер? Говоря точнее, вы играете в техасский холдем? Допустим, два человека играют в техасский холдем, и вы украдкой заглянули в их «карманные» карты. Пусть у первого на руках A♠K♥, а у второго 10♦9♦. У кого выше вероятность выиграть? У первого игрока карты большего достоинства, зато у второго игрока больше шансов на стрит и флэш.

Нам необходима дополнительная информация о пяти общих картах, лежащих рубашкой вниз. В колоде осталось 48 карт из 52. Нам придется перебрать все варианты, какими могут быть перетасованы эти карты, чтобы выяснить, какие пять карт окажутся на столе и кто из двух игроков победит (или же оба сыграют вничью). Есть около двух миллионов комбинаций по 5 карт из 48 карт. Нам не под силу провести все расчеты самостоятельно, поэтому прибегнем к помощи компьютера. Забейте в поисковик словосочетание «покерный калькулятор», и вы найдете уйму сайтов, где можно провести необходимые вычисления.

С помощью покерного калькулятора мы выясним, что игрок с «карманными» картами A♠K♥ побеждает с вероятностью 58,6 %, игрок с «карманными» картами 10♦9♦ побеждает в 41 % случаев, а 0,4 % остается на ничью.

Вывод: лучше иметь «карманные» карты A♠K♥, чем 10♦9♦.

Теперь ваша очередь. С помощью покерного калькулятора сравните шансы на выигрыш двух игроков со следующими наборами «карманных» карт:

– 10♦9♦ и 2♣2♥.

– 2♣2♥ и A♠K♥.

Дальше попробуйте построить рейтинг трех наборов «карманных» карт: A♠K♥, 10♦9♦ и 2♣2♥. Глава подошла к концу, поэтому вы вот-вот узнаете ответ.

 

Глава 20

Вероятность в медицине

Объявлено медицинское тестирование, диагностирующее наличие или отсутствие некой редкой болезни. Это чрезвычайно надежный тест. Вы принимаете решение пройти его и с ужасом получаете положительный результат. Насколько стоит беспокоиться?

Перевести беспокойство на язык цифр непросто, но в подобных ситуациях нужно сосредоточиться, потому переформулируем вопрос: насколько велика вероятность, что вы действительно подхватили это редкое заболевание?

Для ответа необходимо знать уровень надежности теста, а кроме того, как мы скоро увидим, уровень распространения болезни. Вот эти данные.

Редкая болезнь поразила 0,1 % населения. Состояние здоровья одного человека из тысячи вызывает тревогу.

Тест не идеален, как и всякий медицинский тест. Предположим, он дает верную информацию в 98 % случаев. Таким образом:

– среди 100 здоровых людей 98 человек получают верный отрицательный результат и 2 человека – неверный положительный;

– среди 100 больных людей 98 человек получают верный положительный результат и 2 человека – неверный отрицательный.

Разумеется, мы хотим пройти еще более надежный тест, но предположим, что это единственный возможный способ диагностировать наличие или отсутствие болезни.

Вопрос: если результаты теста положительные, какова вероятность того, что вы больны?

Ответ выглядит очевидным. Мы указали, что тест дает верные результаты в 98 % случаев. Таким образом, вы больны с вероятностью 98 %. Верно?

Вообразим город с миллионом жителей. Один из тысячи болен. Другими словами, 1000 жителей больны и 999 000 здоровы.

Все жители проходят медицинское тестирование. Посмотрим, сколько будет положительных результатов, если тест эффективен на 98 %.

• Среди тысячи больных жителей положительный результат получит большинство, но не все. Их количество 1000 × 0,98 = 980.

• Среди 999 000 здоровых жителей большинство покинет поликлинику с радостной новостью об отсутствии болезни, но 2 % получат ложный результат. Это дает еще 999 000 × 0,02 = 19 980 положительных результатов.

В общей сложности 980 + 19 980 = 20 960 жителей получат положительный результат.

Теперь мы можем правильно ответить на поставленный вопрос: какова вероятность того, что вы больны, если ваш результат тестирования положительный?

Среди двадцати с лишним тысяч людей с положительным результатом всего лишь меньше тысячи действительно больны. Точная вероятность правильности теста в этом случае равна

Вероятность того, что вам стоит беспокоиться, не равна 98 %! На самом деле вероятность того, что вы заражены этой редкой болезнью, меньше 5 %!

Стало быть, тесту грош цена? Не совсем.

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

Во-вторых, если болезнь действительно опасна, тест, эффективный на 98 %, позволяет хорошо просеять большие массы населения на предмет наличия или отсутствия болезни. Пациенты с положительным результатом могут пройти вторую диагностику, дающую еще более точные результаты.

Разумеется, отрицательный результат – не повод успокаиваться полностью. Какова вероятность того, что он верен? (Ответ я дам в конце главы.)

Интуиция отказывается принимать тот факт, что тест, надежный на 98 %, может быть настолько несовершенным, но вычисления говорят сами за себя. Впрочем, голые цифры могут обманывать нашу интуицию. Попробуем нарисовать картинку.

Заметим: диаграмма не соблюдает пропорции (0,1 % больных, эффективность теста 98 %).

На чертеже большой прямоугольник изображает все население. Фрагмент прямоугольника слева вверху обозначает группу больных жителей, оставшаяся часть – группу здоровых жителей. Серая полоса сверху – это все жители (из обеих групп) с положительным результатом. Белая область внизу – все жители (опять-таки из обеих групп) с отрицательным результатом

Чертеж иллюстрирует основные детали вышеописанной ситуации:

• болезнь редкая – крохотный фрагмент большого прямоугольника символизирует больную часть населения;

• тест верно диагностирует наличие болезни у подавляющей части больных – почти весь прямоугольник слева вверху закрашен серым;

• тест верно диагностирует отсутствие болезни у подавляющего большинства здоровых людей – огромная область большого прямоугольника остается белой;

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

Условная вероятность [205]

Мы вычислили вероятность того, что пациент с положительными результатами медицинского тестирования действительно болен. Мы вообразили гипотетический город, где живет миллион человек, и посчитали численность разных категорий населения. Это был способ ad hoc. В общем случае мы должны руководствоваться языком теории вероятностей, и я завершу главу разъяснениями по этому поводу.

Для события A мы обозначаем P (A) вероятность того, что событие A произойдет, и  – вероятность того, что событие A не произойдет; таким образом,

Для событий A и B мы обозначаем P (A∧B) вероятность того, что произойдут оба события – и A, и B.

Запись P (A|B) означает вероятность того, что из события A следует событие B; это условная вероятность того, что A влечет за собой B. Формула Байеса говорит нам:

Надежность диагноза, вынесенного на основе упомянутого медицинского теста, может быть выражена на языке математики следующим образом. Пусть S означает, что некто заражен редкой болезнью, а T означает положительный результат тестирования. Таким образом:

• болезнь поразила 0,1 % населения, откуда следует, что P(S) = 0,001;

• тест дает верную информацию о наличии или отсутствии заболевания в 98 % случаев, откуда следует, что P (T|S) = 0,98;

• тест дает верную информацию о том, что человек здоров, в 98 % случаев, откуда следует, что Иначе говоря, тест ошибочен в 2 % случаев:

Вопрос: какова вероятность того, что пациент с положительным результатом тестирования действительно болен?

Если перевести задачу на язык символов, то мы ищем величину P (S|T). По формуле Байеса эта вероятность равна Нам нужно узнать P (S∧T) и P (T).

Начнем хоть с P (S∧T), хоть с P (T∧S). По формуле Байеса

Мы знаем, что P (T|S) = 0,98, а P (S) = 0,001. Следовательно,

P ( S ∧ T ) = P ( T ∧ S ) = P ( T | S ) × P ( S ) = 0,98 × 0,001 = 0,00098.

Теперь вычислим P (T). Нам известно, что В то же время Далее:

Применим формулу Байеса в последний раз:

Это совпадает с нашими предыдущими вычислениями.

 

Глава 21

Хаос

Что делает событие непредсказуемым? Предыдущие главы были посвящены понятию вероятности. Центральная идея теории вероятностей заключается в том, что некоторые феномены случайны: их нельзя предсказать в точности, поскольку они недетерминированы. Разумно и эффективно рассматривать некоторые феномены внешнего мира, такие как вращение брошенного кубика, в качестве случайных.

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

Есть ли что-нибудь случайное? Физики утверждают, что некоторые феномены действительно непредсказуемы; таков основополагающий принцип квантовой механики. Поведение элементарных частиц, таких как электрон и фотон, нельзя предсказать, поскольку неопределенность – одно из их фундаментальных свойств.

Другие физические, биологические и социальные феномены могут быть чрезвычайно хорошо смоделированы с помощью теории вероятностей. Это потрясающе. Но насколько они случайны? Не исключено, что они чересчур сложны для понимания.

Так возникает главный вопрос этой главы: может ли система быть простой, полностью детерминированной, но все же непредсказуемой?

Функции

Ключевая идея этой главы – итерация функций. Под итерацией мы подразумеваем повторение одной и той же операции снова и снова. Что математики подразумевают под функцией?

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

Например, представим себе ящик, выполняющий следующую операцию. Мы бросаем туда число, он возводит его в квадрат, добавляет к результату единичку и выплевывает то, что получилось. Дадим этой функции имя; назовем ее «возведи в квадрат и прибавь один». Вот как она работает с числом 3:

Описывать действия функции словами обременительно, гораздо проще использовать математические символы. Что касается числа 3, мы вначале возводим его в квадрат: 3² = 9, а затем прибавляем единичку: 3² + 1 = 10. Как будет выглядеть результат с числом 4? Очевидным образом, 4² + 1 = 17.

Вместо длинных имен (вроде «возведи-в-квадрат-и-прибавь-один»), математики обозначают функцию какой-нибудь буквой, чаще всего f. Число, с которым имеет дело функция, помещают в круглые скобки сразу за буквой, например: f(4).

Эта форма записи удобна для описания функции:

f ( x ) = x ² + 1.

Это значит, что функция превращает число x в число x² + 1.

Вот еще один пример. Определим новую функцию g таким образом:

g ( x ) = 1 + x + x ².

Чему равно g(3)? Мы подставляем число 3 в формулу и получаем:

g (3) = 1 + 3 + 3² = 13.

Функции можно комбинировать, чтобы одна операция следовала за другой. Подумаем, чему равно f(g(2)).

Это выражение вынуждает нас вычислить функцию f от какой-то величины. От какой? Она зависит от того, чему равно g(2). А чему оно равно? g(2) = 1 + 2 + 2² = 7. А теперь посчитаем f(7) = 7² + 1 = 50. Если уложить всё в одну строчку, получится:

f ( g (2)) = f (7) = 50.

Давайте проверим, хорошо ли вы усвоили материал. Посчитайте g(f(2)). Это не 50! Верный ответ – в конце главы.

Вернемся к определению итерации. Как я уже сказал, итерация означает просто повторение одной и той же операции снова и снова. Еще раз: итерация означает просто повторение одной и той же операции снова и снова. Еще раз: итерация означает просто повторение… (Окей, надеюсь, вы уловили юмор.)

Подумаем о функции f(x) = x² + 1. Запись f(f(x)) означает, что мы применяем операцию f дважды: берем число x, закидываем его в функцию f, а потом снова закидываем то, что получилось, в функцию f. Вот пример:

f ( f (2)) = f (2² + 1) = f (5) = 5² + 1 = 26.

Можно проводить итерацию сколько угодно раз. Например, трижды:

f ( f ( f (2))) = f ( f (5)) = f (26) = 26² + 1 = 677.

Когда мы выходим на четвертую итерацию, запись становится громоздкой. Поэтому вместо f(f(f(f(x)))) мы будем записывать f⁴(x), подразумевая, что верхний индекс означает не возведение в степень, а последовательное применение функции. Для положительного целого числа n выражение f n(x) означает:

Итерация логистического отображения

Сейчас мы проитерируем функции вида f(x) = mх(1 – х), где m – некое число. Это семейство функций называется логистическим отображением. Во всех случаях мы будем начинать с числа x = 0,1, итерировать функцию и наблюдать за происходящим. Мы начнем с функции:

f ( x ) = 2,5 x (1 – x ).

Начнем с x = 0,1 и на первом шаге посчитаем:

f (0,1) = 2,5 × 0,1 × (1–0,1) = 2,5 × 0,1 × 0,9 = 0,225.

Применим f снова:

f ²(0,1) = f (0,225) = 2,5 × 0,225 × (1–0,225) = 2,5 × 0,225 × 0,775 = 0,4359375.

Прибегнем к помощи компьютера. Программа, итерирующая f, даст такие результаты:

Заметим, что успешное итерирование все больше и больше приближает нас к 0,6. Есть хороший способ продемонстрировать это наглядно. Отметим на графике величины f(0,1), f(f(0,1)), f(f(f(0,1))) и т. д. На оси абсцисс нанесем номера итераций, n. На каждом шаге будем отмечать значение f n(x) («нулевая» итерация – это наше начальное число 0,1). Соединим все точки отрезками. Вот что получится:

Мы видим, что итерации f(x) сходятся к числу 0,6.

А что, собственно, особенного в числе 0,6? Заметим, что

f (0,6) = 2,5 × 0,6 × (1–0,6) = 2,5 × 0,6 × 0,4 = 0,6.

Число 0,6 называют неподвижной точкой функции f, поскольку применение функции к этому числу не меняет его: f(0,6) = 0,6.

Продублируем эксперимент с другой функцией того же семейства; на сей раз возьмем множитель m = 2,8; таким образом, функция приобретает вид f(x) = 2,8 x (1 – x). Как и в предыдущем случае, мы начнем итерирование с x = 0,1. Вот первые 10 значений:

Похоже, итерации выплясывают вокруг 0,64. Продолжим итерировать и построим график:

В пределах первых 10 итераций значения функции слегка колеблются вверх и вниз, но уже на 30-й они выравниваются. На какой величине? Это число между 0 и 1, такое, что f(x) = x. Нам остается решить незамысловатое уравнение:

Итерации f(x) = 2,8 x (1 – x) сходятся к числу 0,642857.

Итерирование логистического отображения f(x) = m x (1 – x) можно рассматривать в качестве простой эволюционирующей системы. Число x показывает состояние системы, а функция f диктует, как система эволюционирует при смещении на один шаг. В двух рассмотренных нами случаях (m = 2,5 и m = 2,8) долгосрочное поведение системы приводит к «равновесию» в неподвижной точке функции.

Мы продолжим исследование итераций логистического отображения в случае m = 3,2. Как и в предыдущих случаях, мы начнем с х = 0,1. Вот первые десять значений:

Что происходит? Итерации не сходятся к одной величине. Значения на четных шагах становятся меньше (это примерно 0,66; 0,64; 0,62; 0,6; 0,57), а на нечетных – растут (примерно 0,72; 0,74; 0,75; 0,77). Значения расходятся, а не сходятся!

Начертим график первых 30 итераций, чтобы изобразить наглядно проведение системы:

Посмотрите! Она не выравнивается к одному числу, а осциллирует между двумя величинами. Доведем вычисления до 50-й итерации. Вот последние строчки таблицы:

Долгосрочное поведение системы – осцилляция между двумя величинами, s = 0,799455… и t = 0,5130445… Эти числа таковы, что f(s) = t, а f(t) = s. Правило осцилляции можно изобразить так:

Какое еще поведение функции мы можем наблюдать, итерируя логистическое отображение? В следующем пункте нашей экспедиции m = 3,52. Посмотрим на график итераций f(x), f²(x), f³(x), …

А вот таблица итераций:

Долгосрочное поведение функции занятно, но по-прежнему стабильно. Система идет по циклу из четырех величин ad infinitum, как показано на иллюстрации.

От порядка к хаосу

Мы проследили долгосрочное поведение итераций логистического отображения f(x) = m x (1 – x). Итерации всегда приводили нас к стабильности. В некоторых случаях (m = 2,5 и m = 2,8) система сходилась к одной величине: неподвижной точке функции f. В других случаях (m = 3,2 и m = 3,52) она приобретала стабильный, предсказуемый ритм.

Жизнь хороша. Мы знаем исходную величину: x = 0,1. И мы знаем правило, по которому переходим от одного шага к другому: f(x) = m x (1 – x). Разумеется, мы можем предвидеть поведение функции на любом шаге до бесконечности. Верно?

Настало время для последнего примера: m = 3,9. Доверим подсчет первых 10 итераций компьютеру:

Что происходит? Неясно. Попробуем изобразить на графике первые 30 итераций:

Хм… Ритм не прослеживается. Спокойствие, только спокойствие! Изобразим на графике первые 100 итераций.

Колебания величин выглядят случайными. Разумеется, на самом деле это не так! Значение функции на каждом шаге можно точно подсчитать по формуле f(x) = 3,9 x (1 – x). Но итерации логистического отображения никогда не приведут к стабильности. Хаос будет длиться вечно.

Великолепно: итерации беспорядочны, но система предсказуема на 100 %!

• Мы знаем исходную величину: x = 0,1.

• Мы знаем правило перехода от одного шага к другому: x → f(x) = 3,9 x (1 – x).

Следовательно, мы можем вычислить состояние системы, скажем, на тысячной итерации. Верно?

Неверно.

Мы загнаны в угол стечением двух обстоятельств: ошибок округления и чувствительности системы к исходному состоянию. Обсудим каждое из них.

Когда мы проводим вычисления на калькуляторе или на компьютере, результат зачастую оказывается приблизительным. Например, если мы делим 1 на 3, наши приборы выдают десятичную дробь 0,3333333. В ней, скажем, семь знаков после запятой. На самом деле троек после запятой бесконечно много, но калькулятор ограничивается конечным количеством цифр. После нескольких итераций функции f(x) = 3,9 x (1 – x) количество знаков после запятой достигает дюжины. Рано или поздно компьютер выдает лишь приблизительный, а не точный результат. Обычно мы не придаем значения таким ошибкам. Если мы подсчитываем, сколько картин уместится на пустой стене, нас не волнует ошибка на одну триллионную. Почему ошибки округления имеют значение в данном случае?

Они ведут нас к загвоздке – чувствительности системы к исходному состоянию. Посчитаем итерации нашей функции, начиная с двух почти что равных величин: х = 0,1 и х = 0,10001. Интуитивно мы предполагаем, что скромная разница между исходными величинами не играет роли. Так ли это? Что произойдет?

Замечу, что первые десять итераций или около того не приводят к значительным отличиям. Но затем траектории начинают расходиться. Это можно проиллюстрировать на графиках эволюции той и другой системы. Сплошная линия соответствует итерированию системы с исходным значением 0,1. Пунктирная линия иллюстрирует итерирование системы с исходным значением 0,10001.

Каково значение f1000 (0,1)? К чему мы придем, если мы проделаем тысячу итераций функции f(x) = 3,9 x (1 – x)?

Разумеется, мы доверяем вычисления компьютеру, но получается какая-то чепуха. Проиллюстрируем этот факт, проделав вычисления трижды с разным уровнем точности (заданным количеством знаков после запятой). Мы получим следующие результаты:

Ни одна из этих величин не равна f 1000 (0,1) в точности.

Мы будем биться до последней капли крови. Компьютер может работать с произвольной точностью. Он может не округлять полученное значение. К чему это приведет?

Точное значение f ⁶ (0,1) имеет длину 127 знаков после запятой, а точное значение f ⁷ (0,1) растягивается после запятой на 255 знаков. Количество знаков после запятой увеличится примерно вдвое на каждой итерации. Нет настолько мощного компьютера, чтобы вычислить точное значение f1000 (0,1).

К чему мы пришли? Несмотря на то что мы знаем исходное состояние системы и правило перехода от одного шага к другому, мы не в силах в точности предугадать ее состояние на 1000-м шаге.

Можно доказать, что точное значение f1000 (0,1) лежит между 0 и 1, и задаться вопросом: какова вероятность того, что f1000 (0,1), скажем, больше 0,5?

Ответ: либо 0, либо 1, потому что здесь нет ничего случайного. Либо f 1000 (0,1) > 0,5, либо f 1000 (0,1) ≤ 0,5, третьего не дано. Никаких «может быть», ничего случайного.

Даже настолько простая система способна оказаться хаотичной. Она абсолютно детерминирована и в то же время непредсказуема.

Огромное количество математических систем ведет себя хаотично, и многие из них позволяют строить модели явлений природы, например в метеорологии.

3 x + 1, или проблема Коллатца [212]

До сих пор мы говорили об итерациях логистических отображений. Мы закончили обсуждением разных типов функций и тернистой, неразрешимой проблемы их итерации.

Логистическое отображение – функция, заданная простой алгебраической формулой. Однако функции можно задавать иначе. Функция F, о которой сейчас пойдет речь, определена исключительно для положительных целых чисел и задана следующим образом:

Эта функция задается двумя простыми алгебраическими формулами, но мы выбираем формулу в зависимости от того, четное число x или нечетное.

Пример:

• F (9) = 28. Число 9 – нечетное, поэтому мы руководствуемся формулой 3х + 1 и получаем 3 × 9 + 1 = 28;

• F (10) = 5. Число 10 – четное, поэтому мы руководствуемся формулой x/2 и получаем 10/2 = 5.

Вне зависимости от того, четное число мы подставляем в функцию или нечетное, ее значение будет целым положительным числом.

Короче говоря, если x – целое положительное число, F (x) – тоже целое положительное число.

Мы можем итерировать нашу функцию, потому что выходное значение удовлетворяет условию, наложенному на входное значение. Что мы получим, итерируя функцию при начальном значении x = 12?

• F (12) = 6, потому что число 10 четное;

• F² (12) = F (6) = 3, потому что число 6 четное;

• F³ (12) = F (3) = 10, потому что число 3 нечетное;

• F⁴ (12) = F (10) = 5.

Вот удобный способ проиллюстрировать итерации. Мы записываем 12 → 6, подразумевая, что значение функции от 12 равно 6. Мы можем записать итерации F следующим образом:

Тройка 4 → 2 → 1 повторяется! А что дальше? Так как F(1) = 4, F(4) = 2, F(2) = 1, следующие три значения те же самые.

Другими словами, когда мы дошли до числа 1, тройка 4 → 2 → 1 будет повторяться до бесконечности.

Начнем с другой величины, скажем с 9. Вот что мы имеем: 9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

Вот еще один впечатляющий ряд итераций:

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

Мы снова дошли до 1, но после ста с лишним итераций.

Гипотеза Коллатца заключалась в том, что вне зависимости от того, с какого целого положительного числа x мы начинаем, последовательность итераций рано или поздно достигает единицы и тройка 4 → 2 → 1 повторяется до бесконечности.

Проблема была решена самым умопомрачительным образом – штурм потребовал чудовищной дотошности математиков-профессионалов и математиков-любителей.

 

Глава 22

Демократический выбор и теорема Эрроу

Демократия – процесс, основанный на предпочтениях членов общества. Людям дают возможность выразить свое мнение (путем голосования) и затем учитывают их голоса, когда принимают окончательное решение.

Выбор в случае двух кандидатов

Знакомая всем демократическая процедура – выборы, на которых два кандидата претендуют на одну и ту же должность. Избиратели отдают голоса за первого или второго кандидата, и побеждает тот, кто наберет больше голосов.

Ключевая фраза: побеждает тот, кто наберет больше голосов – краеугольный камень демократического общества. Но насколько справедлив этот принцип?

Вообразим, что два кандидата, претендующих на одну и ту же должность, зовутся A и B. Избиратели отдают голос за того или другого. Если отдано n голосов, данные голосования выглядят следующим образом:

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

Правило диктатора подразумевает, что решение принимается на основе голоса одного-единственного человека, скажем избирателя № 1. Если № 1 выбирает A, побеждает A; если № 1 выбирает B, побеждает B. Другие мнения не учитываются.

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

Для вящей справедливости метод принятия решения должен обладать определенными свойствами. Обидная особенность правила диктатора заключается в том, что голоса не учитываются равным образом. Более формально: справедливый метод принятия решения должен следовать нейтральности учета голосов – не важно, кто голосует, важно, сколько голосов отдано за того или другого кандидата. Правило большинства отвечает требованию нейтральности учета голосов, а правило диктатора – нет.

Если мы руководствуется только теми методами, которые обладают свойством нейтральности учета голосов, мы просто суммируем голоса, отданные за того или другого кандидата. Итоговая статистика может выглядеть следующим образом:

Есть и другой метод. Назовем его правилом алфавита. Побеждает тот кандидат, чье имя идет первым по алфавиту. Тогда в любом случае побеждает кандидат A.

Очевидно, и этот метод несправедлив, но почему?

Он обладает свойством нейтральности учета голосов: все избиратели равны в том плане, что не учитывается ничье мнение! Проблема состоит в том, что кандидаты поставлены в неравное положение. Мы будем говорить, что метод обладает свойством нейтральности учета кандидатов, если к кандидатам относятся одинаково; если кандидат сменит имя, это не повлияет на итог выборов.

Чувство справедливости требует нейтральности учета голосов и нейтральности учета кандидатов. Достаточно ли этого?

Есть еще один метод, который мы будем называть правилом нечетности: победу одерживает тот кандидат, который набрал нечетное число голосов. Если A предпочли 20 избирателей, а B – 13 избирателей, побеждает B. Этот метод отвечает требованиям нейтральности учета голосов и нейтральности учета кандидатов.

Или рассмотрим правило меньшинства: побеждает тот, кто набрал меньше всего голосов. Если A предпочли 12 избирателей, а B – 30 избирателей, побеждает A. Этот метод также отвечает требованиям нейтральности учета голосов и нейтральности учета кандидатов.

Два требования, нейтральность учета голосов и нейтральность учета кандидатов, исключают некоторые нечестные методы (такие как правило диктатора и правило алфавита), но кое-какие несуразные методы отвечают тому и другому требованию. Введем новое свойство, позволяющее отсеять разумные методы (такие как правило большинства) от несуразных.

Вот в чем заключается проблема с правилом нечетности. Вообразим, что профиль предпочтений следующий:

Если руководствоваться правилом нечетности, побеждает A.

Теперь предположим, что один избиратель передумал, забрал свой голос за B (проигравшего) и отдал A (победителю). Передумал всего лишь один избиратель; другие остаются при своем мнении. Итог таков:

Правило нечетности приводит B к победе.

Нечестно! Если один избиратель меняет свое мнение и предпочитает победителя проигравшему, это не должно влиять на результат. Правило нечетности нарушает требование монотонности.

Есть еще одна проблема с правилом нечетности. Что произойдет, если избирателей четное количество? Рассмотрим две ситуации:

В первом случае победителей нет, во втором случае побеждают оба кандидата. В том или ином случае мы заходим в тупик.

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

Даже если мы накладываем условия нейтральности учета голосов и нейтральности учета кандидатов, половина голосов может уйти первому кандидату, а другая половина – второму, так что нельзя будет принять внятное решение. Такое вероятно даже в случае правила большинства.

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

Правило меньшинства тоже в целом однозначное (но не монотонное).

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

Но ведь должны быть альтернативы! Есть ли другие методы принятия решений, отвечающие всем четырем требованиям?

Ответ отрицательный. В 1952 году Кеннет Мэй доказал, что правило большинства – единственный метод, обладающий всеми четырьмя свойствами.

Выбор в случае более чем двух кандидатов [222]

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

Ситуация существенно меняется, если число кандидатов возрастает. Но мы все еще вправе надеяться, что методы вроде правила большинства остаются эффективны.

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

Как и раньше, мы ищем методы принятия решений, учитывающие распределение голосов на входе, а на выходе выносящие решение о победителе.

Например, правило диктатора подразумевает, что победа достанется тому, кто возглавляет список предпочтений одного-единственного избирателя № 1. В нашем случае это кандидат A. Прочие голоса игнорируются.

Правило диктатора не отвечает требованию нейтральности учета голосов (хотя требование нейтральности учета кандидатов здесь выполняется). Вероятно, разумнее руководствоваться методами, нейтрально учитывающими голоса, и посчитать, каков приоритет того или иного кандидата для каждого избирателя. Например, в случае трех кандидатов итоговая статистика выглядит так:

Согласно этой статистике, 20 человек поставили на первое место A, 14 предпочли B, 9 предпочли C. Как нам выбрать победителя?

Правило большинства хорошо подходит, когда кандидатов двое. В случае трех кандидатов перевес возникает тогда, когда больше половины избирателей поставили на первое место одного кандидата. Это происходит не всегда, потому руководствоваться правилом большинства становится проблематично. Кроме того, правило большинства не учитывает распределение приоритетов второй и третьей степени. Посмотрим, насколько это важно. Проанализируем следующий профиль предпочтений:

Отмечу, что больше половины избирателей поставили на первое место A. Следует ли из этого, что отдать победу A – лучший выбор? А что значит «лучший»? Математика ответить не в силах. Для нас справедливо то, что соответствует нашей системе ценностей. Проиллюстрируем это обстоятельство. Вообразим, что «кандидаты» у нас – рестораны, а «избиратели» – офисные клерки, ищущие место для проведения корпоратива. Вот информация о ресторанах:

Ситуация вполне реальная. Большинство клерков (24 человека) предпочитает поужинать в стейк-хаусе, но значительное число (20 человек) не любит стейки. Индийская и греческая кухня остались в меньшинстве, но собрали равное число голосов.

Однако абсолютно все отметили ресторан со шведским столом в качестве второго приоритета. Это выглядит хорошим компромиссом, и мудрый босс выбирает заведение со шведским столом для корпоратива. Можно ли построить аналогичный метод принятия решения на выборах?

Профиль предпочтений против бюллетеней

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

Обычно избиратель отмечает в бюллетене одного кандидата, так что возможности расставить приоритеты нет. Такое оправдано, если мы руководствуемся правилом большинства : имеет значение только первый приоритет избирателя.

Иногда используют бюллетени, где можно отметить более одного кандидата. Если руководствоваться правилом первых двух приоритетов , избирателям нужно будет указать двух самых предпочитаемых кандидатов, и нет необходимости уточнять, кто из них важнее.

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

Иными словами, мы разрабатываем такой бюллетень, который даст достаточно информации для использования выбранного нами метода.

Существует множество методов для проведения выборов, когда кандидатов более двух. Правило большинства идеально подходит в случае выборов среди двух кандидатов, но в других ситуациях кандидат может не получить больше 50 % голосов и, как показывает наш пример с ресторанами, тогда становится неясно, как принять «верное» решение.

Давайте обсудим несколько методов принятия решений и выясним, какой из них самый лучше. Будем использовать следующий профиль предпочтений:

Профиль предпочтений в случае трех кандидатов

•  Правило большинства. Это наиболее распространенный метод. Мы выясняем, за какого кандидата отдано наибольшее число голосов, причем не обязательно больше половины. В вышеуказанном профиле предпочтений кандидата А выбрало наибольшее число избирателей (шесть), затем идет В (пять), на последнем месте С (два). По правилу большинства побеждает А.

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

– A получил 6 + 1 = 7 голосов (шесть раз на первом месте и один раз на втором);

– В получил 5 + 4 = 9 голосов (пять раз на первом месте, четыре раза на втором);

– С получил 2 + 8 = 10 голосов (дважды на первом месте и восемь раз на втором).

Таким образом, по правилу первых двух приоритетов побеждает С.

•  Метод Борда. Если мы руководствуемся правилом большинства, то не учитываем, кого каждый избиратель ставил на второе место. В правиле первых двух приоритетов второй приоритет имеет тот же вес, что и первый. Метод Борда  – компромисс между ними [225] .

Он заключается в том, что первый приоритет избирателя приносит кандидату 2 очка, второй приоритет – 1 очко, третий приоритет – ни одного очка. Дальше мы складываем очки. Побеждает тот кандидат, у кого их окажется больше.

Давайте проанализируем, как работает метод Борда в случае рассмотренного выше профиля предпочтений:

– кандидат A имеет первый приоритет у шести избирателей и второй – у одного, таким образом, он набирает 6 × 2 + 1 × 1 = 13 очков;

– кандидат B имеет первый приоритет у пяти избирателей и второй – у четырех, таким образом, он набирает 5 × 2 + 4 × 1 = 14 очков;

– кандидат C имеет первый приоритет у двух избирателей и второй – у восьми, таким образом, он набирает 2 × 2 + 8 × 1 = 12 очков.

В соответствии с методом Борда победителем станет кандидат B.

Нарисуем сводную таблицу победителей для одного и того же профиля предпочтений при использовании трех разных методов:

Результат обескураживает. Сложно обвинить какой-либо из трех методов в нелепости (в отличие от правила нечетности или правила меньшинства). Все три подхода удовлетворяют критериям честности: им свойственны нейтральность учета избирателей, нейтральность учета кандидатов и монотонность, потому нельзя отбраковать хотя бы один из них на этом основании. Может быть, мы найдем еще какой-нибудь критерий честности, чтобы выбрать «наилучший» метод?

Независимость от посторонних альтернатив

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

Вообразите, что ваша подружка выбирает десерт после ужина в ресторане. В меню указаны три варианта: торт, пирог и мороженое. Девушка заказывает мороженое. Официант, приняв ее заказ, говорит вам: «О, похоже, у нас закончились пироги». Тут девушка отвечает: «В таком случае я закажу торт!»

Что за чушь? Если она предпочитает мороженое (а не торт и не пирог), нет никакой разницы, остались ли в ресторане пироги. Но перемена выбора вашей подружки связана именно с фактом отсутствия пирогов, это не совпадение. Есть искушение заподозрить, все ли у нее в порядке с головой!

Мы ожидаем, что методы принятия решений будут разумными. Допустим, некий метод провозглашает кандидата X победителем на основании определенного профиля предпочтений. Допустим также, что другой кандидат, Y, снимает свою кандидатуру (и ни один избиратель не меняет своего мнения). В таком случае X должен остаться победителем. Если метод удовлетворяет такому условию, это и есть независимость от посторонних альтернатив.

Подумаем в том же ключе о правиле большинства. Для рассмотренного выше профиля предпочтений этот метод провозглашает победителем A. Теперь представим, что C снимает кандидатуру. Профиль предпочтений меняется следующим образом:

На сей раз победителем становится кандидат B! Таким образом, правило большинства не удовлетворяет критерию независимости от посторонних альтернатив.

Может быть, правило первых двух приоритетов лучше? На основе того же профиля предпочтений победителем становится C. Что произойдет, если A сойдет с дистанции? Останется всего два кандидата! Тут мы заходим в тупик. Вот вам головоломка: попробуйте составить такой профиль предпочтений при голосовании за четырех кандидатов (A, B, C, D), чтобы правило первых двух приоритетов провозглашало победителем A, но если бы из гонки выбыл D, победителем стал бы B. Ответ я дам в конце главы.

Наконец, протестируем метод Борда. Он провозглашает победителем B, но если C выбывает, победителем становится A.

Ни один из трех методов не удовлетворяет критерию независимости от посторонних альтернатив.

Спокойствие, только спокойствие! Есть множество других методов. Разумеется, какие-нибудь из них удовлетворяют критерию независимости от посторонних альтернатив. Например, правило диктатора (если кандидат A имеет первый приоритет у избирателя № 1, он останется победителем, кто бы из других кандидатов ни выбыл из игры). Разумеется, правило диктатора – не лучший метод, потому что не удовлетворяет одному из основных критериев – нейтральности учета избирателей.

Возникает вопрос: какой из справедливых методов голосования удовлетворяет критерию независимости от посторонних альтернатив? Ответ был найден Кеннетом Эрроу в 1950 году: увы, но такого метода нет.

Теорема невозможности Эрроу носит несколько технический характер, но ее смысл заключается в том, что при наличии более чем двух кандидатов ни один метод не удовлетворяет базовому критерию независимости от посторонних альтернатив.

Как нам теперь быть? Если все методы «несправедливы», каким из них нам руководствоваться? Или просто нужно отбросить критерий независимости от посторонних альтернатив? Нанесет ли это большой вред?

Проблема методов, не удовлетворяющих последнему критерию, заключается в том, что они поощряют избирателей голосовать иначе, чем они планировали изначально, если какой-нибудь кандидат портит шансы вероятного победителя. Например, вам по душе кандидаты A и B, но вы питаете отвращение к кандидату C. Вы склоняетесь к тому, чтобы голосовать за A, но внезапно узнаете из выпуска новостей, что шансы A на победу невелики. За кого вы будете голосовать? При подсчете голосов по правилу большинства (и при использовании некоторых других методов) неразумно голосовать за A, хотя изначально вы планировали поступить именно так. Если вы проголосуете за A, то отнимете один голос у B.

Если A не выбывает из игры, а избиратели, чьи изначальные приоритеты совпадают с вашими, не меняют своего решения и все-таки голосуют за A, это отнимает голоса у B и обеспечивает победу C. Но если A по тем или иным причинам выбывает из игры, вы голосуете за B, и его шансы на победу возрастают.

Если метод принятия решений удовлетворяет критерию независимости от посторонних альтернатив, такой дилеммы не возникает. Вы можете голосовать, как и планировали, потому что выбор в пользу A не обесценит вашего голосования.

 

Глава 23

Парадокс Ньюкома

Человеческое поведение предсказуемо. В самом деле: многие социальные науки, от экономики до культурной антропологии, строятся на том факте, что мы можем видеть закономерности в человеческой деятельности и предсказывать поступки людей (пусть даже с разными степенями уверенности).

В этой главе я расскажу о парадоксе Ньюкома. Он касается предсказания человеческого поведения и приводит к умопомрачительным выводам.

Игра Ньюкома

Парадокс Ньюкома подразумевает игру на деньги, где участвуют два человека: Предсказатель и Игрок, который должен выбрать между двумя вариантами. Перед началом игры Предсказатель угадывает, какое решение примет его оппонент. Давайте придадим всему этому личностный оттенок: я предлагаю вам примерить роль Игрока на себя.

Перед вами два ящика: № 1 и № 2, оба непрозрачные, что внутри – не видно. Я гарантирую, что в ящике № 1 лежит 1000 долларов. А вот ситуация с ящиком № 2 смутная: либо там 1 000 000 долларов, либо ничего.

Чуть позже я объясню, от чего зависит, пуст или полон второй ящик, но сперва расскажу о ваших возможностях. Вам предстоит выбрать один из двух вариантов действий:

– забрать содержимое того и другого ящика;

– забрать содержимое ящика № 2.

Разумеется, деньги останутся у вас.

Однако первый ход – не за Игроком. Перед тем как вы примете решение, Предсказатель попытается предугадать ваш выбор. Представим, что это невероятно одаренный психолог, годами втихомолку наблюдавший за вами; он читает в вашем сердце, знает, когда и от чего вас бросает в пот, и на основе всего этого прекрасно понимает, что вы предпочтете. Формально говоря, Предсказатель прав в 95 % случаев.

Теперь я объясню, по какому принципу Предсказатель распределяет купюры. Как уже было сказано, в ящике № 1 всегда лежит 1000 долларов. Содержимое ящика № 2 зависит от того, как Предсказатель видит ваши действия. Если он думает, что вы заграбастаете оба ящика (на что вы имеете полное право), он оставляет ящик № 2 пустым. Если же он предполагает, что вы возьмете только ящик № 2, он кладет туда 1 000 000 долларов. Занесем эту логику действий в таблицу:

Подытожим.

1. Первый ход за Предсказателем:

– если он думает, что Игрок выберет только ящик № 2, он кладет туда 1 000 000 долларов;

– если Предсказатель считает, что Игрок возьмет оба ящика, то ящик № 2 остается пустым.

2. Второй ход за Игроком, то есть за вами. У вас два варианта:

– взять только ящик № 2;

– взять оба ящика.

Когда вы берете один ящик или два, все деньги, которые там лежали, достаются вам!

Вот вопрос для анализа:

Переформулируем вопрос (на первый взгляд кажется, что разницы нет никакой): как вы поступите в такой ситуации? Люди могут рассуждать так:

– Я возьму только второй ящик, я не хочу показаться жадным.

– Я возьму оба ящика. Так мне в любом случае что-то достанется.

Мысли разумные, но это не ответ на наш вопрос. Здесь нет стратегии, позволяющей выиграть побольше денег. А мы хотим узнать именно это. Как поступить, чтобы выиграть максимальную сумму денег?

Вот еще один ответ, и, поскольку он тоже по-своему разумен, я в последнюю минуту немного поменяю правила игры, чтобы данная стратегия стала невыгодной.

– Я просто сыграю в орлянку.

Такая стратегия ставит нам палки в колеса, потому что Предсказатель психолог, а не маг, он не в силах предсказать, как выпадет монетка. Поэтому введем дополнительное правило: решение должно быть личным выбором Игрока. Вам запрещено с кем-либо консультироваться, вам запрещено играть в орлянку и предпринимать еще что-либо, влияющее на ваш личный выбор.

Итак, каким должен быть ваш выбор, чтобы вы заработали больше денег?

Хорошая новость состоит в том, что правильный ответ существует. Но есть и плохая новость: правильный ответ – не единственный. Посмотрим, почему это так.

Не оставляйте деньги на столе!

Вне всякого сомнения, забрать два ящика в любом случае на тысячу долларов лучше, чем просто взять ящик № 2. Предсказатель ходит первым. Поскольку он редко ошибается, вы не знаете, как он поступит. Если вы возьмете ящик № 2, вам достанется только то, что в нем лежит. Но если вы возьмете оба ящика, вам достанется и то, что находится в ящике № 2, и еще 1000 долларов. Вне всякого сомнения, так вы получите больше денег.

Вот наглядное представление о ваших возможностях в зависимости от того, пуст или полон ящик № 2:

Теперь все кристально ясно. Что бы там себе ни думал Предсказатель, в любом случае выгоднее брать оба ящика.

Жадность не доводит до добра

Вы ждете своей очереди. Несколько ваших друзей уже сделали выбор. Кое-кто из них руководствовался изложенной только что логикой и забрал оба ящика. Другие решили даже под давлением железобетонной логики взять только ящик № 2. И что они получили в итоге?

Рациональные игроки забрали свою тысячу, а вот азартные теперь миллионеры! В одном случае Предсказатель просчитался, но в целом он всегда оказывался прав.

А теперь ваш ход.

Если вы согласны с логикой предыдущих абзацев, вы возьмете оба ящика. Действительно, какой смысл оставлять на столе тысячу долларов? Предсказатель наверняка угадает ваш выбор (потому что знает, что вы за человек) и оставит ящик № 2 пустым. Это плохо: да, вы получите утешительный приз (1000 долларов), но так и не станете миллионером.

С другой стороны, ход ваших мыслей может быть следующим: «Предсказатель знает свое дело. Если я решу взять только ящик № 2, есть все шансы, что он заранее поймет это». И в самом деле: в таком случае вы с огромной вероятностью разбогатеете!

Иными словами, игрок, забирающий только ящик № 2, получает больше денег, чем «рациональный» игрок, забирающий оба ящика. Ошеломляющий вывод: выбрать ящик № 2 означает скорее всего получить больший выигрыш, в то время как выбрать оба ящика означает скорее всего ограничиться утешительным призом.

Выбрать ящик № 2 – наилучший путь к богатству!

Эти аргументы можно перевести на язык математики. Довольно просто вычислить, с какой вероятностью приносит деньги та или иная стратегия. Скоро мы вернемся к противостоянию Предсказателя и Игрока, но сначала для наглядности разберем очевидный пример: лотерею «Выбери три цифры».

Игроки покупают билеты стоимостью 1 доллар. Каждый билет дает возможность выбрать три цифры. Тем же вечером выигрышное трехзначное число генерируется случайным образом. Каждый билет с этим числом приносит 500 долларов.

Вопрос: какой ожидаемый выигрыш в лотерее «Выбери три цифры»?

Грубо говоря, никакой. Вероятность того, что мы в точности угадаем заветное число, равна одной тысячной, или 0,01 %. Почти всегда (но все-таки «почти») билет проигрывает.

Но когда об ожидаемом выигрыше говорят на математическом языке, подразумевается средний выигрыш. Как его вычислить?

С вероятностью 0,999 выигрыш по одному билету равен 0 долларов и с вероятностью 0,001 равен 500 долларам. В целом это дает:

0 × 0,999 + 500 × 0,001 = 0,5 доллара.

То есть средний выигрыш равен всего 50 центам.

Вот другой способ прийти к этому числу. Представим, что лотерейщики продали миллион билетов. Каждый билет стоит 1 доллар. Таким образом, выручка составляет миллион долларов. Сколько им придется заплатить?

Заветное число – трехзначное, поэтому резонно предположить, что выиграет где-то один билет на тысячу. Всего будет около 1000 выигрышных билетов, каждый сделает лотерейщиков беднее на 500 долларов. Таким образом, они потеряют в среднем 50 центов с каждого билета.

Применим этот метод анализа к игре Ньюкома. Игрок может взять оба ящика или только ящик № 2. Каков средний выигрыш в каждой ситуации?

• Если вы берете ящик № 2, в 95 % случаев Предсказатель угадывает это и кладет туда 1 000 000 долларов. В 5 % случаев он ошибается, и ящик остается пустым. Таким образом, средний выигрыш равен 1 000 000 × 0,95 + 0 × 0,05 = 950 000 долларов.

• Если вы берете оба ящика, в 95 % случаев ящик № 2 оказывается пуст, а в 5 % случаев там лежит 1 000 000 долларов. В любом случае Игрок получает 1000 долларов из первого ящика. Таким образом, средний выигрыш составляет 1000 × 0,95 + 1 001 000 × 0,5 = 51 000 долларов.

Теперь все ясно. Лучший способ заработать деньги – выбрать только ящик № 2.

Противоречие и вывод

Мы пришли к двум неоспоримым выводам. Первый: лучше взять оба ящика (зачем оставлять деньги на столе?). Второй: лучше взять ящик № 2 (есть все шансы стать миллионером). Как такое возможно? Верно должно быть либо то, либо другое.

Мы столкнулись с противоречием. С нами уже такое случалось. В главе 1 мы вообразили число N, которое, как выяснилось, (a) делится на некое простое число и (b) не делится ни на какое простое число. Разумеется, это невозможно. Если мы пришли к противоречию, значит, мы исходили из ложной посылки. Так оно и было: мы предположили, что количество простых чисел конечно, и пришли к двум прямо противоположным выводам. Если вывод абсурден, то изначальное предположение было ошибочным. Неверно, что простые числа можно пересчитать: это приводит к бессмыслице. Таким образом, простых чисел бесконечно много.

Что касается парадокса Ньюкома, мы сделали два неявных допущения.

Первое допущение – относительно Игрока. Может ли он сделать независимый выбор? Обладают ли человеческие существа свободной волей? Разумеется, нельзя (и мы даже не будем пытаться) в точности разрешить эту старую как мир философскую проблему.

Второе – относительно Предсказателя. Действительно ли он способен предвидеть поступки другого человека? Ясно, что в целом поведение людей может быть предсказано с большой долей уверенности. Но в нашей игре Предсказатель пытается предугадать выбор одного-единственного индивидуума, а ведь это весьма зыбкая материя. Точность 95 % неправдоподобно высока.

Однако вот что интересно: противоречие не исчезает, даже если Предсказатель прав в 51 % случаев! Аргумент «не оставляйте деньги на столе» по-прежнему не работает. Вот расчет среднего выигрыша:

• Если вы берете только ящик № 2, средний выигрыш составляет 1 000 000 × 0,51 + 0 × 0,49 = 510 000 долларов.

• Если вы берете оба ящика, средний выигрыш составляет 1 000 × 0,51 + 1 001 000 × 0,49 = $491 000 долларов.

Даже если Предсказатель предугадывает ваше решение с точностью 51 %, вам лучше выбрать только ящик № 2! Разница в средних выигрышах на сей раз невелика, поэтому расчеты не вызывают особых эмоций, но выигрышная стратегия остается прежней.

Итак, вот два допущения, приводящих к парадоксу:

– Игрок обладает свободой воли;

– Предсказатель предугадывает решение Игрока с высокой точностью.

Иными словами, свобода выбора и уверенное предсказание будущего несовместимы.

Компьютер в роли Игрока

Вообразим, что в роли Игрока – компьютерная программа, а в роли Предсказателя – мы, человеческие существа. По правилам, Игроку запрещено играть в орлянку; таким образом, компьютер не должен совершать случайного выбора.

У компьютера есть все те же две возможности: выбрать оба ящика или только ящик № 2. Как он поступит?

Мы можем с легкостью предсказать выбор компьютера. Нам нужно всего лишь сделать копию компьютерной программы, запустить на другом компьютере и следить за ее действиями. Наше предсказание будет идеальным (если компьютер не заглючит). Когда игра начнется, мы убедимся в безошибочности предсказания. Практически без исключений выбор двух ящиков принесет компьютеру тысячу долларов, а выбор ящика № 2 принесет миллион долларов.

Если нас попросят разработать программу для парадокса Ньюкома, наше решение будет кристально ясно. Вот вся программа:

print («Я беру только ящик № 2»)

Мы запускаем программу, компьютер каждый раз получает миллион долларов, и мы счастливы.

Нет никакого резона выбирать оба ящика. Действия компьютера полностью предсказуемы (потому что мы имеем дело с машиной, а не с человеком), и выбор двух ящиков всякий раз будет приносить всего лишь 1000 долларов.

Почему противоречие возникает, когда в роли Игрока оказывается человек, и пропадает, когда в роли Игрока выступает компьютер? Парадокс Ньюкома подразумевает свободу воли: никакой Предсказатель не в силах в точности предвидеть наши действия.