That's what the article suggests.
Clicking through to SO explains it (but assumes you can read numpy). The `s * u` and `t * v` (where `u` and `v` are vectors) are the transformation from right-triangle (half of square) to triangle (half of parallelgram).
Affine transformations just scale the probability density by a constant, so a uniform distribution is still uniform.
You can think of it this way. There's a density function on the shapes in question. Whenever you transform the 2d space, you have to adjust the density at the same time to preserve "volume" (area times density).
Non-linear transforms, such as interpreting a square as polar coordinates to obtain a disk, will expand or shrink area differently in different parts of the space, which means that if you start with a uniform density, you end up with a non-uniform density. But linear/affine transforms affect area the same everywhere in the space, and so if the density is uniform to begin with, it remains uniform.
const r = sqrt(random()) * radius;
const theta = random() * TAU;For an n-simplex, start by generating a random point in an n-cube (i.e. n uniform random numbers between 0 and 1).
Next, sort the coordinates. This leaves you with a chain `0 <= c_1 <= ... <= c_n <= 1`.
Taking successive differences from this chain gives you n+1 numbers `d_j` (`0 <= j <= n`) that sum to 1.
Finally, the random point in the n-simplex is just `j_0 v_0 + ... + j_n v_n`, where `v_j` are the vertices of the simplex.
It's not hard to verify that this produces the accept-flip technique in dimension 2. As for why it's uniform: the sorting step is mapping a coordinate in the cube into a fundamental domain for the action of the symmetric group (which breaks the cube into a number of simplices of equal size); the other steps are linear maps, which therefore preserve the uniformity.
Your picture is a great geometric way to think about riffle shuffling. Your n-simplex represents a sorted deck of n cards. Choosing a point uniformly at random in this simplex makes the needed choices all at once to predetermine an arbitrary number of riffle shuffles. Think of k riffle shuffles as a single 2^k shuffle (as if you had 2^k hands); we can now study an "a-shuffle". Scale the n-simplex by a factor of a. Where does our random point end up? Either view all of space as tiled by your n-cubes, or reduce all coordinates mod 1. Either way the random point ends up in some n-simplex described by a different (or the same) order (mod 1) of the coordinates. That's your shuffle.
For a single shuffle of two cards, doubling the 2-simplex ("up-triangle") covers three up-triangles and one down-triangle, so the odds of reversing the cards is 1 in 4. This makes sense if you imagine two "stowaway" cards face up, placed at random in a face-down deck. Shuffling the deck, to reverse these cards they can't both be in the same packet, and being in different packets only reverses them half the time.
Increasing "a" for two cards, one sees the up and down-triangle counts converge to a 1:1 ratio. The error "fringe" looks like a numerical integration error.
For a triangle, drawing α and β uniform over [0,1) the barycentric coordinates given by (1-sqrt(α), sqrt(alpha)(1-β), βsqrt(alpha)) is uniform over the triangle. No rejection and no test for flipping.
For simplices (triangle, tetrahedron, 5-cell etc) barycentric coordinates obtained by drawing uniformly from (0,1] taking a log and normalizing will be uniform within the simplex.
I wrote about this and other related sampling below.
I think this should be a uniform distribution by symmetry. Obviously the boundaries of the triangles never get picked but that's a measure 0 set.
ok123456•1h ago
simlevesque•32m ago