3 ms·

A tidbit here some might be interested in is that a version of the accept-flip method works for simplices of arbitrary dimension. For an n-simplex, start by ge

A tidbit here some might be interested in is that a version of the accept-flip method works for simplices of arbitrary dimension. 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.

Syzygies 1y ago
I coauthored the paper "Trailing the Dovetail Shuffle to its Lair" which solved the GSR model for riffle shuffling in closed form, leading to the recommendation to shuffle a 52 card deck seven times. 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.

Syzygies 1y ago

I coauthored the paper "Trailing the Dovetail Shuffle to its Lair" which solved the GSR model for riffle shuffling in closed form, leading to the recommendation to shuffle a 52 card deck seven times. 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.