Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

решение задачи про вероятности

Решение задачи про Алису и Боба, которая была тут позавчера; дальше спойлеры.

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

В первом варианте задачи Алиса и Боб бросают каждый свою независимую монету; нам сказано, что в итоге игры оба разорились. Как это смоделировать математически? Давайте обозначим последовательности исходов Алисы и Боба с помощью цепочек букв О(рел) и Р(ешка). Конкретная игра задается парой цепочек: например "ОРРО|РРРР" означает, что Алиса выбрасывала О,Р,Р,О, а Боб Р,Р,Р,Р. Игра после этого еще не закончилась (только 4 броска прошло), но мы можем сказать, какова вероятность того, что дела шли именно так: всего есть 8 бросков, из них 6 решек и два орла, значит, это 0.51^6*0.49^2 - 0.51 это вероятность орла, а 0.49 решки.

Нам нужно оценить что-то (вероятность того, что Алиса разорилась первой) в предположении, что оба разорились в итоге. Это значит, что мы можем рассматривать только такие записи исходов, которые заканчиваются разорением обоих. Для наглядности предположим, что исходный капитал $2, а не $100; тогда "ОРРР|ОО" это пример такой записи. Напомню, что Боб теряет $1 на орле, а Алиса тереяет $1 на решке, так что в этой игре Боб разорился за два шага, а Алиса за четыре. Конечно, записи могут быть намного намного длиннее, оба игрока могут набирать много денег, но в конце концов спускаться к разорению. У каждой такой возможной записи есть своя вероятность. Например, у "ОРРР|OO" это 0.51^3*0.49^3 - три орла, три решки. Теперь представим себе, что мы сложили все вероятности таких "разорительных" записей, в которых Алиса разоряется первой, и сравнили с суммой вероятностей всех "разорительных" записей, в которых Боб разоряется первым (строго говоря, это бесконечные суммы, потому что запись может быть сколь угодно длинной - но чем длиннее, тем меньше ее вероятность, и суммы сходятся - если вам непонятно это замечание, можете игнорировать его). Тот, у кого сумма вероятностей больше, тот с большей вероятностью разорится первым.

Теперь заметим следующее. Раз Алиса в конце своей записи разорилась, она спустилась от $100 к $0, так что в ее части записи решек на 100 больше, чем орлов; у Боба наоборот орлов на 100 больше, чем решек. Всего вместе у Алисы и Боба в каждой "разорительной" игре одинаковое количество решек и орлов, так что вероятность каждой "разорительной" игры равна какому-то 0.51^k*0.49^k. Теперь покажем, что любой "разорительной" игре можно сопоставить симметричную "разорительную" игру: а именно, поменять местами исходы Алисы и Боба и сами исходы поменять на противоположные. Например, "ОРРР|ОО" превращается таким образом в "РР|РООО": вместо того, чтобы Боб выкидивал дважды орла, Алиса выкидывает дважды решку, и вместо ОРРР Алисы есть РООО Боба. Легко видеть, что такая симметричная игра тоже разорительная, она симметричным образом приводит обоих игроков к $0, только Алиса движется про траектории Боба в изначальной игре и наоборот. Более того, число орлов и решек не меняется, хотя каждый орел превращается в решку и наоборот, потому что их число было равным в исходной "разорительной" игре, а следовательно вероятность остается такой же: 0.51^k*0.49^k. Но если в исходной игре первым разорялся Боб, то в симметричной - Алиса, и наоборот.

Мы придумали способ сопоставить каждой разорительной игре, где первым разоряется Боб, симметричную, где первой разоряется Алиса, и наоборот, и у симметричных игр одинаковые вероятности, значит и суммы по "Боб первый" и "Алиса первая" одинаковые, и ответ теперь очевиден: Алиса и Боб с одинаковой вероятностью разоряются первыми (эта вероятность меньше 50%, т.к. есть еще случаи, когда они разоряются одновременно).

===============================

В бонус-задаче у нас есть только одна монета, и до разорения первого игрока они оба действуют по ее исходам, а затем продолжает один. Теперь у нас есть только одна цепочка, в которой можно отметить место разорения первого игрока, например "РР-РООООО" с начальным капиталом $2: после первых двух решек разоряется Алиса, у Боба в этот момент $4, и после РООООО он тоже разоряется. Но на этот раз общий баланс О и Р в записи игры не будет одинаковым. Если Алиса разоряется первой, то к моменту ее разорения Р на 100 больше, чем О; после этого Бобу надо с $200 спуститься к 0, и это требует перекоса в 200 орлов; всего перекос в 100 решек вначале и 200 орлов впоследствии дает общий перекос в 100 орлов (в примере "РР-РООООО" с начальным капиталом $2 это перекос в 2 орла). Вероятность равна 0.49^k*0.51^(k+100) для какого-то k. Если же заменить всех орлов на решки и наоборот, мы получим симметричную разорительную игру, где Боб теперь разоряется первым, и в ней наоборот на 100 решек больше, и ее вероятность 0.49^(k+100)*0.51^k. Отношение этих двух вероятностей равно (0.49/0.51)^100 (примерно 1/50, т.е. 2%) и не зависит от k или того, как выглядит конкретная разорительная игра. Значит, после суммирования по всем разорительным играм Боба-первого и Алисы-первой это отношение сохраняется, и у Алисы намного намного больше шансов разориться первой, чем у Боба: примерно в 50 раз больше.
Tags: задачка, математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 76 comments