On 03/07/2020 14:47, Keith F. Lynch wrote:
For the circular five-point case I calculated 0.3561808623 and posted 0.356181. That page doesn't give the solution. Assuming the solution is in the same form as the circular four-point case, 1 - (i / (j pi^2)), where i and j are integers, (35 and 12 in the 4-point case), if I try 1 - (305 / (48 pi^2)), I get 0.356188312... which differs from my answer by 7 in the sixth digit. Does anyone know if that's the correct formula?
That was with about 9 billion sets. With 59 billion (and counting) I get 0.35618796, so it's looking like it really is 1 - (305 / (48 pi^2)), as it differs from that formula by only 3 in the *7th* digit. That's a hell of a way to find a formula.
With 216 billion sets, I get 0.356188363, even closer to that formula. That's the probability of a convex pentagon given five random points in a circle. The probability of a quadrilateral with one point in it is 0.548822606, and the probability of a triangle with two points in it is 0.094989031.
Suppose we pick five points in some region R (say, a circle). They form a convex pentagon _unless_ one of them lies within the triangle formed by three others. The expected number of times this happens is (5 choose 2) times the probability that a given point lies within a given triangle, which is 10 times the expected (area of triangle / area of R) so, calling that ratio f, the expected number of counterexamples to convexity is 10f. How much does this expected number overcount the probability that the number isn't zero? In the case where we have four points, the answer is "not at all" because if you have four points one of which lies in the triangle formed by the other three, it's easy to see that there aren't any other failures of convexity. This is how the solution to Sylvester's problem goes. With five points it's only a little more difficult. We have the following nonconvex configurations, ignoring probability-0 ones: - Four points forming a convex quadrilateral and one point somewhere inside. In this case there is exactly one point-in-triangle convexity failure and no overcounting. - Three points on the convex hull and two points inside. There's basically only one configuration of this type and for this we overcount by 1 because it yields 2 point-in-triangle incidents instead of 1 for whichever "inside" point we select. So we need to subtract off the expected number of configurations of that second type (= the probability of having one), which is (5 choose 2) times the probability that a _particular_ pair of points lie inside the triangle formed by the other two. You might naively think this is f^2 but it's not; it's expectation of (area(T)/area(R))^2 rather than (expectation of area(T)/area(R))^2. Call it f2. So it seems like the probability of convexity is 1 - 10f + 10f2. (Compared with 1 - 4f for the four-point case.) We have f = 35/(48pi^2), which is why the four-point probability is 35/(12 pi^2), but we haven't yet found f2. Now, you can find one computation of f at https://math.stackexchange.com/questions/1243160/ and it's readily adapted to compute f2 as well. If I've done it right, the expected _squared_ area of a triangle whose points are chosen randomly from the unit circle is exactly 3/32, which means that f2 is 3/(32pi^2). So, finally, we need 1 - 10.35/48pi^2 + 10.3/32pi^2 which equals 1 - 1/48pi^2 (350 - 45) = 1 - 305/48pi^2 matching the value you found. (Phew.) One could in principle do the same sort of calculations for any number of points, but they get messier. Also, the fact that we ended up with two (rational/pi^2) terms is kinda-coincidental; with six points we would need the expected _cube_ of (area(T)/area(R)), and if my calculations -- more honestly, my invocations of Mathematica's symbolic integration facilities -- are right then the expectation of area(T)^3 is 1001/(3200pi) and so we will start to get terms with pi^4 in the denominator as well as ones with pi^2 in the denominator. (Which will also make it trickier to guess the right answer purely by numerical experiment...) -- g