Парадокс двух конвертов

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

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

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

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

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

$v_{2}={\frac {1}{2}}\,(2x)+{\frac {1}{2}}\,(x/2)={\frac {5}{4}}\,x.$

Таким образом, игрок при выборе второго конверта получает больше, чем при выборе первого, который даёт ему только $\textstyle v_{1}=x$. Независимо от значения суммы $\textstyle x$, относительная доходность при выборе закрытого конверта больше на $\textstyle (v_{2}-v_{1})/v_{1}=25\%$.

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

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

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

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

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

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

В задаче с двумя конвертами необходимо сначала определить способ формирования конвертов. Вариантов может быть множество. Для определённости будем считать, что ведущий игру выбирает некоторую сумму $\textstyle x_{max}$, которую считает большей. Соответственно во второй конверт он кладёт $\textstyle x_{min}=x_{max}/2$. После этого конверты случайно перемешиваются.

Второе уточнение связано со способом выбора большей суммы $\textstyle x=x_{max}$. Предполагается, что она выбирается случайно. Это означает, что существует некоторое распределение вероятностей выбора того или иного значения $\textstyle x$. Возможны два варианта: \item[1)] Суммы, участвующие в игре, являются дискретными. Например, это может быть ограниченная последовательность $\textstyle \{1,\,2,\,4,\,8\}$ с возможными парами конвертов $\textstyle (1,2)$, $\textstyle (2,4)$ и $\textstyle (4,8)$. Можно также рассматривать неограниченную (в одну или обе стороны) последовательность. Например: $\textstyle \{...,\,2^{-2},\,2^{-1},\,1,\,2,\,2^{2},\,..\}.$. В любом случае вероятности будут дискретными числами $\textstyle p_{i}$, где $\textstyle i$ — номер значения суммы. \item[2)] Суммы, участвующие в игре — непрерывные вещественные положительные числа. Их вероятность необходимо уже задавать при помощи плотности вероятности $\textstyle P(x)$ (или распределения вероятностей). В этом случае вероятность того, что при некотором малом $\textstyle \Delta x$, выбранное число попадёт в интервал $\textstyle [x,x+\Delta x]$, равняется $\textstyle P(x)\Delta x$.

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

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

Понятно, что для равновероятных значений $\textstyle x$ (т.е. $\textstyle p_{i}=const$ или $\textstyle P(x)=const$) эти соотношения выполнятся не могут. Другими словами, невозможно ни в теории, ни на практике реализовать равновероятное распределение на бесконечном интервале.

Пусть, например, случайная величина $\textstyle x$ непрерывна. Тогда возможны только два варианта для плотности вероятности:\\ 1) равномерное распределение с границей так, что $\textstyle P(x)=0$ при $\textstyle x>L$.\\ 2) неравномерное распределение, при котором $\textstyle P(x)$ убывает при $\textstyle x\to \infty$.\\ Ниже на левом рисунке представлен первый вариант, а на правом, соответственно, второй:

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

Задача двух конвертов в более общей постановке предполагает формирование различных стратегий поведения игрока и выбор из них наиболее доходной. Стратегии могут учитывать или не учитывать информацию о сумме $\textstyle x$ в открытом конверте. Например: \item[$\textstyle v_{1}$:] Всегда забираю открытый конверт. \item[$\textstyle v_{2}$:] Всегда забираю закрытый конверт. \item[$\textstyle v_{3}$:] Если $\textstyle x>100$, беру открытый конверт, иначе — закрытый. В случае, если конверты были тщательно перемешаны, первые две стратегии должны приводить к одинаковому доходу. Они никак не используют знания об $\textstyle x$, и в открытый конверт в этом случае можно даже не заглядывать. Собственно, это и утверждалось в первом варианте рассуждения. Поэтому не верны именно рассуждения при вычислении среднего $\textstyle v_{2}=5x/4$. Нам предстоит разобраться в чём состоит проблема.

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

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

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

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

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

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

