Вероятность выиграть поворотную игру с случайным элементом

Question

Я готовлюсь к программированию экзамен по теории вероятностей, и я наткнулся на вопрос, который я не могу решить.

Учитывая сумку, которая содержит некоторое количество белых камней $ W $ и некоторая данная сумма черных камней $ b $ , два игрока по очереди рисуют камни равномерно в случайных из сумки. После того, как каждый игрок повернул камень, выбранный равномерно со случайным образом, исчезает, и только тогда другой игрок забирает свою очередь. Если нарисован белый камень, игрок, который нарисовал его, мгновенно теряет и Игра заканчивается. Если сумка становится пустой, игрок, который играл вторым, побеждает.

Какова общая вероятность того, что игрок, который играл вторым, выигрывает?

Я предполагаю, что это вопрос динамического программирования, хотя я не могу понять формулу рекурсии. Любая помощь была бы очень ценится. :)

Пример ввода : $ W $ = 3, $ b $ = 4, то ответ в том, что я верю, 0,4, который я приехал после вычисления вручную все возможные пути для игры, поэтому не очень эффективно.

Answer 1

Давайте обозначаем через $ \ pr (w, b) $ Вероятность выигрыша P2 приведена его очередь, и есть $ w $ Белые камни и $ B $ Черные камни, оставшиеся и аналогичные, мы пишем $ \ overline \ PR (W, B) $ Для вероятности выигрыша P2 приведена его поворот P1.

Из правил игры мы получаем, что любой из следующих случаев может произойти в очереди P2 (предполагая, что осталось достаточно камней):

1. белый рисуется и p2 теряет. Это происходит с вероятностью $ w / (w + b) $ .
2. черная тянутся и белый камень исчезает. Вероятность этого является $ b / (w + b) \ cdot w / (w + b - 1) $ .
3. черная тянутся и черный камень исчезает. Мы находим вероятность того, что это будет $ B / (W + B) \ CDOT (B - 1) / (w + b - 1) $ .

   Если это поворот P1, чтобы играть, мы находим аналогичные случаи:

   1. белый рисун и выигрывает P2. Это происходит с вероятностью $ w / (w + b) $ .
   2. черная тянутся и белый камень исчезает. Вероятность этого является $ b / (w + b) \ cdot w / (w + b - 1) $ .
   3. черная тянутся и черный камень исчезает. Мы находим вероятность того, что это будет $ B / (W + B) \ CDOT (B - 1) / (w + b - 1) $ .

      Теперь мы можем фактически факторовать $ \ pr $ и $ \ overline \ pr $ Использование наших различий И какая-то простая теория вероятностей: $$ \ begin {align *} \ Pr (w, b) &=pr (\ text {case 1.2}) \ cdot \ uverline \ pr (w - 1, b - 1) + \ pr (\ text {case 1.3}) \ cdot \ uverline \ PR (W, B - 2), \\ \ uverline \ pr (w, b) &=pr (\ text {case 2.1}) + \ pr (\ text {case 2.2}) \ cdot \ pr (w - 1, b - 1) + \ pr (\ Текст {чехол 2.3}) \ cdot \ pr (w, b - 2) \ end {align *} $$ Обратите внимание, что мы можем объединить эти 2 уравнения, чтобы найти рекурсивную формулу для $ \ pr $ (который я не буду вводить здесь для краткости). Соединение их с начальными значениями $ \ Pr (w, b) $ где $ w + b \ leq 4 $ (который можно предварительно получать) даст нам алгоритмический способ найти желаемую вероятность.