10 ms·

Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits): 1. Randomly assign

by orlp 2y ago

Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits): 1. Randomly assign each element to list A or list B. 2. Recursively shuffle lists A and B. 3. Concatenate lists A and B. To prove it's correct, note that assigning a random real number to each element and sorting based on that number is an unbiased shuffle. Then we note the above does in fact do that by considering the fractional base-2 expansion of the random numbers, and noting the above is in fact a base-2 radix sort of these numbers. We can sort these random real numbers even though they have an infinite amount of random bits, as we can stop expanding the digits when the prefix of digits is unique (which corresponds to the event that a list is down to a single element). I call the above algorithm RadixShuffle. You can do it in base-2, but also in other bases. For base-2 you can make it in-place similar to how the partition for Quicksort is implemented in-place, for other bases you either have to do it out-of-place or in two passes (the first pass only counting how many elements go in each bucket to compute offsets). The above can be combined with a fallback algorithm for small N such as Fisher-Yates. I believe even though the above is N log N it can be faster than Fisher-Yates for larger N because it is exceptionally cache-efficient as well as RNG-efficient whereas Fisher-Yates requires a call to the RNG and invokes an expected cache miss for each element. --- Another fun fact: you can turn any biased memoryless coin into an unbiased one with a simple trick. Throw the coin twice, if it gives HH or TT you throw away the toss, if it's HT or TH you use the first toss as your unbiased coin. This works because if p is the probability that heads comes up we have: HH: p^2 HT: p(1-p) TH: (1-p)p TT: (1-p)^2 Naturally, p(1-p) and (1-p)p are equiprobable, thus if we reject the other outcomes we have distilled an unbiased coin out of our biased coin.

amelius 2y ago
Regarding your second fact: if we need N tosses, then is your method the most efficient one?
- orlp 2y ago
  Looking into it a bit, it appears that this particular fun fact was first thought of (or at least put to paper) by von Neumann in "Various techniques used in connection with random digits" in 1951. Yuval Peres proves in "Iterating von Neumann's procedure for extracting random bits" that if N goes to infinity it approaches the entropy limit. So for particular small choices of N there might be more clever schemes, but for large N you can't do a whole lot better.
  - deleted 2y ago
    [deleted]
thaumasiotes 2y ago
> Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits): How does this compare to a regular Knuth shuffle where, since you only have a 1-bit generator, when you need (for example) an integer between 0 and 23, you treat the bits you generate as the binary expansion of a real number in [0, 1), and generate them until floor(24*n) is unambiguous? (Obviously, the random number generation is more conceptually complex, but aside from that.)
- slaymaker1907 2y ago
  You need at least nlog(n) bits for the same reason as regular shuffling. There are n! permutations and it therefore takes log(n!) bits to uniquely describe a shuffle. nlog(n) is the same as log(n^n) which is obviously greater than log(n!) (this is Stirling’s approximation).
  - thaumasiotes 2y ago
    OK, but I was kind of hoping for a treatment that involved the workings of one or both algorithms. They are subject to the same theoretical lower bound, yes. Do they have any advantages or disadvantages relative to each other? Does one of them do a much better job reaching the theoretical bound?
    - orlp 2y ago
      This paper goes in way more detail than you'd likely ever want on that topic: https://dl.acm.org/doi/10.1145/3009909 https://dl.acm.org/doi/10.1145/3009909.
      - slaymaker1907 2y ago
        It kind of makes me mad that the very simple RS algorithm (divide and conquer) isn't more widely known given that it's so easy to implement and that it's actually parallelizable unlike Fisher-Yates. I think it's also better pedagogically since you can easily do it with a deck of cards and a coin or some dice while Fisher-Yates is pretty unwieldy for anything beyond very small lists.
