Парадокс двух конвертов — различия между версиями

Материал из synset
Перейти к: навигация, поиск
(Равномерное ограниченное распределение)
(Равномерное ограниченное распределение)
Строка 127: Строка 127:
 
Чтобы найти средний доход, получаемый при выборе разумной стратегии, необходимо снова проинтегрировать <math>\textstyle v_3</math> c плотностью <math>\textstyle P(x)</math>:
 
Чтобы найти средний доход, получаемый при выборе разумной стратегии, необходимо снова проинтегрировать <math>\textstyle v_3</math> c плотностью <math>\textstyle P(x)</math>:
  
:<center><math>\left\langle v_2\right\rangle = \int\limits^L_0 v_2(x) \cdot P(x) dx = \frac{15}{32}\,L</math></center>
+
:<center><math>\left\langle v_2\right\rangle = \int\limits^L_0 v_2(x) \cdot P(x) dx = \frac{15}{32}\,L.</math></center>
  
 
Относительная доходность "разумной стратегии" по сравнению с пассивным выбором любого конверта оказывается равной <math>\textstyle (v_3-v_1)/v_1=25\%</math>. Это значение не зависит от <math>\textstyle L</math>, поэтому "отодвигание границы" на бесконечность ничего не изменит.
 
Относительная доходность "разумной стратегии" по сравнению с пассивным выбором любого конверта оказывается равной <math>\textstyle (v_3-v_1)/v_1=25\%</math>. Это значение не зависит от <math>\textstyle L</math>, поэтому "отодвигание границы" на бесконечность ничего не изменит.

Версия 16:57, 11 сентября 2010

Формулировка парадокса

Рассмотрим следующую игру:

Есть 2 конверта. В один из них вкладывается сумма , во второй — . Значение неизвестно и каждый раз случайно изменяется. Конверты неразличимы. Игрок открывает один из конвертов и видит лежащую там сумму. У него есть две возможности - забрать её или выбрать второй, нераспечатанный конверт. Какая из этих возможностей в среднем даст большую прибыль?

Так как конверты неразличимы, вероятность того, что в данном конверте лежит сумма или , равна 1/2. Значения сумм, лежащих в каждом конверте, заранее неизвестны. Знание суммы в открытом конверте не добавляет информации о том, какая сумма лежит во втором. Поэтому любой выбор даст одинаковую доходность.

С другой стороны. Пусть игрок видит сумму . Тогда во втором конверте лежит или . Эти две возможности равноправны. Поэтому средний доход от выбора второго конверта равен:

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

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

Парадокс был предложен в 1953 году Кратчиком (Maurice Kraitchik), в терминах двух карманов. Широкую популярность парадокс получил благодаря Гарднеру (Martin Gardner), который описал его в 1982 г. в книге "Aha! Gotcha". В дальнейшем карманы превратились в конверты.

Вокруг парадокса время от времени вспыхивают споры в интернет-сообществе. Иногда появляются "сенсационные" заявления от том, что некто парадокс наконец решил. С другой стороны, часто в общих словах происходит, в принципе, верное объяснение сути, но без конкретных расчётов. В результате создаётся ощущение философского надувательства.

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

Уточнение задачи

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

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

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

  • 1) Суммы, участвующие в игре, являются дискретными. Например, это может быть ограниченная последовательность с возможными парами конвертов , и . Можно также рассматривать неограниченную (в одну или обе стороны) последовательность. Например: . В любом случае вероятности будут дискретными числами , где — номер значения суммы.
  • 2) Суммы, участвующие в игре — непрерывные вещественные положительные числа. Их вероятность необходимо уже задавать при помощи плотности вероятности (или распределения вероятностей). В этом случае вероятность того, что при некотором малом , выбранное число попадёт в интервал , равняется .

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

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \sum^\infty_{i=0} p_i = 1,\;\;\;\;\;\;\;или\;\;\;\;\;\;\; \int\limits^\infty_0 P(x)dx = 1.}

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

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

  • 1) равномерное распределение с границей так, что при .
  • 2) неравномерное распределение, при котором убывает при .

Ниже на левом рисунке представлен первый вариант, а на правом, соответственно, второй:

Envel Px.png

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

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

  • : Всегда забираю открытый конверт.
  • : Всегда забираю закрытый конверт.
  • : Если , беру открытый конверт, иначе — закрытый.

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

Ниже мы рассмотрим сначала влияние краевого эффекта для равномерного распределения с границей. Это будет проделано отдельно для непрерывного и дискретного случаев. Мы увидим, что даже при формальном "отодвигании" границы на бесконечность существует выигрышная стратегия, и в ряде случаев симметрия между открытым и закрытым конвертами не восстанавливается. В заключение мы приведём примеры моделирования задачи о двух конвертах на C++.

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

Равномерное ограниченное распределение

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

Envel 24.png

