0
$\begingroup$

Suppose me and an opponent are racing to 100 points. We take turns rolling some die and adding the roll to our score. If the die is fair (and we randomly determine who goes first) it's clear this game is completely 50/50.

However, I'm interested in calculating the probability when the die isn't fair or when we each have different score targets.

For example, suppose we're playing with a fair 6-sided die but I only have to reach 90 points to win while my opponent must reach 100. Alternatively, suppose we're both racing to 100 but I have a 7-sided die and my opponent only has a 6-sided die.

While I'm able to determine these probabilities with great precision using Monte Carlo simulations I'm unsure how to derive these figures mathematically.

It seems promising to calculate the "average number of rolls required" for both players and compare these. Clearly, the player with the lower of these two values will be the favorite, however, I need some help in calculating the actual probability itself.

$\endgroup$
6
  • $\begingroup$ $\texttt{"While I'm able to determine these probabilities with great precision}$ $\texttt{using Monte Carlo simulations"}$ What were your results? $\endgroup$ Jul 12, 2018 at 16:21
  • $\begingroup$ There's not a nice closed form for these two problems. You can either estimate the probabilities by approximating the relevant probability distributions by Gaussians, or (since you know how to do Monte Carlo simulations, this might be the option for you) you can use dynamic programming, which involves generalizing the problem (e.g. $p(m,n)$ is the probability of the first player winning when the first player needs $m$ and the second player needs $n$) and recursively reducing bigger cases to smaller cases, caching the results for efficiency. $\endgroup$
    – joriki
    Jul 12, 2018 at 16:25
  • $\begingroup$ I have tried a similar problem once. Comparing averages is a logical idea but due to some level of dependence this doesn't work formally. I would recommend setting up the whole thing from scratch, i.e., determine the probability of winning for all scores from low (0) to high (100) by using Markov chain methods. Although I am not sure whether this would work. So, yeah that's almost exactly joriki's comment. $\endgroup$ Jul 12, 2018 at 16:26
  • $\begingroup$ Why do you holding back information? This is a forum where the "give and take" principle is crucial. $\endgroup$ Jul 12, 2018 at 16:41
  • $\begingroup$ @StanTendijck Yes, Markov chains should work, but you have to realize its an absorbing Markov chain $\endgroup$
    – saulspatz
    Jul 12, 2018 at 17:00

2 Answers 2

2
$\begingroup$

Expanding on joriki's answer.

Let $\alpha=(\alpha_{ij})$ be the matrix whose $(i, j)$-th entry is the probability that the first player rolls $i > 0$ and the second player rolls $j > 0$.

Let $p(m, n)$ be the probability that the first player wins given that they are the first to roll, need $m$ more points and that the second player needs $n$ more points. Then, $$ p(m,n)=\begin{cases} 1 & \text{if }m\leq0\\ 0 & \text{elseif }n\leq0\\ \sum_{i,j}\alpha_{ij}p(m-i,n-j) & \text{else}. \end{cases} $$

Since you stipulate that the order of the players need not be predetermined, we can generalize as follows: if the first player is the first (resp. second) to roll with probability $q$ (resp. $1-q$), then the probability that the first player wins is $$ p(m,n;\alpha)q+(1-p(n,m;\alpha^\intercal))(1-q) $$ where the notation $p(\cdot ; \alpha^\intercal)$ is used to mean that the transpose of $\alpha$ should be used in the computations. Of course, if both players are playing with the same die, then $\alpha = \alpha^\intercal$.

Here's some Python code to perform the above computation:

import numpy as np

class pp:
    def __init__(self, alpha):
        # Cache results (a.k.a. memoization)
        self._p = {}

        # alpha[i][j] = Prob(P1 rolls (i+1) and P2 rolls (j+1))
        self._alpha = alpha

    def __call__(self, m, n):
        # Base cases
        if m <= 0: return 1
        if n <= 0: return 0

        # Caching
        if (m, n) in self._p: return self._p[(m, n)]

        # Compute
        tmp = 0.
        for (i, j), alpha_ij in np.ndenumerate(alpha):
            tmp += alpha_ij * self.__call__(m - (i+1), n - (j+1))
        self._p[(m, n)] = tmp
        return tmp

