Парадокс обмена

[sergey zhukov]

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

Каждый участник рассуждает так: в моем конверте $x$, значит в конверте противника с вероятностью $50/50$ либо $x/2$, либо $2x$. Если $x/2$, то при обмене я теряю $x/2$. Если $2x$, то при обмене я выигрываю $x$. Т.к. оба случая равновероятны, обмен мне выгоден. Так рассуждает каждый, что невозможно. В чем ошибка?

Есть простой ответ. Рассуждение должно быть таким: общая сумма в конвертах равна $x$. Тогда ее равновероятное распределение между нами может быть $3/2x$ и $1/2x$ или наоборот. Обмен ничего не меняет в среднем.

Но ведь мы ничего не знаем о сумме $x$. Она ничем не ограничена. Если у меня в конверте $x$, то у другого действительно равновероятно может быть $x/2$, либо $2x$. Почему эта логика не работает?

Я вижу только такое объяснение: такая логика предполагает, что общая разыгрываемая сумма - это случайная величина, равномерно распределенная на бесконечном интервале. Т.е. это ноль. Любое равномерное распределение ограничено, а неограниченное - неравномерно. Следовательно, вероятность того, что у противника $x/2$ на самом деле больше, чем вероятность того, что у него $2x$ при достаточно больших $x$. В случае ограниченного равномерного распределения это особенно очевидно. Если даже я не знаю его границу, то она все равно существует и для некоторого достаточно большого $x$ вероятность, что у противника $x/2$ равна $1$, а вероятность того, что у него $2x$ равна $0$.

А вы как считаете?

[mihaild]

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

[worm2]

Можно по-простому объяснить:

sergey zhukov в сообщении #1422517 писал(а):

мы ничего не знаем о сумме $x$. Она ничем не ограничена.

Это неверное допущение. На самом деле никто в конверт не положит миллион долларов. Ни одно шоу в мире не окупится, если будет так делать. Да и тысячу далеко не все могут себе позволить положить. Передача с большим охватом телеаудитории может позволить себе более крупный бюджет, с меньшим — поменьше. Когда мы рассуждаем о том, меньшая ли в нашем конверте сумма или же большая, мы по сути оцениваем этот бюджет. И если он в действительности окажется существенно меньше или существенно больше нашей оценки — мы проиграем.
Правда, если игра продолжается многократно, то бюджет дробится на маленькие суммы, которые между собой могут отличаться очень сильно. Здесь стратегия усложняется, но и тут можно что-то оценить исходя из примерного количества раундов и уже потраченной суммы. По сути, стратегия одна: если сумма в конверте меньше некоторого порога, мы меняемся, если больше — держим деньги при себе. По ходу игры порог меняется. Начальное его значение и величину изменения можно рассчитать исходя из априорных оценок суммарного бюджета и числа раундов. Если же суммарный бюджет, число раундов и (может быть) ещё функция распределения вероятности следующей ставки заданы заранее, мне кажется, тут интересная задачка получается на оптимальную стратегию. Даже ряд задач: ведущий может быть нейтрален, а может играть против игрока со своей стратегией; суммы могут быть кратны, скажем, 1 доллару, 10 долларам или 1 центу; и т.п.

-- Сб окт 26, 2019 23:10:02 --

Правда, я ещё не подумал, как быть, если суммы в конвертах заданы в неких условных единицах, причём в каждом раунде курс этой условной единицы к реальной валюте может быть произвольным. Тут всё равно будут какие-то ограничения, но мне уже сложнее сообразить, какие. Тут тоже интересные варианты могут быть. Например, если мы условимся, что числа всегда целые, то, очевидно, нужно меняться, если в моём конверте нечётное число. Усложняя мне задачу, ведущий, разумеется, сделает все суммы чётными, и в игру вступает делимость на 4, и т.д. Тут ресурсом будет максимальная степень двойки, на которую будут делиться все числа и, понятно, что этот ресурс тоже до бесконечности не сможет расти и мне нужно будет гадать, докуда организаторы будут готовы этот ресурс увеличивать, чтобы у зрителя не рябило в глазах от обилия цифр.

-- Сб окт 26, 2019 23:17:26 --

В каких-то формулировках действительно может быть выгоден обмен. Например, мне всегда приходит конверт с надписью "1 у.е.", а сопернику с равной вероятностью — либо "2 у.е.", либо "1/2 у.е.". Тут всё очевидно и никакого парадокса нет. Но если ведущий играет против меня, мне, наоборот, выгоднее никогда не меняться (стандартный расчёт теории игр приводит к такому ответу).

[sergey zhukov]

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

