Теория вероятностей против интуиции

2014-05-31 в 8:07, admin, рубрики: математика, теория вероятностей, метки: теория вероятностей

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

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

К этой задаче мы еще вернемся. И да, я знаю, что ответ на парадокс Монти-Холла — 66%.

Причиной написать эту статью стала интересная задача, с которой я столкнулся. Я люблю играть в Flappy Bird. И некоторые мои друзья любят играть в Flappy Bird. Иногда мы спорим, кто наберет больше очков. Проблема, однако, заключается в том, что результат в Flappy Bird очень не предсказуемый. Поэтому, чтобы немного это исправить, мы спорим на серии из пяти игр. Если в первой игре убиться об первое же дерево, есть еще четыре, чтобы исправить ситуацию.
И вот однажды, когда я играл третью игру из пяти, и уже набрал 25 очков, что по меркам моих способностей много, мне внезапно стало надо срочно отойти. «Окей,» — сказал я, — «я сейчас специально убьюсь, а потом начну третью игру с начала, а текущие очки мы все равно прибавим к результату. Это никак не повлияет на ожидаемое количество очков.» — сказал я. «Конечно повлияет,» — ответил друг, — «ты можешь потом начать третью игру с начала, но текущие очки мы не прибавим. Это, разумеется, повысило бы твое ожидаемое количество очков».

Разумеется, ни я ни мой друг никакой математики в уме не провернули, мы опираемся на наше представление о том, что является честным, и используем математический термин «ожидаемое количество» в интуитивно верном, но на самом деле ничем не подкрепленном смысле.
Почему вариант, который предлагает мой друг (не прибавить очки за текущую игру) интуитивно честный — понятно. Если их не прибавить, то я как будто эту игру и не играл. Я сыграю еще три, всего получится пять, и это честно.
Почему я считаю, что мой вариант честный? Ну потому что если я убился, а потом начал новую игру, то это, в принципе, тоже самое, что если бы я не убивался, а продолжил эту игру.
Но, конечно, в моем варианте я наберу ровно на 25 очков больше, чем в его. То есть один из них заведомо не честный. Кого-то из нас подводит интуиция.

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

Допустим, я не знаю теорию вероятностей, и хочу для себя понять ответ на какую-то задачу.
Один простой способ это сделать — это рассмотреть, что получится, если описанная в задаче ситуация происходит одновременно большом количестве (например, в трех миллионах) вселенных.
В задаче Монти-холла из трех миллионов вселенных где-то в одном миллионе вы сразу выберете машину, а в двух миллионах вы выберете козла. В первом миллионе вселенных ведущий откроет одну из двух оставшихся дверей, без разницы какую, за ними обеими козел. В других двух миллионах вселенных одна из дверей, за которой козел, уже выбрана вами, и ведущий выберет вторую. В итоге, в первом миллионе вселенных машина по прежнему за той дверью, которую выбрали вы, а в остальных двух миллионах — за той, которую вы не выбрали, а значит шанс получить машину, не меняя выбор — 33%, а меняя — 66%.
В чем разница в задаче в начале статьи? В том, что в ней за одной из дверей не козел, а овца.
Это сарказм, конечно. В том, что в задаче Монти-Холла ведущий намеренно выбирает дверь с козлом. В задаче в начале статьи он выбрал дверь случайно, и за ней по факту оказалась овца. Рассмотрим опять три миллиона вселенных. Разобьем их на шесть групп:
1. Я выбрал машину, ведущий выбрал овцу.
2. Я выбрал машину, ведущей выбрал козла.
3. Я выбрал козла, ведущий выбрал овцу.
4. Я выбрал козла, ведущей выбрал машину.
5. Я выбрал овцу, ведущий выбрал козла.
6. Я выбрал овцу, ведущей выбрал машину.
Все варианты равновероятны, а значит каждый произойдет примерно в 500000 вселенных. Однако, мы знаем, что в нашем сценарии ведущий открыл дверь, за которой прячется овца. Значит, по факту, мы либо в одной из вселенных из первой группы, либо в одной из вселенных из третьей группы. Во всех остальных вселенных мы видим, что ведущий либо открыл дверь с козлом, либо дверь с машиной. Получается, что из одного миллиона вселенных, в которых мы сейчас можем быть, примерно в половине машина за нашей дверью, а в другой половине за той, которую мы не выбрали, и ведущий не открыл, а значит не важно, менять выбор или не менять выбор.

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

Начем с симуляции монти-холла:

Скрытый текст

import random

x_iters = 1000000

good = 0
bad = 0
for i in range(x_iters):
    carIsBehind = random.randint(1,3)
    doorIChose = random.randint(1,3)
    doorsWithGoats = []
    for i in range(1,4):
        if i != carIsBehind and i != doorIChose:
            doorsWithGoats.append(i)
    doorHostChose = random.choice(doorsWithGoats)
    doorThatIsLeft = 1 + 2 + 3 - doorIChose - doorHostChose

    if carIsBehind == doorIChose:
        good += 1
    elif carIsBehind == doorThatIsLeft:
        bad += 1
    else:
        assert False, "%d %d %d" % (carIsBehind, doorIChose, doorThatIsLeft)

print good, bad

Ожидаемо, результат

333860 666140

Теперь, задачу с начала статьи (для простоты уберем овцу, и допустим, что там два козла):

Скрытый текст

import random

x_iters = 1000000

