/r/problemoftheday

The following question was posed on the subreddit /r/problemoftheday:

Alice randomly chooses x_1 from [0,1], x_2 from [0,2], x_3 from [0,3], ... and x_n from [0,n]. What is the probability that x_1

Here's the answer I've come up with:


The general case is P(n) = (n+1)/(2^n)

Explanation:

A quick simulation shows that P(2) = 3/4 and P(1) obviously equals 1. For each term, it's fairly easy to see that the probability that the next term is *smaller* is the average value of that term (which is just the range divided by 2) over the entire range of the next value.

So the probability that the next term is greater than the last term, after any n number of terms, is (n+1)/(2n)

To get the probability that every consecutive term is larger than the last, we multiply all of these probabilities together to get:

Which simplifies to:

Which gives us our final form: