Cutting a circle to find a point part two

[BMAD]

This is an extension of my previous question. I honestly am torn between two different solutions (one found in theory and the other in simulation). I am curious what solution we will find here.

Recall that we have a unit circle where three random points define three arcs.  What is the probability that the longest arc contains the point (1,0)?

[bubbled]

@bubbled, our numbers agree, including sum of the squares of means being 0.426...

I also find that the mean of the sum of the squares is 0.500.

I think it's interesting that the sum of the squares of the means doesn't match the mean of the sum of the squares. 

Maybe that shouldn't be interesting?

[plasmid]

Apologies if this seems a bit rambling, but it is an analytic solution unless I goofed somewhere.

I'll base this approach on the approach that Kamalukala described.

Consider three randomly placed points which divide the circle into three arcs. Without loss of generality put one of the points at 0 degrees, and put the other two at X degrees and Y degrees. Define arc A as the arc going clockwise from 0 degrees to whichever comes first of X or Y. It can be shown that the probability of arc A being any given size S will decrease linearly from a maximum at S=0 to a probability of zero at S=1.

Aside: argument supporting that statement

Since points X and Y are randomly distributed, the odds that X is any distance S away from 0 is uniform and does not depend on S. The odds that the nearest of X and Y is distance S away from 0 (meaning arc A is size S) does depend on the value of S: the odds that point X is distance S away from 0 is uniform, but the odds that point Y is farther away from S than point X is given by the ratio of the area going from 0 to X clockwise vs going from X back to 0 clockwise around the rest of the circle. For arc A to be size S, point Y must fall outside the interval from 0 to X, so the probability of that happening drops off linearly as S increases from a probability of 1 when S=0 to a probability of 0 when S=1.

Without using calculus, you can tell that since the integral of the probability density function of arc A being size S over the range S=0 to S=1 must be 1, the value of the probability density function at S=0 must be 2. So the probability density function is just given by p(arc A = S) = 2 - 2S.

For any given arc A size of S, we know that arc B + arc C = 1-S. Since the size of arc B and arc C are determined by a randomly placed point in that interval of 1-S, the larger segment will be any size from 1-S to (1-S)/2 with uniform probability, and its average size would be 3(1-S)/4.

But what we really care about is the size of the largest arc out of A, B, and C. If arc A has size S, and the largest of arcs B and C has size (1-S)/2 to (1-S) with uniform probability, then what's the size of the largest arc for any given value of S? Clearly if S is less than 1/3 of the circle then arc B or C must be the largest, and if S is greater than 1/2 of the circle then arc A must be the largest. What we need to do is take the integral of (probability that arc A is size S) times (average size of the longest arc given that arc A is size S), and that function has different properties over the ranges S=0 to S=1/3, S=1/3 to S=1/2, and S=1/2 to S=1. (If you haven't worked with probability density functions before, this is conceptually the same as taking a weighted average to compute the expected payout of a gambling game, like taking the sum of [odds that you'll roll a given number on a weighted die] times [amount of money you win or lose if you roll that number]. For this problem, we do something analogous by taking the integral of [size of the longest arc given that arc A is size S] times [probability that arc A is size S].)

First consider the case where S is greater than 1/2 of the circle. You can just take the integral of the probability density function times S (because in this case the size of the largest arc is S since arc A is largest when S > 1/2).

Next consider the case where arc A is less than 1/3 of the circle, so S=0 to 1/3. The average size of the longest segment for any given value of S is 3(1-S)/4 in that range, so take the following integral

Finally, consider the case where S is between 1/3 and 1/2. The longest arc could be either arc A or one of the other two arcs. The odds that arc A is the longest is p(S > random number from (1-S) to (1-S)/2), which can be visualized as a line segment from (1-S)/2 to (1-S) where you randomly pick a point and see if it's smaller than S, and is given by [S - (1-S)/2] / [(1-S) - (1-S)/2] = [(3S-1)/2] / [(1-S)/2] = (3S-1) / (1-S).

So now for the more complicated equations. First consider the cases where S is in the range 1/3 to 1/2 and arc A is the longest. The probability density function for that is given by (the probability density function that arc A is size S) times (the probability that arc A is longest given that it's size S). Substituting that where we had the probability density function in the first equation, we have

Lastly, consider the cases where S is in the range from 1/3 to 1/2 and arc A is not the longest. The probability density function is (the probability density function that arc A is size S) times (the probability that arc A is not the longest given that it's size S). The probability that arc A is not longest = 1 - (the probability that arc A is longest) = 1 - [(3S-1) / (1-S)] = (1-S-3S+1) / (1-S) = (2-4S) / (1-S). But there's one more thing to consider: if we're given that arc B or arc C is largest, then the range is no longer (1-S)/2 to (1-S). The arc must be larger than S, so instead the range would be from S to (1-S), and the average value would be [S+(1-S)] / 2 = 1/2. Which is fortunate since it makes the math a lot easier.

And the grand total is 1/6 + 19/54 + 1/27 + 1/18 = (9+19+2+3)/54 = 33/54

In decimal form, that's 0.61111...

I wonder if there's a more elegant approach with less brute force.

Edited December 5, 2015 by plasmid
fixed a boo-boo in the last formula

[bonanova]

Quick simulation (10,000 cases)

The probabilities (lengths of the three arcs for unit-circumference circle) sorted longest to shortest:
0.6102    0.278    0.1116  which sum to unity, as they should.
Strange numbers. Approximately in the ratio 11 : 5 : 2.

The squares of these numbers are the weighted sums of the three sorted lengths:
0.3944    0.0877    0.0186 which sum to 0.501 => pi for unit radius

[bonanova]

I did more simulations.
The expected middle length remains slightly larger than the geometric mean of the other two.
If I impose a 2.3 ratio I get

0.6150, 0.26775, 0.11641

Slightly larger, slightly smaller, and about the same, respectively, compared to simulated values.
For what it's worth, the subtended angles are

221.7^o,  96.389^o,  41.908^o

[BMAD]

Interestingly I believe i found the theoretical probability to be 50% but my simulations have it around 60-62%.

[CaptainEd]

I did a few simulations, with n = number of points (2, 3, 4). Generated  n uniform points in (0,1), sorted, calculated section lengths (including round-the-corner length from max to min), and picked max length. Averaged over 2000 tries. I expect that our varying numbers derive ultimately from using subtly different experiments.

.754 (n=2), .6166 (n=3), .5466 (n=4)

[bonanova]

Interestingly I believe i found the theoretical probability to be 50% but my simulations have it around 60-62%.

What do you get for prob (middle arc) and prob (shortest arc)?

[bonanova]

I did a few simulations, with n = number of points (2, 3, 4). Generated  n uniform points in (0,1), sorted, calculated section lengths (including round-the-corner length from max to min), and picked max length. Averaged over 2000 tries. I expect that our varying numbers derive ultimately from using subtly different experiments.

.754 (n=2), .6166 (n=3), .5466 (n=4)

CaptainEd, are these numbers the expected (average) lengths of the longest arc (interval) for each value of n?

Concerned about using the round-the-corner length, since the (sorted) n uniform points will tend to cluster around i/(n+1), i=1, ... n which will make r-t-c lengths twice as long as the other intervals. the i=0th point is eliminated when you join the 0 and 1 endpoints. For n uniform points on [0,1) the intervals are properly (after sorting the points lowest to highest) n₁, n₂-n₁, n₃-n₂, n₄-n₃ ... 1-n_max. Note the first interval, n₁, is formally n₁ - 0.

[plasmid]

Just wondering: how did you find the theoretical probability to be 50%? I'll spoilerize this since it references the previous incarnation of this problem.

Previously the question was "What's the expected length of the arc that contains point (1,0)?" and Bonanova through simulation and Mark Weitzman analytically showed that it's pi. Since the expected length of an arc containing a given point is pi, and sometimes the point will fall on an arc that's not the longest, that means the longest arc will on average be longer than pi. Since the longest arc will typically be longer than pi, the odds that a point will fall on the longest arc should be greater than 50%.

Edited December 2, 2015 by plasmid

[CaptainEd]

@Bonanova, yes, it's true, I'm working on the wrong problem still.

As you pointed out from the beginning, we have to know what is meant by "randomly chosen points". To me, in the circumference of the circle, there is no boundary, so I expect n points to space themselves out evenly from each other, NOT evenly from an artificial boundary. I expect three points' expected relationships to be about 2pi/3 apart.
This is not what happens, as you pointed out, when I pick locations from [0,1), regardless of whether I normalize by 2pi. As you say, the round-the-corner length winds up roughly double the other intervals.
The numbers I gave were fractions of the circumference, thus they are scaled like probabilities or expected values. In other words, they were in the range (0,1), and can be scaled up by 2pi to provide arc lengths.
How would we pose a similar-looking puzzle so that arc lengths would not be affected by how close they are to a boundary? I know your solution spread out the impact of the bias by spinning the disk, but the disk still has an anomalous boundary...

[CaptainEd]

Too bad I can't think things out before I post.

 I now see that Bonanovas construction yields exactly the result I wanted-- three points roughly equally distributed around the circumference. 

[bubbled]

I ran a simulation of 100,000,000 trials using bonanova's method (I think) on a unit circumference. I pick two random numbers, P1 and P2,  between 0 and 1.

If P1 < P2, then my three lengths are L1 = P1, L2 = P2 - P1, and L3 = 1 - P2.

If P2 < P1, L1 = P2, L2 = P1 - P2, and L3 = 1 - P1.

I sort the three lengths and put them into a matrix where the first column consists of all the shortest lengths, the second column is the middle length and the third column is the longest length. I then calculate the mean of the various columns.

I get this result:

mean of longest arcs = 0.611101750112

mean of middle arcs = 0.277769774084

mean of shortest arcs = 0.111128475804

This matches bonanova's results pretty closely and those lengths add up to 1, as expected.

It would seem to me that the probability that a particular point falls in the longest arc should be 0.6111...

And the middle arc 0.277... and shortest arc 0111...

Which means that the average length of the arc that a random point (or fixed point) falls in should be the sum of the squares of the mean arc lengths. However, the sum of the squares is only 0.462950934519. I would expect it to be .5, given the analysis from the previous problem.

I'm a bit confused. Thoughts? 

[bubbled]

I ran a simulation of 100,000,000 trials using bonanova's method (I think) on a unit circumference. I pick two random numbers, P1 and P2,  between 0 and 1.

If P1 < P2, then my three lengths are L1 = P1, L2 = P2 - P1, and L3 = 1 - P2.

If P2 < P1, L1 = P2, L2 = P1 - P2, and L3 = 1 - P1.

I sort the three lengths and put them into a matrix where the first column consists of all the shortest lengths, the second column is the middle length and the third column is the longest length. I then calculate the mean of the various columns.

I get this result:

mean of longest arcs = 0.611101750112

mean of middle arcs = 0.277769774084

mean of shortest arcs = 0.111128475804

This matches bonanova's results pretty closely and those lengths add up to 1, as expected.

It would seem to me that the probability that a particular point falls in the longest arc should be 0.6111...

And the middle arc 0.277... and shortest arc 0111...

Which means that the average length of the arc that a random point (or fixed point) falls in should be the sum of the squares of the mean arc lengths. However, the sum of the squares is only 0.462950934519. I would expect it to be .5, given the analysis from the previous problem.

I'm a bit confused. Thoughts? 

OK, so I continued by using bonanova's idea of picking the arcs and then spinning the wheel. I used the same method as above (picking two random points) and creating three arcs. I then pick a random new point and find the length of the arc it falls in. I store those lengths in a separate array and find the mean length.

With 100,000,000 million trials, I get 0.500034371498. This it what we'd expect. But I'm confused as to why the sum of the squares doesn't add up to .5 as well.

It must be something to do with the distribution of the actual lengths of the arcs. Maybe because when the longest arc is bigger than the mean of the other longest arcs, the random point will fall in it more often? More simulations necessary to answer that question.

 

[bonanova]

@bubbled, our numbers agree, including sum of the squares of means being 0.426...

I also find that the mean of the sum of the squares is 0.500.

[bonanova]

@bubbled, our numbers agree, including sum of the squares of means being 0.426...

I also find that the mean of the sum of the squares is 0.500.

I think it's interesting that the sum of the squares of the means doesn't match the mean of the sum of the squares. 

Maybe that shouldn't be interesting?

I think it's instructive. Taking the mean is usually the last step.
That guides us first to determine the most relevant quantities.

Edit:
And now I have to somehow correct my first post.
The numbers I gave that sum to ~.5 are misrepresented as the squares of the probabilities.

Edited December 3, 2015 by bonanova
Error in my first post.

[BMAD]

Just wondering: how did you find the theoretical probability to be 50%? I'll spoilerize this since it references the previous incarnation of this problem.

Hidden Content

After reading your post and reconsidering bonanova's earlier post I think my theoretical maybe shortsighted but what i originally calculated was rather simple:

Given the typical arc length found by bonanova to be pi.  I thought the probability of the longest arc length containing the point would simply be: 

-(the expected arc length)/(circumference)

-which in this case would be pi / (2pi)

-which reduces to 1/2.

However my simulations yield a much larger result.  So in retrospect, I am guessing that bonanova actually found a lower bound of pi and therefore the probability has a lower bound of 1/2?

 

Edited December 3, 2015 by BMAD

[bubbled]

I just ran one more 100M simulation and captured a lot more info. 

Probability that a new random point will fall in the largest arc: 0.61104318

Mean of the arc length that captures the random point: 0.499978733972

Mean of the sums of the squared arc lengths: 0.500018084204

Median length of the longest arc: 0.591768881555

Histogram of the shortest arc lengths:

Histogram of the middle arc lengths:

Histogram of the longest arc lengths:

I might be the only one, but I find these graphs to be interesting. Anytime you have two or more random variables and are trying to say things about their relationships to each other, things get pretty non-intuitive. 

 

 

 

[Kamalukala]

Hello, fellow puzzle solvers!

I see that many of you have found numerical solutions to the question. Using some hand-wavy mathmatics I came up with the following theoretical approach:
The question is "Recall that we have a unit circle where three random points define three arcs.  What is the probability that the longest arc contains the point (1,0)?"
Assigning three random points on a circle to form three arcs is equivalent to defining two random points on a straight line to form three linear segments. (After placing the first dot on the circle it more or less becomes a 1D line.)
The probability can be found by knowing the avarage length of the longest segment:

p = L1 / L,

where L1 is the average length of the longest segment and L is the total length of the circle.

-------------------------------------------

If we randomly place a single dot on the line it will divide the line into two segments; a long segment and a short one. Due to symmetry the segment will (on average) be divided into a (1/4)L part and a (3/4)L part. This can be explained by assuming, without loss of generality (due to the fact that the halfs are equivalent), that the dot will be placed in the left half of the line. On average it would be placed at exactly L/4. This seems to agree with bananova's numerically obtained value for n=2, which is an L1 value of 0.754.
Now comes a hand-wavy part: If an additional dot is placed on the line it has (on average) a probability of 1/4 to be placed in the small segment, and, (on average) a probablility of 3/4 to be placed in the large segment. This would (on average) devide that segment into pieces of length:

• (1/4*1/4)L and (1/4*3/4)L in case of the short segment (note that in this case the overall longest segment is (3/4)L )
• (3/4*1/4)L and (3/4*3/4)L in case of the long segment

The average value of L1 is given by:

L1 = 1/4*(3/4)*L + 3/4*(3/4)^2*L = 0.6094*L

--> p = L1/L = 0.6094 = 60.94%

This seems to be in agreement with previously posted numerical values.

----------------------------------------

Although I don't posses the notational skills to make this into a hard proof, I think that the general approach may very well be correct. I'd like to hear how you solved it analytically.

[bonanova]

Hello, fellow puzzle solvers!

I see that many of you have found numerical solutions to the question. Using some hand-wavy mathmatics I came up with the following theoretical approach:
The question is "Recall that we have a unit circle where three random points define three arcs.  What is the probability that the longest arc contains the point (1,0)?"
Assigning three random points on a circle to form three arcs is equivalent to defining two random points on a straight line to form three linear segments. (After placing the first dot on the circle it more or less becomes a 1D line.)
The probability can be found by knowing the avarage length of the longest segment:

p = L1 / L,

where L1 is the average length of the longest segment and L is the total length of the circle.

-------------------------------------------

If we randomly place a single dot on the line it will divide the line into two segments; a long segment and a short one. Due to symmetry the segment will (on average) be divided into a (1/4)L part and a (3/4)L part. This can be explained by assuming, without loss of generality (due to the fact that the halfs are equivalent), that the dot will be placed in the left half of the line. On average it would be placed at exactly L/4. This seems to agree with bananova's numerically obtained value for n=2, which is an L1 value of 0.754.
Now comes a hand-wavy part: If an additional dot is placed on the line it has (on average) a probability of 1/4 to be placed in the small segment, and, (on average) a probablility of 3/4 to be placed in the large segment. This would (on average) devide that segment into pieces of length:

• (1/4*1/4)L and (1/4*3/4)L in case of the short segment (note that in this case the overall longest segment is (3/4)L )
• (3/4*1/4)L and (3/4*3/4)L in case of the long segment

The average value of L1 is given by:

L1 = 1/4*(3/4)*L + 3/4*(3/4)^2*L = 0.6094*L

--> p = L1/L = 0.6094 = 60.94%

This seems to be in agreement with previously posted numerical values.

----------------------------------------

Although I don't posses the notational skills to make this into a hard proof, I think that the general approach may very well be correct. I'd like to hear how you solved it analytically.

At first blush I'm amazed that you came up with the number .6094, Hi, by the way, and welcome to the Den, because it's not a familiar number, and it agrees closely with simulations. Also given an assumption that a single point, repeatedly placed, will cluster at 1/4 or 3/4 (the center points of either half of the line). Simulations show that it will cluster at 1/2. But then 1/4 and 3/4 would average to 1/2 so maybe that doesn't matter.

Very interesting result.