Breaking sticks, not throwing them

[AaronBrown]

I’ve split off this thread from Uniform Distribution Puzzle/Breaking Sticks. That started with a puzzle. I posted three solutions, one complete, one with a missing step and one was just a hint. Two posters got upset. If you want the chapter and verse you can read that thread, the gist of the complaint seems to be that the missing step and hint were too hard.

I apologized and did my best to calm things down, but nothing helped. Finally, at the direction of one of the angry posters, I agreed to start this thread to discuss just the math. I respectfully request that people interested in flaming use the other thread. I suggested that the unhappy posters stay away from this thread, and I have promised not to read or post on their thread.

The next four posts contain the original puzzle (reworded), and my three solutions (also reworded), each completely spelled out. Each of them gives some different insight into the puzzle, and demonstrates different mathematical tools.

[AaronBrown]

PUZZLE: Take a stick and break it at a location selected with uniform density along its length. Throw away the left-hand piece and break the right-hand one at a location selected with uniform density along its length. Continue forever. What is the probability that one of the discarded left-hand pieces is more than half as long as the original stick?

[AaronBrown]

Solution 1: Start with a ruler scaled from 0 to 1 instead of a stick. Pick numbers from a uniform 0,1 distribution until you get one number greater than 0.5. Each time you get a number, break the ruler at that number. If the number is smaller than the remaining left edge of the rule, ignore it. This is the same as the original problem because each break is done with uniform density over the remaining length of the ruler. We can stop after the first number greater than 0.5, because if we don’t have a piece longer than 0.5 by then, we can’t get one afterwards since the remaining right-hand piece is too short.

To have a left-hand piece longer than 0.5, the last break must be more than 0.5 greater than the largest of all the previous breaks. We know it is uniformly selected from the interval 0.5 to 1. If we subtract 0.5 from it, it is uniformly distributed from 0 to 0.5, just like all the previous breaks. Now having a piece of length greater than 0.5 is the same as the last point minus 0.5 being the largest of all the points selected.

If a total of k points are selected, the chance is 1/k that the last one will be the largest. The chance that k points will be selected is 0.5^(k+1), that is there is 0.5 chance there will be only one point (the first one will be between 0.5 and 1), 0.25 chance there will be two points (the first one is between 0 and 0.5 and the second one between 0.5 and 1), and so on.

The expected value of the chance that the last point is the largest is the sum from k = 1 to infinity of [0.5^(k+1)]/k which equals ln(2).

[AaronBrown]

Solution 2: Half the time, the first break will end the game and the left hand piece will be longer than 0.5 If not, the first break is uniformly distributed from 0 to 0.5. The last break must be uniformly distributed from 0.5 to 1. Therefore, we can define a reduced game as starting with a stick with independent uniformly distributed amounts from 0 to 0.5 broken off from each end. The chance of getting a piece longer than 0.5 in the original game is equal to 0.5 + 0.5 times the chance of getting a piece longer than 0.5 in the reduced game.

Half the time, the reduced game will have no further breaks. One quarter of the time it will have one additional break. It will have k additional breaks with probability 0.5^(k+1). If X is the amount of the upper break, if the first break or any of the additional breaks are greater than X – 0.5, there will be no piece longer than 0.5. Otherwise, there will be a piece longer than 0.5.

Since the first and additional breaks are uniformly distributed from 0 to 0.5, the chance of all k+1 of them being less than X – 0.5 is (2*X – 1)^(k+1). The expected value of this probability is the sum from k = 0 to infinity of 0.5^(k+1)*(2*X – 1)^(k+1) = the sum from k = 1 to infinity of (X – 0.5)^k which equals (X – 0.5)/(1.5 - X).

X is uniformly distributed between 0.5 and 1, so we have 2 times the integral from 0.5 to 1 of (X – 0.5)/(1.5 – X) dX, which is 2 times the integral from 0 to 0.5 of X/(1 – X) which is 2 times -ln(1 – X) – X evaluated from 0 to 0.5 which is 2 times -ln(0.5) – 0.5 which is 2*ln(2) – 1.

Half of the reduced game probability is ln(2) – 0.5, 0.5 plus that is ln(2).

[AaronBrown]

Solution 3: Two equally likely things can happen on the first break. We can get a stick longer than 0.5 or not.

If there is a second break, the first break was between 0 and 0.5. Draw a number from a uniform distribution from 0 to 1. Four equally likely things can happen. It can be lower than the first number, greater than the first number but less than 0.5, greater than 0.5 but less than the first number plus 0.5 or greater than the first number plus 0.5. In the first case, it is not a break, so there are three remaining cases. One ends the game with a stick longer than 0.5 (second break is greater than the first break plus 0.5), one ends the game with no stick longer than 0.5 (second break is between 0.5 and first break plus 0.5) and one allows the game to continue (second break is between first break and 0.5).

