Random Sampling Reduction

I did it using pretty elementary math,but thought it might be worth a mention

Probability of finishing in 1 turn

$\large \displaystyle \frac{1}{10}$

Probability of finishing in 2 turns

$\large \displaystyle \int_{1}^{10}\frac{dr_{1}}{10} \times \frac{1}{r_{1}}=\frac{ln10}{10}$

Probability of finishing in 3 turns

$\large \displaystyle \frac{1}{10} \int_{1}^{10} \int_{1}^{r_{1}}\frac{dr_{2}}{r_{1}r_{2}}dr_{1}=\frac{1}{10} \frac{(ln10)^{2}}{2!}$

Probability of finishing in $n$ turns (By induction )

$\large \displaystyle \frac{1}{10} \int_{1}^{10} \int_{1}^{r_{1}} \int_{1}^{r_{2}}.... \int_{1}^{r_{n-2}}\frac{dr_{n-1}}{r_{1}r_{2}r_{3}...r_{n-1}}dr_{n-2}dr_{n-3}...dr_{1}=\frac{1}{10} \frac{(ln10)^{n-1}}{(n-1)!}$

---

Expected value of number of turns

$\large \displaystyle \frac{1}{10} \sum_{r=0}^{\infty}\frac{(r+1)x^{r}}{r!}$ where, $x=ln10$

$\large \displaystyle \frac{1}{10} \sum_{r=0}^{\infty}\frac{(r+1)x^{r}}{r!}=\frac{1}{10}(e^{x}+xe^{x})=1+ln10 \approx 3.303$

Let $N_x$ denote the number of turns in the slightly more general game where $r_1$ is chosen between $0$ and $x$ and let $F(x) = \mathbb{E}[N_x]$ .

Then we immediately have the conditional expectation $\mathbb{E}[N_x|r_1] = \begin{cases}0 & x<1 \\ 1 + F(r_1) \quad & x\geq 1\end{cases}$ and therefore $\begin{aligned} F(x) = \mathbb{E}\Big[\mathbb{E}[N_x|r_1]\Big] &= \begin{cases}0 & x<1 \\ 1 + \int_0^x \frac{1}{x}F(r_1)\,dr_1 \quad & x \geq 1\end{cases} \\ &= \begin{cases}0 & x<1 \\ 1 + \frac{1}{x}\int_1^x F(r_1)\,dr_1 \quad & x \geq 1\end{cases} \end{aligned}$

For the rest of the problem, we focus purely on the case where $x \geq 1$ , under which we have just shown $F(x) = 1 + \frac{1}{x}\int_1^x F(t)\,dt.$

By rearranging, $x\big(F(x) - 1\big) = \int_1^x F(t)\, dt,$ and differentiating, $F(x) - 1 + xF'(x) = F(x),$ we can write $F'(x) = \frac{1}{x} \Rightarrow F(x) = C + \ln x.$

Looking back at the integral equation for $F(x)$ when $x\geq 1$ , we see that $F(1) = 1$ , so we may solve for $C$ to find $C=1$ . Therefore, we have $F(x) = \begin{cases}0 & x < 1 \\ 1 + \ln x \quad & x\geq 1\end{cases}$ so the expected number of moves when $x=10$ is $F(10) = 1 + \ln 10 \approx \boxed{3.30}$ .

Note: There's a sizable hole in the above proof - see if you can find it! All of the results are true, but it would require a little bit more work to be a formal proof.