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