in mathematics 1,481 Words

Dice Problem, Part 1

I came across an interesting question on the “/r/learnmath” subreddit.  The poster describes two players, A and B, playing a game of dice. Each one has a die that has a specific side weighted. Each player rolls his die. If it lands on the weighted side, he gets the value of the side added to his score and rolls again. If it lands on any of the nonweighted sides, his turn is over. Whoever has the highest score wins. I found this question intriguing, and thought it would be a good opportunity for me to work on understanding infinite series, a weak area for me. Note that the original question states that if the first roll is a nonweighted side, the player gets that many points (instead of zero like on subsequent rolls). I’m going to ignore that rule and focus on the general pattern.

Problem: Each player has a die that is weighted on one side. He gets that many points and gets to roll again if it lands on the weighted side; if it lands on the unweighted side, his turn is over. More specifically, A’s weighted side is 3 and he has a 20% chance of rolling it; B’s weighted side is 2 and she has a 30% chance of rolling it. What is the chance that A will win (not tie)?

Let’s define some variables to make the solution as general as possible: a = 3 (A’s weighted side), b = 2 (B’s weighted side), p = 0.2 (A’s weighted probability), and q = 0.3 (B’s weighted probability). And let’s say P(A=x) is the probability that A has x successful rolls.

I’m hoping this can be solved with infinite series, but I’m not sure how it will handle the infinite number of cases within each sum.

The probability that A has 0 successful rolls, P(A=0), is simply 1 – p (an unsuccessful roll). The score would be 0×3=0 of course. P(A=1), with a score of 1×3 requires the first roll to be successful (p), and the next roll to be unsuccessful (1–p). The general pattern will be for having n successful rolls is P(A=n) = pn(1–p), with a score of na.

So we can sum for all values of n to get the probability A will win, by multiplying for each n the probability of A getting n rolls by the probability of B getting fewer than k rolls (where k is the yet-to-be-determined number that B needs to tie or beat A).

\displaystyle W = \sum_{n=0}^{\infty} [p^n(1-p)\cdot P(\textrm{A beats B})]

The probability that A beats B will be the sum of all cases where B didn’t get a high enough score to tie or beat A.

\displaystyle W = \sum_{n=0}^{\infty} \left[p^n(1-p)\cdot \sum_{m=0}^{k-1} q^m(1-q)\right]

I have no idea how to evaluate that second (finite) series. It occurs to me that it might be easier to consider the complementary case, where B wins or ties (that is, A does not win). That will switch the series to the remainder infinite series, which maybe will be easier to solve. We will have to remember that we are now solving for A losing or tying, not A winning.

\displaystyle 1 - W = \sum_{n=0}^{\infty} \left[p^n(1-p)\cdot \sum_{m=k}^{\infty} q^m(1-q)\right]

This is an infinite sum, where each term in the sum itself contains an infinite series. I will have to evaluate that series if I am to have any hope of evaluating the primary series. I don’t know how to evaluate that.

