The transformed problem is now: take 24 samples from a normal distribution.
The first task is to see how big we can make the radius,
for both the ball and the intersection of the ball and the simplex have content proportional to r^{n}.
Its maximum size is when it touches the face opposite the vertex where its center is located.
If the center is at <1, 0, 0, ...> then the closest point on the opposite face is at <0, 1/n, 1/n, ...>.
The distance between these two points is √(g_{ij}Δx^{i}Δx^{j}) using the metric for our oblique barycentric coordinates introduced half way thru here.
In C speak, g_{ij} = i == j ? 1 : 1/2.
The implicit summations above run from 1 to n when we number the coordinates thus:
<x^{0}, x^{1}, x^{2}, ... x^{n}>, barycentric coordinates are redundant and we omit the 0th here.
The ball center is at vertex 0.
That is tantamount to taking the n edges from the vertex at our ball center as basis vectors for our oblique coordinate system.
We define the altitude of a simplex as the distance of a vertex from the opposite face.
The vertex is at x^{i} = 0 and the closest point in the opposite face in our regular n-simplex is x^{i} = 1/n.
Δx^{i} = 1/n.
Altitude = √(g_{ij}Δx^{i}Δx^{j}) = √((n + n*(n-1)/2)*(1/n)*(1/n))
= √((1 + 1/n)/2).
For 24D the altitude = √(25/48) = .72168 . This is enough bigger than 1/2, for large n, that increasing r by that ratio substantially increases r^{n} and our Monte Carlo efficiency accordingly.
To select a number X in (0, 1) with a pdf (probability density function) proportional to x^{n}, compute X = u^{1/(n+1)} where u is chosen from U{0, 1}. This selects a slice which is a simplex whose edges are (1−X) times the edge of the sliced simplex.
Taking the ball’s origin to be at vertex 0 leaves us the task of deciding which sample points are in the ball.
In the rest of this page i and j range from 1 thru 24.
We evaluate g_{ij}y^{i}y^{j}.
We split g_{ij} = δ_{ij}/2 + 1/2 where δ_{ij} = i==j ? 1 : 0.
If r is the distance of the random point from the ball center then
r^{2} = g_{ij}y^{i}y^{j}
= (δ_{ij}/2 + 1/2)y^{i}y^{j}
= δ_{ij}y^{i}y^{j}/2 +
Σ_{i}Σ_{j}y^{i}y^{j}/2
= Σ_{j}(y^{j})^{2}/2
+ (Σ_{i}y^{i})(Σ_{j}y^{j})/2.
Σ_{j}y^{j}= 1 − y^{0}
since the sum of the n+1 coordinates is 1.
We come thus to 2r^{2}
= Σ_{j}(y^{j})^{2}
+ (1 − y^{0})^{2}.
Here is code using this scheme to pick points in an n-simplex and report what fraction is within the n-ball centered at a vertex and tangent to the opposite face.
We now need the content of the n-simplex and n-ball. This Scheme program indicates that the determinant, g, of our oblique metric tensor is (n+1)2^{−n}. The content of a parallelepiped with basis vectors as edges is √g, and the simplex content is (√g)/n!. The content of our regular unit n-simplex is thus 2^{−n/2}√(n+1)/n!. The content of the n-ball is r^{n}π^{n/2}/(n/2)!.
Let “s” be the regular unit n-simplex. Let “b(r)” be the ball (set of points) of radius r and center at vertex 0 of s. Let “c(t)” be the content (n-dimensional volume) of point set t. Let a_{n} = √((1 + 1/n)/2), be the altitude of s (distance between vertex and opposite face). b(a_{n}) is the ball that is tangent to face 0. Our statistics show that when n=24, c(b(a_{n})∩s)/c(s) ≅ .6565 . c(s) = 2^{−n/2}√(n+1)/n!. c(b(a_{n})) = a_{n}^{n}π^{n/2}/(n/2)! .
We want the fraction of the ball in the simplex:
c(b(a_{n})∩s)/c(b(a_{n})).
For n=24:
c(s) = 10^{−27}1.967453090
a_{24} = .7216878366
c(b(a_{24})) = 10^{−7}7.688591115385
c(b(a_{n})∩s) = 10^{−27}1.2916
c(b(a_{n})∩s)/c(b(a_{24}))
= A^{24}_{24} = 10^{−21}1.67989
α^{24}_{24} = 10^{−23}7.7795
angle diameter = (α^{24}_{24})^{1/23} = 0.1093
n | c(s) | c(ball) | A^{n}_{n} | α^{n}_{n} |
2 | .4330 | 2.356 | .1666 | 1.047 |
3 | .117851 | 2.28009 | .438905 | .551544 |
6 | 4.59332e-04 | 1.02577 | 3.40688e-04 | 1.05635e-02 |
12 | 1.17613e-10 | 3.37256e-02 | 2.43148e-09 | 3.89599e-08 |
24 | 1.96745e-27 | 7.68859e-07 | 1.68101e-21 | 7.78474e-23 |