3
$\begingroup$

I posted this on puzzling stack exchange three months ago and it was immediately closed as off-topic, for being a "fairly straightforward probability calculation".

I have the solution to the problem, which I do not give here in case you might want to solve it yourself. My two questions for this forum are: 1) is this indeed an interesting problem to solve and not "fairly straightforward", and 2) how can I prove that the answer for the probability of N laps converges over time (i.e. as N increases)? (This second part I have been unable to solve.)

=== Here is the original post: ===

I created this dice and paper game for my kids years ago, and at the same time gave myself an interesting puzzle.

This game is a horse race between two horses: Slowpoke and Doubles.

With a sheet of lined writing paper, draw vertical lines to make six columns down the paper. The first five columns belong to Slowpoke, and the sixth column belongs to Doubles.

Each row across the paper represents one lap around a racetrack. Before the race starts, decide on the number of laps that will be run. You can then have fun predicting which horse will win the race.

To begin the race, roll a pair of dice. If you roll a double -- (1,1), (2,2), (3,3), (4,4), (5,5), or (6,6) -- then draw an X in Doubles' column in the first lap. Doubles has just completed the first lap!

If you roll anything other than doubles, then draw an X in Slowpoke's first column in the first lap. Slowpoke has made it one fifth of the way around the track.

Keep rolling the dice. Each time a doubles comes up, Doubles completes another lap.

Each time anything else comes up, Slowpoke advances across the current lap, left to write. Draw an X in the next free column. It will take five non-doubles rolls for Slowpoke to complete the lap.

In this way, roll after roll, one or the other horse advances with another X, until finally, one of the two horses completes their last lap and wins!

My puzzle for you is:

Is one of the two horses favored to win the race?

If so, what is the probability that a given horse wins a race of N laps?

Enjoy!

=== UPDATE:

