Krdytkyu

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.

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^1fleft(frac xuright) du$$

In other words,
$$f(x) = 1 + int_x^1fleft(frac xuright) 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 + bln 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.

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