Consider a game where you can toss a fair coin up to 10 times. The payoff you get is the number of heads obtained divided by the number of tosses you've taken. After any toss you've got the choice of stopping there and then, taking your payoff, or to continue going. For example, If you've tossed the coin 5 times of which 3 were heads, if you decided to stop the game there and then you'd received 3/5 = $0.60 ... or you could keep going and hope for a higher value.
What is the fair price of this game?

Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
Какова наиболее выигрышная стратегия?

Здравствуйте, SEH, Вы писали:

SEH>Какова наиболее выигрышная стратегия?

Остановиться как только текущий выигрыш будет больше 0.5
Если первой выпала решка, то соответственно больше и не кидать

Здравствуйте, SEH, Вы писали:

Маленькая поправка: heads — это орлы, а решки — это tails.
fair price — это не выигрышная стратегия, а справедливая цена (за участие в игре).

Здравствуйте, hexamino, Вы писали:

H>fair price — это не выигрышная стратегия, а справедливая цена (за участие в игре).

И в самом деле
Перевод исказил задачу...

Здравствуйте, SEH, Вы писали:

SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

У меня получилось так:

Математическое ожидание выигрыша при правильной игре = 0.7436972966269841

Стратегия такая. Если уже было сделано k ходов, то остановимся в том случае, если ранее монеты выпадала нужным образом (решкой?) чаще, чем k/2.
Например, выпало 3 раза из 4 ходов — останавливаемся (3 > 4/2). Выпало 3 из 7 — играем дальше (3 <= 7/2).

А>Остановиться как только текущий выигрыш будет больше 0.5
А>Если первой выпала решка, то соответственно больше и не кидать

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

А для вычисления fair price просто рекурсивную функцию написать.

Код на Писуне:

>>> def foo(a, b, n):
...    if (b == 0):
...      frac = 0.5
...    else:
...      frac = a/b
...      if (frac > 0.5):
...        return(frac)
...    if (n == 0):
...      return(frac)
...    return(0.5*foo(a, b+1, n-1) + 0.5*foo(a+1, b+1, n-1))
...
>>> print(foo(0, 0, 10))
0.743697296627

Здравствуйте, dilmah, Вы писали:

