Breaking sticks, not throwing them

[jason1990]

[ QUOTE ]
Two equally likely things can happen with the first break, we can get a piece longer than 0.5 (the first 1 in the denominator) or we can continue (the rest of the denominator). If we continue, three equally likely things can happen. 2 of them end the game (the 2) and one of them continues (the rest of the fraction). And so on.

[/ QUOTE ]
As pzhon pointed out, these events are not equally likely. There are several ways to construct the break points X_1, X_2, .... I will describe 1 valid method and 1 invalid method. Under the invalid method, these events are equally likely. Under the valid method, they are not. For simplicity, I will only construct the first 2 break points. Note that in order to verify that a method is valid, we must check that (1) X_1 ~ Uniform(0,1), and (2) the distribution of X_2 - X_1, given X_1, is Uniform(0, 1 - X_1). To check condition (2), we need to verify that, for x < y, P(X_2 < y | X_1 = x) = (y - x)/(1 - x).

First, the invalid method. This I will call the conditioning method. In this, we choose two points independently and uniformly from [0,1]. If the second point is smaller than the first, we throw away both points and try again. This amounts to simply choosing the point (X_1, X_2) uniformly from the triangle {0 < X_1 < X_2 < 1}. With this method, it is easy to verify condition (2). However, condition (1) fails, showing that this method is invalid. With this method, it is also easy to compute

P(X_2 in [X_1, 0.5] | X_1 < 0.5) = 1/3
P(X_2 in [0.5, X_1 + 0.5] | X_1 < 0.5) = 1/3
P(X_2 in [X_1 + 0.5, 1] | X_1 < 0.5) = 1/3.

So these events are equally likely. Unfortunately, since this is an invalid construction, this fact is irrelevant for the original problem.

The valid method, I will call the resampling method. We again choose two points independently and uniformly from [0,1]. This time, though, if the second point is smaller than the first, we throw away only the second point. To write this down formally, construct an iid sequence Y_1, Y_2, ... of Uniform(0,1)'s. Let N be the first index such that Y_N > Y_1. Define X_1 = Y_1 and X_2 = Y_N. Clearly, X_1 = Y_1 is Uniform(0,1), so condition (1) is satisfied. To verify condition (2), take x < y and calculate

P(Y_N < y | Y_1 = x)
= \sum_{n=2}^\infty P(N = n, Y_n < y | Y_1 = x).

If we are given that Y_1 = x, then in order to have N = n and Y_n < y, we must have Y_i < x for all i strictly between 1 and n, and x < Y_n < y. The probability of this is x^{n-2}(y - x). Summing this from 2 to infinity gives (y - x)/(1 - x). Hence, condition (2) is satisfied and this is a valid construction.

Now, it is true that

P(Y_2 in [0, Y_1] | Y_1 < 0.5) = 1/4
P(Y_2 in [Y_1, 0.5] | Y_1 < 0.5) = 1/4
P(Y_2 in [0.5, Y_1 + 0.5] | Y_1 < 0.5) = 1/4
P(Y_2 in [Y_1 + 0.5, 1] | Y_1 < 0.5) = 1/4.

If the first case happens, we are going to throw away Y_2 and choose a new point Y_3. But when we do that, the analogous events for Y_3 are no longer equally likely. The fact that we have thrown away Y_2 will tell us that the interval [0, Y_1] is longer than we would expect it to be without that information. For example, one can calculate that

P(Y_3 in [0, Y_1] | Y_1 < 0.5 and Y_2 in [0, Y_1]) = 1/3.

All in all, this means that Y_N is not equally likely to be in the three intervals [Y_1, 0.5], [0.5, Y_1 + 0.5], [Y_1 + 0.5, 1]. To verify this rigorously, it suffices to check that P(Y_N > 0.5 | Y_1 < 0.5) is not equal to 2/3. Using our earlier computations, we have

P(Y_N > 0.5 | Y_1 < 0.5) = P(Y_N > 0.5, Y_1 < 0.5)/P(Y_1 < 0.5)
= 2P(Y_N > 0.5, Y_1 < 0.5)
= 2\int_0^{0.5} P(Y_N > 0.5 | Y_1 = x) dx
= 2\int_0^{0.5} 0.5/(1 - x) dx
= ln(2),

which is not 2/3.

So the heuristic argument that led to the above quote is false. For future reference, I will call this the false heuristic.

[ QUOTE ]
What I actually solved for was the expected number of breaks less than 0.5

[/ QUOTE ]
Let us pretend for now that the false heuristic is actually true. We will use it to compute the expected number of breaks less than 0.5. Under the false heuristic, there will be exactly 1 break less than 0.5 with probability (1/2)(2/3). There will be exactly 2 breaks less than 0.5 with probability (1/2)(1/3)(3/4). In general, there will be exactly n breaks less than 0.5 with probability (n + 1)/(n + 2)! So the expected number of breaks less than 0.5 is

S = \sum_{n=1}^\infty n(n + 1)/(n + 2)!

Define

f(x) = (e^x - 1)/x
= \sum_{n=1}^\infty x^{n - 1}/n!

By differentiating the series term-by-term, it is easy to verify that f''(1) = S. We then compute

f'(x) = (xe^x - e^x + 1)/x^2
f''(x) = (x^3 e^x - 2x^2 e^x + 2xe^x - 2x)/x^4.

Thus S = e - 2 = 0.7182818... Your first continued fraction evaluates to 0.69777... This is shown here and was originally linked by pzhon. Your second continued fraction evaluates to ln(2) = 0.69314... Neither of them are equal to e - 2. So if you used the false heuristic to calculate the expected number of breaks less than 0.5, you would not be led to either of the continued fractions which you mentioned.

Edit: So as not to confuse anyone, I want to emphasize that e - 2 is not the expected number of breaks less than 0.5. It is what the expected number would be if the false heuristic were correct.