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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...