Uniform Distribution Puzzle/Breaking Sticks

[jason1990]

Consider the following game.

Step 1: choose a point x_1 uniformly from the interval [0,1]. If the length of the interval [0,x_1] is greater than 0.5, you lose. Otherwise, you continue.

Step 2: choose a point x_2 uniformly from the interval [x_1,1]. If the length of the interval [x_1,x_2] is greater than 0.5, you lose. Otherwise, continue. ...

Step n: choose a point x_n uniformly from the interval [x_{n-1},1]. If the length of the interval [x_{n-1},x_n] is greater than 0.5, you lose. Otherwise, continue. ...

In order to win, you must survive all (infinitely many) steps. What is the probability you win?

An alternative description for the notationally challenged:

Take a stick of length one. Randomly (i.e. uniformly) break off a piece of it and discard it. Do the same with the remainder of the stick. Continue this infinitely many times. What is the probability that every discarded piece has length less than 0.5?

[AaronBrown]

You will lose ln(2) = 69% of the time and win the rest.

[jay_shark]

The probability you pass the first round is 1/2 . The probability you pass the second round given that you passed the first round is the following :

First label the points A(0,0) B(0,1/2) C(1/2,1) D(1/2,0) The probability is just the area of the trapezoid ABCD which is 3/8 .

[jason1990]

[ QUOTE ]
You will lose ln(2) = 69% of the time and win the rest.

[/ QUOTE ]
0 points. Show your work. [img]/images/graemlins/wink.gif[/img]

[jason1990]

No elegant solutions to this one?

[PairTheBoard]

How about a hint?


PairTheBoard

[pzhon]

[ QUOTE ]
No elegant solutions to this one?

[/ QUOTE ]
I don't know how elegant others will find the following, but I have a suggestion for a more elegant method below.

Let f(c) be the probability of winning when you have not been disqualified yet after choosing x=c. We'd like to determine f(0).

For 1/2<=c<=1, f(c)=1.

For 0<=c<=1/2,
f(c) = (Integrate f(x) dx)/(1-c)
where the integral is from c to c+1/2.

Integral equations are pretty, but there are standard tools for solving differential equations, so let's try to convert this to a differential equation.

for 0<=c<=1/2
(1-c)f(c) = Integral_c^(c+1/2) f(x) dx
D_c[LHS] = D_c[RHS], as the equation is between functions
(1-c)f'(c)-f(c) = f(c+1/2) - f(c)
(1-c)f'(c) = f(c+1/2)
(1-c)f'(c) = 1
f'(c) = 1/(1-c)
f(c) = -ln(1-c) + constant

We can determine the value of the constant by considering c=1/2, where f is continous, and f(c)=1 for c>1/2.
1 = f(1/2) = -ln(1/2) + constant
constant = 1 + ln (1/2)
constant = 1 - ln 2.

f(0) = - ln (1) + constant
f(0) = constant
f(0) = 1 - ln 2. [img]/images/graemlins/diamond.gif[/img]

Once we know the value of f(c) for 0<c<1/2, we can get the values of f(c) for -1/2<c<0 by solving the lag differential equation f'(c) = f(c+1/2)/(1-c). f(-1/2) means the probability that no interval would be 1/2 or greater when you start with a stick of length 3/2, or equivalently, the probability that no interval would be 1/3 or greater when you start with a stick of length 1.


The following problem has been solved here before and seems related. Choose x_i to be independently and uniformly distributed on [0,1]. What is the expected index of the first partial sum s_i = x_1 + x_2 + ... + x_i which is at least 1?

Again, there is a way to translate this into an integral equation, then a differential equation which would turn into a lag differential equation if you adjust the target partial sum. There is also another solution by computing the probability that the nth partial sum is at most 1. Is there an analogous series solution?

I wonder whether there is a way to apply inclusion-exclusion which would provide a series like 1/2 - 1/3 + 1/4 - 1/5 ... Perhaps it is possible to compute the probability that no point is on a particular line segment of length at least 1/2.

[pzhon]

[ QUOTE ]

First label the points A(0,0) B(0,1/2) C(1/2,1) D(1/2,0) The probability is just the area of the trapezoid ABCD which is 3/8 .

[/ QUOTE ]
This is incorrect, even assuming that you want the probbility of passing the first two rounds rather than the conditional probability of passing the second round given that you survived the first. If the first number is 1/4, the probability that the second number disqualifies you is 1/3, not 1/4. You want the area under (1/2)/(1-x) from x=0 to x=1/2, (ln 2)/2 ~ 0.347.

[jason1990]

[ QUOTE ]
I don't know how elegant others will find the following

[/ QUOTE ]
Of course I can't speak for others, but I think this is very nice. It beats what I did, which is too cumbersome to type in plain text in full detail. The sketch is this. Let f_n be the density of the n-th chosen point. By conditioning on this point, we can obtain

f_{n+1}'(x) = f_n(x)/(1 - x).

This gives

f_{n+1}(x) = [(-1)^n/n!]*[ln(1 - x)]^n.

I then expressed the probability we want to compute as an infinite sum where the n-th term is an integral of f_n. Passing summation under integral turns this into an integral of a sum which is just a geometric series and can be computed. From there, it is just basic integration.

By the way, this problem was inspired by the following puzzle:

<ul type="square">
A prison contains 100 prisoners. In a special room are 100 boxes. Each box contains the name of one of the prisoners. Tomorrow, each prisoner will be compelled to enter the room and select 50 boxes, hoping to find the box with his or her name in it. They need not select all 50 at once. They can select one, open it, then select the next, open it, and so on. If every prisoner succeeds, they are all set free. If even one prisoner fails to find his name, they are all executed. The prisoners may not communicate tomorrow, but they may communicate today. That is, they may discuss and decide upon a selection strategy. Find a strategy which guarantees they will have at least a 30% chance of being freed.[/list]
I can't tell you what the connection is between the two without giving a substantial hint to the prisoner puzzle. So I think I will leave at this for now and say more later.

Edit: Sorry, it's not a geometric series. I was trying to recall this from memory and typing too quickly. It's the Taylor expansion for the exponential function. The point, of course, is that it's something which can be summed explicitly.

[AaronBrown]

I don't understand the prisoner problem. The first prisoner has a 50% chance of succeeding. If she does, she can put all the names in alphabetical order, then each subsequent prisoner can select his or her name with one box. So there is a 50% chance of succeeding.

As to showing my work for the ln(2) answer, recall that ln(2) = 1/(1 + 1/(2 + 1/(3 + . . .