[math-fun] Gary Antonick is edging away from the following bonus puzzle
because he thinks only Gene Salamin can solve it. Can any of you? (who didn't already know the answer) For a ceremonial match, a soccer ball is colored with a map of the Globe instead of a traditional pattern. At the start of the match, the ball rests on its south pole, with its lat 0, long 0 point aimed due east. At the end of the match, the ball lies forgotten on the pitch, in a truly random orientation. For any orientation, there will always be an axis through the center about which a single rotation will restore the original north up, 0,0 east orientation. What is the (surprising) expected magnitude of this required rotation? And yet last week Gary ran (with great satisfaction) Julian's tympanhedron, which, to my knowledge, has *never* been found when posed as a puzzle. --rwg
RWG wrote:
For a ceremonial match, a soccer ball is colored with a map of the Globe instead of a traditional pattern. At the start of the match, the ball rests on its south pole, with its lat 0, long 0 point aimed due east. At the end of the match, the ball lies forgotten on the pitch, in a truly random orientation. For any orientation, there will always be an axis through the center about which a single rotation will restore the original north up, 0,0 east orientation. What is the (surprising) expected magnitude of this required rotation?
SPOILER SPACE ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... SOLUTION: --------- We want to find the average distance in the rotation group SO(3) between an arbitrary rotation and the identity, where distance is measured by the angle t of the rotation, 0 <= t <= pi. (*) Every rotation f in SO(3) is represented by either of exactly two unit quaternions, which are antipodal. This works by first identifying S^2 with the unit sphere in S^3 that is the equator with respect to the poles +-1. Then for any x in S^2, the rotation f_q(x) is defined by f_q(x) = q' x q where q' denotes the reciprocal of q (for a unit quaternion, just its conjugate). If t is the least angle between q and the real axis (so that 0 <= theta <= pi/2), then the rotation f_q is by an angle of 2t. We can now find the average rotation angle from the identity among all rotations in SO(3). By (*), SO(3) corresponds almost exactly to the hemisphere Hem^3 of S^3 nearest to the identity . . . except that those points farthest from the identity, forming a copy of a unit 2-sphere, need to be identified by the antipodal map to get just one quaternion for each rotation. But since this 2-sphere is measure 0 inside Hem^3, we can ignore this nicety to find the average rotation angle. All the quaternions q of Hem^3 at angle t > 0 from the identity form a locus that is a 2-sphere of radius = sin(t). For all these q, the rotation angle of the rotation f_q is 2t., and their 2-volume is 4 pi sin^2(t). The total 3-volume of the (unit) 3-sphere S^3 is 2 pi^2, so that of Hem^3 is just pi^2. So we get for the probability density of the angle t d(t) = 4 pi sin^2(t) / pi^2 and so the expected rotation angle is E(2t) = Integral_{0,pi/2} (2t) 4 pi sin^2(t) dt / pi^2 = (8/pi) Integral_{0,pi/2} t sin^2(t) dt = pi/2 + 2/pi . Which is pretty mystical. Makes you wonder if there isn't some good reason it turns out like that. --Dan
At first I'm thinking, "why wouldn't that just be pi/2?" so I had to stare at the problem until I understood it correctly. It then became apparent that the answer must be greater than pi/2, and understanding the problem, I probably could have solved it after much torturous effort via standard analytic geometry and calculus, perhaps within my remaining lifetime. The answer is quite nice, though.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Bill Gosper Sent: Friday, July 04, 2014 11:50 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Gary Antonick is edging away from the following bonus puzzle
because he thinks only Gene Salamin can solve it. Can any of you? (who didn't already know the answer)
For a ceremonial match, a soccer ball is colored with a map of the Globe instead of a traditional pattern. At the start of the match, the ball rests on its south pole, with its lat 0, long 0 point aimed due east. At the end of the match, the ball lies forgotten on the pitch, in a truly random orientation. For any orientation, there will always be an axis through the center about which a single rotation will restore the original north up, 0,0 east orientation. What is the (surprising) expected magnitude of this required rotation?
And yet last week Gary ran (with great satisfaction) Julian's tympanhedron, which, to my knowledge, has *never* been found when posed as a puzzle. --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]! To put it differently, you can generate a random point (x,y,z) like this: choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta This is only true for the 3-dimensional sphere, of course! - Cris On Jul 5, 2014, at 9:31 AM, "David Wilson" <davidwwilson@comcast.net> wrote:
At first I'm thinking, "why wouldn't that just be pi/2?" so I had to stare at the problem until I understood it correctly. It then became apparent that the answer must be greater than pi/2, and understanding the problem, I probably could have solved it after much torturous effort via standard analytic geometry and calculus, perhaps within my remaining lifetime. The answer is quite nice, though.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Bill Gosper Sent: Friday, July 04, 2014 11:50 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Gary Antonick is edging away from the following bonus puzzle
because he thinks only Gene Salamin can solve it. Can any of you? (who didn't already know the answer)
For a ceremonial match, a soccer ball is colored with a map of the Globe instead of a traditional pattern. At the start of the match, the ball rests on its south pole, with its lat 0, long 0 point aimed due east. At the end of the match, the ball lies forgotten on the pitch, in a truly random orientation. For any orientation, there will always be an axis through the center about which a single rotation will restore the original north up, 0,0 east orientation. What is the (surprising) expected magnitude of this required rotation?
And yet last week Gary ran (with great satisfaction) Julian's tympanhedron, which, to my knowledge, has *never* been found when posed as a puzzle. --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length. -- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\ Cris On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
<< Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length. >> Er --- how does one normalise without employing sqrt() ? << choose theta uniformly in [0,2pi] >> Though as RWG observed, pi is unavailable for this purpose ... WFL On 7/5/14, Cris Moore <moore@santafe.edu> wrote:
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, I slipped up; you do need sqrt to normalize the vector. That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes. Also, in doing integrations over the sphere in spherical coordinates, the element of area sinθ dθ dφ under the change of coordinates μ = cosθ becomes dμ dφ. -- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 9:47 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________
From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the followingbonuspuzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
From http://mathworld.wolfram.com/SpherePointPicking.html << Cook (1957) extended a method of von Neumann (1951) to give a simple method of picking points uniformly distributed on the surface of a unit sphere. Pick four numbers x_0, x_1, x_2, x_3 from a uniform distribution on (-1,1) , and reject pairs with x_0^2 + x_1^2 + x_2^2 + x_3^2 >= 1. (12)
From the remaining points, the rules of quaternion transformation then imply that the points with Cartesian coordinates x = 2 (x_1x_3 + x_0x_2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (13) y = 2 (x_2x_3 - x_0x_1) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (14) z = (x_0^2 + x_3^2 - x_1^2 - x_2^2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (15) have the desired distribution (Cook 1957, Marsaglia 1972). >>
WFL On 7/5/14, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Yes, I slipped up; you do need sqrt to normalize the vector.
That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes.
Also, in doing integrations over the sphere in spherical coordinates, the element of area sinθ dθ dφ under the change of coordinates μ = cosθ becomes dμ dφ.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 9:47 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________
From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the followingbonuspuzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oh, nice, that (together with Archimedes) `explains' the solution to my Gaussian puzzle. Thanks! Sincerely, Adam P. Goucher
Sent: Saturday, July 05, 2014 at 7:24 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
From http://mathworld.wolfram.com/SpherePointPicking.html
<< Cook (1957) extended a method of von Neumann (1951) to give a simple method of picking points uniformly distributed on the surface of a unit sphere. Pick four numbers x_0, x_1, x_2, x_3 from a uniform distribution on (-1,1) , and reject pairs with x_0^2 + x_1^2 + x_2^2 + x_3^2 >= 1. (12)
From the remaining points, the rules of quaternion transformation then imply that the points with Cartesian coordinates x = 2 (x_1x_3 + x_0x_2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (13) y = 2 (x_2x_3 - x_0x_1) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (14) z = (x_0^2 + x_3^2 - x_1^2 - x_2^2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (15) have the desired distribution (Cook 1957, Marsaglia 1972). >>
WFL
On 7/5/14, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Yes, I slipped up; you do need sqrt to normalize the vector.
That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes.
Also, in doing integrations over the sphere in spherical coordinates, the element of area sinθ dθ dφ under the change of coordinates μ = cosθ becomes dμ dφ.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 9:47 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________
From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the followingbonuspuzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Gene, is there a rigorous proof of that using just Eucidean solid geometry, without calculus? --Dan ----- That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes. -----
Gene, is there a rigorous proof of that using just Eucidean solid geometry, without calculus?
Yes. For a region R on the surface of the sphere, we define a volume V_R by taking the union of every line segment {OX : X in R}, where O is the centre of the sphere. Now we will compute this volume using solid geometry. Assume wlog the sphere is the sphere centred at the origin of radius r, and R is the region bounded between planes z = a and z = b, with a < b. Then the volume V_R can be computed as follows: V_R = pi*a*(r^2 - a^2)/3 - pi*b*(r^2 - b^2)/3 + Q where Q is the volume of the `slice' of sphere bounded between the planes z = a and z = b. To calculate Q, we appeal to Cavalieri's principle: https://cp4space.files.wordpress.com/2014/06/cavalieri.png Hence Q = pi*r^2*(b-a) - pi*b^3/3 + pi*a^3/3. Consequently, V_R = (2/3)*pi*r^2*(b-a). This is a function of b-a, so we are done. :) Sincerely, Adam P. Goucher
--Dan
----- That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes. ----- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If you allow the use of area elements, yes, there's a proof. Circumscribe a cylinder about the sphere of unit radius tangent at the equator. Project the sphere outward to the cylinder from the axis, i.e. the lines of projection are parallel to the equatorial plane. An area element at latitude λ is located distance cosλ from the axis, so it gets expanded by projection by factor 1/cosλ. But the normal to the element on the sphere is inclined to the line of projection by angle λ, and so it gets foreshortened by factor cosλ. So projection preserves area, independent of latitude. -- Gene
________________________________ From: Dan Asimov <dasimov@earthlink.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Gene, is there a rigorous proof of that using just Eucidean solid geometry, without calculus?
--Dan
----- That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes.
What are those points, geometrically? Somehow we're getting rid of two dimensions (from the interior of a 4-sphere to the surface of a 3-sphere). On Sat, Jul 5, 2014 at 11:24 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
From http://mathworld.wolfram.com/SpherePointPicking.html
<< Cook (1957) extended a method of von Neumann (1951) to give a simple method of picking points uniformly distributed on the surface of a unit sphere. Pick four numbers x_0, x_1, x_2, x_3 from a uniform distribution on (-1,1) , and reject pairs with x_0^2 + x_1^2 + x_2^2 + x_3^2 >= 1. (12)
From the remaining points, the rules of quaternion transformation then imply that the points with Cartesian coordinates x = 2 (x_1x_3 + x_0x_2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (13) y = 2 (x_2x_3 - x_0x_1) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (14) z = (x_0^2 + x_3^2 - x_1^2 - x_2^2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (15) have the desired distribution (Cook 1957, Marsaglia 1972). >>
WFL
On 7/5/14, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Yes, I slipped up; you do need sqrt to normalize the vector.
That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes.
Also, in doing integrations over the sphere in spherical coordinates, the element of area sinθ dθ dφ under the change of coordinates μ = cosθ becomes dμ dφ.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 9:47 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________
From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the followingbonuspuzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://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
The interior of the 4-sphere may equally well be any spherically-symmetric distribution. In that case, what we are doing geometrically is: 1. Normalising the vector (sending R^4 to S^3); 2. Applying the Hopf map (sending S^3 to S^2); 3. Taking one coordinate (sending S^2 to [-1, 1]). Sincerely, Adam P. Goucher
Sent: Saturday, July 05, 2014 at 7:48 PM From: "Mike Stay" <metaweta@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
What are those points, geometrically? Somehow we're getting rid of two dimensions (from the interior of a 4-sphere to the surface of a 3-sphere).
On Sat, Jul 5, 2014 at 11:24 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
From http://mathworld.wolfram.com/SpherePointPicking.html
<< Cook (1957) extended a method of von Neumann (1951) to give a simple method of picking points uniformly distributed on the surface of a unit sphere. Pick four numbers x_0, x_1, x_2, x_3 from a uniform distribution on (-1,1) , and reject pairs with x_0^2 + x_1^2 + x_2^2 + x_3^2 >= 1. (12)
From the remaining points, the rules of quaternion transformation then imply that the points with Cartesian coordinates x = 2 (x_1x_3 + x_0x_2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (13) y = 2 (x_2x_3 - x_0x_1) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (14) z = (x_0^2 + x_3^2 - x_1^2 - x_2^2) / (x_0^2 + x_1^2 + x_2^2 + x_3^2) (15) have the desired distribution (Cook 1957, Marsaglia 1972). >>
WFL
On 7/5/14, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Yes, I slipped up; you do need sqrt to normalize the vector.
That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes.
Also, in doing integrations over the sphere in spherical coordinates, the element of area sinθ dθ dφ under the change of coordinates μ = cosθ becomes dμ dφ.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 9:47 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________
From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the followingbonuspuzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A feature of quaternions that is even more remarkable has not so far been explicitly discussed at all: the fact that uniformly distributed unit quaternions (transitive in all 4 components) correspond to "random" 3-space rotations (scalar angle unrelated to 3 axis vector components)! This is reminiscent of the Stewart platform representation of 3-space isometries as a function of 6 transitive variables, contrasted with the familiar 3+3 dichotomy between rotation and translation. There is an admirably succinct discussion of this problem at http://math.stackexchange.com/questions/131336/uniform-random-quaternion-in-... which commences with a transitive generator for random quaternions involving sqrts, trig fns and 3 uniform variables (citation Ken Shoemake). Is there a rational generator, presumably using more uniform variables? If rejection is allowed, the simplest possibility is surely just to generate 4 uniform unit components, reject vectors with norm exceeding unity, otherwise scale up to unity; success rate is (pi^2/2)/2^4 ~ 30% . What about a transitive generator for 3-space isometries ... Fred Lunnon On 7/5/14, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Yes, I slipped up; you do need sqrt to normalize the vector.
That z is uniform in [-1,+1] is a consequence of the solid geometry theorem that the area of a sphere between two parallel planes depends only on the separation between the planes, and is independent of what part of the sphere lies between the planes.
Also, in doing integrations over the sphere in spherical coordinates, the element of area sinθ dθ dφ under the change of coordinates μ = cosθ becomes dμ dφ.
-- Gene
________________________________ From: Cris Moore <moore@santafe.edu> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 9:47 AM Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
Yes, of course... but the fact that z is uniform in [-1,+1] is quite surprising when you first see it.\
Cris
On Jul 5, 2014, at 9:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
-- Gene
________________________________
From: Cris Moore <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, July 5, 2014 8:38 AM Subject: Re: [math-fun] Gary Antonick is edging away from the followingbonuspuzzle
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
- Cris
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Fred, Where you say "uniformly distributed unit quaternions" I am confused. Uniformly distributed in what? I also don't know what "transitive in all four components" means. Clicked on the link to Stack Exchange and confronted a section of . . . I'm not sure what language of something by Ken Shoemake, but the question was not written in a way I can understand easily, so I don't care to read it. I certainly am reasonably familiar with quaternions and with probabilityt distributions, so if you give me just a few hints I can probably understand. Thanks, Dan P.S. Did you watch any of Wimbledon (on the telly) ? I don't care for spectator sports in general, but top-notch tennis I like a lot. On Jul 6, 2014, at 2:09 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
A feature of quaternions that is even more remarkable has not so far been explicitly discussed at all: the fact that uniformly distributed unit quaternions (transitive in all 4 components) correspond to "random" 3-space rotations (scalar angle unrelated to 3 axis vector components)!
Dear Dan, You apparently intended this for me personally; but since it was addressed to the list, I feel it only polite to others to reply publicly. On 7/6/14, Dan Asimov <dasimov@earthlink.net> wrote:
Dear Fred,
Where you say "uniformly distributed unit quaternions" I am confused. Uniformly distributed in what?
The 3-sphere: presumably the Euclidean measure there is essentially the only one to remain invariant under conjugation by quaternion --- or perhaps composition --- I guess that makes no difference [vide Haar measure ...]
I also don't know what "transitive in all four components" means.
The random generator has obvious symmetries involving transposing variables and sin,cos, which permute the vector components transitively.
Clicked on the link to Stack Exchange and confronted a section of . . . I'm not sure what language of something by Ken Shoemake, but the question was not written in a way I can understand easily, so I don't care to read it.
Try instead http://planning.cs.uiuc.edu/node198.html
I certainly am reasonably familiar with quaternions and with probabilityt distributions, so if you give me just a few hints I can probably understand.
Thanks,
Dan
P.S. Did you watch any of Wimbledon (on the telly) ? I don't care for spectator sports in general, but top-notch tennis I like a lot.
Don't have a telly. Nor time to watch it. Regards, Fred
On Jul 6, 2014, at 2:09 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
A feature of quaternions that is even more remarkable has not so far been explicitly discussed at all: the fact that uniformly distributed unit quaternions (transitive in all 4 components) correspond to "random" 3-space rotations (scalar angle unrelated to 3 axis vector components)!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Fred, Sorry -- I seem unable to consistently remember to change the recipient from math-fun to an individual I'm writing to. So I'll follow suit and continue in public. Since conjugation of the unit quaternions S^3 by any quaternion implements only arbitrary rotations of the equatorial S^2, fixing the real axis and preserving all the S^2's of various radii given by Re(q) = constant, there are actually a lot of measures on S^3 preserved by just conjugation. Left multiplication of S^3 by an arbitrary unit quaternion implements the (left) isoclinic rotations -- (half of all the) rotations that move everything by the same angle, with all of R^4 as the common eigenspace. I'm almost sure that only (scaled) Haar measure on S^3 is invariant by this S^3 action, but I don't have a proof at the moment. --Dan On Jul 6, 2014, at 4:41 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
You apparently intended this for me personally; but since it was addressed to the list, I feel it only polite to others to reply publicly.
On 7/6/14, Dan Asimov <dasimov@earthlink.net> wrote:
Dear Fred,
Where you say "uniformly distributed unit quaternions" I am confused. Uniformly distributed in what?
The 3-sphere: presumably the Euclidean measure there is essentially the only one to remain invariant under conjugation by quaternion --- or perhaps composition --- I guess that makes no difference [vide Haar measure ...]
I also don't know what "transitive in all four components" means.
The random generator has obvious symmetries involving transposing variables and sin,cos, which permute the vector components transitively.
Clicked on the link to Stack Exchange and confronted a section of . . . I'm not sure what language of something by Ken Shoemake, but the question was not written in a way I can understand easily, so I don't care to read it.
Try instead http://planning.cs.uiuc.edu/node198.html
I certainly am reasonably familiar with quaternions and with probabilityt distributions, so if you give me just a few hints I can probably understand.
And what Gene mentions is far better than the obvious "rejection method" I used as a green programmer: keep picking sets of n+1 points at random in [-1,1] until the sum S of their squares is in (0,1] then normalize the point in R^(n+1) to the sphere. But the fraction of sets that will be accepted decreases faster than 1/(n/2)!, so this method quickly fails to be practical as n gets big. For n = 10 the fraction is less than 1 in 50 million. --Dan (Begun before Fred's post on the rejection method in R^4.) On Jul 5, 2014, at 8:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
My mistake here; you do need sqrt to normalize, but that's not a big deal. But it's not restricted to any particular dimension. -- Gene
________________________________ From: Dan Asimov <dasimov@earthlink.net> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
And what Gene mentions is far better than the obvious "rejection method" I used as a green programmer: keep picking sets of n+1 points at random in [-1,1] until the sum S of their squares is in (0,1] then normalize the point in R^(n+1) to the sphere.
But the fraction of sets that will be accepted decreases faster than 1/(n/2)!, so this method quickly fails to be practical as n gets big. For n = 10 the fraction is less than 1 in 50 million.
--Dan (Begun before Fred's post on the rejection method in R^4.)
On Jul 5, 2014, at 8:55 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Random points on the unit n-sphere can be generated without the need for sqrt and trig. Generate n+1 independent Gaussian random numbers, and normalize the vector to unit length.
On Sat, 5 Jul 2014, Cris Moore wrote:
Consider also the following lovely fact: choose a point on the unit sphere uniformly at random. It's z-coordinate is uniformly distributed in the interval [-1,+1]!
To put it differently, you can generate a random point (x,y,z) like this:
choose z uniformly in [-1,+1] choose theta uniformly in [0,2pi] set x = sqrt(1-z^2) cos theta, y = sqrt(1-z^2) sin theta
This is only true for the 3-dimensional sphere, of course!
Oddly, I had a dream last night that hinged on this fact. Now I'm sorry that I can't remember any more details... -- Tom Duff. NONSPILLABLE BATTERY INSIDE.
participants (9)
-
Adam P. Goucher -
Bill Gosper -
Cris Moore -
Dan Asimov -
David Wilson -
Eugene Salamin -
Fred Lunnon -
Mike Stay -
Tom Duff