Re: [math-fun] Number of ways to pick 4 points from an m X n grid?
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
One method I did not see listed in that linked MathWorld article is to choose the points from a standard normal distribution in the plane, i.e., with density given by
p(x,y) = (2?)^(-1) exp(-(x^2 + y^2)/2).
This is of course circularly symmetric, but it's not at all clear to me that four points picked from this distribution will have the same chance of their convex hull being a quadrilateral as four points picked from the uniform distribution on a disk.
It seems to be different. I've only started, but the first 3 billion give me 0.64905, as contrasted with 0.704480 for a circle and 0.694444 for a square. I'll let it run for a couple days.
With a quarter trillion sets, i.e. a trillion random points, I get 0.6490403. At the halfway point I had 0.6490408, so probably all but the last digit are correct.
To make sure I'm generating a standard normal distribution in the plane correctly, please tell me what the means of the r values (distances from the origin) should be. I'm measuring the arithmetic, quadratic ("RMS"), and cubic means.
The respective means were 1.253315, 1.414214, and 1.554989. I hope those are close to what they should be. (I didn't track the geometric or negative power means, since those would be dominated by how close the one point closest to the origin happened to be.) The only other test I made was to count how many of the trillion random points were in each quadrant: 249999663573, 250000431639, 249999574409, and 250000329923. Those sum to 999999999544. The remaining 456 points must have been on the borders of the quadrants, i.e. with an x or y value of 0. More specifically, given how theta was generated, x must have been positive and y must have been zero. And indeed 10^12 / 456 is close to the expected 2^31. As always, I checked for parallel lines and vertical lines. There were none. The only divisions by zero was when I took a log to get the r value. I prevented that by replacing any zero, before taking the log, with 10^-10. Again, I generated the pseudo-random numbers using Unix's random() function, which gives 31 bit integers. This time, after every billion sets (4 billion points) I switched to exclusive-oring the randoms with a different *pair* of distinct rows of the same order-32 Hadamard matrix as last time, again with its -1 entries replaced with 0s, and the leftmost bit (which was always 1) stripped off. This is to keep the random numbers from repeating. There are 496 (32 choose 2) such pairs of rows. Each such pair, when exclusive-ored together, has 16 1-bits and 15 0-bits. Each of the 122760 (496 choose 2) *pair* of pairs differs from every other pair of pairs in 12, 16, or 20 bit positions. If you want to take it further, or search for bugs, I can email you my C code.
Also on Sunday, I posted:
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. I got 1089 vertical lines and no parallel lines in that run.
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
participants (2)
-
Gareth McCaughan -
Keith F. Lynch