5 ms·

My initial intuition is telling me that it would be diameter/2, from the perspective of a single point, the closest points would be near zero distance away, and

• adgjlsfhk1 5y ago
  I think the most intuitive way of thinking about this is sphere packing. Asking what percent of points are within distance d of an n-sphere of radius 1 is equivalent to asking what the ratio of volumes is. For d<1, the n-volume of a radius d sphere tends to 0 as n goes towards infinity, so that means almost all of the points are as far away as possible.
• dan-robertson 5y ago
  If you consider a point on the sphere it means choosing a bunch of xi such that: x1^2 + x2^2 + … + xn^2 = 1. Suppose wlog you pick (1,0,0,…,0). Then the distance from your point to a random point is: D = (x1-1)^2 + x2^2 + … + xn^2 And from the first equation we know: x1^2 = 1 - x2^2 - x3^2 - … - xn^2 Intuitionistically, your point will be far from a random point if x1 is close to zero, and x1 will be close to zero because everything is close to zero. But we can be more mathematical about it. Our (very reasonable) assumption is that the volume of a n-dimensional disk is proportional to the nth power of its radius. The third equation shows that x1 is going to be big (meaning the distance to the chosen point above is not so close to the diameter) if a corresponding[1] point on the n-disk is close to the middle. But the distance from the origin, R, of a random point in the n-disk is distributed with pdf proportional to p(r) = r^n for r in [0,1]. So the cdf is just r^(n+1) and E[x1^2] = 1 - E[R] = 1 - (n+1)/(n+2), which tends to 0 as n grows. Therefore we get E[D] = E[(1-x1)^2] + 1 - E[x1^2] which tends to 2 as n grows large. [1] the correspondence is that if I give you a point on a disk, you can turn it into a point on a sphere by flipping a coin to decide if it goes in the upper or lower hemisphere and then projecting up or down perpendicular to the disk from the point onto the sphere. But thinking a little more, I’m not sure this preserves the metric as it favours points on the sphere that correspond to the middle parts of the disk. So I think the actual expected value of x1 should be smaller.
  • WithinReason 5y ago
    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