D>А для вычисления fair price просто рекурсивную функцию написать.
...
>>>> print(foo(0., 0., 10)

У меня заработало при мелком фиксе выше. Fair price это, как я понимаю, мат ожидание?

>>>>> print(foo(0., 0., 10)
SEH>У меня заработало при мелком фиксе выше.

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

> Fair price это, как я понимаю, мат ожидание?

я тоже так понял

Здравствуйте, dilmah, Вы писали:


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

Не могу понять в какие неравенства. Может, хинт на тему как должно выглядеть строгое доказательство?

D>А для вычисления fair price просто рекурсивную функцию написать.
D>

>>>> def foo(a, b, n):
>> skipped
D>

Почему ?

Здравствуйте, dilmah, Вы писали:

D>жесть, это я планировал ознакомиться с новым языком, написал первую программу,
D>и оказалось что 2 реализации (windows и linux) интерпретируют простейший код по разному.
D>Это даже хуже перла..

Можно чуть подробнее?
Под какой версией/реализацией/ОС сработал вариант с foo ( 0, 0, 10 ) (целочисленными нулями)?

AF>Под какой версией/реализацией/ОС сработал вариант с foo ( 0, 0, 10 ) (целочисленными нулями)?

Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> print(1/2)
0.5

ну, собственно, на сайте так и написано "the new backwards-incompatible series of Python"..

Здравствуйте, Alexey F, Вы писали:

AF>Здравствуйте, dilmah, Вы писали:

D>>Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on
D>>win32
D>>Type "help", "copyright", "credits" or "license" for more information.
>>>>> print(1/2)
D>>0.5

D>>ну, собственно, на сайте так и написано "the new backwards-incompatible series of Python"..
А, фух, всё в порядке
'/' (используемое в "frac = a/b") в Python с версий 3.* означает деление с плавающей запятой, а '//' — целочисленное

Сам пользуюсь линейкой 2.6.*, поэтому сильно удивился

Здравствуйте, Буравчик, Вы писали:


Б>Математическое ожидание выигрыша при правильной игре = 0.7436972966269841

Я не могу понять как его посчитать правильно?

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

А>Не могу понять в какие неравенства. Может, хинт на тему как должно выглядеть строгое доказательство?

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


D>>А для вычисления fair price просто рекурсивную функцию написать.
D>>

>>>>> def foo(a, b, n):
>>> skipped
D>>

А>Почему ?

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

foo(a, b, n) возвращает матожидание выигрыша, если уже сделано b ходов, из них было a решек, и осталось еще n возможных ходов.
Если n == 0, то она просто возвращает a/b потому что выигрыш уже определен.
Если n > 0, то есть 2 опции -- прекратить игру (тогда мы получим a/b), либо продолжить (тогда матожидание выигрыша равно 0.5*foo(a+1, b+1, n-1) + 0.5*foo(a, b+1, n-1)).
Нужно сравнить эти 2 величины и выбрать ту опцию, которая дает более высокое матожидание. Потому что этот выбор во власти игрока.
Волшебным образом получится, что мы будем всегда выбирать "прекратить игру", если a/b > 0.5

>>> def foo(a, b, n):
...     if (n == 0):
...         return(a/b)
...     cont_opt = 0.5 * foo(a+1, b+1, n-1) + 0.5 * foo(a, b+1, n-1)
...     if (b == 0):
...         return(cont_opt)
...     stop_opt = a/b
...     return max(cont_opt, stop_opt)
... 
>>> print(foo(0., 0., 10))
0.743697296627

Здравствуйте, hexamino, Вы писали:

H>Здравствуйте, SEH, Вы писали:

H>Маленькая поправка: heads — это орлы, а решки — это tails.
H>fair price — это не выигрышная стратегия, а справедливая цена (за участие в игре).

Маленькая поправка. Heads -- это не орел... и не решка. Происхождение этих названий настолько разное, что однозначного перевода просто нет.

У всех монет есть лицевая сторона и обратная (вне зависимости от страны и времени выпуска). Со времен Петра в России было принято на одной стороне рисовать двуглавого орла, а с другой -- либо чье-то лицо (ряха), либо всякие данные о том, кто, когда и зачем эту деньгу напечатал (решетка). Отсюда и пошло "орел" и "решка". Причем, орлом могла быть как лицевая (главная) сторона монеты, если на обратной были данные, так и обратная сторона монеты, если на другой было лицо.

На Западе со средних веков (и, может, даже раньше) было принято рисовать голову правящего монарха, а на обратной -- все, что угодно. Поэтому лицевая сторона монеты тождественно называлась Head(s) (голова), а обратная Tail(s) (хвост).

Если монету с императором на одной стороне и орлом на другой показать кому-то на Западе, то орла они обзовут Tails, т.к. с другой стороны лицо (Heads). Если же монете будет Орел и черти-чего с другой стороны, то Орла обзовут Heads, а всякую статистику с обратной стороны -- Tails.

Здравствуйте, SEH, Вы писали:

SEH>

Consider a game where you can toss a fair coin up to 10 times. The payoff you get is the number of heads obtained divided by the number of tosses you've taken. After any toss you've got the choice of stopping there and then, taking your payoff, or to continue going. For example, If you've tossed the coin 5 times of which 3 were heads, if you decided to stop the game there and then you'd received 3/5 = $0.60 ... or you could keep going and hope for a higher value.
SEH>What is the fair price of this game?

SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

Пусть мы сделали k ходов и сейчас выпало m решек. Рассмотрим любой вариант, который может выпасть в будущем за s ходов. Пусть это РООРР... Ему соответствует другой вариант ОРРОО..., в результате которого выпадет столько решек, сколько орлов при первом варианте. Значит, если один добавит x решек, то другой -- s-x решек. В первом случае будем иметь m+x решек, во втором -- m+s-x решек. Вероятности обоих вариантов одинаковые. В среднем оба варианта дадут m+s/2 решек. Т.е. продолжать имеет смысл, если (m+s/2)/(k+s)>m/k или m/k<1/2. Заметим, что эта граница НЕ зависит от s, т.е. при m/k>=1/2 если мы продолжим, то при любом числе ходов после этого мы в среднем получим меньше, т.е. любая стратегия после этого в среднем даст меньше.

Сколько в среднем получится выиграть? Очень интересный вопрос! Рассмотрим первый ход. Если решка -- берем $1, если орел -- кидаем дальше. Каждой решке припишем +1, а орлу -- -1. Нам надо набрать максимум за 9 ходов в сумме +1. Тогда мы выиграем ровно $0.5. В каком случае это не получится? Для этого нужно, чтобы за 9 ходов сумма полученных +1 и -1 всегда была неположительной. Сколько таких вариантов? Будем считать по количеству плюсиков (решек, выпавших за последующие 9 бросков):
0: все минусы, порядок, очевидно, не важен, 1 вариант, выигрыш 0.
1: один плюсик, должен быть не первым (иначе, при втором решка и получаем 1 решку за два броска), т.е. 8 вариантов, выигрыш 0.1.
2: два плюсика, первый должен быть не первым, если он второй, то второй должен быть не третьим, ну а если первый не первый и не второй, то они где угодно (надеюсь, понятно, что сказал). Варианты: -+-* --*, итого 6 + C(7,2) = 27, получит 0.2.
3: три плюсика, варианты: ---* --+-* --++-* -+--* -+-+-*, итого C(6,3)+C(5,2)+4+C(5,2)+4=48, получит 0.3.
4: четыре плюсика, варианты: если срели первых 5 нет плюсов, то дальше все минусы, годится (1), если среди первых 5 один плюс, то он должен быть не первый, а дальше еще три плюса как угодно (4*4=16), если среди первых 5 два плюса, то для них 5 вариантов, а далее среди 4 оставшихся еще два плюса как угодно, но только не два сразу, т.е. (5*5=25), итого 42, получит 0.4.

В среднем получается: (0.0 * 1 + 0.1 * 8 + 0.2 * 27 + 0.3 * 48 + 0.4 * 42) / 512 + 1 * 1 / 2 + 0.5 * (1 — 1/2 — 126/512) = (37.4 + 256 + 65) / 512 = 358.4 / 512, т.е. средний выигрыш при такой стратегии равен 1792 / 2560 = 7 / 10 = 0.7.

Т.е. при такой стратегии ровно 0.7, если нигде не ошибся в расчетах.

V>Здравствуйте, vadimcher, Вы писали:
V>если (m+s/2)/(k+s)>m/k или m/k<1/2

Не получается так... Или я где-то ошибаюсь?

Здравствуйте, SEH, Вы писали:

V>>Здравствуйте, vadimcher, Вы писали:
V>>если (m+s/2)/(k+s)>m/k или m/k<1/2

SEH>Не получается так... Или я где-то ошибаюсь?

Эти два выражения вроде бы эквивалентны. Другое дело, что я там где-то в вычислениях дальше наплел, т.к. ответ вроде должен быть больше, чем 0.7. Да и на счет стратегии надо бы еще разок подумать...

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, SEH, Вы писали:
[]
SEH>>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>>Какова наиболее выигрышная стратегия?
[]
V>Сколько в среднем получится выиграть? Очень интересный вопрос! Рассмотрим первый ход. Если решка -- берем $1, если орел -- кидаем дальше. Каждой решке припишем +1, а орлу -- -1. Нам надо набрать максимум за 9 ходов в сумме +1. Тогда мы выиграем ровно $0.5. В каком случае это не получится? Для этого нужно, чтобы за 9 ходов сумма полученных +1 и -1 всегда была неположительной. Сколько таких вариантов? Будем считать по количеству плюсиков (решек, выпавших за последующие 9 бросков):
[]
V>В среднем получается: (0.0 * 1 + 0.1 * 8 + 0.2 * 27 + 0.3 * 48 + 0.4 * 42) / 512 + 1 * 1 / 2 + 0.5 * (1 — 1/2 — 126/512) = (37.4 + 256 + 65) / 512 = 358.4 / 512, т.е. средний выигрыш при такой стратегии равен 1792 / 2560 = 7 / 10 = 0.7.

V>Т.е. при такой стратегии ровно 0.7, если нигде не ошибся в расчетах.

Разумеется, ошибся. Вероятность каждой рассмотренной траектории в случае, когда первый орел, 1/1024, а не 1/512. И выигрыш будет больше, чем 0.7, около 0.725. Впрочем, это не самая грустная новость. Мое доказательство того, что это оптимальная стратегия ложное. Все, ушел в себя...

Здравствуйте, SEH, Вы писали:

SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

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

Я там где-то доказал, что как только получили хотя бы 0.5, надо брать... Это неверно. Простая иллюстрация, которая прояснит немного суть происходящего. Допустим, что у нас 4 решки при 8 бросках. Это верно, что если бросать еще один раз, то ожидание будет все равно $0.5, или даже если бросать 2 раза. Это даже, как бы, очевидно... Весь фокус в том, что стратегия может при это давать положительную отдачу за счет того, что можно остановиться, если все хорошо, а если плохо, то играть до конца. Действительно, всего четыре возможных продолжения.
РР: 5 из 9, 6 из 10.
РО: 5 из 9, 5 из 10.
ОР: 4 из 9, 5 из 10.
ОО: 4 из 9, 4 из 10.
Мы можем, если все хорошо, т.е. сначала выпала решка, и стало 5 из 9, остановиться. Если выпала сразу решка, то отношение решек к числу бросков подскочило, чтобы потом упасть (в среднем, если бросать дальше). Т.е. если мы не остановимся, то ожидание после этого будет меньше. Если же выпал орел, то мы продолжаем, т.е. в этой подветке при таком развитии событий мат.ожидание не меняется. Таким образом наша остановка в хорошем случае (первая решка) увеличивает мат.ожидание в той подветке, а тот факт, что мы продолжаем в случае первого орла -- его в этой подветке не изменяет. В целом это приводит к тому, что изначальное мат.ожидание увеличивается, т.е. становится больше 0.5. А значит, в случае 4 решек при 8 бросках нам останавливаться не надо. Это очень похоже на опционы. Если все хорошо, мы его реализуем, получаем прибыль. Если плохо, то не реализуем, а живем как есть. Такая своеобразная страховка дает положительное ожидание прибыли, а потому опционы обычно не бесплатные.

Стратегия остановки при хорошем развитии событий дает положительное мат.ожидание результата в случае, когда решек ровно половина. Т.е. в этом случае, очевидно, надо продолжать. В случае, если решек сейчас меньше половины, то, тем более, так как даже если сразу сказать, что бросаем до конца, мат. ожидание результата будет положительным, а уж со стратегией "стоп, если все ОК" тем более. Остается неясность, как быть со случаем, когда сейчас решек больше половины. С одной стороны, если продолжить, то мат.ожидание само по себе падает. С другой стороны, стратегия остановки в благоприятных случаях увеличивает его. Может так оказаться (при большем, чем 10 бросках), что для некоторых текущих значений выигрыша, которые на чуть-чуть больше 1/2, например, 11/20, окажется, что надо продолжать играть, так как положительный результат от стратегии будет больше отрицательного от изменения мат.ожидания выигрыша. Как показать, что это не так, я не знаю. Т.е. доказательства оптимальности нет.

Хорошая новость. Брут-форс подтвердил, что алгоритм "стоп, если БОЛЬШЕ, чем $0.5" (предложенный ранее) является единственным оптимальным. Стоимость: $0.743697. Я написал еще генетический алгоритм, который тоже находит эту стратегию. Генетический код игрока -- его стратегия, которая генерится для новых случайным образом. При скрещивании игрок, который играет лучше, имеет преимущество. Алгоритм можно будет попробовать на большем числе бросков, когда брут-форс загнется, на предмет, может ли быть что-то лучше стратегии "бери, если больше 0.5" при другом числе бросков.