Breaking sticks, not throwing them

[AaronBrown]

[ QUOTE ]
But please only use notation which is formal and completely unambiguous.

[/ QUOTE ]
I don't want to be petty, but you have your own thread to impose rules. You asked me to leave it, and I did. Isn't it fair to let me set the rules on this thread? You don't have to read it if you don't like the rules.

I don't claim to have a formal proof, and I'm not sure any notation is completely unambiguous. Plus it's hard to type formal notation into this message board.

I sketched a solution in what I think are clear terms. I might be wrong, what's clear to me might not be clear to someone else. That's especially true after I've worked on the problem for a while.

If someone asks a question, I'm happy to clarify. But I don't see why I should post an answer to a math puzzle that meets academic publication requirements.

Even if I were willing to do all the work to post in this form, and if anyone wanted to read it, it wouldn't reflect the way I actually solved the problem. I often make provisional assumptions and logical leaps in solving, if the solution works out, I go back and fill in the gaps later. If it doesn't work out, I don't bother.

I think this board, or at least this thread, is for people who want to solve things, meaning they'd rather see the way I actually did the problem than a formal proof developed once the answer was known. I think most people don't want long formal posts, they want enough information to recreate the solution on their own, and the ability to ask questions if they get stuck.

[PairTheBoard]

[ QUOTE ]
That is it so far. Would anyone like to add to this? If there is anyone (PairTheBoard?) who thinks they understand Aaron's ideas on a rigorous level, please feel free to contribute. Also feel free to scrap all this and start over if you think this notation will not adequately express Aaron's ideas. But please only use notation which is formal and completely unambiguous.

[/ QUOTE ]

Your notation is good jason. If Aaron wants to go to less cumbersome notation to express his ideas we should be able to translate anything he says into your notation for purposes of rigor.

I'm afraid I'm at a disadvantage in this discussion because I have no experience using continued fractions to express probability calculations. I had hoped that at the point where Aaron segues from probability statements to the continued fraction I'd be able to see what was going on with it. Unfortunately, it's at this point I find his explanation most vague. For example, in his OP he says, "This suggests the chance of getting a stick longer than 0.5 is equal to the continued fraction:". So I'm lost right there. Why should it "suggest" any such thing. Maybe for those with experience with continued fractions it's more clear. But I'm afraid not for me.

Maybe you could give me a short lesson with a simple example where it's easy to see how a continued fraction is a natural way to compute a probabilty. I think that would help me follow along here quite a bit.

Using your notation, I believe the key step at issue that Aaron is trying to make is based on the observation that, without any stopping conditions on drawing the U_i's, it's true that for any k, the following random intervals are equally likely for U_k:

[0,O(1,k-1)], [O(1,k-1),O(2,k-1)], ..., [O(k-1,k-1),1]

I'm pretty sure this is correct and could be proved without too much trouble. Call it Step One.

I think the next step toward Aarons goal is a leap which I suspect is not that big saying that, conditioned on the U_i's being stopped if 0.5 is ever exceeded, then for any k such that U_k is also less than 0.5, the following random intervals are equally likely for U_k:

[0,O(1,k-1)], [O(1,k-1),O(2,k-1)], ..., [O(k-1,k-1),0.5]

Given Step One, this looks to me like it's probably ok as well. All the U_i's are being conditioned on being less than 0.5 so they basically become uniform on [0,0.5] and this Step Two is just a restatement of Step One on the smaller interval.

However, Aaron now makes a bit bigger leap. U_1,...,U_(k-1) are still conditioned on being all less than 0.5. But this k is special. This U_k is not conditioned on falling in the fixed interval [0,0.5]. This U_k is conditioned on falling in the random interval [O(k-1,k-1),1]. Now, if U_k were being conditioned on falling in the fixed interval [0.5,1] I don't think there would be a problem making a +0.5 translation of the intervals in Step 2 and saying the following random intervals are equally likely for a [0.5,1] conditioned U_k:

[0.5,0,5+O(1,k-1)], [0.5+O(1,k-1),0.5+O(2,k-1)], ...
... [0.5+O(k-1,k-1,1]

Call this the +0.5 Step Two Translation

Given Step Two I see no problem with the +0.5 Step Two Translation. Now the final Step to the Conclusion Aaron says serves his purposes, I believe depends on the idea that you could take any one of the k random interval lengths in the +0.5 Step Two Translation, form a k+1st random interval of that length contained in [0,0.5] and condition U_k on being in the Union of [0.5,1] and the new k+1st random interval. Since the new random interval is of the same length as one of the old ones it seems reasonable to conclude that the newly conditioned U_k will be equally likely to fall into the k+1 random intervals. I think this is probably true and can be made rigorous without too much trouble. If true then Aaron's conclusion is the special case where the new k+1st interval is formed by taking the right most interval length in the +0.5 Step Two Translation and tacking it onto the left hand side of the [0.5,1] forming the new interval,
[(0.5+O(k-1,k-1))-0.5,1-0.5] = [O(k-1,k-1),0.5]

Conditioning U_k on being in the Union of [0.5,1] and the new k+1st random interval [O(k-1,k-1),0.5] is the same as conditioning U_k on just being greater than O(k-1,k-1). ie. U_k is a Break that may or may not end the game. Thus this Final Step in Aaron's assertion concludes that since there are k+1 equally likely random intervals for this U_k, such a Break Point has probabilty 1/(k+1) of ending the game with a loss - in the interval [0.5+O(k-1,k-1),1] - and probabilty 1/(k+1) of continuing the game - in the interval [O(k-1,k-1),0.5]. In other words, he can conclude that a Break Point is always equally likely to End the Game with a Loss or Continue the Game. But I think we really knew that already and I don't see what else he can get out of it because, as I pointed out to him above, we don't know when these k's are coming to produce the breaks so we don't know how big the k's are.

It looks like Aaron miscounted here:

[ QUOTE ]
If B_i exists, it can cause one of three things:

It can represent a stick longer than 0.5 being broken off from the left, that happens if B_i > B_i-1 + 0.5, which has probability 1/(i + 2)

[/ QUOTE ]

From what I did I think 1/(i+2) should be 1/(i+1). Translating Aaron's notation to ours, his B_i corresponds to my U_k where U_k is conditioned on being greater than
O(k-1,k-1) and his B_i-1 is my O(k-1,k-1) under the condition that U_k > O(k-1,k-1).

I now notice a wrinkle in Aaron's notation for B_i-1 and B_i. Notice, B_i-1 is one of the U_j's all conditioned on being less than 0.5. B_i is not so conditioned at this point in his discussion as he talks about the probability B_i > B_i-1 + 0.5. But if he were to go on and talk about a B_i+1, his current B_i would not be the same as the B_i he would talk about in relation to B_i+1. That would be a different B_i newly conditioned on being less than 0.5. A caveat for the terse notation.

PairTheBoard

[AaronBrown]

Maybe this will help. I did not write this program to solve the problem, I just wrote it to verify that each break is uniformly distributed among the relevant intervals. If the issue is whether my argument is rigorous or not, this of course means nothing. But if the issue is whether the statement is true, the simulation looks pretty convincing:

Public Sub stick()
Do
cnt = 0
Max = 0
Do
cnt = cnt + 1
u(cnt) = Rnd()
If u(cnt) > Max Then
Max = u(cnt)
If u(cnt) < 0.5 Then
b = 0
Else
b = 1
For i = 1 To cnt - 1
If u(i) > u(cnt) - 0.5 Then b = b + 1
Next i
End If
Cells(cnt, b + 1) = Cells(cnt, b + 1) + 1
End If
Loop Until u(cnt) > 0.5
Loop
End Sub

Here are the results. Line 1 means that 21,978 simulations ended when the first break was greater than 0.5 while 21,862 continued. Of those 21,862, 16,402 drew a second uniform number greater than the first one (as expected, about 25% of the time, the second number was smaller than the first). Those draws were distributed 5,554 less than 0.5, 5,418 between 0.5 and 0.5 + the first number and 5,430 greater than 0.5 + the first number. Going down the chart, you can see the simulation looks uniform the entire way.

21,862 21,978
5,554 5,418 5,430
1,832 1,847 1,865 1,786
716 727 649 688 688
277 289 269 255 284 279
125 120 101 109 130 110 116
47 47 54 50 55 54 63 44
23 14 34 23 30 19 22 28 8
12 11 6 10 7 5 8 12 8 10
4 4 9 4 4 3 8 3 5 4 6
2 3 3 2 2 4 2
1 1 1 2 1 1
2 1 1
1 1

1 1

[PairTheBoard]

Aaron, I made my last post in response to jason's while you were making your last two. I'm going to have to study the one you made about continued fractions.

However, on your notation, here's the thing I find most confusing and potential for trouble.

[ QUOTE ]
If B_i exists, it can cause one of three things:

It can represent a stick longer than 0.5 being broken off from the left, that happens if B_i > B_i-1 + 0.5, which has probability 1/(i + 2)



[/ QUOTE ]

You have a B_i and a B_i-1. But the i in B_i-1 is not the same i as the i in B_i. The i in B_i-1 is not such that the i-1 in B_i-1 is one less than the i in B_i. If you draw conclusions about the continued fraction as if it were you are bound to be in trouble.

Also, as I pointed out above, I think you miscounted the intervals and the 1/(i+2) should be 1/(i+1)

PairTheBoard

[djames]

Isn't it possible that your simulation results "looks uniform the entire way" not because it truly is uniform, but because it is simply nearly uniform?

Simulations are great to solve problems that can't be solved with rigor. In this case, since the discussion has gone on so long, I vote for rigor.

If the web form is too cumbersome to apply your favorite rigorous notation, perhaps creating & linking to a PDF wouldn't be too much trouble. I'm sure some other posters would even help you host the PDF (or host it for you) if you didn't know how.

[AaronBrown]

[ QUOTE ]
Maybe you could give me a short lesson with a simple example where it's easy to see how a continued fraction is a natural way to compute a probabilty. I think that would help me follow along here quite a bit.

[/ QUOTE ]
How about this. It's the classic textbook introduction. It's not a probability, but the problem could be easily translated to a probability one.

A restaurant bakes a rectangular cake, 45" x 16". For each customer, it cuts off the largest square slice it can. How many customers will the cake serve?

The continued fraction representation of 45/16 is 2 + 1/(1 + 1/(4 + 1/3)). All rational numbers have finite continued fraction representations.

The answer to the question is 2 16x16 squares, 1 13x13, 4 3x3 and 3 1x1, so 10 customers will be served. How is this related to the continued fraction? The number of customers served are the denominators in the fractions.

The geometric argument is given in the link I posted earlier, and may help you think about continued fractions.

[djames]

[ QUOTE ]
45/16 is 2 + 1/(1 + 1/(4 + 1/3))
...
The answer to the question is 2 16x16 squares, 1 13x13, 4 3x3 and 3 1x1, so 10 customers will be served.
...
The number of customers served are the denominators in the fractions.

[/ QUOTE ]

I don't think you really mean this last sentence.

[PancakeBoy]

2 + 1/(1 + 1/(4 + 1/3))
=
1/(1/2) + 1/(1 + 1/(4 + 1/3))

2,1,4,3 as i see it

[AaronBrown]

I think I do. 2 + 1 + 4 + 3; the initial "2" is thought of as a denominator in continued fractions, although that's sloppy. 2 for the first squares (16 x 16), 1 for the next (13 x 13), 4 for the next (3 x 3) and 3 for the last (1 x 1).

Perhaps I should say, numbers that are not 1 followed immediately by a "/".

[AaronBrown]

[ QUOTE ]
Isn't it possible that your simulation results "looks uniform the entire way" not because it truly is uniform, but because it is simply nearly uniform?

Simulations are great to solve problems that can't be solved with rigor. In this case, since the discussion has gone on so long, I vote for rigor.

If the web form is too cumbersome to apply your favorite rigorous notation, perhaps creating & linking to a PDF wouldn't be too much trouble. I'm sure some other posters would even help you host the PDF (or host it for you) if you didn't know how.

[/ QUOTE ]
Yes, it's possible. But I didn't try a lot of rules to see if I could find one that looked uniform, I used an argument that I personally find convincing that they should be uniform. Given that some people disagree, or at least are unconvinced by my argument, the simulation might help. Not just with the numeric results, but to show by the code that the statement is fully rigorous. Someone who doesn't like my words might find the code more precise.