Адаптивная выигрышная стратегия для проблемы двух конвертов
Рассматривается пороговая стратегия для проблемы двух конвертов. Предлагается подход, позволяющий адаптивно находить оптимальный порог. Приводятся результаты экспериментальных исследований. Розглядається порогова стратегія для проблеми двох конвертів. Пропонується підхід, який дозволяє адаптивно зна...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84579 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Адаптивная выигрышная стратегия для проблемы двух конвертов / В.П. Шило, В.А. Рощин // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 153-160. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860051003220426752 |
|---|---|
| author | Шило, В.П. Рощин, В.А. |
| author_facet | Шило, В.П. Рощин, В.А. |
| citation_txt | Адаптивная выигрышная стратегия для проблемы двух конвертов / В.П. Шило, В.А. Рощин // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 153-160. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассматривается пороговая стратегия для проблемы двух конвертов. Предлагается подход, позволяющий адаптивно находить оптимальный порог. Приводятся результаты экспериментальных исследований.
Розглядається порогова стратегія для проблеми двох конвертів. Пропонується підхід, який дозволяє адаптивно знаходити оптимальний поріг. Наводяться результати експериментальних досліджень.
Threshold strategy for a problem of two envelopes is considered. The paper proposes an approach to obtain optimum threshold. The results of computing experiments are given.
|
| first_indexed | 2025-12-07T17:00:06Z |
| format | Article |
| fulltext |
Компьютерная математика. 2010, № 1 153
Рассматривается пороговая стра-
тегия для проблемы двух конвер-
тов. Предлагается подход, позво-
ляющий адаптивно находить оп-
тимальный порог. Приводятся ре-
зультаты экспериментальных ис-
следований.
В.П. Шило, В.А. Рощин, 2010
ÓÄÊ 519.854
Â.Ï. ØÈËÎ, Â.À. ÐÎÙÈÍ
ÀÄÀÏÒÈÂÍÀß ÂÛÈÃÐÛØÍÀß
ÑÒÐÀÒÅÃÈß ÄËß ÏÐÎÁËÅÌÛ
ÄÂÓÕ ÊÎÍÂÅÐÒÎÂ
Введение. Проблема (парадокс) двух конвер-
тов была сформулирована около 80 лет тому
назад [1], но по-прежнему вызывает большой
интерес у исследователей, о чем можно су-
дить по многочисленности посвященных ей
публикаций [1–10]. В некоторых работах
[4, 5] даются объяснения парадокса, в других
[6–8] обосновывается неполнота этих объяс-
нений и ведутся дискуссии о том, в чем же
собственно состоит парадокс. На фоне этих
работ своей практической направленностью
выделяется работа [9]. В ней рассматривают-
ся вопросы существования выигрышных
стратегий при обмене конвертов. Этой же
теме посвящена данная работа, в которой
предлагается адаптивная выигрышная стра-
тегия обмена конвертов (рис. 1).
РИС. 1
Проблема двух конвертов уже дала толчок
многим исследованиям в области теории ве-
роятностей, теории игр, теории принятия
решений [11]. Кроме того, во многих при-
кладных областях (экономика, фондовые
рынки, технические системы, оптимизация)
возникают ситуации, подобные выбору меж-
ду конвертами. Все это и стимулирует инте-
рес к этой проблеме.
В.П. ШИЛО, В.А. РОЩИН
154 Компьютерная математика. 2010, № 1
Суть проблемы. Парадокс двух конвертов состоит в следующем. Предпо-
ложим, что вы участвуете в следующей игре: перед вами лежат два одинаковых
конверта с деньгами, суммы которых не известны. Известно лишь, что в одном
из конвертов находится сумма, в два раза превышающая сумму в другом кон-
верте. Вы можете выбрать любой конверт и посмотреть, какая сумма находится
в нем, затем оставить этот конверт с деньгами себе либо поменять его на другой.
Далее игра повторяется. Ваша цель – получить по возможности большую сумму
денег с помощью некоторой стратегии обмена конвертов. На первый взгляд, ве-
роятность наличия в выбранном вами конверте большей суммы равна вероятно-
сти того, что в нем лежит меньшая сумма (это следует из произвольности ваше-
го выбора конверта). Вам не известна процедура, с помощью которой выбира-
ются суммы, положенные в конверт. Далее делается вывод, что с равной вероят-
ностью в другом конверте находится сумма или в два раза меньшая или в два
раза большая, чем сумма в выбранном конверте. Но тогда, если в выбранном
конверте находится x грн, то математическое ожидание суммы во втором кон-
верте равно 0.5(x/2) + 0.5(2x) = 1.25x грн. Получается, что выгодно всегда менять
выбранный конверт. Очевидно, что этот вывод вступает в противоречие со здра-
вым смыслом, который говорит о равноценности конвертов. Это и порождает
парадокс.
Интуитивно понятно, что стратегии «никогда не менять конверты» и «все-
гда менять конверты» подобны и не приводят ни к выигрышу, ни к проигрышу.
Действительно, если применяется одна из этих стратегий, то открывать конверт
ни к чему: увиденная сумма ничего не изменит. Но тогда, в случае первой стра-
тегии, произвольно выбранный конверт не меняется, а в случае второй стратегии
всегда меняется, что в среднем приводит к одинаковым результатам. Из этих
соображений следует, что стратегия «менять конверты с заданной вероятно-
стью p» подобна первым двум и дает те же результаты. Эти утверждения
нетрудно доказать [9].
Подход к решению. Для дальнейшего изложения понадобится некоторая
формальная модель. Будем считать, что случайная величина ( )ξ ω принимает
значения k = 0,1,2,… с вероятностью p(k). Опишем процедуру генерации сумм
в конвертах. Пусть
_
ξ − реализация случайной величины ( )ξ ω . Тогда в один кон-
верт кладется
_
ξ грн, а во второй – либо
_
2ξ грн, либо
_
2 1ξ+ грн с равными веро-
ятностями.
АДАПТИВНАЯ ВЫИГРЫШНАЯ СТРАТЕГИЯ ДЛЯ ПРОБЛЕМЫ ДВУХ КОНВЕРТОВ
Компьютерная математика. 2010, № 1 155
Вышеописанные рассуждения приводят к мысли, что все стратегии, не ис-
пользующие величину суммы в открытом конверте, подобны и дают одинако-
вый результат. Однако использование этой величины приводит к выигрышным
стратегиям [9] в силу того, что открытие конверта ведет к исчезновению равно-
ценности конвертов. Действительно, пусть в открытом конверте мы видим x
гривен. Это произойдет, в соответствии с описанной процедурой, при наступле-
нии одного из двух событий A = {ξ(ω) = x/2} или B = { ξ(ω) = x} (здесь и далее
при делении в качестве частного рассматривается целая часть числа, например,
3/2=1). Воспользовавшись формулой Байеса, получаем
{ } { }
{ } { }
0.5 0.5 ( / 2)
| видим грн.
0.5 0.5 ( / 2) ( )
P A p x
P A x
P A P B p x p x
= =
+ +
,
{ } { }
{ } { }
( )
| видим грн.
0.5 0.5 ( / 2) ( )
P B p x
P B x
P A P B p x p x
= =
+ +
,
где P{A}– вероятность события A, p(x) – функция вероятности.
Таким образом, после открытия конверта условная вероятность наличия во
втором конверте x/2 грн равна
0.5 ( / 2)
0.5 ( / 2) ( )
p x
p x p x+
, а вероятность того, что в нем
находится 2x грн, равна
( )
0.5 ( / 2) ( )
p x
p x p x+
. Следовательно, математическое ожи-
дание E суммы во втором конверте равно
( )0.25 ( / 2) 2 ( )
0.5 ( / 2) ( )
x p x p x
p x p x
+
+
, и оптимальная
стратегия обмена конвертов состоит в том, чтобы менять конверты при x E≤
и не менять их в противном случае.
Однако реализация такой стратегии требует знания вероятностей p(k),
k = 0,1,2,…, которым мы не обладаем. Рассмотрим стратегию обмена конвертов,
использующую некоторое заданное пороговое значение h. Пусть в открытом
конверте находится x гривен. Тогда при x > h обмен конвертов не производится,
в противном случае происходит обмен конвертов. Проанализируем эту страте-
гию. Рассмотрим три случайных события: { } { }( ) / 2 , / 2 ( )A h B h h= ξ ω ≤ = < ξ ω ≤
и { }C= ( ) hξ ω > . Очевидно, что при наступлении событий A и B всегда
происходит обмен конвертов, а при наступлении события C этого обмена нет.
В.П. ШИЛО, В.А. РОЩИН
156 Компьютерная математика. 2010, № 1
В силу произвольности выбора первого конверта очевидно, что при наступлении
событий A и C выигрыша / проигрыша в среднем не будет. А вот при наступле-
нии события B c вероятностью 0.5 будет выигрыш реализации
_
ξ случайной ве-
личины ( )ξ ω , так что средний выигрыш составит
/ 2
0.5 ( )
h
k h
kp k
=
∑ .
Вышеприведенные рассуждения делают понятной идею адаптивной страте-
гии. После каждого розыгрыша конвертов пороговое значение выбирается таким
образом, чтобы сумма
[ ]
_
_
/ 2,i
i
h hξ ∈
ξ∑ была максимальной, где
_
iξ , i = 1,.., n − реализа-
ции случайной величины ( )ξ ω , а n – число розыгрышей.
Рассмотрим следующую процедуру, задав величину d.
Шаг 1. Инициализация: H = k = 0, 0h hw n= = , h = 0,1,2…
Шаг 2. Полагаем k=k+1. Пусть величина kζ с вероятностью 0.5 равна
_
kξ
и с вероятностью 0.5 равна 2
_
kξ .
Шаг 3. Если H + d ≤ kζ , конверты обмениваются, иначе обмен не происходит.
Шаг 4. Пусть
_
2 , ,
, ,
k
h
h
h
ξ ζ ≤θ =
ζ ζ >
для всех h ≤ H+d. Полагаем hn =
1, .h h h hn w w= + = + θ
Шаг 5. Находим значение порога *h , при котором величина /h hw n имеет
максимальное значение. Полагаем H = *h и переходим на шаг 2.
Если hn → ∞ , то очевидно, что при применении порога h величина /h hw n
стремится к среднему доходу участника. Отсюда следует, что величина H
сходится к оптимальному значению порога. Описанная процедура позволяет
построить адаптивную выигрышную стратегию при задании некоторого числа
d > 0.
Результаты экспериментальных исследований. Для проверки предло-
женной адаптивной стратегии был проведен вычислительный эксперимент при
d = 16. Аналогично [9] моделировалось экспоненциальное распределение
АДАПТИВНАЯ ВЫИГРЫШНАЯ СТРАТЕГИЯ ДЛЯ ПРОБЛЕМЫ ДВУХ КОНВЕРТОВ
Компьютерная математика. 2010, № 1 157
с плотностью 3
1
( )
3
t
f t e
−
= . Было проведено миллиард имитаций. Вероятности
определялись по формуле
( 1)
( ) ( )
k s
ks
p k f t dt
+
= ∫ , где s = 0.01.
На рис. 2 приведены графики вероятностей генерации пар (k, 2k), (p1(k));
(k/2, k), (p2(k)) и график вероятности p_see(k) увидеть в открытом конверте k грн.
На графиках (рис. 3) представлены вероятности pl(k) и pg(k) наличия во вто-
ром конверте соответственно меньшей или большей суммы по сравнению с со-
держащимися в открытом конверте k грн. График (рис. 4) отражает зависимость
математического ожидания суммы денег во втором конверте от суммы, находя-
щейся в открытом конверте. Пересечение этого графика с прямой y = k опреде-
ляет оптимальный порог.
График (рис. 5) отражает результаты применения адаптивной процедуры.
РИС. 2
В.П. ШИЛО, В.А. РОЩИН
158 Компьютерная математика. 2010, № 1
РИС. 3
РИС. 4
АДАПТИВНАЯ ВЫИГРЫШНАЯ СТРАТЕГИЯ ДЛЯ ПРОБЛЕМЫ ДВУХ КОНВЕРТОВ
Компьютерная математика. 2010, № 1 159
РИС. 5
Как видно из приведенных графиков, уже после сотни имитаций выигрыши
от адаптивной стратегии и от стратегии с оптимальным значением порога прак-
тически совпадают, хотя и наблюдаются колебания значения настраиваемого
порога вокруг оптимального.
Заключение. Из вышесказанного следует, что до открытия конвертов си-
туация является симметричной. Однако после открытия одного конверта оба
конверта уже не равноценны, а их обмен с использованием порога позволяет по-
лучать выигрыш при большом числе розыгрышей. Это похоже на парадокс
«кота Шредингера»”, что близко к проблеме влияния наблюдателя на результат
наблюдения и свидетельствует о близости данной тематики к неким основам
природы. Целесообразно и далее продолжать исследования в этом направлении,
поскольку рассматриваемая проблема имеет, как отмечалось выше, много воз-
можных приложений, например, фондовый рынок и др.
В.П. Шило, В.О. Рощин
АДАПТИВНА ВИГРАШНА СТРАТЕГІЯ ДЛЯ ПРОБЛЕМИ ДВОХ КОНВЕРТІВ
Розглядається порогова стратегія для проблеми двох конвертів. Пропонується підхід, який
дозволяє адаптивно знаходити оптимальний поріг. Наводяться результати експеримен-
тальних досліджень.
В.П. ШИЛО, В.А. РОЩИН
160 Компьютерная математика. 2010, № 1
V.P. Shylo, V.O. Roschyn
ADAPTIVE WINNING STRATEGY FOR THE PROBLEM OF TWO ENVELOPES
Threshold strategy for a problem of two envelopes is considered. The paper proposes an approach to
obtain optimum threshold. The results of computing experiments are given.
1. Kraitchik M. Le paradoxe des cravates. In La mathematique des jeux. – Bruxelles, Belgium: Im-
primerie Stevens Frères, 1930. – 253 p.
2. Zabell S. Loss and gain: the exchange paradox. In Bayesian Statistics, Proc. 3rd Valencia Int.
Meeting (eds J.M. Bernardo, M.H. DeGroot, D.V. Lindley & A.F.M. Smith), Oxford, UK:
Clarendon Press. –1988. – P. 233–236.
3. Agnew R.A. On the two-box paradox // Math. Mag. – 2004 . – 7. – P. 302–308.
4. Christensen R., Utts J. Bayesian resolution of the «exchange paradox» // Am. Stat. – 1992. – 46.
– P. 274–276.
5. McGrew T., Shier D., Silverstein H. The two-envelope paradox resolved // Analysis. – 1997. –
57. – P. 28–33.
6. Castell P., Batens D. The two envelope paradox: the infinite case // Analysis. – 1994. – 54. –
P. 46–49.
7. Clark M., Shackel N. The two-envelope paradox // Mind. – 2000. –109. – P. 415–442.
8. Albers C.J., Kooi B.P., Schaafsma W. Trying to solve the two-envelope problem // Synthese. –
2005. –145. – P. 89–109.
9. Varshamov R.R. A class of codes for asymmetric channels and a problem from the additive the-
ory of numbers // IEEE Trans. Inform. Theory. – 1973. – 19. – P. 92 –95.
10. McDonnell M.D., Abbott D. Randomized switching in the two-envelope problem // Proc. R. Soc.
A. – 2009. – 465, N 2111. – P. 3309–3322.
11. Abbott D. Overview: unsolved problems of noise and fluctuations // Chaos. – 2001. – 11, N 3. –
P. 526–538.
Получено 26.01.2010
Îá àâòîðàõ:
Шило Владимир Петрович,
доктор физико-математических наук, ведущий научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
e-mail: v.shylo@gmail.com
Рощин Валентина Алексеевна,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
e-mail: d135@i.com.ua
|
| id | nasplib_isofts_kiev_ua-123456789-84579 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T17:00:06Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, В.П. Рощин, В.А. 2015-07-10T14:56:08Z 2015-07-10T14:56:08Z 2010 Адаптивная выигрышная стратегия для проблемы двух конвертов / В.П. Шило, В.А. Рощин // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 153-160. — Бібліогр.: 11 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84579 519.854 Рассматривается пороговая стратегия для проблемы двух конвертов. Предлагается подход, позволяющий адаптивно находить оптимальный порог. Приводятся результаты экспериментальных исследований. Розглядається порогова стратегія для проблеми двох конвертів. Пропонується підхід, який дозволяє адаптивно знаходити оптимальний поріг. Наводяться результати експериментальних досліджень. Threshold strategy for a problem of two envelopes is considered. The paper proposes an approach to obtain optimum threshold. The results of computing experiments are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Адаптивная выигрышная стратегия для проблемы двух конвертов Адаптивна виграшна стратегія для проблеми двох конвертів Adaptive winning strategy for the problem of two envelopes Article published earlier |
| spellingShingle | Адаптивная выигрышная стратегия для проблемы двух конвертов Шило, В.П. Рощин, В.А. Теория и методы оптимизации |
| title | Адаптивная выигрышная стратегия для проблемы двух конвертов |
| title_alt | Адаптивна виграшна стратегія для проблеми двох конвертів Adaptive winning strategy for the problem of two envelopes |
| title_full | Адаптивная выигрышная стратегия для проблемы двух конвертов |
| title_fullStr | Адаптивная выигрышная стратегия для проблемы двух конвертов |
| title_full_unstemmed | Адаптивная выигрышная стратегия для проблемы двух конвертов |
| title_short | Адаптивная выигрышная стратегия для проблемы двух конвертов |
| title_sort | адаптивная выигрышная стратегия для проблемы двух конвертов |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84579 |
| work_keys_str_mv | AT šilovp adaptivnaâvyigryšnaâstrategiâdlâproblemydvuhkonvertov AT roŝinva adaptivnaâvyigryšnaâstrategiâdlâproblemydvuhkonvertov AT šilovp adaptivnavigrašnastrategíâdlâproblemidvohkonvertív AT roŝinva adaptivnavigrašnastrategíâdlâproblemidvohkonvertív AT šilovp adaptivewinningstrategyfortheproblemoftwoenvelopes AT roŝinva adaptivewinningstrategyfortheproblemoftwoenvelopes |