Random Points on a Sphere | Hacker News Reader

Random Points on a Sphere

johncarlosbaez.wordpress.com

120 pointsjohndcook29 comments

High dimensional spheres are very counterintuitive! The volume of a n-dimensional unit sphere goes to zero as n increases, almost all the volume is contained near the surface.

Some interesting musings in this realm: https://marckhoury.github.io/counterintuitive-properties-of-...

This is a fantastically intuitive walkthrough.

It was discussed on HN a few months ago: https://news.ycombinator.com/item?id=16523786

Hyper-spheres are a recurrent theme, see for example https://news.ycombinator.com/item?id=3995615

Related phenomenon in ML: https://en.m.wikipedia.org/wiki/Curse_of_dimensionality

Don't forget 3Blue1Brown's incredible video about visualizing higher dimensions[1]. He's getting to xkcd levels of "Of course there's a relevant video"

[1]: https://www.youtube.com/watch?v=zwAD6dRSVyI

Related: In 4D and higher space, the concept of rotating around an axis does not make sense.

In 3D there are three ways to turn: yaw, pitch and roll. In 4D, there are not 4 but 6 ways.

> Related: In 4D and higher space, the concept of rotating around an axis does not make sense.

I think that this is like saying "rotating in 3D doesn't make sense"; it's not so much that it doesn't make sense as that it's not uniquely specified.

(Then there's the fact, which maybe is what you meant (since you referenced the dimension of SO(4)), that a 4D Euclidean rotation need not fix an axis at all!)

Awesome.

Also it seems Greg Egan is the SF author[1] which for me makes it extra cool.

[1] https://en.wikipedia.org/wiki/Greg_Egan

It was a real treat seeing his name at the start of this.

Definitely. I had no idea he was involved going in, I thought it would just be some neat math I didn't understand (which it still was). Greg Egan has been my favourite author for a few years now, ever since reading Diaspora.

His twitter account is chock full of interesting animations and links to math he's working on.

I finally read some Greg Egan recently and was not disappointed (started with 'Axiomatic' which is a collection of short stories, I'm not sure if this is the best place to start but I found it to be a good introduction...haven't read an author who could write a story around Cantor sets before!).

Wow, mind blown. Unfortunately, even with an undergraduate degree in mathematics, I was lost after this paragraph:

`This made me eager to find a proof that all the even moments of the probability distribution of distances between points on the unit sphere in \mathbb{R}^d are integers when \mathbb{R}^d is an associatve normed division algebra.`

Nonetheless, very interesting!

The point of an undergraduate degree isn't to teach you everything in mathematics. It's to give you the tools to figure it out.

I'm pretty sure that by

> \mathbb{R}^d is an associatve normed division algebra

the author is referring simply to a generalization of the euclidean structure.

Not quite -- the comment refers to the fact that R^d has the structure of a normed division algebra in dimensions 1, 2, 4, and 8. This means that you can multiply things together in a nice way when you're in one of those spaces. For R^1, this is just multiplying real numbers, for R^2 it's multiplying complex numbers, R^4 is quaternions, and R^8 is octonions. As you go up in dimensionality, you lose more and more nice properties: the quaternions are not commutative and the octonions are also not associative (which is why there's no mention of them in the blog post). The point is that in dimension 1, 2, and 4 all sorts of interesting things happen. John Baez has a paper about this: http://math.ucr.edu/home/baez/octonions/node1.html

Sort of. A Euclidean structure has “addition” but not “multiplication”. Having an additional operation that’s required to be associative, have inverses, distribute over addition, and play nicely with the norm turns out to be such a constraint that, as he mentions in the previous paragraph, the real numbers, complex numbers, and quaternions are the only such structures.

Literally speaking then, “... when R^d is an associative normed division algebra” just means “when d = 1, 2, or 4”, except of course that the idea is to use the multiplicative structure in the proof.

read his post on octonions http://math.ucr.edu/home/baez/octonions/

The 1, 2, 4, 8 phenomenon surprised 20th-century mathematicians, and derives from weird facts about how S7, S3, and S1 fiber. (fibration is lining one shape with other shapes)

> read his post on octonions http://math.ucr.edu/home/baez/octonions/

Not for a discussion on associative normed algebras ….

Aren't there other strange facts about dimensions 1, 3 and 7, particularly in linear algebra?

Persi Diaconis https://www.ams.org/notices/200511/what-is.pdf

Niles Johnson on Hopf/Milnor fibrations https://nilesjohnson.net/hopf.html

The obvious question is actually the converse: assume all even moments of the distance are integers - does it follow that S^(n-1) is a group (hence n=1, 2 or 4)?

N.b. the article uses d for the dimension, and n for the moment index. I haven't cranked out the details, but I believe that this is already true just assuming the fourth moments of the distance are integers. That is, for n != 1, 2, or 4, the fourth moment is never an integer. Idea of the "brute force" proof:

Take the formula in the article for the 4th moment of the d-dimensional sphere, which is always a rational number. Basically, for n=2^k, the denominator should be divisible by a larger power of two than the numerator (specifically, if I crunched the numbers right, the gap should be k-2). When n is not a power of two, then for any odd prime p dividing n, I believe the denominator should be divisible by a larger power of p than the numerator. This requires calculating exactly how many powers of p divide various factorial expressions, but you get the idea.

Wait, there are a lot of ways in computer science to choose points randomly, and points randomly with constraints (here belong to unit sphere) and that could change the result, no ?

It won't change the result if you're doing it correctly.

>We’ll be ‘randomly choosing’ lots of points on spheres of various dimensions. Whenever we do this, I mean that they’re chosen independently, and uniformly with respect to the unique rotation-invariant Borel measure that’s a probability measure on the sphere. In other words: nothing sneaky, just the most obvious symmetrical thing!

There are an infinite number of probability distributions over most objects, yes, but there's also often a good default that is the "uniform" distribution. That's what they're talking about here.

As an aside, there's an interesting way to generate a uniform distribution on a sphere. It uses the fact that the joint distribution of several independent standard Gaussians has rotational symmetry. So to generate a random point on the surface of the n-sphere, you can sample n+1 numbers independently from the standard Gaussian and then normalise them so that their squares sum to 1 (if they're all 0 then you have to reroll).

In fact the result has little to do with computer science - it is purely a mathematical result. The way points are sampled (uniform distribution) is clarified in the text

Persi Diaconis https://www.ams.org/notices/200511/what-is.pdf — you want to choose randomly from the eigenvalues of a matrix

Reply on news.ycombinator.com