Here's the description of the game.
We have a target number x in mind and start by picking a number c1 uniformly at random from (0,1). Then c2 is picked uniformly at random from (0,c1), and in general, ci is picked uniformly at random from (0,ci−1). The game stops when we pick a ci such that ci<x.
What is the expected number of times we'll have to pick a number ci?
Alternatively, what is the expected length of the sequence of ci'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 c1, but I couldn't work it out.
Edit: we have x∈(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−lnx.
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)⋅(#future moves).
Now, suppose we have to continue, i.e., ci∈(x,1). Rather than choosing the next number ci+1 from (0,ci), we can instead scale x appropriately so that ci+1 is chosen from (0,1), effectively restarting the game with x/ci instead of x.
To account for the infinitely many ways to choose ci∈(x,1), we can take the following integral:
#future moves=11−x∫1xf(xu) du
In other words,
f(x)=1+∫1xf(xu) du.
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+blnx. 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