[math-fun] Salamin's empty hemisphere problem
You can get upper and lower bounds on the answer. The problem is: N gas atoms in an 0-centers D-dimensional ball. (D>0.) What is chance there exists an empty hemi-ball? Lower bound: The left hemiball (x<0) is empty with chance 2^(-N). Better lower bound: Pempty >= 2^(1-N) by considering both the x<0 and x>0 hemiballs. Still better lower bound: Pempty >= N * 2^(1-N) by considering all hemiballs arising from semicircles in xy plane (assuming Salamin correct about the exact solution when D=2). And when D=4 this would give the lower bound (2*N)^2 * 2^(-N) by considering xy and zt planes. And when D=3 it would give (2*N+2)*2^(-N) by considering xy plane and the z<0 and z>0 hemiballs. Upper bound: If all 2^D quadrants are occupied, then there is no empty hemiball, because any hyperplane passing thru ball-center must contain at least one entire quadrant on one side. Better upper bound: divide D-space into D+1 equal regions by "coning off" the D+1 faces of a regular D-simplex centered at 0, to the origin. If every region is occupied, then there can be no empty hemiball. (Because any hyperplane passing thru ball-center must contain at least one entire region on one side.) The chance that all D+1 regions are occupied is lower bounded by D^N / (D+1)^N <= 1-Pempty. On-sphere lemma: (As somebody already noted) If all N points lie on the unit sphere, rather than in it, that makes no difference (Pempty unaffected). Special argument when D=2: The question is equivalent to this: is the longest side of the N-gon formed by N random points on the unit circle, on the "wrong" side of 0? (I.e. 0 lies on opposite side from all the other points.) There are N sides. Special argument when D=3: The question is equivalent to this: is the largest-circumradius-triangular-face of the polyhedron that is the convex hull of N random points on the unit sphere, on the "wrong" side of 0? (I.e. 0 lies on opposite side from all the other points.) There are 2*N-4 such faces (generically triangular, i.e. the probability a nontriangular face exists, equals 0). It seems to me that in both the D=2 and D=3 cases, the answer can be written in closed form as a definite integral using (a) the two special observations above, (b) the fact that it is impossible for more than 1 "special face" to exist, it automatically is unique one. So I think when D=2 you are going to get Pempty = N * int(0<u<1) (u/2)^(N-2) * du where u=theta/pi, if you see what I mean. I admit, this is off by a factor N-1 versus Salamin's claimed answer, so I'm probably missing something. Perhaps I was suppose to divide by int(0<u<2) (u/2)^(N-2) * du to normalize probability distribution or something. I think that yields Salamin's claimed answer. When D=3 you similarly (presumably also wrongly + missing something) would get Pempty = C * (2*N+4) * int(0<u<1) (u/2)^(N-3) * (1-(1-u)^2)^(3/2) * du using Archimedes in the direction orthogonal to the face, for some positive constant C I have not bothered to work out. If the same "normalize by dividing" fix worked then Pempty = (2*N+4) * int(0<u<1) (u/2)^(N-3) * (1-(1-u)^2)^(3/2) * du / int(0<u<2) (u/2)^(N-3) * (1-(1-u)^2)^(3/2) * du. So anyhow, I have not worked out the full details, but if this approach works you should be able using my hints, to get exact 2D and 3D answers; plus I have shown how to find upper & lower bounds in any dimension (which are undoubtably improvable).
Better upper bound: divide D-space into D+1 equal regions by "coning off" the D+1 faces of a regular D-simplex centered at 0, to the origin. If every region is occupied, then there can be no empty hemiball. (Because any hyperplane passing thru ball-center must contain at least one entire region on one side.)
The chance that all D+1 regions are occupied is lower bounded by D^N / (D+1)^N <= 1-Pempty.
--wrong. I should have said cone off the 2*D faces of an 0-centered hypercube to get 2*D regions. Need a centrosymmetric thing like hypercube; the regular D-simplex not being centrosymmetric, does not work. Then the corrected chance that all 2*D regions are occupied is lower bounded by (2*D-1)^N / (2*D)^N <= 1-Pempty.
sorry re my not-very-good coherence before re the upper bounds. Now let me try to work out the idea, which I explained badly and with two errors before, for exact results in 2 and 3 dimensions. Specifically in D=3 dimensions. [My errors: a wrong factor in integral, and the wrong claim at most one face of the convex hull of N points on sphere, could separate the polyhedron from 0.] There are N points random on unit sphere. They define a convex hull polyhedron with 2N-4 faces, each a triangle. WLOG let the face F with largest circumcircle be parallel to xy plane and facing outward in the negative-z direction. All N points lie in one hemisphere if and only if F lies above the xy plane, at altitude z>0, and all N-3 other points lie above it. Using Archimedes's uniform-z "cylinder-sphere" surface-area lemma with great simplifying effect, we see Prob(empty hemiball exists) = 2* integral(0<z<1) (2-z)^(N-3) * dz / integral(|z|<1) (2-z)^(N-3) * dz = 2*(9/4)*(2^N-4)/(3^N-9). The factor 2 is because of freedom to turn everything upside down. This formula is completely unchecked via Monte carlo. Unless I made another mistake, which is reasonably likely since this is tricky, it ought to be valid if N>=3. It gives the right answer 1 when N=3. When N=4 it gives 3/4. Now let us try to derive the formula in D=2 dimensions. The longest side S of the convex hull N-gon of the N points on unit circle WLOG is parallel to x-axis and at altitude y. All N points lie in one hemicircle if and only if S lies above the xy plane, at altitude z>0, and all N-2 other points lie above it. We see Prob(empty hemiball exists) = 2* integral(0<t<pi/2) (t)^(N-2) * dt / integral(0<t<pi) (y)^(N-2) * dt = 2^(2-N) if N>=2 which disagrees with Salamin's claim the formula is N*2^(1-N). Crap. Off by a factor of N/2. I can re-derive Salamin's formula. The probability that N points on circle, one of them red, rest blue, has property all blue points lie on on the left side of the diameter with one end at the red point, is 2^(1-N). The uncolored version involves a factor of N versus the colored version. QED Hence, my approach with these integrals is wrong. I presume the reason for the wrongness is that the "largest circumball face" is not distributed a priori in the same way as "a D-tuple of points on the sphere." You could try to fix my D=3 formula by saying there ought to be a fudge factor of 2N-4 for the "one red face" out of 2N-4 total faces, but that won't work because in the 3D case it is possible for TWO faces to separate from 0, unlike the D=2 case where only one side of the N-gon can separate. So it looks like this approach is dead for D=3, sorry. ---------------Other remarks: First of all, I don't see this claim by Miller the "N points on sphere, empty circle" problem is "not exactly the same" as the "N points in ball, empty hemisphere problem." It IS exactly the same. Proof: Mapping points in ball radially up to surface leaves emptiness of hemiballs unaltered. The mathpages guy Miller cited, assuming he did what he did right, using dodecahedral finite hemisphere set, should get a valid lower bound on Pempty(N). http://www.mathpages.com/home/kmath327/kmath327.htm Second, I have no idea what Veit E. was talking about with "N axes." Huh? If what he was trying to say was "a linear transformation of D-space preserves the fact points are on opposite sides of a hyperplane" then this is true but seems useless because the probability measure on hyperplanes and points in a ball is distorted by linear transformations... you'd have to use orthogonal transforms only (hence orthogonal axes only) in which case I fail to see what was being accomplished. Third, the inclusion exclusion approach can be made to work in any dimension using an infinite set of (all) hemispheres (actually cardinality-H set of random ones, then take limit H-->infinity if desired)... but it gets nasty. The main term is 2^(-N) is the chance a given hemiball is empty. The 2nd term involves the expected volume of the intersection of 2 random hemiballs, which still is pretty easy to calculate. The Kth term involves expected volume of intersection of K random hemiballs. When K>3 things are going to be ultra-nasty, and the approximation got by only using the first 2 terms, say, seems pretty useless.
participants (1)
-
Warren D Smith