But, as I think about it, there’s another way. The chance that B gets at least k rolls will be qk (times 1, rather than times 1–q, since it doesn’t matter what the rest of the rolls are.

\displaystyle 1 - W = \sum_{n=0}^{\infty} p^n(1-p)q^k

Now we’re getting somewhere! I almost feel like I could tackle this series, except for the tiny problem that I have no idea what k is, or how it depends on n. Well, I take that back. I can describe it, but the problem is that this isn’t a smooth, continuous relationship. If A gets 0 successful rolls, he has a score of 0×3 = 0, and so B needs at least 0/2 = 0 rolls. If A gets 1 successful roll, he has a score of 1×3 = 3, and so B needs at least 3/2 = 1.5 → 2 successful rolls. This rounding is where the problem is. I could write this as

\displaystyle k = \left \lceil{\frac{3n}{2}}\right \rceil ,

where those partial brackets represent the ceiling function, rounding the value up to the nearest integer. I can substitute this in, but I won’t be able to further simplify it.

\displaystyle 1 - W = \sum_{n=0}^{\infty} p^n(1-p)q^{\left \lceil{\frac{3n}{2}}\right \rceil}

I’m almost stuck. This is the part I was afraid of when first tackling this problem.

However, a and b are such small numbers, that we might be able to just delineate the specific cases (and unfortunately, lose part of the generality of our solution).

Let’s look for a pattern. For n = 0, k = 0. For n = 1, k = 2. (These are the cases I went through above. For n = 2, k = 3 (2×3 = 6; 3×2 = 6). For n = 3, k = 5 (3×3 = 9; 5×2 = 10). For n = 4, k = 6 (4×3 = 12; 6×2 = 12). For n = 5, k = 8 (5×3 = 15; 8×2 = 16).

There’s an alternating pattern here. We have (0, 0), (2, 3), (4, 6), and so on, where 3n is even, yielding an integer when divided by 2. Then we have (1, 2), (3, 5), (5, 8), and so on (the “half” cases, where 3n is odd and we have to round). In each group, every time n goes up by 2, k goes up by 3, which is just what we’d expect from the values of a = 3 and b = 2.

Let’s split our series into the sum of these two component series. I’m going to use a new index, i, for the summation. For the first sum, for A, we have 0, 2, 4, … which we can represent as 2i. For B, we have 0, 3, 6, … which we can represent as 3i. For the second sum, for A, we have 1, 3, 5, … which we can represent as 2i + 1. And for B, we have 2, 5, 8, … which we can represent as 3i + 2. Putting this all together yields:

\displaystyle 1 - W = \sum_{i=0}^{\infty} p^{2i}(1-p)q^{3i} + \sum_{i=0}^{\infty} p^{2i + 1}(1-p)q^{3i + 2}

I don’t know how to evaluate this. However, I do know the formula for the infinite geometric series:

\displaystyle \sum_{i=0}^{\infty} r^i = \frac{1}{1-r}

So I’m going to try to reformulate my series into that form. Let’s work on one series at a time. First, I’ll factor out the constant (1 – p):

\displaystyle 1 - W = (1-p)\sum_{i=0}^{\infty} p^{2i}q^{3i} + \sum_{i=0}^{\infty} p^{2i + 1}(1-p)q^{3i + 2}

\displaystyle 1 - W = (1-p)\sum_{i=0}^{\infty} \left(p^2\right)^i \left(q^3\right)^i + \sum_{i=0}^{\infty} p^{2i + 1}(1-p)q^{3i + 2}

\displaystyle 1 - W = (1-p)\sum_{i=0}^{\infty} \left(p^2q^3\right)^i + \sum_{i=0}^{\infty} p^{2i + 1}(1-p)q^{3i + 2}

This is now in the proper form for the geometric series, where r = p2q3 .

\displaystyle 1 - W = (1-p)\cdot\frac{1}{1-p^2q^3} + \sum_{i=0}^{\infty} p^{2i + 1}(1-p)q^{3i + 2}

\displaystyle 1 - W = \frac{1-p}{1-p^2q^3} + \sum_{i=0}^{\infty} p^{2i + 1}(1-p)q^{3i + 2}

It worked! Now let’s tackle the second sum. We’ll factor out the “extra” p’s and q’s.

\displaystyle 1 - W = \frac{1-p}{1-p^2q^3} + \sum_{i=0}^{\infty} p^{2i}p^1(1-p)q^{3i }q^2

Next, we can factor out everything which does not depend on i:

\displaystyle 1 - W = \frac{1-p}{1-p^2q^3} + (1-p)pq^2\sum_{i=0}^{\infty} p^{2i}q^{3i }

This infinite series is exactly the same as the one I just simplified, so I’ll jump ahead.

\displaystyle 1 - W = \frac{1-p}{1-p^2q^3} + (1-p)pq^2\cdot\frac{1}{1-p^2q^3}

\displaystyle 1 - W = \frac{1-p}{1-p^2q^3} + \frac{(1-p)pq^2}{1-p^2q^3}

Factoring out the common terms yields

\displaystyle 1 - W = \frac{1-p}{1-p^2q^3}\cdot(1+pq^2)

\displaystyle 1 - W = \frac{(1-p)(1+pq^2)}{1-p^2q^3}

And solving for W, we get

\displaystyle W = 1 - \frac{(1-p)(1+pq^2)}{1-p^2q^3} \ \blacksquare

That should be the general formula (for the predefined values a=3 and b=2, but for any values of p and q). If we substitute in p=0.2 and q=0.3, we get

\displaystyle W = 1 - \frac{(1-0.2)(1+0.2\cdot 0.3^2)}{1-0.2^2 0.3^3} \approx 0.1847 \ \blacksquare

I believe this answer to be correct, but it is far lower than I had expected. I had actually expected it to be greater than 0.5, but I suppose there are many ties (especially 0 = 0 ties), and a tie means A didn’t win. I’d like to explore this more in a future post.