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

Материал из synset
Перейти к: навигация, поиск
(Неравномерное распределение)
(Неравномерное распределение)
Строка 219: Строка 219:
 
:<center><math>v_3 = \frac{2P(2x)}{2P_o(x)}\cdot 2x+ \frac{P(x)}{2P_o(x)}\cdot (x/2),\;\;\;\;\;\;\;if\;x<x_0.</math></center>
 
:<center><math>v_3 = \frac{2P(2x)}{2P_o(x)}\cdot 2x+ \frac{P(x)}{2P_o(x)}\cdot (x/2),\;\;\;\;\;\;\;if\;x<x_0.</math></center>
  
Вероятности разделены на <math>\textstyle 2P_o(x)</math>, чтобы суммарная условная вероятность была равна единице. Найдём среднее значение <math>\textstyle v_3</math>:
+
Вероятности разделены на <math>\textstyle 2P_o(x)</math>, чтобы сумма условных вероятностей была равна единице. Найдём среднее значение <math>\textstyle v_3</math>:
  
 
:<center><math>\left\langle v_3\right\rangle = \int\limits^\infty_{0} v_3(x) P_{o}(x) dx = \int\limits^{x_0}_{0} x\left[2P(2x)+ \frac{1}{4}\, P(x)\right]dx + \int\limits^\infty_{x_0} x P_{o}(x) dx.</math></center>
 
:<center><math>\left\langle v_3\right\rangle = \int\limits^\infty_{0} v_3(x) P_{o}(x) dx = \int\limits^{x_0}_{0} x\left[2P(2x)+ \frac{1}{4}\, P(x)\right]dx + \int\limits^\infty_{x_0} x P_{o}(x) dx.</math></center>

Версия 17:30, 12 сентября 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\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) исчезающе мал и роли она не играет. Основной вклад в разницу средних даёт правая граница. И этот вклад остаётся, даже когда она формально отодвигается на бесконечность. Причина связана с быстрым (экспоненциальным) ростом величины суммы , потенциально получаемой во втором конверте. В тоже время эта сумма ни когда не встречается в первом конверте. При больших она равна сумме всех денег до этой границы:

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

Неравномерное распределение

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

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

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

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

В частности, среднее значение суммы в открытом конверте равно:

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

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

: Если в открытом конверте обнаружена сумма и при этом

забираем открытый конверт, иначе — закрытый.

Наша задача состоит в вычислении оптимального значения .

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

Вероятности разделены на , чтобы сумма условных вероятностей была равна единице. Найдём среднее значение :

После несложного преобразования, получаем:

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

Для определённости вычислим доходности для распределения в виде убывающей экспонентны:

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

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

В результате, активная стратегия оказывается на 12\% более доходной, чем пассивные.

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

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

Решение или проверка решения задач по теории вероятности почти всегда могут быть реализованы при помощи компьютера. Ниже приведен исходный код на 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)); ). Несколько последовательных запусков позволят увидеть, какая цифра "дёргается". Это и есть примерная ошибка моделирования.

Немного философии

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


Иногда на форумах при обсуждении задачи о двух конвертах, задаётся следующий вопрос:

Хорошо. Выбрав конкретные правила игры (=распределение) можно показать, что противоречия нет. Но как быть, если игрок не знает каким образом формируются конверты и суммы в них. В этом же случае вероятности по-любому 50/50?

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

незнание равновозможности

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

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


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

Материалы статьи могут быть использованы в некоммерческих и public information целях на условиях лицензии GNU Free Documentation License (версии 1.2 или более поздней). При использовании необходима ссылка на источник: http://synset.com/ru/Парадокс_двух_конвертов