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
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.
No comments:
Post a Comment