Выше на правом рисунке изображено дерево вариантов, сопровождающих открытие конверта. С вероятностями 1/2 в открытом конверте может находиться меньшая и большая сумма. Если эта сумма большая, она снова равновероятно может быть меньше или больше .

Таким образом, мы имеем три исхода при открытии первого конверта со следующими вероятностями:

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

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

С вероятностью 1/2 в закрытом конверте находится (большая сумма). С такой же вероятностью там (меньшая сумма). Поэтому:

Упс. Фактически мы повторили рассуждение парадокса и, несмотря на все уточнения формулировки задачи, снова пришли к противоречию. Что неверно в наших вычислениях?

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

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

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

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

Таким образом, до открытия вероятности были 1/2 и 1/2. После открытия и получения информации они стали 2/3 и . Соответственно в закрытом конверте эти вероятности обратные.

Теперь не составляет труда записать условное среднее для стратегии при условии, что :

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

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

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

Envel sum.png

Обратим внимание, что в 2 раза уже и выше чем , как и должно быть для выполнения условия нормировки (см. левый рисунок).

Чтобы найти абсолютный средний доход от выбора второго конверта, необходимо провести усреднение:

Этот же результат ранее мы получили более простым способом.

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

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

Чтобы найти средний доход, получаемый при выборе разумной стратегии, необходимо снова проинтегрировать c плотностью :

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

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

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

Закрытый конверт на 50\% более доходный (конверты неравноправны!).

Абсолютная средняя доходность равна:

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

Дискретная задача двух конвертов

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

Соответственно возможны следующие пары:

Они выбираются равновероятно, затем конверты перемешиваются.

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

Пусть, например, , т.е. разрешены суммы от 1 до 64. В открытом конверте (если раунд игры не прекращён) равновероятно могут находится суммы от 2 до 32. Соответственно, во втором конверте, снова равновероятно, будут суммы в два раза больше или меньше. Изобразим это в виде следующего дерева:

Envel 1 64.png

Пары крайних значений 1,2 и 32,64 во втором конверте встречаются по разу, а остальные числа — по два раза. Поэтому гистограммы появления сумм в первом и втором конверте (число возможностей) имеют вид:

Envel n.png

Для чисел вероятность появления (в игре) в первом конверте сумм от 2 до одинаковые и равны . Чтобы найти вероятности во втором конверте необходимо посчитать число квадратиков в гистограмме. В нижнем ряду их , а в верхнем . Поэтому всего их . В результате вероятности сумм в середине диапазона равны , а по краям — .

Нарисуем эти два распределения:

Envel n2.png

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

Однако это не так, даже при ! Действительно, найдём доход при выборе первого (открытого) конверта:

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

Таким образом, относительная доходность второй стратегии при любом больше на 25\%, чем для первой стратегии.

Разберёмся с тем, что получилось. Для больших вклад в или левой границы (суммы 1 и 2) исчезающе мал и роли она не играет. Основной вклад в разницу средних даёт правая граница. И этот вклад остаётся, даже когда она формально отодвигается на бесконечность. Причина связана с быстрым (экспоненциальным) ростом величины суммы , потенциально получаемой во втором конверте. В тоже время эта сумма ни когда не встречается в первом конверте. При больших она равна сумме всех денег до этой границы:

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

Компьютерное моделирование

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

#include <stdlib.h>
#include <stdio.h>
#include <math.h> 
#include <time.h> 

// случайное число [0 .. 1]
inline double Rnd(){ return double(rand()) / double(RAND_MAX); }          

void main()
{
   srand(time(0));                         // встряхиваем генератор
   double c[2];                            // конверты
   double L = 1;                           // граница

   int n=0;                                // число игр
   double v1=0, v2=0, v3=0;                // заработки от стратегий
   for(int iter=0; iter<10000000; iter++){
      c[0]=Rnd()*L;
      c[1]=c[0]/2;

      int i1 = rand()%2;                   // номер открытого конверта
      int i2 = (i1+1)%2;                   // номер закрытого конверта

      //if(c[i1]>L/2) continue;            // прерываем раунд

      v1+=c[i1];                           // доходы от стратегий:
      v2+=c[i2];
      v3+=( (c[i1]>L/2)? c[i1]: c[i2] );
      n++;
   }
   v1/=n; v2/=n; v3/=n;

   printf("v1=%.4f\tv2=%.4f\tv3=%.4f\n", v1, v2, v3);
}

Закомментированная строка соответствует дополнительному условию по началу игры (прерываем раунд). Любое компьютерное моделирование требует проведения статистической оценки достоверности полученных результатов. Можно поступить проще и поставить встряхиватель случайных чисел (строка srand(time(0)); ). Несколько последовательных запусков позволит увидеть, какая цифра "дёргается". Это и есть примерная ошибка моделирования.

Степанов Сергей по просьбе Степанова Дениса
(с) 2010, synset.com