good = 0
bad = 0
for i in range(x_iters):
    carIsBehind = random.randint(1,3)
    doorIChose = random.randint(1,3)
    doorsHostCanChoose = []
    for i in range(1,4):
        if i != doorIChose:
            doorsHostCanChoose.append(i)
    doorHostChose = random.choice(doorsHostCanChoose)
    if doorHostChose == carIsBehind: # we know this did not happen
        continue

    doorThatIsLeft = 1 + 2 + 3 - doorIChose - doorHostChose

    if carIsBehind == doorIChose:
        good += 1
    elif carIsBehind == doorThatIsLeft:
        bad += 1
    else:
        assert False, "%d %d %d" % (carIsBehind, doorIChose, doorThatIsLeft)

print good, bad

Опять же, ожидаемо

333537 332792

Да, получается, что в задаче в начале статьи ответ действительно 50%.

Вернемся к задаче, с которой я столкнулся, играя в Flappy Bird. Для начала, ее нужно формализовать. Допустим, что одна игра в Flappy Bird — это последовательность попыток проскочить через дерево. Так же допустим, что шанс проскочить через любое дерево одинаковый, и составляет примерно 99/100. Игра заканчивается, когда в очередной раз проскочить через дерево не удалось. Формализовать наш спор немного сложнее. Попытаемся формализовать его так: пусть, если в третьей игре игрок набрал ровно 50 очков, то он принудительно убивается, и ему дается возможность сыграть дополнительную игру. Следует понять, нужно ли прибавить эти 50 очков к счету, чтобы ожидаемое количество очков, по сравнению со сценарием, когда игрок просто играет пять игр, не изменилось. При такой формализации парадокс, описанный в начале статьи, сохраняется:
1. Кажется, что если не засчитать 50 очков, то игрок просто сыграет пять игр. Ожидаемое количетсво очков не должно отличаться от того, какое было бы, если бы игрок просто играл пять игр.
2. Но с другой стороны, 50 ходов игрок по факту в соответствующей игре не умер, данную ему дополнительную игру можно рассматривать как продолжение той игры, в которой мы его принудительно убили. То есть, добавление 50 очков тоже не должно повлиять на результат.
Пытаться симулировать это в миллионе вселенных в уме немного сложно. Поэтому сразу перейдем к подходу номер два — просимулируем оба варианта на питоне. Очевидно, что если игрока принудительно не убивать, а просто дать ему сыграть пять игр, то он наберет примерно 500 очков, так что будем смотреть, насколько далеки полученные оценки от 500.

Начнем с моего варианта, пусть 50 очков прибавляются.

Скрытый текст

import random  
x_iters = 100000
ans = 0

def doGame(canKill):
    score = 0
    while True:
        if random.randint(0,99) == 0:
            break;
        elif score == 50 and canKill:
            return score, True
        else:
            score += 1
    return score, False

for i in range(x_iters):
    addt = 0
    res = 0
    for i in range(5): # i is game id
        score, killed = doGame(canKill = (i == 3))
        res += score
        if killed:
            score, killed = doGame(canKill = False)
            assert not killed
            res += score

    ans += res

print ans / x_iters

Запускаем, ждем немного, получаем ответ:
502

Ну окей, это достаточно близко. Тогда пусть они не прибавляются

Скрытый текст

import random  
x_iters = 100000
ans = 0

def doGame(canKill):
    score = 0
    while True:
        if random.randint(0,99) == 0:
            break;
        elif score == 50 and canKill:
            return score, True
        else:
            score += 1
    return score, False

for i in range(x_iters):
    addt = 0
    res = 0
    for i in range(5): # i is game id
        score, killed = doGame(canKill = (i == 3))
        if not killed:
            res += score
        else:
            score, killed = doGame(canKill = False)
            assert not killed
            res += score

    ans += res

print ans / x_iters

Ответ:
464

Похоже, что я оказался прав. Или нет?
Чтобы закрепить результат, давайте попробуем немного поменять код. Сейчас мы учитываем как те пятерки игр, где в третьей игре игрок был принудительно убит, так и те, где не был. Что, если в рассмотрении оставить только те пятерки, где он был принудительно убит?
Теперь, в случае прибавления 50 очков в третьей игре получается 550, а в случае не прибавления — 500. Теперь прав мой оппонент.
Разница между двумя подходами такая же, как и разница между задачей монти-холла и задачей из начала этого поста. Первый подход говорит
«Если в миллионе вселенных игроки убиваются на третьей игре, когда набирают в ней 50 очков, и тогда они играют третью игру заново, то они в среднем набирают ровно 500 очков, если им эти 50 очков засчитать, и меньше 500, если не засчитать».
А второй подход говорит:
«Если в миллионе вселенных игроки убиваются на третьей игре, когда набирают в ней 50 очков, и тогда они играют третью игру заново, то среди тех вселенных, где они были принудительно убиты, они в среднем набирают больше 500 очков, если им эти 50 очков засчитать, и ровно 500, если не засчитать».
Так как наш спор изначально не был формализован, то и правы в какой-то мере мы оба. В итоге я предложил: «ну тогда давай так, мы не прибавляем текущий счет к общему, но я буду начинать третью игру заново до тех пор, пока не наберу в ней хотя бы 25 очков», и друг ответил: «да, так будет честно». Все счастливы.

А в заключение предлагаю еще одну очень старую задачу.
Положим что вероятность того что Клавдия Ивановна на самом деле зашила бриллианты в стул не сто процентов, а 90 (ну всяко бывает, может на старости лет придумала). Правы ли были Киса и Ося что с каждым вскрытым стулом «Шансы все увеличиваются» и какова была вероятность того что в последнем (еще не вскрытом) стуле есть приз?

Правильный ответ — не тот, который самый популярный в голосовании.

Автор: SkidanovAlex

Источник