Given a permutation , the associated shuffle of a deck of cards, numbered from up to , sends the card in position of the deck to position . For example, the shuffles in Exercise 4 which always fix the top card, correspond to permutations such that .
Let be a probability distribution. Imagine the following game: our opponent takes a fresh deck of cards (in which card number appears in position ) and chooses a permutation using the distribution . He then shuffles the deck according to , and turns over the cards one-by-one. We have to guess the number of each card, before it is shown.
A deterministic guessing strategy will, if we have seen cards , always makes a fixed guess for the card in position . Of the permutations satisfying , exactly also satisfy . Therefore such strategies guess correctly on position in a proportion of shuffles. It follows that, if shuffles are selected uniformly at random, then the expected number of correct guesses is
the -th harmonic number. Note this is independent of our strategy; since we expect uniform shuffling to be unexploitable, this seems reasonable.
Let be the number of correct guesses made if the cards are shuffled according to the permutation . If is the uniform probability distribution on , then the argument above shows that
When we play the game above, our expected number of correct guesses is
The difference measures the degree to which our strategy exploits the opponent’s departure from uniform shuffling. Let be the set of permutations which are preferred by , i.e.
Using the crude bound we get
The variation distance is defined by
Hence , as claimed in the remark. So the variation distance gives a bound on the degree to which we can exploit the depature of from uniform randomness.
If we allow strategies that have a random component then the same bound holds, and the argument above goes through, provided we replace with the expected number of correct guesses when the shuffle is . It is worth noting that this expectation is taken with respect to the `internal’ randomness of our guessing algorithm. It has nothing to do with the probability distribution . It would be interesting to know if there are cases where a random strategy can do better, on average, than a deterministic strategy.
One final example. Suppose that our opponent (wrongly) believes that a good shuffle should not fix any card. If is the probability distribution assigning equal probability to each derangement in then . It seems highly unlikely that any strategy can hope to average anywhere near to correct guesses against this opponent, so in this case at least, the bound we have proved is probably rather weak.