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

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.

• You don't care about the prime exponents, just their parity. So index a state by a triple $(a_1,a_2,a_3)$ where $a_i\in \{0,1\}$ and $a_1$ tracks the (parity of the) power of $2$ in the product, $a_2$ the power of $3$ and $a_3$ the power of $5$. Now you have a nice finite collection of states to play with.
– lulu
Commented Nov 24, 2023 at 14:27
• Cute problem. I wonder what the asymptotic behavior is for an $n$-sided die as $n \to \infty$. Commented Nov 24, 2023 at 17:39
• I've now asked this generalization as a question here. Commented Nov 24, 2023 at 18:48

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$$.

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!