Re: [math-fun] math-fun Digest, Vol 127, Issue 19
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. --still wrong (duh): the left hand side actually gives (a lower bound on) the probability that NOT all 2*D regions are occupied, so really Pempty <= (1 - 1/(2*D))^N = (2*D-1)^N / (2*D)^N is the upper bound I was seeking. Brilliant. Anyhow, the point is, the upper bound is exponentially shrinking with N, and so is the lower bound, though sadly their growth factors do not match so we get a goodly gap.
participants (1)
-
Warren D Smith