Morning thought: 2x2 diagrams work so well because a random pair of vectors in a high dimensional space are orthogonal with probability ~1
Conversation
Replying to
Damn this is genius. Immediately strikes me as true though I can’t see a trivial proof. Don’t you need an extra condition though of the vectors being sparse or something? Is this a well known result?
For vectors drawn randomly from {-1,1}^N, the expected angle between them is 1/N.
2
1
Update: don't need a sparsity condition (which makes sense since it would be weird to have this result be dependent on the coordinate system)
3
This Tweet was deleted by the Tweet author. Learn more
If they’re sparse product elements would all be zero with high probability. It might even be true without a sparsity condition via central limit theorem. Ie likely as many product elements being positive as negative, and normally distributed in [-1, 1]
It's roughly Gaussian; mean 0, stddev=dim^{-1/2}. Some intuition:
1. Mean 0: symmetry.
2. Mean square = 1/d: if v1,...,vd form orthogonal basis then sum_i (vi,w)^2 =1 for any unit vector w. Now use symmetry (added d terms).
3. Gaussian: dot product is a sum of many small things
1
1
7
high dimensional spaces are weird
Quote Tweet
Vitali Milman's insight: convex sets in high dimension look like hedgehogs math.tau.ac.il/~milman/files/






