Example B: Hypervolume of a Thin Shell between 2 Hyperspheres.

Contents

Theory

Consider 2 spheres centered on the origin, one with radius $r$ and the other with slightly smaller radius $r - \epsilon$. The volume of a $d$-dimensional hypershere with radius $r$ is given by:

$$ V_d(r) = \frac{r^d\pi^{d/2}}{\Gamma(d/2+1)}\  $$

Now consider the fraction of the volume of the Iarger sphere in between the 2 concentric hyperspheres:

$$ f_s = \frac{ V_d(r) - V_d(r-\epsilon)} {V_d(r)}\ = \frac{r^d - (r-\epsilon)^d}{r^d}\ = 1 - (1-\frac{\epsilon}{r})^d\
      \rightarrow1 $$ when $$ d\rightarrow\infty $$

Hence, virtually all of the content of a hypersphere is concentrated close to its surface, which is only a $(d-1)$-dimensional manifold. Thus, for data distributed uniformly over both the hypersphere and the hypercube (see Example A), most of the data fall near the boundary and edges of the volume. Most statistical techniques exhibit peculiar behavior if the data fall in a lower-dimensional subspace. This example illustrates one important aspect of the $\bf{curse}$ $\bf{of }$ $\bf{dimensionality}$.

% Workspace Initialization.
clc; clear; close all;

Monte Carlo Evaluation of the Volume Fraction $f_s$ between the 2 Hyperspheres (Thin Shell).

a = 10;               % 2*a = Hypercube Edge.
r = 10;               % Hypersphere radius.
NumOfRuns = 6e5;      % Number of Monte Carlo runs.
Dimensions = 3:12;    % Problem dimensions.
LD = length(Dimensions);
epsilon = 1;
counter_inshell   = zeros(1,LD);
counter_outshell = zeros(1,LD);
counter_interior = zeros(1,LD);

for i=1:LD
     dim = Dimensions(i);
     for k=1:NumOfRuns
          ndUniformSamples = 2*a*(rand(1,dim)-0.5);           % Generate uniform samples in [-a  a]^dim.
          if sum(ndUniformSamples.^2)<r^2                     % First deal only with data that belong to the bigger
             counter_interior(i) = counter_interior(i) + 1;   % hypersphere and discard the rest.
             if sum(ndUniformSamples.^2)> (r - epsilon)^2     % From them select only those belonging to the
                counter_inshell(i) = counter_inshell(i) + 1;  % hypershell of epsilon thickness.
             else
                counter_outshell(i) = counter_outshell(i) + 1;
             end
          end
     end
end

Calculate the Theoretical Value of $f_s$ Analytically from the formula given above:

f_s = zeros(1,LD);
for i=1:LD
    dim = Dimensions(i);
    f_s(i) = 1 - (1 - epsilon/r)^dim;
end

Plot the Results:

Plot the value found by Monte Carlo simulation:

stem(Dimensions,counter_inshell./counter_interior,'r*');
hold on;
% Now plot the theoretical value with blue circles:
stem(Dimensions,f_s);
grid on;
xlabel('Dimension');
ylabel('Fraction Volume f_s');
title('Analytically Calculated (blue circles) and Monte Carlo Estimated (red stars)');

Note

The Monte Carlo simulation is less accurate in higher dimensions because the data points that fall in the interior of the bigger sphere are very few: For examle, out of 600.000 uniform data points, only 26 fell into the bigger 14-dimensional hypersphere. Therefore the calculated fraction is not very accurate because its value came from very few measurements.