${\begin{array}{r|c|c|c|}x=&\;\;\;\;\;\;x_{min}\;\;\;\;\;&\;\;x_{max}<{\frac {L}{2}}\;\;&\;\;x_{max}>{\frac {L}{2}}\;\;\\\hline p_{i}=&1/2&1/4&1/4\end{array}}$

Рассмотрим сначала пассивные стратегии: "всегда берём открытый конверт" ($\textstyle v_{1}$) и "всегда берём закрытый конверт" ($\textstyle v_{2}$). Если в открытом конверте находится сумма $\textstyle x$, то понятно, что средняя доходность первой стратегии равна $\textstyle v_{1}=x$. Конверты были перемешаны, значение $\textstyle x$ никак не учитывается, поэтому вторая стратегия должна иметь такую же доходность $\textstyle v_{2}=x$.

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

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

$v_{2}={\frac {1}{2}}\,(2x)+{\frac {1}{2}}\,(x/2)={\frac {5}{4}}\,x.$

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

Зайдём с другого конца и вычислим абсолютный средний доход, получаемый игроком при выборе денег из открытого конверта. Большая и меньшая сумма в открытом конверте может появиться равновероятно. Меньшая сумма имеет равномерное распределение на интервале $\textstyle [0,L/2]$. Поэтому её среднее значение равно $\textstyle L/4$. Большая сумма, равномерно распределённая на интервале $\textstyle [0,L]$, имеет среднее значение $\textstyle L/2$. Поэтому среднее значение суммы в открытом конверте равно:

$\left\langle x\right\rangle ={\frac {1}{2}}\cdot {\frac {L}{4}}+{\frac {1}{2}}\cdot {\frac {L}{2}}={\frac {3L}{8}}.$

Очевидно, что такое же рассуждение и результат справедливы для средней доходности от выбора закрытого конверта. Поэтому средние абсолютные доходности первой и второй стратегий равны $\textstyle \left\langle v_{1}\right\rangle =\left\langle v_{2}\right\rangle =3L/8$.

Но что же тогда означают соотношения $\textstyle v_{1}=x$, $\textstyle v_{2}=5x/4$, полученные выше, и какая при их выводе была сделана ошибка? Ответ прост. Вероятности появления большей или меньшей суммы в открытом конверте действительно одинаковы. Однако, выражая доход, полученный от выбора закрытого конверта через сумму $\textstyle x$, которая обнаружилась в открытом, мы вычисляем условное среднее. Т.е. вопрос стоит так: какова в среднем сумма в закрытом конверте, если в открытом мы видим $\textstyle x$. Знание значения $\textstyle x$ меняет вероятности $\textstyle p_{1}$ и $\textstyle p_{2}$ для сумм $\textstyle x/2$ и $\textstyle 2x$ в закрытом конверте. Например, если $\textstyle x>L/2$, то в закрытом конверте заведомо находится меньшая сумма и $\textstyle p_{1}=1$, $\textstyle p_{2}=0$. Поэтому в этом случае:

$v_{2}=0\cdot (2x)+1\cdot (x/2)={\frac {x}{2}}.$

Если же $\textstyle x<L/2$, то вероятности того, что в открытом конверте лежит меньшая или большая суммы $\textstyle x$, изменяются. Это уже условные вероятности, рассчитанные после получении информации о том, что $\textstyle x<L/2$. Они по-прежнему пропорциональны $\textstyle 1/2$ и $\textstyle 1/4$, т.е. меньшая сумма в открытом конверте в два раза более вероятна. Однако, их необходимо отнормировать, чтобы суммарная вероятность была равна единице. В результате имеется две возможности в открытом конверте:

$if\;x<{\frac {L}{2}}\;\;\;\;\;\;\;\;{\begin{array}{r|c|c|c|}x=&\;\;\;\;\;\;x_{min}\;\;\;\;\;&\;\;x_{max}<{\frac {L}{2}}\\\hline p_{i}=&2/3&1/3\end{array}}$

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

