Saturday, April 30, 2016

let's play a (continuous) probability game!



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,ci1). 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)=1lnx.



The probability that we finish the game on the first step is x; the game continues with probability 1x. We therefore have
f(x)=1+(1x)(#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=11x1xf(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

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...