If there is an n-th break, there are 2*n equally likely outcomes, n – 1 of which don’t count as breaks. The draw from a uniform distribution can be less than or greater than 0.5. If it’s less than 0.5, it can be less than all the previous breaks, less than all but one of the previous breaks and so on up to greater than all the previous n-1 breaks. If it’s greater than 0.5, it has the same intervals, just with 0.5 added. If it’s below 0.5, only the interval between the highest break to date and 0.5 counts. Of the n+1 possible events, one ends the game with a stick longer than 0.5 (last break is more than 0.5 greater than the biggest previous break), n – 1 end the game with no stick longer than 0.5 (last break is greater than 0.5, but less than 0.5 plus biggest previous break) and one allows the game to continue (last break is greater than biggest previous break, but less than 0.5).

This suggests the chance of getting a stick longer than 0.5 is equal to the continued fraction:

1/(1 + 1/(2 + 1/(3 + 1/(4 + . . . .

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. The numerators are all 1, representing the one of n+1 ways to end the game with a stick longer than 0.5 at each break.

In fact, that was the first answer I got for this problem. That sum is equal to 0.6978 while ln(2), the correct answer, is 0.6932. The standard continued fraction for ln(2) starts off the same as my guess, but changes (see the coefficients in bold, which are not 1):

1/(1 + 1/(2 + 1/(3 + 4/(4 + 4/(5 + 9/(6 + 9/(7 + . . . .

What I actually solved for was the expected number of breaks less than 0.5, rather than the probability of ending up with a stick longer than 0.5. My denominators were correct, but my numerators were not. I used 1, although the chance of ending the game with a stick longer than 0.5 is slightly greater than 1/(n + 1). There is 1 event of the n + 1 equally likely ones that ends the game immediately, but there is a chance on the order of 1/(n + 1)^2 of prolonging the game and then getting a stock longer than 0.5.

[djames]

In the future, could you always post answers with this level of clarity? If so, I believe all of the other extracurricular activity would have been avoided.

I for one never responded in the other thread, but I enjoy reading & answering puzzles without posting as I read these puzzles from work.

This was my chain of thought after the first few posts:

AaronBrown: ln(2)
me: wow, that was quick & is an answer I didn't expect:
?: 0 points:
me: yeah, how'd he get ln(2)?
?: show your work:
AaronBrown: ln(2) = 1/(1 + 1/(2 + 1/(3 + ...
me: no, that's not right. maybe the answer isn't ln(2) afterall. I'll try to find out the real answer after lunch.
?: someone wrote a clear proof also reaching ln(2)
me: ah ok, it is ln(2) and I understand that answer. Aaron must have simulated, recognized ln(2) and tried to express it in a continued fraction. Or, he simulated the wrong answer, but one that "looked" like ln(2).
?: wrote my same sentiments
all: drama bomb

[pzhon]

[ QUOTE ]
Solution 3:

[/ QUOTE ]
The other two were solutions. This one was clearly not a solution, even though some people who were not paying attention might have thought that it was. Why did you call it a solution?

Please retract your statement that this was a solution, and apologize for intentionally attempting to mislead people with these statements and the suggestion that you had a derivation involving ln(2)=1/(1+1/(2+1/(3+....

Once again, if you construct a logical argument solving this problem while deriving a continued fraction for ln(2), this will be a publishable derivation for that continued fraction for ln(2). It is unethical to claim to have such a proof when you know you don't have it.

[ QUOTE ]
If we continue, three equally likely things can happen.

[/ QUOTE ]
These are not equally likely. Given that the first break did not end the game, the conditional probability that the second break does not end the game is not 1/3. It is 1-ln(2) = 0.306853.

[ QUOTE ]
What I actually solved for was the expected number of breaks less than 0.5, rather than the probability of ending up with a stick longer than 0.5.

[/ QUOTE ]
Do you claim that the expected number of breaks less than 1/2 has something to do with that ratio of Bessel function values [0;1,2,3,4,...]? That looks wrong to me, but I haven't done a rigorous calculation yet. Have you, or did you again say solve to mean something very different?

[ QUOTE ]
The standard continued fraction for ln(2) starts off the same as my guess, but changes ... My denominators were correct, but my numerators were not. ... There is 1 event of the n + 1 equally likely ones that ends the game immediately, but there is a chance on the order of 1/(n + 1)^2 of prolonging the game and then getting a stock longer than 0.5.

[/ QUOTE ]
I believe I quoted those in context. You guessed incorrectly, came up with the wrong numerators through a heuristic argument with flawed assumptions, and then you don't explain how to get the magic correction factor in the numerator of (n/2)^2 when n is even, and ((n-1)/2)^2 when n is odd to get the correct value ln(2). You haven't distinguished the even and odd cases. Whatever you meant by 1/(n+1)^2, that is far from (n/2)^2 in this context. How can you call this a solution?

Mathematics is not a democracy, but I'm curious how many people agree with me rather than you.

[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.

[jogsxyz]

[ QUOTE ]


This suggests the chance of getting a stick longer than 0.5 is equal to the continued fraction:

1/(1 + 1/(2 + 1/(3 + 1/(4 + . . . .



[/ QUOTE ]

I don't understand it. Never of a continued fraction.
Can you list the first four terms of this continued fraction? Or that just isn't the way it's done.

[jay_shark]

Aaron , thx for taking the time to respond . I read all the posts and I appreciate everyones input on here .

Also , I must say, your solution to this problem is the best one I've read !!