if __name__ == '__main__':
    # Compute example by OP in which each player rolls a 6-sided dice
    # Trivially, the answer should be 0.5
    alpha = np.ones((6, 6)) / 36.
    q = .5
    m = 36
    n = 36
    p = pp(alpha)
    res = q * p(m, n) + (1. - q) * (1. - p(n, m))
    print(res)
$\endgroup$
0
$\begingroup$

The number of outcomes to consider for this actual question is huge so I thought I'd take a simpler example to analyze and see how it works.

Edit 2: My original example still wasn't simple enough and required too much counting due to its complexity. Some of the counts are really tricky as is the consideration of conditional probability. Now I understand more about the recommendation for a simulation solution. However, I've redone it with the simpler example again.

We have a four sided die and it's the first to reach $4$ for player A or $5$ for their opponent player B.

To reach a sum of $4$ can be from $1$ to $4$ tosses for A

And to reach $5$ takes from $2$ to $5$ tosses for B

The probability of A winning if they go first is:

$P(A\text{win|A first}) = \frac{1}{4} + \frac{3}{4}\cdot \frac{3}{4} + \frac{3}{4}\cdot \frac{1}{4}\cdot \frac{11}{12}\cdot \frac{3}{8} + \frac{3}{4}\cdot \frac{1}{4}\cdot \frac{1}{12}\cdot \frac{1}{1}\cdot \frac{3}{8}\cdot \frac{1}{6}$ $$P(A\text{win |A first}) = .8779$$

The explanation of the series of terms is, term one is the probability of winning on the first roll and getting a $4$. Term two is the probability of not getting a $4$ on the first roll times the probability of getting a winning roll on the second roll. Term three is the probability of not winning on the first and second roll times the probability of a winning roll on the third roll times the probability of player B not winning on their second roll. Term four is the probability of not getting a winning roll on the first three rolls times the probability of a winning roll on the fourth roll times the probability of player B not winning on their second and third roll.

The probability of A winning if B goes first is:

$P(A\text{win|B first}) = \frac{1}{4}+\frac{3}{4}\cdot \frac{3}{4}\cdot \frac{3}{8} + \frac{3}{4}\cdot \frac{1}{4}\cdot \frac{11}{12}\cdot \frac{3}{8}\cdot \frac{1}{6}+\frac{3}{4}\cdot \frac{1}{4}\cdot \frac{1}{12}\cdot \frac{1}{1}\cdot \frac{3}{8}\cdot \frac{1}{6}\cdot \frac{1}{16}$ $$P(A\text{win|B first}) = .4717$$

enter image description here

$\endgroup$
10
  • $\begingroup$ I've got P(Awin|Afirst) = 0.8569 and P(Awin|Bfirst) = 0.4040 over 10 million trials each. $\endgroup$
    – Abovestand
    Jul 15, 2018 at 4:12
  • $\begingroup$ The P(Awin|Afirst) answer is close to mine. The P(Awin|Bfirst} $\endgroup$
    – Phil H
    Jul 15, 2018 at 5:49
  • $\begingroup$ The P(Awin|Bfirst) answer doesn't look feasible to me. Even if B goes first they are always lagging behind A in the number of tosses to reach 10 compared to A's 8 and so should be less likely than A to win. What do you think? $\endgroup$
    – Phil H
    Jul 15, 2018 at 5:59
  • $\begingroup$ @Abovestand I can see a fundamental error I made, I'll redo it and edit it later today. $\endgroup$
    – Phil H
    Jul 15, 2018 at 13:02
  • $\begingroup$ @Abovestand I redid my answer with a simpler example. $\endgroup$
    – Phil H
    Jul 15, 2018 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.