Если ведущий пристрастен, теория вероятности становится просто бесполезной.
Например, возьмем известный парадокс Монти Холла. Есть три случая настроя ведущего: он против нас ($-$), за нас ($+$) или ему все равно ($0$) (всегда предлагает перевыбрать). Если он против нас, перевыбирать нельзя, если за нас - перевыбирать обязательно. Если ему все равно, то перевыбор повышает наши шансы на выигрыш вдвое. Только в последнем случае имеет смысл применять теорию вероятностей. В первых двух никакой неопределенности просто нет, там все точно известно.
Перевыбирать однозначно выгодно только тогда, когда суммарная вероятность случаев $+$ и $0$ выше, чем $-$, но это скорее задача по психологии. Парадокс Монти Холла сформулирован для случая $0$.

Кстати, этот парадокс можно сформулировать так, что ответ будет очевиден. Представим себе, что ведущий сам совершенно ничего не знает о том, в какой ящике приз (скажем, маленький ключ). После того, как вы выбрали свой ящик (скажем, №1), ведущий просто берет ящик №2 и вытряхивает его содержимое в ящик №3 (или наоборот). Причем он так плотно подносит ящики друг к другу, что ни вы ни он не видите, пересыпается ли что-то из одного ящика в другой или нет. После этого он показывает пустой ящик, из которого только что пересыпал и спрашивает, не хотите ли вы перевыбрать? Очевидно, что хотим, ведь теперь в оставшемся ящике содержимое сразу двух ящиков, а в нашем - только одного.
Почему такой вариант проще для понимания? Дело в том, что когда ведущий открывает пустой ящик, он заранее должен знать, какой из них пуст. Его действия не случайны: он не может открыть ящик с ключом. Открывание пустого ящика не бесполезно, оно показывает нам, какой ящик ведущий не может открыть. А в варианте с перетряхиванием он сам не знает, где ключ, и действует случайно, все происходит автоматически. Поэтому в первом случае помощь ведущего не очевидна, она заключена в том, что он не может делать, а во втором – очевидна, она заключена именно в том, что он делает.


Да, выше вместо $1/2x$ и $3/2x$ нужно было написать $1/3x$ и $2/3x$. Ошибся.

[Лукомор]

sergey zhukov в сообщении #1422517 писал(а):

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

Два замечания.

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

2.

sergey zhukov в сообщении #1422517 писал(а):

Каждый участник рассуждает так: в моем конверте $x$, значит в конверте противника с вероятностью $50/50$ либо $x/2$, либо $2x$. Если $x/2$, то при обмене я теряю $x/2$. Если $2x$, то при обмене я выигрываю $x$. Т.к. оба случая равновероятны, обмен мне выгоден. Так рассуждает каждый, что невозможно. В чем ошибка?

Ошибка в том, что в целом для двух игроков ожидание выигрыша переоценено.
Первый участник, у которого в конверте $x$, ожидает получить либо $x/2$, либо $2x$, то-есть, в среднем - $5x/4$.
Но у второго участника в конверте не $x$, а $y = 2x$, и он ожидает получить либо $y/2 = x$, либо $2y = 4x$,
то есть, в среднем $5x/2$.
Таким образом, два участника в сумме ожидают получить $15x/4$, хотя в двух конвертах реально находится $x+y = 3x$.
Ожидание выигрыша, в целом, - переоценено.

[podih]

Проще всего плясать от МО. Для двух равновозможных наборов $(1, 2), (2, 4) $ оно равно $(1+2\cdot 2+4)/4=9/4=2.25$. При n=1 или n=4 выбор очевиден. При n=2 меняться выгодно!
Далее МО растёт как $21/6, 45/8, 93/10, 189/12, 381/14, ...$ - числители можно обнаружить в A068156 OEIS. - Если сумма в твоём ящике меньше твоего МО - меняйся.
Про неограниченность верхнего предела ведущий ничего не говорит: число денег в ящиках ограничено объёмом последних.

[Евгений Машеров]

Я бы механизм появления данного парадокса назвал "Заблуждение опытного школьника". Который знает, что задачи из учебника всегда можно решить на основе приведенных в задаче условий. А стало быть, если что-то в условии не указано, это для решения несущественно. Можно приняь по своему усмотрению. А не указано распределение бюджета конкурса, какова вероятность, что на выигрыши будет назначено x рублей. И думая, что неуказанная информация несущественна, неизвестное распределение заменяют "несобственным", с равной вероятностью всех сумм без ограничения сверху. Однако это существенно, зная сумму в своём конверте X и вероятностное распределение призовых сумм $p(x)$, можно построить выигрышную стратегию.
Очевидно, что если на руках Х, то общая сумма либо 3Х, либо 1.5Х. А дальше Байес и оценка вероятности того, что на руках меньший конверт и менять надо. Но если распределение сумм призовых неизвестно - оснований для решения нет, заменять неизвестное распределение каким-то произвольным - ошибка, а невозможным в реальности - вообще нонсенс.

[sergey zhukov]

Лукомор в сообщении #1422588 писал(а):

Но у второго участника в конверте не $x$, а $y = 2x$

Тут, видимо, должно быть среднее между $x/2$ и $2x$, которые я ему приписываю, т.е. $y = 1,25x$.

Да, если я приписываю себе $x$, то должен приписать противнику $1,25x$. А он, согласно зеркальной логике, должен в это же время приписывать мне уже $1,25^2x$.

Я бы сказал так: каждый рассматривает два варианта и считает, что если в игре общая сумма больше ($x+2x$), то он обделен (на $x$), а если меньше ($x+x/2$) - то он в выигрыше (на $х/2$). Т.е. неявно вводится зависимость между величиной общей суммы и вероятностью ее распределения.

Евгений Машеров
Нужно учитывать, что игроки принимают решение до вскрытия конвертов. Никто из них не знает, сколько денег он получил. Когда рассуждают об $x$, то это реально неизвестная величина для игрока. Единственное, что можно предполагать, это что разыгрываемая сумма - случайная величина с каким-то неизвестным распределением. Формулировка задачи подталкивает к тому, что это неограниченное равномерное распределение, т.е. невозможное.

podih
Простите, не уловил нить рассуждений.

[podih]

sergey zhukov
Кто-то уловит.
Я не пострадал, чтобы прощать.

[Yadryara]

sergey zhukov в сообщении #1422605 писал(а):

Лукомор в сообщении #1422588 писал(а):

Но у второго участника в конверте не $x$, а $y = 2x$

Тут, видимо, должно быть среднее между $x/2$ и $2x$, которые я ему приписываю, т.е. $y = 1,25x$.

Условие есть условие. У одного(назовём его первым) в конверте $x$, а у другого(назовём его вторым) $2x$. Так что Лукомор прав, а приведённые в стартовом посте рассуждения игроков ошибочны.

podih, вы не заметили, что совсем рядом с окошком для ответа есть тег oeis ?

[podih]

sergey zhukov в сообщении #1422605 писал(а):

Формулировка задачи подталкивает к тому, что это неограниченное равномерное распределение, т.е. невозможное.

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


Yadryara, да, спасибо.

[Лукомор]

sergey zhukov в сообщении #1422517 писал(а):

Участники могут поменяться конвертами перед тем, как их вскрыть, если хотят.

Совершенно невероятное условие вы выдумали! Зачем менять конверты, перед тем как их вскрыть?
И что будем делать, если один участник непременно хочет поменять конверт на противоположный,
а второй категорически против?

-- Вс окт 27, 2019 14:09:47 --

sergey zhukov в сообщении #1422517 писал(а):

Какая стратегия максимизации выигрыша?

Чьего выигрыша?! Кто против кого играет?
И что понимать под выигрышем в данном случае?
Вы в каждом туре только получаете деньги, ничего не вкладывая.
Проиграть в такую игру невозможно, Вы всегда будете в выигрыше,
при положительном сальдо, независимо от стратегии.

[sergey zhukov]

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

[worm2]

sergey zhukov в сообщении #1422645 писал(а):

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

Соглашусь. Я попробовал ещё проще, но получилось что-то не то.

[Лукомор]

sergey zhukov в сообщении #1422645 писал(а):

Суть парадокса в том, что меняться получается выгодно даже вслепую.

Выгоднее - не получается!

Вслепую, - так оно и вообще не получается, потому что, если взять конверт, и не глядя поменяться,
и это еще и выгодно, то это означает, что с вероятностью $P=1$ Вы всегда выбираете конверт с меньшей суммой, и меняете ее на конверт с большей суммой, причем такое получается у обоих игроков одновременно...
Никакие обмены, до вскрытия первого конверта, на результат не влияют вообще., иначе, поменявшись дважды,
и вернувшись к исходным конвертам, получили бы еще больший выигрыш.

Теперь, еще раз, внимательно следите за руками!
У меня есть белые перчатки, два конверта, и триста долларов.
Я одеваю перчатки, бережно укладываю в один конверт сто долларов,
в другой конверт - двести долларов, заклеиваю конверты, укладываю на серебряный поднос,
и выношу игрокам.
Один берет конверт, вскрывает его, заглядывает, так чтобы не видел второй игрок, и видит там сто долларов.
И решает меняться, поскольку при обмене может получить либо $50$, либо $200$ долларов, в среднем, где-то
$125$.
Второй находит в своем конверте $200$ долларов,
следовательно, при обмене он может получить либо $100$, либо $400$ долларов, в среднем $250$.
Получается, что имея на руках $300$ долларов на двоих, в результате обмена игроки будут иметь в среднем на двоих 375 долларов, а в самом удачном раскладе, даже $450$!
Разумеется, они с радостью соглашаются на обмен.
В результате первый, со $100$ имеет $100 + 100 = 200$, а второй с двухсот имеет $200 - 100 = 100$.
Сто долларов перекочевали от второго к первому, и в сумме они имеют те же $300$, что и до обмена конвертами.
Никаких $375$ , и уж тем более $450$ не наблюдается.

Уф-ф!
Кажется, нигде не соврал, кроме белых перчаток, и серебряного подноса, которых у меня нет!