3
$\begingroup$

I've read online that you need to shuffle a deck of cards at least 7 times (depending on the game being played) for the deck to be 'random enough', i.e. that it is nearly impossible to predict the suit or face of the next card above chance levels.

How can this be evaluated in a general sense? How can we start from a deck of cards and calculate its randomness value? So not working with specific techniques like seeing if the faces are in increasing order or something like that (because then we would need to describe every card counting technique which exists, which is impossible).

$\endgroup$
  • 1
    $\begingroup$ See: statweb.stanford.edu/~cgates/PERSI/papers/bayer92.pdf You essentially find a mathematical model for the riffle shuffle, and then define a measure of randomness. It's tricky, but it is elementary math, and the model of the riffle shuffle is convincingly "close" to actually human shuffling. In practice, it really changes your home bridge game. $\endgroup$ – Thomas Andrews Feb 2 '16 at 17:26
  • $\begingroup$ You are about to go down a rabbit hole... Shuffling cards is mathematically more interesting than one would expect. There are numerous publications on the matter and depending on how exactly you plan to shuffle your deck, various phenomena can occur. See for example arxiv.org/abs/1003.4422 , arxiv.org/abs/1501.05485 and arxiv.org/abs/math/0606031. (Disclaimer: I've read none of them and my knowledge regarding your question is limited to a couple of talks that I've been to.) $\endgroup$ – Stefan Mesken Feb 2 '16 at 17:29
  • $\begingroup$ An "ideal" shuffle gives you all permutations equally likely. You are roughly measuring the distance from an ideal shuffle. More shuffling gets you closer to the ideal shuffle, but you never achieve it. What the result shows is that after $7$ shuffles, additional shuffles start getting closer much more slowly, so the payoff for continuing to shuffle is negligible. But there is a noticeable difference between six and seven. $\endgroup$ – Thomas Andrews Feb 2 '16 at 17:31
  • $\begingroup$ True story. At a bridge tournament, we pulled out cards to play a hand, and I saw it was a hand we'd played the last round. So, we threw the cards together, and I shuffled them. On about the fifth shuffle, the man on the right was getting impatient, so I told him about this result. I finished shuffling, and dealt him an eight card suit, a five card suit, and two voids. Afterwards, he said, "That was like one of those computer-generated hands." Precisely. :) $\endgroup$ – Thomas Andrews Feb 2 '16 at 17:38
  • $\begingroup$ You can't measure the 'randomness of a given deck of cards,' and that is not what the proof does. The randomness is a measure of the whole probability function, not a single permutation. $\endgroup$ – Thomas Andrews Feb 2 '16 at 18:21
2
$\begingroup$

There is no "measure" like the one you are looking for. The proof establishes a measure of the randomness of a probability function on all permutations, not a measure of the randomness of an individual permutation/configuration of the deck. No individual deck configuration is "more random" than another in any sense that is meaningful for probability and statistics.

Rather, we are measuring how far a probability function is away from an "ideal" probability function.

Given a finite set $X$ and a probability function $p:X\to\mathbb R^{\geq 0}$, we can define the distance from that probability function to the uniform probability function as a vector distnce. If $X=\{x_1,\dots,x_N\}$, then treat $p$ as the vector $(p(x_1),p(x_2),\dots,p(x_N))$ and compute the Euclidean distance of that vector to $(1/N,1/N,\dots,1/N)$, the uniform probability vector.

You might think that measure is arbitrary, but it is actually closely related to the "standard deviation." It is a remarkably useful measure of how far from "uniform" a probability function is.

(I'm not sure this distance is the distance used in the paper, I forget, but it is a useful example of the type of distance used to measure "How close to uniform randomness is this random variable?")

Now, in this case, you have $N=52!$, because $X$ is the space of all possible permutations of the cards. $52!$ is a huge number, and you are not going to be able to write out the vectors.

But that doesn't mean you can't compute estimates for this distance.

The model for $X$ in shuffling is the group of permutations $\Sigma_{52}$. And a single riffle shuffle has a probability function $r:\Sigma_{52}\to\mathbb R^{\geq 0}$ which is mostly zero - that is, most permutations cannot result from a single riffle shuffle. But the fact that $X=\Sigma_{52}$ is a group lets us do clever math to deal with repeated riffle shuffles. And we can get good estimates for our measurement.

The number of riffle shuffle outputs is roughly $2^{52}=4.5\times 10^{15}$. So the number of different outputs from $4$ riffle shuffles is at most $2^{52\cdot 4}=4.1\times 10^{62}<52!\approx 8.1\times 10^{67}$. Indeed, only one in ever rougly $20,000$ permutations can even be output after four shuffles. So if you want a chance for every permutation after shuffling, you'd have to shuffle at least $5$ times. But the riffle shuffle isn't uniform - each of its roughly $2^{52}$ outputs are not equally likely. You are likely, for example, to initially cut closer to the middle of the deck than near an end.

What the proof shows is that you get significantly closer to the ideal with each shuffle up to $7$, and then the progress slows. Additional shuffles do improve the measure, but not by much.

$\endgroup$
  • $\begingroup$ thanks for the great explanaition; I do still have a question: what about in other shuffling techniques? Is there a systematic way to calculate the upper bound or do you need to run simulations? For example: a technique used by a lot of people is to take the top few cards (say 10) of a deck and place them at the bottom and doing this for some iterations (I know: this method sucks). Is there a systematic way that I could calculate how many times this should happen for the deck to be shuffled properly. $\endgroup$ – Héctor van den Boorn Feb 2 '16 at 21:05
  • $\begingroup$ The riffle shuffle turns out to be one of the easier ones to analyze, but a lot of other shuffles have been studied. That particular "top cards moved to bottom" technique is notoriously bad - requiring, if I recall correctly, hundreds of interations to get good randomness. @HéctorvandenBoorn $\endgroup$ – Thomas Andrews Feb 2 '16 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.