Re: [math-fun] Probability that all molecules of a gas are in one half of the container
So Veit E.'s idea (as he now describes) involves what has been called "spherical polars" or "duality." I'll now re-do his solution so I can understand it (you too, maybe). That is, each new point on the sphere, defines an excluded hemiball (centered at it) in which the empty hemiball's center (if any) cannot lie. I.e. the sphere is cut by a new centered hyperplane every time you add new point. After N points added, we've cut the sphere using N "polar" hyperplanes into 2^N regions (some of these "regions" may not actually exist, i.e. are empty sets). Only the ++++...+++ region (if any) is eligible for occupancy by an empty-hemiball center (if any). The probability an empty hemiball exists, is the probability that this region exists. Now then Veit continues by arguing that by considering replacing points by their antipodes, all regions are "equivalent" i.e. under some assignment of {points, antipodes} any region you like becomes the +++...++++ region. Hence, if there are Reg(N,D) genuine regions, Veit argues the probability a +++...++++ region exists, is just Reg(N,D)/2^N. And Reg(N,D) is a combinatorial quantity that can be found using recurrences. In particular Reg(N,2) = 2*N obviously, explaining Salamin's formula. And Reg(N,3) = 2*(N-1) + Reg(N-1, 3) more generally Reg(N,D) = Reg(N-1, D-1) + Reg(N-1, D) by considering adding 1 new cut-hyperplane and considering the D-1 dimensional situation within that hyperplane. Hence Reg(N,D) always is a degree=D-1 polynomial in N which you can determine by fitting to the data for N=0,1,2,...,D-1. So the problem is now solved in every dimension. Very nice. Elegant.
This is the recurrence for Pascal's triangle. Quoting Warren D Smith <warren.wds@gmail.com>:
And Reg(N,3) = 2*(N-1) + Reg(N-1, 3)
more generally Reg(N,D) = Reg(N-1, D-1) + Reg(N-1, D) by considering adding 1 new cut-hyperplane and considering the D-1 dimensional situation within that hyperplane.
Wrt part 2 of the puzzle, to provide a test, the following might work: If Vi are the locations of the atoms, compute W = sum Vi. Then see if all the dot products W.Vi are positive. Rich
Not quite. Put a bunch of atoms at Lat 89 deg N, Long 0 deg. Put one atom atLat 89 deg S, Long 0 deg. These all fit within the hemisphere bisected by the Greenwich Meridian. But W is near 89N so its dot product with that last atom is negative. -- Gene
________________________________ From: "rcs@xmission.com" <rcs@xmission.com> To: math-fun@mailman.xmission.com Cc: rcs@xmission.com Sent: Wednesday, September 18, 2013 5:04 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Wrt part 2 of the puzzle, to provide a test, the following might work: If Vi are the locations of the atoms, compute W = sum Vi. Then see if all the dot products W.Vi are positive.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Then make it a linear programming problem: Assign non-negative weights Wi to vectors Vi, with sum Wi = 1. Put W = sum WiVi. Then require the dot products W.Vi >=0. The dot products are linear in the weights, so it's a conventional linear programming problem. If it's feasible, you have a solution W. We need to prove that if there's a solution, there's one in the convex hull of the Vi. This seems plausible, but I don't see an immediate proof. Rich ------ Quoting Eugene Salamin <gene_salamin@yahoo.com>:
Not quite. Put a bunch of atoms at Lat 89 deg N, Long 0 deg. Put one atom atLat 89 deg S, Long 0 deg. These all fit within the hemisphere bisected by the Greenwich Meridian. But W is near 89N so its dot product with that last atom is negative.
-- Gene
________________________________ From: "rcs@xmission.com" <rcs@xmission.com> To: math-fun@mailman.xmission.com Cc: rcs@xmission.com Sent: Wednesday, September 18, 2013 5:04 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Wrt part 2 of the puzzle, to provide a test, the following might work: If Vi are the locations of the atoms, compute W = sum Vi. Then see if all the dot products W.Vi are positive.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Eugene Salamin -
rcs@xmission.com -
Warren D Smith