Re:High-dimensional spheres are "spikey"
by ColinWright on Wednesday May 23, 2012 @02:32AM
(#4011847)
But for a given e, that probability goes to zero as n goes to infinity, or as n goes to infinity, the e required to be within a given delta of 50% gets smaller. In other words, choose your step size in an optimisation. As n gets larger, the chances of it working get smaller. In even moderately large dimensions the step sixe required is so small, you don't make any progress.
This doesn't seem to be true.
Imagine a sphere in n-dimensions, S = {Sum(x_i^2)<1}. Top of the sphere is p=(1,0,0,...,0). Now for any random direction r, if you take a very small step from p towards r, you have exactly 50% chance to be inside the sphere.
To be mathematically precise, for any r (unit vector) chosen at random, probability that there is e>0 such that p + e*r is within S is 1/2.
So half the time the steps take you out, half the time it takes you in - considering the step is small enough compared to the radius.