4 ms·

Let me hijack your explanation starting from this point: D = (x₁-1)² + (x₂² + … + xₙ²) Since all the xₙ² sum to 1, as the dimensionality grows (∑xₙ²→1 as

Let me hijack your explanation starting from this point: D = (x₁-1)² + (x₂² + … + xₙ²) Since all the xₙ² sum to 1, as the dimensionality grows (∑xₙ²→1 as n→∞) each individual xₙ will converge towards 0. Since x₁ is almost 0, therefore the (x₁-1)² term will be almost 1. Since we know that ∑xₙ²=1, and that x₁² is almost 0, then we also know that ∑xₙ² - x₁² is almost 1, which is the 2nd half of the above expression for D. So the average distance converges to "almost 1 + almost 1", which "almost 2", which is the diameter.

Retric 5y ago
Close, the distance formula is square root of (X1^2 + X2^2 …). So exactly 1 gives a distance of 1, but almost 1 + almost 1 gives a distance of almost square root of 2.
- WithinReason 5y ago
  Good point!
akomtu 5y ago
"each individual xₙ will converge towards 0" I'm not sure it will. x1 is chosen randomly in the -1..1 interval. I dont see how the million other dimensions would force it to stick to 0. Those N other dimensions shrink the stddev(xi) by sqrt(N), though.
- WithinReason 5y ago
  Then try normalizing a random 1000-element vector. The average of the vector elements is around 0.027.
  - akomtu 5y ago
    The fact that average of D is sqrt(2) is the easy part. But average doesnt mean that random D values would concentrate in that spot. D may be evenly distributed. So the question is what's the variance of D? Using your formulas above: D^2 = (1 - x1)^2 + (1 - x1^2) = 2 - 2x1 We know that x1 is 0 on average, but its distribution is restricted by the fact that we choose a random point on the n-sphere. So what's the probability of that random point falling into a thin stripe where abs(x1) < eps? And how does this probability behave for large n? This eps-stripe is basically the (n-1)-sphere of width eps, so the stripe's area A(n)=eps•S(n-1), and so our probability p=eps•S(n-1)/S(n). The "magical" property of n-spheres is that their area grows at first, reaches maximum in 7 dimensions and then falls off rapidly to zero. Using formulas from wikipedia, I get: p = eps•(n/4)^(n/2) for large n. In other words, the distribution of x1 approaches the look of the delta function at the n^n pace and for all practical matters, D=sqrt(2) with high precision for n > 10. Where

Retric 5y ago

Close, the distance formula is square root of (X1^2 + X2^2 …). So exactly 1 gives a distance of 1, but almost 1 + almost 1 gives a distance of almost square root of 2.

WithinReason 5y ago
Good point!

akomtu 5y ago

"each individual xₙ will converge towards 0" I'm not sure it will. x1 is chosen randomly in the -1..1 interval. I dont see how the million other dimensions would force it to stick to 0. Those N other dimensions shrink the stddev(xi) by sqrt(N), though.

WithinReason 5y ago
Then try normalizing a random 1000-element vector. The average of the vector elements is around 0.027.
- akomtu 5y ago
  The fact that average of D is sqrt(2) is the easy part. But average doesnt mean that random D values would concentrate in that spot. D may be evenly distributed. So the question is what's the variance of D? Using your formulas above: D^2 = (1 - x1)^2 + (1 - x1^2) = 2 - 2x1 We know that x1 is 0 on average, but its distribution is restricted by the fact that we choose a random point on the n-sphere. So what's the probability of that random point falling into a thin stripe where abs(x1) < eps? And how does this probability behave for large n? This eps-stripe is basically the (n-1)-sphere of width eps, so the stripe's area A(n)=eps•S(n-1), and so our probability p=eps•S(n-1)/S(n). The "magical" property of n-spheres is that their area grows at first, reaches maximum in 7 dimensions and then falls off rapidly to zero. Using formulas from wikipedia, I get: p = eps•(n/4)^(n/2) for large n. In other words, the distribution of x1 approaches the look of the delta function at the n^n pace and for all practical matters, D=sqrt(2) with high precision for n > 10. Where