Expected number of rolls until lcm is greater than $2000$?

Question

You continually roll a fair $10$ sided dice. What is the expected number of rolls until the lowest common multiple of all numbers that have appeared is greater than $2000$?

The primes in the numbers $1$ to $10$ are $2,3,5,7$. The lowest common multiple of these numbers is $210$. However, different numbers could come in different frequencies (one $9$ is worth two $3$s). How can you deal with this?

I am happy for solutions with approximate answers. The true value by simluation is around $18.8$.

Answer 1

The least common multiple of all the numbers $1-10$ is $2520$. Since half of this number is less than $2000$, it follows that you need to achieve $2520$ as an lcm, which means you need to see rolls of $7, 8, 9,$ and one of either $5$ or $10$. Other rolls are irrelevant to getting $2520$ as lcm.

Let $T$ be the number of rolls it takes to see a $7, 8, 9,$ and either a $5$ or $10$. Then $T$ can be written as $$T = X_1 + X_2 + X_3 + X_4,$$ where $X_1, X_2, X_3, X_4$ are independent geometric r.v.'s representing the time to get the first, second, third, and fourth of the four necessary prime factors of $2520$. $X_1$ always has a parameter of $\frac{5}{10}$, but the parameters of $X_2, X_3, X_4$ depend on whether the $5$ or $10$ has been rolled yet after the first, second, third prime factors of $2520$ have been collected.
Let $A_i$, $i = 1, 2, 3, 4$, be the event that the $5$ or $10$ is the $i$th to be achieved out of the $4$ types of roll necessary.
Then we can use conditional expectations to calculate $$\Bbb{E}[T] = \sum_{i=1}^4 \Bbb{E}[T | A_i] \Bbb{P}(A_i).$$ The probabilities of the $A_i$ are easy to find: \begin{align*} \Bbb{P}(A_1) &= \frac{2}{5}, \\ \Bbb{P}(A_2) &= \frac{3}{5} \times \frac{2}{4} = \frac{3}{10}, \\ \Bbb{P}(A_3) &= \frac{3}{5} \times \frac{2}{4} \times \frac{2}{3} = \frac{1}{5}, \\ \Bbb{P}(A_4) &= \frac{3}{5} \times \frac{2}{4} \times \frac{1}{3} = \frac{1}{10}. \ \end{align*}

Conditioned on the $A_i$, we also find \begin{align*} \Bbb{E}[T | A_1] &= \sum_{j=1}^4 \Bbb{E}[X_j | A_1] = \frac{10}{5} + \frac{10}{3} + \frac{10}{2} + \frac{10}{1} = \frac{61}{3}, \\ \Bbb{E}[T | A_2] &= \sum_{j=1}^4 \Bbb{E}[X_j | A_2] = \frac{10}{5} + \frac{10}{4} + \frac{10}{2} + \frac{10}{1} = \frac{39}{2}, \\ \Bbb{E}[T | A_3] &= \sum_{j=1}^4 \Bbb{E}[X_j | A_3] = \frac{10}{5} + \frac{10}{4} + \frac{10}{3} + \frac{10}{1} = \frac{107}{6}, \\ \Bbb{E}[T | A_4] &= \sum_{j=1}^4 \Bbb{E}[X_j | A_4] = \frac{10}{5} + \frac{10}{4} + \frac{10}{3} + \frac{10}{2} = \frac{77}{6}, \\ \end{align*}

and putting it all together, \begin{align*} \Bbb{E}[T] &= \sum_{i=1}^4 \Bbb{E}[T | A_i] \Bbb{P}(A_i) \\ &= \frac{2}{5} \times \frac{61}{3} + \frac{3}{10} \times \frac{39}{2} + \frac{1}{5} \times \frac{107}{6} + \frac{1}{10} \times \frac{77}{6} \\ &= \frac{113}{6} \approx 18.83333... \ \end{align*}

So, it should take a little less than $19$ rolls, on average, to see an lcm of $2520$.

Answer 2

(sketch of the method)

Best to proceed by states.

We remark that $$\text{lcm}(2,3,4,5,6,7,8,9,10)=2^3\times 3^2\times 5\times 7=2520$$ is so close to $2000$ that no divisor of it will suffice. It follows that you need to see the $8$, the $9$, the $7$ and either a $5$ or a $10$.

Introduce states $(a,b,c,d)$ according to whether or not the relevant prime power, $(2^3,3^2,5,7)$, has been fully seen. Here $a,b,c,d\in \{0,1\}$ and, $(1,1,0,0)$, say, means that you have seen $8,9$ but none of $5,7,10$. We remark that there are $16$ states which we can number according to the binary representations of the numbers $0,\cdots, 15$ in an obvious way. Since $14 =1110_2$ we'd have state $14$ be $(1,1,1,0)$, meaning that you have only to see the $7$. Similarly, the state $8=(1,0,0,0)$ would mean that you had seen the $8$ roll but sill needed the $9$, the $7$ and either the $5$ or the $10$.

Let $E_i$ be the expected number of tosses it will take given that you are starting in state $i$. Of course, the answer to the question is $E_0$.
We see that $E_{15}=0$ since state $15$ means you have already seen enough tosses.

$E_{14}=10$ since you expect it to take $10$ tosses to see the $7$.

$E_{13}=5$ since you expect it to take $5$ tosses to see either the $5$ or the $10$.

For $E_{12}=E_{(1,1,0,0)}$ we note that $$E_{12}=\frac 7{10}\times (E_{12}+1)+\frac 2{10}\times (E_{14}+1)+\frac 1{10}\times (E_{13}+1)\implies$$ $$\implies E_{12}=\frac {35}3$$

Continue in this manner. As you see, the computations are tedious but not difficult. They are also a bit error prone, so I suggest simulation to confirm the result.