let's play a (continuous) probability game!

Question

Here's the description of the game.

We have a target number $x$ in mind and start by picking a number $c_1$ uniformly at random from $(0, 1)$. Then $c_2$ is picked uniformly at random from $(0, c_1)$, and in general, $c_i$ is picked uniformly at random from $(0, c_{i -1})$. The game stops when we pick a $c_i$ such that $c_i < x$.

What is the expected number of times we'll have to pick a number $c_i$? Alternatively, what is the expected length of the sequence of $c_i$'s?

I am guessing that the solution will be in terms of our target $x$. How would one go about approaching this problem? I thought about conditioning in terms of $c_1$, but I couldn't work it out.

Edit: we have $x \in (0, 1)$.

Edit 2: I am not hell-bent on using a conditional expectation approach. But if there exists some ridiculously simple solution, I am guessing it would involve it.

Answer 1

Given $x$, let $f(x)$ be the expected length of the game. We'll show that $f(x) = 1 - \ln x$.

The probability that we finish the game on the first step is $x$; the game continues with probability $1 - x$. We therefore have $$f(x) = 1 + (1 - x)\cdot(\textrm{#future moves}).$$

Now, suppose we have to continue, i.e., $c_i \in (x, 1)$. Rather than choosing the next number $c_{i+1}$ from $(0, c_i)$, we can instead scale $x$ appropriately so that $c_{i+1}$ is chosen from $(0, 1)$, effectively restarting the game with $x/c_i$ instead of $x$.

To account for the infinitely many ways to choose $c_i \in (x, 1)$, we can take the following integral: $$\textrm{#future moves} = \frac1{1-x}\int_x^1f\left(\frac xu\right)\ du$$

In other words, $$f(x) = 1 + \int_x^1f\left(\frac xu\right)\ du.\tag{1}$$

The rest (I'm skipping a few steps here...) is a matter of manipulating this to eventually bring it into the form of a differential equation, $$xf''(x) = -f'(x),$$ whose general solution is $f(x) = a + b\ln x$. From there, using $(1)$ we find $a=1, b=-1$, solving the problem.

Given the simplicity of the final expression there may be a much more direct solution, but at the moment I don't see one.

Answer 2

This answer uses the following statements:

Lemma 1: Let $U_1,\ldots,U_n$ be independent and identically distributed uniform random variables on the interval $(0,1)$. Then the probability density function of the product $U_1 \ldots U_n$ is given by $$ f_n(z) = \frac{(-1)^{n-1}}{(n-1)!} \log^{n-1}(z) 1_{(0,1)}(z).$$

Lemma 2: $$\int \log^{n}(z) \, dz = z \sum_{k=0}^n (-1)^{n-k} \frac{n!}{k!} (\log z)^k, \qquad n \in \mathbb{N}$$

Hints: Let $(U_i)_{i \in \mathbb{N}}$ be a sequence of independent random variables which are uniformly distributed on $(0,1)$.

1. Define iteratively $$C_1 := U_1 \qquad C_i := U_i C_{i-1}, \qquad i \geq 2.$$ Check that $(C_i)_{i \in \mathbb{N}}$ can be used to model the outcome of your probability. Show that $$C_i = \prod_{j=1}^i U_j$$ for any $i \in \mathbb{N}$.

2. Define $$\tau := \inf\{i \in \mathbb{N}; C_i < x\}.$$ Use the fact that the sequence $C_i$ is strictly increasing in $i$ to show that $$\mathbb{P}(\tau \geq i+1) = \mathbb{P}(C_i \geq x).$$

3. By Step 1 and Lemma 1, we have $$\mathbb{P}(C_i \geq x) = \frac{(-1)^{i-1}}{(i-1)!} \int_x^1 \log^{i-1}(z) \, dz$$ Use Lemma 2 to conclude that $$\mathbb{P}(C_i \geq x) = 1- x \sum_{k=0}^{i-1} (-1)^k \frac{1}{k!} (\log x)^k \quad \text{for $i \geq 2$}.$$

4. Since $$\mathbb{P}(\tau=i) = \mathbb{P}(\tau \geq i)-\mathbb{P}(\tau \geq i+1)$$ it follows from Step 2 and 3 that $$\mathbb{P}(\tau=i) = x (-1)^{i-1} \frac{(\log x)^{i-1}}{(i-1)!} \quad \text{for $i \geq 3$}.$$ Show that $$\mathbb{P}(\tau=1) = x \qquad \mathbb{P}(\tau=2) = -x \log x$$

5. Deduce from Step 4 that $$\mathbb{E}(\tau) = \sum_{i \in \mathbb{N}} i \mathbb{P}(\tau=i) = x +x \sum_{i \geq 2} i (-1)^{i-1} \frac{\log(x)^{i-1}}{(i-1)!}$$

6. Using $$ \sum_{i \geq 2} i \frac{z^{i-1}}{(i-1)!} = \frac{d}{dz} \sum_{i \geq 2} \frac{z^i}{(i-1)!}$$ prove that $$ \sum_{i \geq 2} i \frac{z^{i-1}}{(i-1)!} = \exp(z) (z+1)-1 $$

7. Conclude that $$\mathbb{E}(\tau) = 1- \log(x).$$