@user2661923 I found solving the probability for Doubles is easier than for Slowpoke. It follows a simple pattern. (I'm using spoiler blocks in case others find it interesting to solve on their own.)

For one lap:

$$ \frac {6^4 + (6^3\cdot 5) + (6^2\cdot 5^2) + (6\cdot 5^3) + 5^4} {6^5} $$

For two laps:

$$ \frac {6^9 + (6^8\cdot 5) + (6^7\cdot 5^2) + (6^6\cdot 5^3) + (6^5\cdot 5^4) + (6^4\cdot 5^5) + (6^3\cdot 5^6) + (6^2\cdot 5^7) + (6\cdot 5^8) + 5^9} {6^{11}} $$

For n laps:

$$ \sum_{k=0}^{5n - 1} \frac{5^k\cdot 6^{(5n - 1) - k}} {6^{6n - 1}} $$

Which simplifies to:

$$ \sum_{k=0}^{5n - 1} \frac{5^k} {6^{k + n}} $$

This last equation I would like to prove continually approaches, but never reaches, 1/2.

$\endgroup$
8
  • $\begingroup$ If the query is a puzzle that you already know the answer to, the issue of whether it is appropriate for mathSE is equivalent to the issue of whether math professionals will (in general) be interested in the math behind the solution. As a rule of thumb, since the query does not represent a problem that you are trying to solve for yourself, you might want to run the problem by a math professor first, to see what the professor thinks, before posting it on mathSE. $\endgroup$ Commented Mar 8, 2021 at 4:25
  • $\begingroup$ The query does represent a problem that I am trying to solve for myself. I do not know how to show that the answer converges, as the number of laps increases, as asked above. $\endgroup$
    – Jim Flood
    Commented Mar 8, 2021 at 5:23
  • $\begingroup$ I did run this past a math professor. Years ago, I was on an airplane flight, seated by chance next to a university math professor, and I showed him the problem. He found it interesting, and could not give me an answer on the flight. That was before I solved it. I did not have the opportunity to ask him about whether or not the solution converges. $\endgroup$
    – Jim Flood
    Commented Mar 8, 2021 at 5:26
  • $\begingroup$ +1 to the query, which (embarrassingly enough) I can only partially solve. $\endgroup$ Commented Mar 8, 2021 at 6:44
  • $\begingroup$ Very interesting approach taken in the enhancements made to your query. My inclination to examine the situation from Slowpoke's perspective was merely based on the idea that for any given value of $n$, there would be fewer terms to deal with. For example, with $n=1$, my approach involves 1 term, while your approach involves 5 terms. However in terms of resolving the issue that Double's chances are steadily decreasing towards (1/2), your approach may turn out to be the better approach. In any event, I am (still) out of my depth, and simply lack the knowledge needed to attack the problem $\endgroup$ Commented Mar 9, 2021 at 22:57

2 Answers 2

1
$\begingroup$

Let $Y_n$ be the number of nondoubles in a sequence of dice-rolls ending upon the $n$th double. Then $Y_n$ is a $\text{NegativeBinomial$(n,p)$}$ random variable with $p={1\over 6},$ having the following probabilty mass function (with $q=1-p$): $$P(Y_n=k) = \binom{k+n-1}{n-1} p^nq^k\quad(k=0,1,2,...).$$

Letting $P_n$ be the probability that Doubles wins an $n$-lap game, we then have: $$\begin{align} P_n&=P(\text{fewer than $5n$ nondoubles occur before the $n$th double occurs})\\ &=P(Y_n< 5n)\\ &=p^n\sum_{k=0}^{5n-1}\binom{k+n-1}{n-1} q^k\tag{1}\\ &=\sum_{k=0}^{5n-1}\binom{k+n-1}{n-1} {5^k\over 6^{k+n}} \end{align}$$

(The OP's formula for $P_n$ has omitted the binomial coefficient.)

Example ($n=2$): Denote each occurrence of a double (resp. nondouble) by $1$ (resp. $0$). Then $P_2$ is the sum of the probabilities of just those sequences that end on the $2$nd occurrence of $1$ and have fewer than $2\times 5=10$ occurrences of $0$, as follows:

sequences                                    probabilities

11,                                          pp,
011, 101,                                    qpp, pqp,
0011, 0101, 1001,                            qqpp, qpqp, pqqp,
00011, 00101, 01001, 10001                   qqqpp, qqpqp, qpqqp, pqqqp,
000011, 000101, 001001, 010001, 100001       qqqqpp, qqqpqp, qqpqqp, qpqqqp, qqqqpp
...                                          ...
00000000011, 00000000101, ..., 10000000001   qqqqqqqqqpp, qqqqqqqqpqp, ..., pqqqqqqqqqp
                                             ------------------------------------------
                                             p^2 (1 + 2q + 3q^2 + 4q^3 + ... + 10q^9)
                                           = 12909191/22674816
                                           = 0.569318445627078...

To obtain the limit of $P_n$ as $n\to\infty,$ we use the fact that a $\text{NegativeBinomial$(n,p)$}$ random variable is distributed as the sum of $n$ i.i.d. $\text{Geometric}(p)$ random variables; thus, $$\begin{align} P_n&=P(Y_n< 5n)\\ &=P(G_1+...+G_n< 5n)\\ &=P(X_1+...+X_n<0) \end{align}$$

where the $G_i$ are i.i.d. $\text{Geometric}(p)$ random variables, and we have defined $X_i=G_i-5.$

Now the $X_i$ are i.i.d. with $E(X_i)=(1-p)/p-5=0,\ V(X_i)=(1-p)/p^2=30,\ $ so the Central Limit Theorem implies convergence in distribution to a standard normal random variable $Z$ as $n\to\infty:$ $${(X_1+...+X_n) - E(X_1+...+X_n)\over \sqrt{V(X_1+...+X_n)}}={X_1+...+X_n\over \sqrt{30n}}\xrightarrow{d} Z.$$ Hence, $$\begin{align} \lim_{n\to\infty}P_n&=\lim_{n\to\infty}P(X_1+...+X_n< 0)\\ &=\lim_{n\to\infty}P\left({X_1+...+X_n\over \sqrt{30n}}<0\right)\\ &=P(Z<0)\\ &={1\over 2}. \end{align}$$

Here are some values of $P_n$ (computed from (1) and rounded to $5$ digits) showing the convergence:

n       P_n

1       0.59812
10      0.53079
100     0.50971
1000    0.50307
10000   0.50097

TBD (Strict monotonic convergence of $P_n\searrow{1\over 2}$?)

It appears from numerical computations -- but remains to be proved -- that the convergence to ${1\over 2}$ is strictly monotonic, such that for all $n$, $P_{n}>P_{n+1}>{1\over 2}.$ As described earlier, this is equivalent to saying that for all $n$, $$P(X_1+...+X_{n}<0)> P(X_1+...+X_{n+1}<0) $$ where the $X_i=G_i-5$ are the i.i.d. "shifted $\text{Geometric}({1\over 6})$" random variables with $E(X_i)=0$ and $V(X_i)=30.$ Note that $$P(X_i<0)=P(G_i<5)=1-\left({5\over 6}\right)^5=0.59812...$$ so each of the independent $X_i$ is more likely to be negative than nonnegative -- yet, the more of them that are added together, the less likely it appears to be that the sum is negative! (If independent quantities are each most likely negative, wouldn't one expect that the more of these that are added together, the more likely it would be that the sum is negative?)


Generalization to races with arbitrary $p$

This more-general game is played with a pair of dice for which the probability of a double is any fixed arbitrary $p$ in the interval $(0,1)$, and there are now $m$ columns and $n$ rows, where $n$ is the number of laps to be run and $m$ is any fixed integer greater than $1$. Now Slowpoke has the first $m-1$ columns and Doubles has only the rightmost column to "X out", as before; i.e., Doubles wins the race if $n$ doubles occur before $(m-1)n$ nondoubles occur, otherwise Slowpoke wins.

Now $$\begin{align}P_n &= P(\text{Doubles wins an $n$-lap race}) \\ &=P(Y_n<(m-1)n)\\ &=P(G_1+...+G_n<(m-1)n)\\ &=P(X_1+...+X_n<0)\\ \end{align}$$ where $X_i=G_i-(m-1)$ and the $G_i$ are i.i.d. $\text{Geometric}(p),$ for which we find $E(X_i)=1/p-m$ and $V(X_i)=(1-p)/p^2.$

By the CLT we have $${(X_1+...+X_n) - E(X_1+...+X_n)\over \sqrt{V(X_1+...+X_n)}}={(X_1+...+X_n)-n(1/p-m)\over \sqrt{n(1-p)/p^2}}\xrightarrow{d} \text{Normal($0,1)$}$$ Hence, $$\begin{align}\lim_{n\to\infty}P_n &=\lim_{n\to\infty}P(X_1+...+X_n< 0)\\ &=\lim_{n\to\infty}P\left({(X_1+...+X_n)-n(1/p-m)\over \sqrt{n(1-p)/p^2}}<{-n(1/p-m)\over \sqrt{n(1-p)/p^2}}\right)\\ &=\lim_{n\to\infty}P\left(\text{Normal($0,1)$}<{-n(1/p-m)\over \sqrt{n(1-p)/p^2}}\right)\\ &=\lim_{n\to\infty}P\left(\text{Normal($0,1)$}<\sqrt{n}{m-1/p\over \sqrt{1-p}}\right)\\ \end{align}$$

and therefore: $$\lim_{n\to\infty}P_n=\begin{cases} 0&\text{if $m<1/p$}\\ 1/2&\text{if $m=1/p$}\\ 1&\text{if $m>1/p$}. \end{cases}$$

Although this proves convergence, it says nothing about monotonicity; however, computations do suggest that the convergence is strictly monotonic if $m=1/p$, but that it need not be so otherwise.

Example (effects of biased dice):

Here's a plot showing the three behaviors of $P_n\ (1\le n\le 1000)$ for $n$-lap races according to the OP's original rules (i.e. $m=6$) with $$ P(\text{double})=\begin{cases} 1/6+0.01 & \color{green}{\text{ (green)}} \\ 1/6 & \color{blue}{\text{ (blue)}} \\ 1/6-0.01 & \color{red}{\text{ (red)}} \end{cases}$$

enter image description here

As illustrated, convergence is to $1/2$ only when $p=1/6,$ otherwise convergence is to $1$ or $0$. The "zoomed view" on the right shows the initial non-monotonic behavior when $p=1/6+0.01$ (green).

$\endgroup$
1
  • $\begingroup$ This answer is beyond my level of math, but I am inspired to continue my study of math so that one day I will fully understand it, and be able to recreate it on my own. Thank you. $\endgroup$
    – Jim Flood
    Commented Mar 11, 2021 at 5:46
0
$\begingroup$

Partial Answer Only


Let $p = (1/6), q = (5/6)$

If I understand the problem correctly, after exactly $(6N - 1)$ rolls there are two mutually exclusive possibilities. Either there have been at least $(N)$ doubles or there have been fewer than $(N)$ doubles.

If there have been at least $N$ doubles, then have been no more than $(5N-1)$ non-doubles. In this scenario, Doubles must have crossed the finish line, and Slowpoke could not have crossed the finish line. If there were fewer than $N$ doubles, then the situation is reversed: Slowpoke had to have crossed the finish line, and Doubles could not have crossed the finish line.

In R Bernoulli trial's of an independent event, with probability of success $= p$, and $q = (1-p)$ the probability of exactly $k$ successes, for $k \in \{0,1,2, \cdots, R\}$ is $\binom{R}{k} p^kq^{(R-k)}$.

Here, this means that the probability of at most $S$ successes is
$\sum_{k=0}^S \binom{R}{k} p^kq^{(R-k)}$,
while the probability of at least $(S+1)$ successes is
$\sum_{k=(S+1)}^R \binom{R}{k} p^kq^{(R-k)}$.

Therefore, you can simply plug in the numbers of
$R = (6N-1)$, $S = (N-1)$, and $p = (1/6)$
to solve the general case of $N$ laps.

Examining the case of $N = 1$ gives Slowpoke's chances as

$$\left(\frac{5}{6}\right)^5 \approx 0.40,$$

while $N = 2$ gives Slowpoke's chances as
$$\left(\frac{5}{6}\right)^{11} + (11) \times (1/6) \times \left(\frac{5}{6}\right)^{10} ~\approx 0.43.$$


This suggests that as $N \to \infty$, Slowpokes chances are strictly increasing, and approach $(1/2)$ from below. This takes some proving however. Shown below, is analysis that goes as far as I can take it.


If you form the sequence of Slowpokes chances, based on the number of laps, as $\{t_1, t_2, \cdots \}$, you can then simplify the analysis by expressing

$$t_n = \frac{a_n}{b_n} ~\text{where} ~b_n = 6^{(6n-1)}.$$

Then, the numerator, $a_n$ will equal

$$a_n = \binom{6n-1}{0} 5^{(6n-1)} + \binom{6n-1}{1} 5^{(6n-2)} + \cdots + \binom{6n-1}{n-1} 5^{(5n)}.$$


Somebody with a better knowledge of statistics than me, is going to have to establish that

as $n \to \infty$, $\frac{a_n}{b_n}$ is strictly increasing and approaches $(1/2)$ from below.

$\endgroup$
1
  • $\begingroup$ I've added my equation as an update to my question. $\endgroup$
    – Jim Flood
    Commented Mar 9, 2021 at 18:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .