[math-fun] Probability that all molecules of a gas are in one half of the container
A spherical vessel contains n molecules of gas. What is the probability that all the molecules can be found in one hemisphere? For a given hemisphere, it is 1/2^n. For 6 hemispheres arranged like the faces of a cube, inclusion-exclusion gives 6/2^n - 12/4^n + 8/8^n. But what is the probability if any hemisphere is allowed? I'm stuck on this problem. In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n. A related question is: Given n vectors x[1], ... , x[n], how do we test if they all lie in some half-space, i.e. does there exist a vector u such that u.x[i] > 0 for all i? I'm stuck on this as well. -- Gene
For each possible point on the sphere, the probability that all the particles are in the hemisphere centered on that point is 2^{-n}. Pull the constant out and integrate over the sphere to get 2^{-n} * 1. Or am I missing something? On Tue, Sep 17, 2013 at 1:02 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
A spherical vessel contains n molecules of gas. What is the probability that all the molecules can be found in one hemisphere? For a given hemisphere, it is 1/2^n. For 6 hemispheres arranged like the faces of a cube, inclusion-exclusion gives 6/2^n - 12/4^n + 8/8^n. But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
A related question is: Given n vectors x[1], ... , x[n], how do we test if they all lie in some half-space, i.e. does there exist a vector u such that u.x[i] > 0 for all i? I'm stuck on this as well.
-- Gene _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On 17/09/2013 20:16, Mike Stay wrote:
For each possible point on the sphere, the probability that all the particles are in the hemisphere centered on that point is 2^{-n}. Pull the constant out and integrate over the sphere to get 2^{-n} * 1. Or am I missing something?
I think so. The cases overlap, so the probabilities don't just add. I have the feeling I've seen this problem, or one awfully similar to it, before. If so, I don't remember the answer. One trivial remark: The answer is the same whether you choose particles uniformly *on the surface of the sphere* or *in the ball bounded by the sphere*. -- g
And more generally, the particles can have any spherically symmetric distribution. If preparing to integrate over space, a useful distribution is the Gaussian, exp(-r^2) = exp(-x^2) exp(-y^2) exp(-z^2). -- Gene
________________________________ From: Gareth McCaughan <gareth.mccaughan@pobox.com> To: math-fun@mailman.xmission.com Sent: Tuesday, September 17, 2013 12:28 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
On 17/09/2013 20:16, Mike Stay wrote:
For each possible point on the sphere, the probability that all the particles are in the hemisphere centered on that point is 2^{-n}. Pull the constant out and integrate over the sphere to get 2^{-n} * 1. Or am I missing something?
I think so. The cases overlap, so the probabilities don't just add.
I have the feeling I've seen this problem, or one awfully similar to it, before. If so, I don't remember the answer.
One trivial remark: The answer is the same whether you choose particles uniformly *on the surface of the sphere* or *in the ball bounded by the sphere*.
-- g
Yes, what you are missing is the observation that the first 3 molecules are free. There is always some hemisphere within which they can be found. -- Gene
________________________________ From: Mike Stay <metaweta@gmail.com> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 12:16 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
For each possible point on the sphere, the probability that all the particles are in the hemisphere centered on that point is 2^{-n}. Pull the constant out and integrate over the sphere to get 2^{-n} * 1. Or am I missing something?
On Tue, Sep 17, 2013 at 1:02 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
A spherical vessel contains n molecules of gas. What is the probability that all the molecules can be found in one hemisphere? For a given hemisphere, it is 1/2^n. For 6 hemispheres arranged like the faces of a cube, inclusion-exclusion gives 6/2^n - 12/4^n + 8/8^n. But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
A related question is: Given n vectors x[1], ... , x[n], how do we test if they all lie in some half-space, i.e. does there exist a vector u such that u.x[i] > 0 for all i? I'm stuck on this as well.
-- Gene
Here is a cute question: I place points uniformly in the unit disk (or equivalently on the unit circle). I stop as soon as these points are not all contained in one sector of width pi, or equivalently, as soon as their convex hull contains the origin. What is the average number of points when this first occurs? Hint: the answer is an integer :-) Cris
I get 4. -- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Cc: Eugene Salamin <gene_salamin@yahoo.com> Sent: Tuesday, September 17, 2013 1:39 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Here is a cute question: I place points uniformly in the unit disk (or equivalently on the unit circle). I stop as soon as these points are not all contained in one sector of width pi, or equivalently, as soon as their convex hull contains the origin. What is the average number of points when this first occurs?
Hint: the answer is an integer :-)
Cris
Do you mean 4 is the average number just before I get the origin in the convex hull, or the number when it first is? (I suppose this might be giving away the answer ;-) On Sep 17, 2013, at 3:19 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
I get 4.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Cc: Eugene Salamin <gene_salamin@yahoo.com> Sent: Tuesday, September 17, 2013 1:39 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Here is a cute question: I place points uniformly in the unit disk (or equivalently on the unit circle). I stop as soon as these points are not all contained in one sector of width pi, or equivalently, as soon as their convex hull contains the origin. What is the average number of points when this first occurs?
Hint: the answer is an integer :-)
Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I mean that you keep adding particles as long as they all lie in some semicircle. When the next particle cannot be fit with the others into a semicircle, stop and do not add that particle. The average number of particles I get is 4. -- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 4:49 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Do you mean 4 is the average number just before I get the origin in the convex hull, or the number when it first is? (I suppose this might be giving away the answer ;-)
On Sep 17, 2013, at 3:19 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
I get 4.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Cc: Eugene Salamin <gene_salamin@yahoo.com> Sent: Tuesday, September 17, 2013 1:39 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Here is a cute question: I place points uniformly in the unit disk (or equivalently on the unit circle). I stop as soon as these points are not all contained in one sector of width pi, or equivalently, as soon as their convex hull contains the origin. What is the average number of points when this first occurs?
Hint: the answer is an integer :-)
Cris
_______________________________________________ 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
in that case I agree :-) On Sep 17, 2013, at 5:58 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
I mean that you keep adding particles as long as they all lie in some semicircle. When the next particle cannot be fit with the others into a semicircle, stop and do not add that particle. The average number of particles I get is 4.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 4:49 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Do you mean 4 is the average number just before I get the origin in the convex hull, or the number when it first is? (I suppose this might be giving away the answer ;-)
On Sep 17, 2013, at 3:19 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
I get 4.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Cc: Eugene Salamin <gene_salamin@yahoo.com> Sent: Tuesday, September 17, 2013 1:39 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Here is a cute question: I place points uniformly in the unit disk (or equivalently on the unit circle). I stop as soon as these points are not all contained in one sector of width pi, or equivalently, as soon as their convex hull contains the origin. What is the average number of points when this first occurs?
Hint: the answer is an integer :-)
Cris
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
On 9/17/2013 12:02 PM, Eugene Salamin wrote:
A spherical vessel contains n molecules of gas. What is the probability that all the molecules can be found in one hemisphere? For a given hemisphere, it is 1/2^n. For 6 hemispheres arranged like the faces of a cube, inclusion-exclusion gives 6/2^n - 12/4^n + 8/8^n. But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
I don't understand the arrangement. Are the hemispheres stuck onto the faces of a cube?
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
That doesn't look right. n=2 -> P=1
A related question is: Given n vectors x[1], ... , x[n], how do we test if they all lie in some half-space, i.e. does there exist a vector u such that u.x[i] > 0 for all i? I'm stuck on this as well.
If the boundary of the half-space is a plane, can't you just take the inner product with a vector normal to that plane? Brent
-- Gene _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- No virus found in this message. Checked by AVG - www.avg.com Version: 2013.0.3408 / Virus Database: 3222/6674 - Release Date: 09/17/13
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
That doesn't look right. n=2 -> P=1
Looks right to me. Given a point inside a circle other than the center, all points inside the circle are in some open semicircle with the original point except the center and radius opposite the original point. (All points share some closed semicircle with the original point.) Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Sep 17, 2013 at 3:19 PM, meekerdb <meekerdb@verizon.net> wrote:
On 9/17/2013 12:02 PM, Eugene Salamin wrote:
A spherical vessel contains n molecules of gas. What is the probability that all the molecules can be found in one hemisphere? For a given hemisphere, it is 1/2^n. For 6 hemispheres arranged like the faces of a cube, inclusion-exclusion gives 6/2^n - 12/4^n + 8/8^n. But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
I don't understand the arrangement. Are the hemispheres stuck onto the faces of a cube?
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
That doesn't look right. n=2 -> P=1
A related question is: Given n vectors x[1], ... , x[n], how do we test if they all lie in some half-space, i.e. does there exist a vector u such that u.x[i] > 0 for all i? I'm stuck on this as well.
If the boundary of the half-space is a plane, can't you just take the inner product with a vector normal to that plane?
Brent
-- Gene ______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
----- No virus found in this message. Checked by AVG - www.avg.com Version: 2013.0.3408 / Virus Database: 3222/6674 - Release Date: 09/17/13
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
OK. Thanks, I misinterpreted it. Brent On 9/17/2013 12:24 PM, Charles Greathouse wrote:
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
That doesn't look right. n=2 -> P=1 Looks right to me. Given a point inside a circle other than the center, all points inside the circle are in some open semicircle with the original point except the center and radius opposite the original point. (All points share some closed semicircle with the original point.)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, Sep 17, 2013 at 3:19 PM, meekerdb <meekerdb@verizon.net> wrote:
On 9/17/2013 12:02 PM, Eugene Salamin wrote:
A spherical vessel contains n molecules of gas. What is the probability that all the molecules can be found in one hemisphere? For a given hemisphere, it is 1/2^n. For 6 hemispheres arranged like the faces of a cube, inclusion-exclusion gives 6/2^n - 12/4^n + 8/8^n. But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
I don't understand the arrangement. Are the hemispheres stuck onto the faces of a cube?
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
That doesn't look right. n=2 -> P=1
A related question is: Given n vectors x[1], ... , x[n], how do we test if they all lie in some half-space, i.e. does there exist a vector u such that u.x[i] > 0 for all i? I'm stuck on this as well.
If the boundary of the half-space is a plane, can't you just take the inner product with a vector normal to that plane?
Brent
-- Gene ______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
----- No virus found in this message. Checked by AVG - www.avg.com Version: 2013.0.3408 / Virus Database: 3222/6674 - Release Date: 09/17/13
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<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
----- No virus found in this message. Checked by AVG - www.avg.com Version: 2013.0.3408 / Virus Database: 3222/6674 - Release Date: 09/17/13
On Sep 17, 2013, at 3:02 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
Here's a trick that works in any dimension. Sample the points in two stages. First sample a set of n axes that pass through the origin. Next sample one point on each axis. It turns out that the homo-hemisphere property doesn't depend on the choice of axes at all, only on which side of the origin each point is placed in the second stage. Calculating your probability is now an exercise in combinatorics. -Veit
I'm not saying that Veit's method is wrong --- but it's not obvious that it doesn't fail as a result of a Bertrand-style paradox. WFL On 9/17/13, Veit Elser <ve10@cornell.edu> wrote:
On Sep 17, 2013, at 3:02 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
Here's a trick that works in any dimension. Sample the points in two stages. First sample a set of n axes that pass through the origin. Next sample one point on each axis. It turns out that the homo-hemisphere property doesn't depend on the choice of axes at all, only on which side of the origin each point is placed in the second stage. Calculating your probability is now an exercise in combinatorics.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
________________________________ From: Fred Lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 4:47 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
I'm not saying that Veit's method is wrong --- but it's not obvious that it doesn't fail as a result of a Bertrand-style paradox. WFL
On 9/17/13, Veit Elser <ve10@cornell.edu> wrote:
On Sep 17, 2013, at 3:02 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
Here's a trick that works in any dimension. Sample the points in two stages. First sample a set of n axes that pass through the origin. Next sample one point on each axis. It turns out that the homo-hemisphere property doesn't depend on the choice of axes at all, only on which side of the origin each point is placed in the second stage. Calculating your probability is now an exercise in combinatorics.
-Veit
_______________________________________________ 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
This is not exactly the same problem but close: "What is the probability that n randomly chosen points on a sphere will all lie in a single hemisphere? " http://www.mathpages.com/home/kmath327/kmath327.htm On Tue, Sep 17, 2013 at 8:05 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
________________________________ From: Fred Lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 4:47 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
I'm not saying that Veit's method is wrong --- but it's not obvious that it doesn't fail as a result of a Bertrand-style paradox. WFL
On 9/17/13, Veit Elser <ve10@cornell.edu> wrote:
On Sep 17, 2013, at 3:02 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
But what is the probability if any hemisphere is allowed? I'm stuck on this problem.
In two dimensions, the probability that all n molecules lie in some semicircle is 2n/2^n.
Here's a trick that works in any dimension. Sample the points in two stages. First sample a set of n axes that pass through the origin. Next sample
one
point on each axis. It turns out that the homo-hemisphere property doesn't depend on the choice of axes at all, only on which side of the origin each point is placed in the second stage. Calculating your probability is now an exercise in combinatorics.
-Veit
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sep 17, 2013, at 8:05 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
We have n axes through the origin and these define n orthogonal hyperplanes, also passing through the origin. In 2D we have n lines that subdivide the unit circle into 2n arcs, in 3D we have n planes that divide the unit sphere into N(3,n) spherical polygons, etc. Let's put off for now the evaluation of N(3,n). The significance of the sphere subdivisions is the following. When you make the binary choice for each axis on the placement of the point with respect to the origin you are adding a constraint on the position of the common hemisphere. Specify the position of the common hemisphere by its "north pole". Suppose this north pole lies within some spherical subdivision. This uniquely determines the binary choice on each axis so that the corresponding point lies within the common hemisphere. So how many of the joint binary choices have _some_ common hemisphere? Answer: the number of spherical subdivisions. (There is a bijection between the set of valid axis choices and the subdivisions of the sphere by hyperplanes.) The probability there exists a common hyperplane is therefore N(d,n)/2^n, which equals 2n/2^n in 2D. Finding the number of spherical subdivisions for arbitrary d and n involves writing recursion formulas and recognizing the solution is a sum of binomial coefficients. In 3D there is a direct approach using Euler's formula. With n intersecting planes we get V=n(n-1) vertices on the sphere and E=2(n-1)n arcs that bound F spherical polygons. From Euler we get F=2-V+E=n^2-n+2=N(3,d). The probability is therefore (n^2-n+2)/2^n. -Veit
That is really pretty, Veit! Jim Propp On Tue, Sep 17, 2013 at 9:35 PM, Veit Elser <ve10@cornell.edu> wrote:
On Sep 17, 2013, at 8:05 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
We have n axes through the origin and these define n orthogonal hyperplanes, also passing through the origin. In 2D we have n lines that subdivide the unit circle into 2n arcs, in 3D we have n planes that divide the unit sphere into N(3,n) spherical polygons, etc. Let's put off for now the evaluation of N(3,n).
The significance of the sphere subdivisions is the following. When you make the binary choice for each axis on the placement of the point with respect to the origin you are adding a constraint on the position of the common hemisphere. Specify the position of the common hemisphere by its "north pole". Suppose this north pole lies within some spherical subdivision. This uniquely determines the binary choice on each axis so that the corresponding point lies within the common hemisphere. So how many of the joint binary choices have _some_ common hemisphere? Answer: the number of spherical subdivisions. (There is a bijection between the set of valid axis choices and the subdivisions of the sphere by hyperplanes.)
The probability there exists a common hyperplane is therefore N(d,n)/2^n, which equals 2n/2^n in 2D. Finding the number of spherical subdivisions for arbitrary d and n involves writing recursion formulas and recognizing the solution is a sum of binomial coefficients. In 3D there is a direct approach using Euler's formula. With n intersecting planes we get V=n(n-1) vertices on the sphere and E=2(n-1)n arcs that bound F spherical polygons. From Euler we get F=2-V+E=n^2-n+2=N(3,d). The probability is therefore (n^2-n+2)/2^n.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks, Veit. I almost understand this. In any case I'll add an interesting footnote: On the unit circle C one can ask, What is the probability that for n points chosen at random from C, there exists some arc of length 2pi*f (i.e., a fraction f of the circumference) that contains all n points. Denote the answer by P(f,n). For a fixed n, as f approaches 1 the formula P(f,n) passes through a countable number of fractions f_1 < f_2 < . . . < f_k < . . . < 1 at which the P(f_k,n) is not differentiable, even though it's continuous everywhere in f. (I think the f_k are at 1/2, 2/3, 3/4, 4/5, etc.) --Dan On 2013-09-17, at 6:35 PM, Veit Elser wrote:
On Sep 17, 2013, at 8:05 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
We have n axes through the origin and these define n orthogonal hyperplanes, also passing through the origin. In 2D we have n lines that subdivide the unit circle into 2n arcs, in 3D we have n planes that divide the unit sphere into N(3,n) spherical polygons, etc. Let's put off for now the evaluation of N(3,n).
The significance of the sphere subdivisions is the following. When you make the binary choice for each axis on the placement of the point with respect to the origin you are adding a constraint on the position of the common hemisphere. Specify the position of the common hemisphere by its "north pole". Suppose this north pole lies within some spherical subdivision. This uniquely determines the binary choice on each axis so that the corresponding point lies within the common hemisphere. So how many of the joint binary choices have _some_ common hemisphere? Answer: the number of spherical subdivisions. (There is a bijection between the set of valid axis choices and the subdivisions of the sphere by hyperplanes.)
The probability there exists a common hyperplane is therefore N(d,n)/2^n, which equals 2n/2^n in 2D. Finding the number of spherical subdivisions for arbitrary d and n involves writing recursion formulas and recognizing the solution is a sum of binomial coefficients. In 3D there is a direct approach using Euler's formula. With n intersecting planes we get V=n(n-1) vertices on the sphere and E=2(n-1)n arcs that bound F spherical polygons. From Euler we get F=2-V+E=n^2-n+2=N(3,d). The probability is therefore (n^2-n+2)/2^n.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For f <= 1/2 the probability is n f^(n-1), i.e. the enhancement factor from allowing any semicircle vs. a fixed semi circle is n/f. I haven't solved the problem for f > 1/2, but my intuition agrees with yours on the location of the breakpoints. -- Gene
________________________________ From: Dan Asimov <dasimov@earthlink.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 7:00 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
Thanks, Veit. I almost understand this.
In any case I'll add an interesting footnote: On the unit circle C one can ask, What is the probability that for n points chosen at random from C, there exists some arc of length 2pi*f (i.e., a fraction f of the circumference) that contains all n points. Denote the answer by P(f,n).
For a fixed n, as f approaches 1 the formula P(f,n) passes through a countable number of fractions f_1 < f_2 < . . . < f_k < . . . < 1 at which the P(f_k,n) is not differentiable, even though it's continuous everywhere in f. (I think the f_k are at 1/2, 2/3, 3/4, 4/5, etc.)
--Dan
On 2013-09-17, at 6:35 PM, Veit Elser wrote:
On Sep 17, 2013, at 8:05 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
We have n axes through the origin and these define n orthogonal hyperplanes, also passing through the origin. In 2D we have n lines that subdivide the unit circle into 2n arcs, in 3D we have n planes that divide the unit sphere into N(3,n) spherical polygons, etc. Let's put off for now the evaluation of N(3,n).
The significance of the sphere subdivisions is the following. When you make the binary choice for each axis on the placement of the point with respect to the origin you are adding a constraint on the position of the common hemisphere. Specify the position of the common hemisphere by its "north pole". Suppose this north pole lies within some spherical subdivision. This uniquely determines the binary choice on each axis so that the corresponding point lies within the common hemisphere. So how many of the joint binary choices have _some_ common hemisphere? Answer: the number of spherical subdivisions. (There is a bijection between the set of valid axis choices and the subdivisions of the sphere by hyperplanes.)
The probability there exists a common hyperplane is therefore N(d,n)/2^n, which equals 2n/2^n in 2D. Finding the number of spherical subdivisions for arbitrary d and n involves writing recursion formulas and recognizing the solution is a sum of binomial coefficients. In 3D there is a direct approach using Euler's formula. With n intersecting planes we get V=n(n-1) vertices on the sphere and E=2(n-1)n arcs that bound F spherical polygons. From Euler we get F=2-V+E=n^2-n+2=N(3,d). The probability is therefore (n^2-n+2)/2^n.
-Veit
_______________________________________________ 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
Velt. thank you for the derivation of this result, and also Victor for providing the link to the proof. This problem was bugging me for quite a while. -- Gene
________________________________ From: Veit Elser <ve10@cornell.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, September 17, 2013 6:35 PM Subject: Re: [math-fun] Probability that all molecules of a gas are in one half of the container
On Sep 17, 2013, at 8:05 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The distance of each particle from the center can be individually scaled by positive numbers without affecting the "contained in a hemisphere" property. Therefore, I do not see how Veit's suggestion is helpful. A little more detail, please.
We have n axes through the origin and these define n orthogonal hyperplanes, also passing through the origin. In 2D we have n lines that subdivide the unit circle into 2n arcs, in 3D we have n planes that divide the unit sphere into N(3,n) spherical polygons, etc. Let's put off for now the evaluation of N(3,n).
The significance of the sphere subdivisions is the following. When you make the binary choice for each axis on the placement of the point with respect to the origin you are adding a constraint on the position of the common hemisphere. Specify the position of the common hemisphere by its "north pole". Suppose this north pole lies within some spherical subdivision. This uniquely determines the binary choice on each axis so that the corresponding point lies within the common hemisphere. So how many of the joint binary choices have _some_ common hemisphere? Answer: the number of spherical subdivisions. (There is a bijection between the set of valid axis choices and the subdivisions of the sphere by hyperplanes.)
The probability there exists a common hyperplane is therefore N(d,n)/2^n, which equals 2n/2^n in 2D. Finding the number of spherical subdivisions for arbitrary d and n involves writing recursion formulas and recognizing the solution is a sum of binomial coefficients. In 3D there is a direct approach using Euler's formula. With n intersecting planes we get V=n(n-1) vertices on the sphere and E=2(n-1)n arcs that bound F spherical polygons. From Euler we get F=2-V+E=n^2-n+2=N(3,d). The probability is therefore (n^2-n+2)/2^n.
-Veit
participants (11)
-
Charles Greathouse -
Cris Moore -
Dan Asimov -
Eugene Salamin -
Fred Lunnon -
Gareth McCaughan -
James Propp -
meekerdb -
Mike Stay -
Veit Elser -
Victor Miller