jmount 2y ago
Nice shuffle, and explanation. I like how the "no items assign to one of the lists" "wasted" recursions throws out coin flips (which is needed to get the uniform permutation distribution).
mlochbaum 2y ago
I was able to make a variant of the higher-base version that runs in a single pass, by stopping when one partition fills up and using a different method for the remaining (asymptotically few) elements. I described the idea, which is based on another effort called MergeShuffle, here: https://mlochbaum.github.io/BQN/implementation/primitive/random.html#shuffling https://mlochbaum.github.io/BQN/implementation/primitive/ran... And it is better when N gets large. My implementation set the cutoff at 2^19 elements, although the effect isn't too big for a few more powers of two. Here's the main radix loop: https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysfn.c#L476-L486 https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysf...
- orlp 2y ago
  I found another in-place approach which also does a higher-base version described here: https://arxiv.org/pdf/2302.03317 https://arxiv.org/pdf/2302.03317, with an open source implementation: https://crates.io/crates/rip_shuffle https://crates.io/crates/rip_shuffle. Might want to compare it with your version.
  - mlochbaum 2y ago
    Performance-oriented library with no benchmarking instructions, fun. I get 850ms to shuffle 32-bit integers up to 1e8 with this library versus 400ms in BQN (•rand.Deal•_timed 1e8). However, BQN also has a large advantage at smaller sizes, such as 425us versus 120us for 1e5 elements, so a lot of this may be the random number generator. I haven't figured out how to get PCG working yet. BQN uses wyrand which is faster but I now know has quality issues (can't even generate every possible output; I need to update the page I linked...). It's substantially the same algorithm so any differences would just be down to implementation details. Other than multi-threading which BQN doesn't do. The usage is also a little different as BQN generates shuffled integers directly; generating the integers is 100ms of the 850ms for rip_shuffle but I'm not sure whether it makes sense to subtract that or not.
    - mlochbaum 2y ago
      Not quite the same, rip_shuffle does have some contortions to be able to run in-place (I'm still scratching my head about who's running these sorts of high-performance algorithms with no auxiliary memory available), so if those cost anything they could contribute to the difference.
zaik 2y ago
> you can turn any biased memoryless coin into an unbiased one with a simple trick This trick is mentioned in the article towards the end.
- orlp 2y ago
  Ah I looked over it in my skim.
slaymaker1907 2y ago
I implemented this for GPUs back in college and you’re right, it’s really good for parallelism. This shuffle is also great if you want to do a completely unbiased shuffle with real cards. Fischer-Yates is impractical to do with a real deck of cards.
- skybrian 2y ago
  It seems like with real cards, it would take too many coin flips to be practical?
tzs 2y ago
That reminds me of a method for rolling a dN if all you have is a dM. Divide the interval [0, 1) into M equal pieces, [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1). Use the dM to generate a real number in [0, 1). If that real number is in the interval [(k-1)/N, k/N), your simulated dN roll is k. To generate a real number in [0, 1) with the dM you simply roll the dM an infinite number of times, and take each roll as a successive base M digit in a base M fraction 0.abcd... where a, b, c, d, etc are base M digits. You don't actually have to roll an infinite number of times. You can stop when you have enough digits to tell which interval the number is in. For example if you were trying to roll a d12 using a d10, and the first two d10 rolls are 0 and 7 you can stop, because all base 10 numbers that start with 0.07 are in [0, 1/12). If the first two rolls had been 0 and 8 you would have to keep rolling, because although 0.08 is in [0, 1/12) subsequent rolls could change that because 1/12 = 0.083333(3). For any particular N and M this can be turned into a state graph where you start at the start node and then select links to follow with your dM until you reach a terminal node labeled with the simulated dN value. Here are such graphs for rolling a d7 with a d2 [1], a d7 with a d6 [2], and a d5 with a d8 [3]. [1] https://imgur.com/a/Qk2kexn https://imgur.com/a/Qk2kexn [2] https://imgur.com/a/EhW7lkc https://imgur.com/a/EhW7lkc [3] https://imgur.com/yFmHbnp https://imgur.com/yFmHbnp
- justinpombrio 2y ago
  Hah, this brings back memories. I remember working this out with other students at ARML.
akoboldfrying 2y ago
This is a nice, practical algorithm. Beware though that in theory it can take an unbounded amount of time, since in order for it to make progress it must generate at least one heads and one tails on the input, and although runs of all-heads or all-tails become exponentially unlikely as input size increases (or as the number of passes performed on a fixed-size input increases), there's still no guarantee that a mixed run will happen before any fixed amount of computation has been done. If it's implemented to run in the typical "depth-first sequential" manner of a recursive algorithm, in which each problem generates its own subproblems, solves them all, and then immediately continues execution until it is itself solved, then it is guaranteed to eventually terminate, since the only way to stall progress forever in this situation would be an infinite, uninterrupted sequence of one outcome (e.g., heads), and that would contradict the assumption that P(heads) = 0.5. OTOH, if a "breadth-first" computation was used, in which all subproblems at a given recursion depth are solved in sequence before any higher-level subproblems, the algorithm could run forever: The top-level problem could produce a mixed run, resulting in two equal-sized subproblems, each of which never makes any progress due to one subproblem always getting all-heads, the other always all-tails.
- orlp 2y ago
  Any unbiased algorithm that uses an unbiased coin to shuffle n > 2 elements must be potentially unbounded. Proof: there are n! possible permutations. If the algorithm always finishes within k coin tosses then there are 2^k possible outcomes. For n > 2 we have that n! does not divide 2^k, so not all outcomes can be equiprobable.
  - klyrs 2y ago
    You proved that not all outcomes are equiprobable, not that they're unbounded.
    - LegionMammal978 2y ago
      This is a proof by contradiction: it shows that any bounded algorithm doesn't have equally probable outputs, i.e., that it is necessarily biased, contradicting our assumption that it is unbiased. Therefore, an unbiased, bounded algorithm cannot exist (for n > 2): any algorithm is necessarily either biased or unbounded.
