="Warren Smith" <warren.wds@gmail.com> Peter Ryan: If you have a list of randomly ordered strings we have the following provable asymmetry:

1) choosing an element at random

2) finding a given string in the set.

Interesting, but it also somehow feels a bit like an asymmetry between apples and oranges, although I can't quite articulate why. First, they don't seem to be quite inverses of eachother. Closer might be something like: 1) Given a list, make a copy, but in random order (each of the n! possible outputs being equally likely) 2) Given the randomized list, return its inverse permutation Or perhaps even something like 2') Verify that the allegedly randomized list IS in fact a permutation Also, there seems to be something a little slippery about the information theoretical accounting around the concept of "given a randomized list". Shuffling and sorting would seem to be "morally" inverse, but it's apparently not straightforwardly symmetrical: Consider sorting a list. Some number, on average O(n log n), of comparisons are executed, and no matter which permutation is input, the output will be in order. Clearly too a list of the decisions made during the sorting process could be fed back into the sorter in reverse to recover the input list. But imagine trying to use this to implement the inverse process, shuffling an ordered input fairly, by injecting random coin flips where the sorting algorithm executes comparisons. These flips aren't simply 50-50; each has to be custom biased in some subtle way to get equiprobable shuffling. This makes sense because injecting 2^(n log n) bits should produce n^n outcomes, and there are only n! possible orders, so the outputs can't be perfectly evenly distributed for n>1. Another way to look at it is that the number of possible distinct "transcripts" output by any sorter must number n!, and although each comparison must yield SOME information (else why do it?) since n! is never a power of two the comparisons are not "radiating" whole bits as they freeze out the entropy in the shuffled list. So I can't decide: are sorting and shuffling really true inverses with different costs, or is some assumption being hidden under the rug?