A fair six-sided die is rolled repeatedly until the product of the rolls is square.

Question

I'm stuck on this problem.

A fair six-sided die is rolled repeatedly. On average how long does it take until the first time that the product of the numbers rolled is a square? (For example, if the first roll is 1 or 4, it takes just one roll; if the sequence begins 3, 2, 6, then it takes three rolls.)

I'm trying to use prime factors to get a solution, for instance if we don't roll a 1 or 4 first, rolling it again will not affect the chance of the next throw giving our product as a square, and we need an even number of 5s, the number of 2s + number of 6s to be even, and the number of 3s + number of 6s to be even.

I know I need to relate this to Markov chains somehow, but I'm stuck as to how.

Answer 1

As suggested by #lulu let Markov chain $X_n$ have $8$ states. Let $a_1$ be the parity of power $2$, Let $a_2$ be the parity of power $3$, Let $a_3$ be the parity of power $5$.

Denote the states:

"1" if $(a_1,a_2,a_3)=(0,0,1)$

"2" if $(a_1,a_2,a_3)=(0,1,0)$

"3" if $(a_1,a_2,a_3)=(0,1,1)$

"4" if $(a_1,a_2,a_3)=(1,0,0)$

"5" if $(a_1,a_2,a_3)=(1,0,1)$

"6" if $(a_1,a_2,a_3)=(1,1,0)$

"7" if $(a_1,a_2,a_3)=(1,1,1)$

"8" if $(a_1,a_2,a_3)=(0,0,0)$ (the absorbing state).

The initial state after the first roll will be with "8" with probability $1/3$ (if you get 1 or 4), or "1","2","4", "6" each with probability $1/6$, i.e. $\pi=\left(\frac16,\frac16,0,\frac16,0,\frac16,0,\frac13\right)$.

The transition probability matrix will be then: $$ P=\left[ \begin {array}{cccccccc} {\frac{1}{3}}&0&{\frac{1}{6}}&0&{ \frac{1}{6}}&0&{\frac{1}{6}}&{\frac{1}{6}}\\ 0&{ \frac{1}{3}}&{\frac{1}{6}}&{\frac{1}{6}}&0&{\frac{1}{6}}&0&{\frac{1}{6 }}\\ {\frac{1}{6}}&{\frac{1}{6}}&{\frac{1}{3}}&0&{ \frac{1}{6}}&0&{\frac{1}{6}}&0\\ 0&{\frac{1}{6}}&0&{ \frac{1}{3}}&{\frac{1}{6}}&{\frac{1}{6}}&0&{\frac{1}{6}} \\ {\frac{1}{6}}&0&{\frac{1}{6}}&{\frac{1}{6}}&{ \frac{1}{3}}&0&{\frac{1}{6}}&0\\ 0&{\frac{1}{6}}&0&{ \frac{1}{6}}&0&{\frac{1}{3}}&{\frac{1}{6}}&{\frac{1}{6}} \\ {\frac{1}{6}}&0&{\frac{1}{6}}&0&{\frac{1}{6}}&{ \frac{1}{6}}&{\frac{1}{3}}&0\\ {}0&0&0&0&0&0&0&1 \end {array} \right] $$ The sub-matrix $[1..7,1..7]$ is $P_0$ and then the expected time to reach the absorbing state "8" from state $i$ is given by $\mu_i$ where $\mu$ is $$ \mu=({\bf I}-P_0)^{-1} \begin{bmatrix} 1\\1\\1\\1\\1\\1\\1 \end{bmatrix} =\begin{bmatrix} 12\\ 10\\ 14\\ 10\\ 14\\ 10\\ 14 \end{bmatrix} $$ where ${\bf I}$ is the $7\times7$ identity matrix.

It takes one roll to get the first number, and after that the expected time to get to full square is 0 with probability 1/3 (if you got "4" or "1") and otherwise $\mu_i$ with probability $\pi_i$, $i=1,...,7$. Consequently the answer is $1+7=8$.

Answer 2

Python code to back it up:

import random
import math

SIMULATIONS = 10000

def is_square(n):
    if math.sqrt(n).is_integer():
        return False # for the while loop to continue until square (while True)
    else:
        return True

def multiply(lst):
    product = 1
    for element in lst:
        product = product * element
    return product

def simulation():
    expected_rolls = []
    for _ in range(SIMULATIONS):
        rounds = 0
        rolls = []
        dice = [1, 2, 3, 4, 5, 6]
        if len(rolls) == 0:
            rolls.append(random.choice(dice))
            rounds += 1
        while is_square(multiply(rolls)):
            rolls.append(random.choice(dice))
            rounds += 1
        expected_rolls.append(rounds)
    print(f"The expected number of rolls is: {sum(expected_rolls)/len(expected_rolls)}")

simulation()

Very interesting problem!