pbsd 2y ago
This is the Rao-Sandelius shuffle [1]. [1] https://doi.org/10.1145/3009909 https://doi.org/10.1145/3009909

by orlp 2y ago

amelius 2y ago

Regarding your second fact: if we need N tosses, then is your method the most efficient one?

orlp 2y ago
Looking into it a bit, it appears that this particular fun fact was first thought of (or at least put to paper) by von Neumann in "Various techniques used in connection with random digits" in 1951. Yuval Peres proves in "Iterating von Neumann's procedure for extracting random bits" that if N goes to infinity it approaches the entropy limit. So for particular small choices of N there might be more clever schemes, but for large N you can't do a whole lot better.
- deleted 2y ago
  [deleted]

thaumasiotes 2y ago

> Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits): How does this compare to a regular Knuth shuffle where, since you only have a 1-bit generator, when you need (for example) an integer between 0 and 23, you treat the bits you generate as the binary expansion of a real number in [0, 1), and generate them until floor(24*n) is unambiguous? (Obviously, the random number generation is more conceptually complex, but aside from that.)

slaymaker1907 2y ago
You need at least nlog(n) bits for the same reason as regular shuffling. There are n! permutations and it therefore takes log(n!) bits to uniquely describe a shuffle. nlog(n) is the same as log(n^n) which is obviously greater than log(n!) (this is Stirling’s approximation).
- thaumasiotes 2y ago
  OK, but I was kind of hoping for a treatment that involved the workings of one or both algorithms. They are subject to the same theoretical lower bound, yes. Do they have any advantages or disadvantages relative to each other? Does one of them do a much better job reaching the theoretical bound?
  - orlp 2y ago
    This paper goes in way more detail than you'd likely ever want on that topic: https://dl.acm.org/doi/10.1145/3009909 https://dl.acm.org/doi/10.1145/3009909.
    - slaymaker1907 2y ago
      It kind of makes me mad that the very simple RS algorithm (divide and conquer) isn't more widely known given that it's so easy to implement and that it's actually parallelizable unlike Fisher-Yates. I think it's also better pedagogically since you can easily do it with a deck of cards and a coin or some dice while Fisher-Yates is pretty unwieldy for anything beyond very small lists.

jmount 2y ago

Nice shuffle, and explanation. I like how the "no items assign to one of the lists" "wasted" recursions throws out coin flips (which is needed to get the uniform permutation distribution).

mlochbaum 2y ago

I was able to make a variant of the higher-base version that runs in a single pass, by stopping when one partition fills up and using a different method for the remaining (asymptotically few) elements. I described the idea, which is based on another effort called MergeShuffle, here: https://mlochbaum.github.io/BQN/implementation/primitive/random.html#shuffling https://mlochbaum.github.io/BQN/implementation/primitive/ran... And it is better when N gets large. My implementation set the cutoff at 2^19 elements, although the effect isn't too big for a few more powers of two. Here's the main radix loop: https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysfn.c#L476-L486 https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysf...

orlp 2y ago
I found another in-place approach which also does a higher-base version described here: https://arxiv.org/pdf/2302.03317 https://arxiv.org/pdf/2302.03317, with an open source implementation: https://crates.io/crates/rip_shuffle https://crates.io/crates/rip_shuffle. Might want to compare it with your version.
- mlochbaum 2y ago
  Performance-oriented library with no benchmarking instructions, fun. I get 850ms to shuffle 32-bit integers up to 1e8 with this library versus 400ms in BQN (•rand.Deal•_timed 1e8). However, BQN also has a large advantage at smaller sizes, such as 425us versus 120us for 1e5 elements, so a lot of this may be the random number generator. I haven't figured out how to get PCG working yet. BQN uses wyrand which is faster but I now know has quality issues (can't even generate every possible output; I need to update the page I linked...). It's substantially the same algorithm so any differences would just be down to implementation details. Other than multi-threading which BQN doesn't do. The usage is also a little different as BQN generates shuffled integers directly; generating the integers is 100ms of the 850ms for rip_shuffle but I'm not sure whether it makes sense to subtract that or not.
  - mlochbaum 2y ago
    Not quite the same, rip_shuffle does have some contortions to be able to run in-place (I'm still scratching my head about who's running these sorts of high-performance algorithms with no auxiliary memory available), so if those cost anything they could contribute to the difference.

zaik 2y ago

> you can turn any biased memoryless coin into an unbiased one with a simple trick This trick is mentioned in the article towards the end.

orlp 2y ago
Ah I looked over it in my skim.

slaymaker1907 2y ago

I implemented this for GPUs back in college and you’re right, it’s really good for parallelism. This shuffle is also great if you want to do a completely unbiased shuffle with real cards. Fischer-Yates is impractical to do with a real deck of cards.

skybrian 2y ago
It seems like with real cards, it would take too many coin flips to be practical?

tzs 2y ago

That reminds me of a method for rolling a dN if all you have is a dM. Divide the interval [0, 1) into M equal pieces, [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1). Use the dM to generate a real number in [0, 1). If that real number is in the interval [(k-1)/N, k/N), your simulated dN roll is k. To generate a real number in [0, 1) with the dM you simply roll the dM an infinite number of times, and take each roll as a successive base M digit in a base M fraction 0.abcd... where a, b, c, d, etc are base M digits. You don't actually have to roll an infinite number of times. You can stop when you have enough digits to tell which interval the number is in. For example if you were trying to roll a d12 using a d10, and the first two d10 rolls are 0 and 7 you can stop, because all base 10 numbers that start with 0.07 are in [0, 1/12). If the first two rolls had been 0 and 8 you would have to keep rolling, because although 0.08 is in [0, 1/12) subsequent rolls could change that because 1/12 = 0.083333(3). For any particular N and M this can be turned into a state graph where you start at the start node and then select links to follow with your dM until you reach a terminal node labeled with the simulated dN value. Here are such graphs for rolling a d7 with a d2 [1], a d7 with a d6 [2], and a d5 with a d8 [3]. [1] https://imgur.com/a/Qk2kexn https://imgur.com/a/Qk2kexn [2] https://imgur.com/a/EhW7lkc https://imgur.com/a/EhW7lkc [3] https://imgur.com/yFmHbnp https://imgur.com/yFmHbnp

justinpombrio 2y ago
Hah, this brings back memories. I remember working this out with other students at ARML.

akoboldfrying 2y ago

This is a nice, practical algorithm. Beware though that in theory it can take an unbounded amount of time, since in order for it to make progress it must generate at least one heads and one tails on the input, and although runs of all-heads or all-tails become exponentially unlikely as input size increases (or as the number of passes performed on a fixed-size input increases), there's still no guarantee that a mixed run will happen before any fixed amount of computation has been done. If it's implemented to run in the typical "depth-first sequential" manner of a recursive algorithm, in which each problem generates its own subproblems, solves them all, and then immediately continues execution until it is itself solved, then it is guaranteed to eventually terminate, since the only way to stall progress forever in this situation would be an infinite, uninterrupted sequence of one outcome (e.g., heads), and that would contradict the assumption that P(heads) = 0.5. OTOH, if a "breadth-first" computation was used, in which all subproblems at a given recursion depth are solved in sequence before any higher-level subproblems, the algorithm could run forever: The top-level problem could produce a mixed run, resulting in two equal-sized subproblems, each of which never makes any progress due to one subproblem always getting all-heads, the other always all-tails.

orlp 2y ago
Any unbiased algorithm that uses an unbiased coin to shuffle n > 2 elements must be potentially unbounded. Proof: there are n! possible permutations. If the algorithm always finishes within k coin tosses then there are 2^k possible outcomes. For n > 2 we have that n! does not divide 2^k, so not all outcomes can be equiprobable.
- klyrs 2y ago
  You proved that not all outcomes are equiprobable, not that they're unbounded.
  - LegionMammal978 2y ago
    This is a proof by contradiction: it shows that any bounded algorithm doesn't have equally probable outputs, i.e., that it is necessarily biased, contradicting our assumption that it is unbiased. Therefore, an unbiased, bounded algorithm cannot exist (for n > 2): any algorithm is necessarily either biased or unbounded.

pbsd 2y ago

This is the Rao-Sandelius shuffle [1]. [1] https://doi.org/10.1145/3009909 https://doi.org/10.1145/3009909