Теперь не составляет труда записать условное среднее для стратегии $\textstyle v_{2}$ при условии, что $\textstyle x<L/2$:

$v_{2}={\frac {2}{3}}\cdot (2x)+{\frac {1}{3}}\cdot (x/2)={\frac {3}{2}}\,x.$

Окончательно, правильное выражение для $\textstyle v_{2}$, т.е. для значения условного среднего дохода при выборе закрытого конверта, если в открытом обнаружена сумма $\textstyle x$, имеет вид:

$v_{2}=\left\{{\begin{array}{ll}3x/2,&\;\;if\;x<L/2\\x/2,&\;\;if\;x>L/2.\\\end{array}}\right.$

Имея это условное среднее можно ещё раз вычислить абсолютное среднее $\textstyle \left\langle v_{2}\right\rangle$. Для этого необходимо найти распределение вероятностей обнаружить в открытом конверте сумму $\textstyle x$. Так как меньшая сумма существует на интервале $\textstyle [0,L/2]$, обозначим ступеньку её плотности вероятностей как $\textstyle P_{L/2}(x)$. Соответственно, для большей суммы это функция-ступенька $\textstyle P_{L}(x)$. Конверты перемешаны, поэтому плотность вероятности для суммы $\textstyle x$ в открытом конверте равна:

$P(x)={\frac {1}{2}}P_{L/2}(x)+{\frac {1}{2}}P_{L}(x).$

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

Обратим внимание, что $\textstyle P_{L/2}(x)$ в 2 раза уже и выше чем $\textstyle P_{L}(x)$, как и должно быть для выполнения условия нормировки (см. левый рисунок).

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

$\left\langle v_{2}\right\rangle =\int \limits _{0}^{L}v_{2}(x)\cdot P(x)dx=\int \limits _{0}^{L/2}{\frac {3x}{2}}\cdot {\frac {3}{2L}}\,dx+\int \limits _{L/2}^{L}{\frac {x}{2}}\cdot {\frac {1}{2L}}\,dx={\frac {3}{8}}\,L.$

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

Если с плотностью вероятностей $\textstyle P(x)$ усреднить $\textstyle v_{1}=x$, то получится такое же выражение: $\textstyle \left\langle v_{1}\right\rangle =3L/8$.

$\textstyle \bullet$ Перейдём теперь к более активной и доходной стратегии. Если игрок в открытом конверте видит $\textstyle x>L/2$, то он должен тут же брать эту сумму, так как в закрытом конверте лежит заведомо меньше. В этом случае выигрыш $\textstyle v_{3}=x$. Если $\textstyle x<L/2$, то более вероятно, что в открытом конверте меньшая сумма, поэтому стоит выбрать закрытый конверт. В этом случае $\textstyle v_{3}=v_{2}$. Поэтому, объединяя оба варианта, запишем условное среднее выигрыша от "разумной стратегии" следующим образом:

$v_{3}=\left\{{\begin{array}{ll}3x/2,&\;\;if\;x<L/2\\x,&\;\;if\;x>L/2.\\\end{array}}\right.$

Чтобы найти средний доход, получаемый при выборе разумной стратегии, необходимо снова проинтегрировать $\textstyle v_{3}$ c плотностью $\textstyle P(x)$:

$\left\langle v_{2}\right\rangle =\int \limits _{0}^{L}v_{2}(x)\cdot P(x)dx={\frac {15}{32}}\,L$

Относительная доходность "разумной стратегии" по сравнению с пассивным выбором любого конверта оказывается равной $\textstyle (v_{3}-v_{1})/v_{1}=25\%$. Это значение не зависит от $\textstyle L$, поэтому "отодвигание границы" на бесконечность ничего не изменит.

$\textstyle \bullet$ Можно изменить правила игры для ослабления краевого эффекта. Пусть, если в открытом конверте лежит $\textstyle x>L/2$, раунд игры останавливается. Игрок ничего не выбирает и не получает. Игра происходит, только если $\textstyle x<L/2$.

Найдём доходы от стратегии выбора открытого конверта $\textstyle v_{1}$ и выбора закрытого конверта $\textstyle v_{2}$. При выборе открытого конверта игрок всегда получает ту сумму которую видит: $\textstyle v_{1}=x$. При выборе закрытого конверта необходимо воспользоваться условными вероятностями:

$v_{2}={\frac {2}{3}}\cdot (2x)+{\frac {1}{3}}\cdot (x/2)={\frac {3}{2}}\,x.$

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

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

$\left\langle x\right\rangle ={\frac {2}{3}}\cdot {\frac {L}{4}}+{\frac {1}{3}}\cdot {\frac {L}{4}}={\frac {L}{4}},$

где $\textstyle L/4$ — среднее значение меньшей суммы, а $\textstyle L/4$ — среднее значение большей на интервале $\textstyle [0,L/2]$ (при условии, что игра началась, т.е. $\textstyle x<L/2$). Фактически сразу можно написать $\textstyle L/4$, так как это середина интервала для сумм, возможных в первом конверте. Поэтому при взятии закрытого конверта получается доход $\textstyle \left\langle v_{2}\right\rangle =(3/2)\cdot (L/4)=3L/8=0.375L$. Эта сумма несколько ниже, чем в игре которая начинается независимо от суммы в открытом конверте.

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

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

$1,\;2,\;2^{2},\;2^{3},\;...,\;2^{n}.$

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

$(1,2);\;(2,2^{2});\;(2^{2},2^{3});\;....;\;(2^{n-1},2^{n}),$

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

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

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

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

Для $\textstyle n+1$ чисел вероятность появления (в игре) в первом конверте сумм от 2 до $\textstyle 2^{n-1}$ одинаковые и равны $\textstyle 1/(n-1)$. Чтобы найти вероятности во втором конверте необходимо посчитать число квадратиков в гистограмме. В нижнем ряду их $\textstyle n+1$, а в верхнем $\textstyle n+1-4$. Поэтому всего их $\textstyle 2(n-1)$. В результате вероятности сумм в середине диапазона равны $\textstyle 1/(n-1)$, а по краям — $\textstyle (1/2)/(n-1)$.

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

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

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

$v_{1}={\frac {2+...+2^{n-1}}{n-1}}={\frac {2(2^{n-1}-1)}{n-1}}\to {\frac {2^{n}}{n}},$

где использована известная формула для суммы геометрической прогрессии $\textstyle 1+q+q^{2}+...+q^{n}=(q^{n+1}-1)/(q-1)$ и записано выражение, к которому стремиться $\textstyle v_{1}$ при $\textstyle n\to \infty$. Аналогично вычисляется средний доход при выборе второго конверта:

$v_{2}={\frac {2+...+2^{n-2}}{n-1}}+{\frac {1+2+2^{n-1}+2^{n}}{2(n-1)}}={\frac {5}{4}}\,v_{1}.$

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

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

$1+2+...+2^{n-1}=2^{n}-1.$

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

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

Решение или проверка решения задач по теории вероятности почти всегда могут быть реализованы при помощи компьютера. Ниже приведен исходный код на C++, который моделирует игру с непрерывным постоянным распределением вероятностей шириной $\textstyle L$. \cppsrc{envel.cpp} \\ \\ Закомментированная строка соответствует дополнительному условию по началу игры (прерываем раунд). Любое компьютерное моделирование требует проведения статистической оценки достоверности полученных результатов. Можно поступить проще и поставить встряхиватель случайных чисел (строка srand(time(0)); ). Несколько последовательных запусков позволит увидеть, какая цифра "дёргается". Это и есть примерная ошибка моделирования.

Степанов Сергей begin_of_the_skype_highlighting     end_of_the_skype_highlighting по просьбе Степанова Дениса

(с) 2010, synset.com