# Random Shuffle - expected distributions **URL:** \ **Category:** Factual Questions\ **Created:** [November 6, 2019, 7:45am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067 "2019-11-06T07:45:57Z")\ **Posts on this page:** 9\ **Page:** 4
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 10, 2019, 1:40pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/61 "2019-11-10T13:40:55Z")
OK, I can see how a 25% chance needs less than 2 bits on average, because half the time, you can stop after the first bit, and not need to call the second one at all. But I can’t see how you could do it in less than 1 bit on average, because that means that you’d sometimes be using zero bits, and how do you decide if you’re in the zero-bit case without using any randomness? Unless you’re referring to a large number of such “biased coin flips” in series, and we’re using extra entropy left over from one of the previous trials, I suppose. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 10, 2019, 2:22pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/62 "2019-11-10T14:22:38Z")
> [@Chronos](#): > > OK, I can see how a 25% chance needs less than 2 bits on average, because half the time, you can stop after the first bit, and not need to call the second one at all. But I can’t see how you could do it in less than 1 bit on average, because that means that you’d sometimes be using zero bits, and how do you decide if you’re in the zero-bit case without using any randomness? > > Unless you’re referring to a large number of such “biased coin flips” in series, and we’re using extra entropy left over from one of the previous trials, I suppose. If your question is, what if “H” has probability 25% and “T” has probability 75%, and you want to represent a sequence of coin flips using a string of bits, then you can do it using a simple arithmetic encoding. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 10, 2019, 4:00pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/63 "2019-11-10T16:00:35Z")
> [@DPRK](#): > > If your question is, what if “H” has probability 25% and “T” has probability 75%, and you want to represent a sequence of coin flips using a string of bits, then you can do it using a simple arithmetic encoding. +++ The _optimal such code will use 0.811278124459132864 bits on average, via a formula attributed to Claude Shannon, or-.25l(.25) - .75_l(.75) nats Arithmetic coding converts biased flips to bits (“50-50 bits”). We need the inverse problem: converting bits to biased flips. As I mentioned above (“in fact barely 0.811 bits are needed”) _The_ library function for that is essentially optimal. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 10, 2019, 4:22pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/64 "2019-11-10T16:22:01Z")
Call it arithmetic decoding, then. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 10, 2019, 11:01pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/65 "2019-11-10T23:01:20Z")
> [@Chronos](#): > > Yes, Quicksort needs n log(n) in all operations, but that’s because the other operations are proportional to the comparisons. Any sorting routine must use at least n log(n) comparisons, because in order to sort a list, you must (directly or indirectly) determine what order it was in originally, which means you must distinguish one of the n! permutations, which means you need n log(n) bits of information about the original arrangement. > > And yes, it’s true that comparison isn’t actually a constant-time operation, because it in principle takes longer for larger numbers. But for any practical number size, it’s still far quicker than generating a good random bit. A random bit takes far longer than anything that would ordinarily be considered a “fundamental operation”, and so it’s absurd to measure the complexity of a shuffle as a count of anything other than random bits. Sorting _by comparison_ requires Ω(n log n) time. Not all sorting methods use comparisons. Radix sort is a famous example. It’s touted as “linear time” however that ignores the length of the keys. If you process m bit keys in blocks of size b then it takes O(n m/b) time. If m/b is really small then it’s linear. (One good use of radix sort is to sort n things whose keys are between 0 and n. So key size is log n and that’ll fit into a 64 bit word, two in really bad cases.) But if the key size is hundreds of bytes then things start looking very non-linear. Now, about comparisons being non-constant. If you do something like Mergesort and maintaining how “far in” a comparison goes before hitting a mismatch on two consecutive keys in a sublist you can save a lot of comparison time by using that measure to resume comparisons when merging lists. The total comparison time falls quite dramatically. But the nature of the data Rules All. I would point out to my students that while the name field in the class roster is quite long, there would typically be only a handful of names that agree on two letters and rarely any that agree on 3 letters. So comparisons are fast here. OTOH, a ton of stuff like part numbers tend to have similar prefixes and mostly differ in the last symbols. So radix sort starts off really doing a lot of useful work. But then it starts wasting time, too. So a mixed approach is best. There are a ton of tricks one can use to tweak sorting that the common undergrad Algorithms class doesn’t cover. I.e., there is no one “best” sorting method\*. One has to be very careful in extrapolating sorting algorithms of one type to another domain. And you are unreasonably hung up on certain bit operations _but not others_. Either you count bits on _everything_ (and get absurd results) or you are practical and consider log n and such size word operations that are built in on computers to be constant time (and get sane results). Look at [WELL](https://en.wikipedia.org/wiki/Well_equidistributed_long-period_linear) and similar RNGs. A constant number of single word operations to generate the next word. - That goes for “Quicksort”. It’s okay on some things. Nothing special on others. YMMV applies. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 11, 2019, 12:12am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/66 "2019-11-11T00:12:54Z")
Doesn’t radix sort depend on an assumed distribution of the objects to be sorted? Like, if you were sorting names, but by some fluke you had 50 names starting with A and only ten for all other letters combined (and didn’t know that from the outset), then radix sort would perform poorly. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 11, 2019, 3:20pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/67 "2019-11-11T15:20:51Z")
> [@Chronos](#): > > Doesn’t radix sort depend on an assumed distribution of the objects to be sorted? Like, if you were sorting names, but by some fluke you had 50 names starting with A and only ten for all other letters combined (and didn’t know that from the outset), then radix sort would perform poorly. A vanilla Radix sort doesn’t care about the distribution. The longer the keys the worse it goes. There are a ton of adaptations to speed things up in certain cases. Buckets and all that. And then the distribution starts to matter. ---
**Author:** ![Jim\_Peebles](https://avatars.discourse-cdn.com/v4/letter/j/5f9b8f/32.png) [@Jim\_Peebles](https://boards.straightdope.com/u/Jim_Peebles)\ **Post date:** [November 12, 2019, 6:04pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/68 "2019-11-12T18:04:16Z")
Check out the research of Persi Diaconis on card shuffling: > **[Persi Diaconis](https://en.m.wikipedia.org/wiki/Persi_Diaconis)** > > Persi Warren Diaconis (/ˌdaɪəˈkoʊnɪs/; born January 31, 1945) is an American mathematician of Greek descent and former professional magician. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University. > He is particularly known for tackling mathematical problems involving randomness and randomization, such as coin flipping and shuffling playing cards. > Diaconis left home at 14 to travel with sleight-of-hand legend Dai Vernon, and was awarded a high school diploma bas... (I haven’t read this thread, and have no interest in doing so, but I searched for his name, and was surprised it hasn’t come up.) ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 12, 2019, 6:13pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/69 "2019-11-12T18:13:41Z")
> [@Jim\_Peebles](#): > > Check out the research of Persi Diaconis on card shuffling: > [Persi Diaconis - Wikipedia](https://en.m.wikipedia.org/wiki/Persi_Diaconis) > (I haven’t read this thread, and have no interest in doing so, but I searched for his name, and was surprised it hasn’t come up.) That paper has been mentioned at least 2 or 3 times in this thread already 🙂 [Previous page](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067.md?page=3)