Hacker News Reader

Comment by lutorm | Hacker News Reader

Nice. But of course, shuffling a deck of cards does not even come close to completely randomizing the sequence compared to the previous ordering (especially if you are a crappy shuffler like me). Thus the sequences are correlated, so it's much more complicated to determine how likely it is to get a repeated configuration.

View on HN

Actually, a deck of card is random after 7 shuffles.

http://en.wikipedia.org/wiki/Shuffling#Randomization

Sort of, depending on what you mean by random. The article seems to imply the uniform distribution on all 52! orders, which 7 shuffles won't get you. For example, you can't reverse a deck with 7 shuffles. There are bets you can put on a deck that's been shuffled 7 times that pay better than the same bet on a uniformly selected order.

Yeah, that phrase "truly random" in the wikipedia page is misleading. At least they do include in the references a link to Bayer and Diaconis' paper. What the paper says is that (for a certain mathematical model of the riffle shuffle, which experimentally seems to match actual results produced by human riffle shufflers) if you measure the total variation distance d between the probability distribution of the order you get after k shuffles and the uniform distribution on all 52! orders, you get d=1 for k=1,2,3,4 (i.e., maximally far in total variation distance from uniform), d=0.924 for k=5, and d drops off exponentially after that:

  k     5     6     7     8     9    10
  d 0.924 0.624 0.334 0.176 0.085 0.043

The total variation distance is an upper bound for the absolute difference in probability over all subsets of permutations.

In particular, we can consider the set:

   U = {all permuations that have never been seen by a human}

The counting arguments in the article lead us to conclude that the uniform probability of U is very close to 1, i.e. almost all permuations have never been obtained by a human shuffle. The Bayer-Diaconis result implies that for certain types of shuffles the probability of ending up in U is at least

   1 - (the total variation distance above)

So for 8 shuffles, we have a probablity of at least 82.4% of landing in U. This is considerably weaker than "every shuffle is unique".

Actually, I think lutorn's point is that most people (including him) do not do a full riffle shuffle when they set out to shuffle cards, thus preserving the order of segments of the cards.

That is indeed lutorm's point.

But the shuffling model used in the Diaconis and Bayer paper that the reply referred to (the "7 shuffles to randomize" result) takes that into account. In particular, the shuffling model gives reasonably high probability to "imperfect" riffle shuffles that take several cards from the left pile and then several cards from the right pile.

This model is on the first page of the paper

http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?vi...

Basically, you split the cards at random, and then you draw sequentially at random from the two piles with probability L/(L+R) versus R/(L+R) (where L is the number of cards remaining in the left pile), to assemble the new deck. This will allow shuffle sequences that take a run from the left and then a run from the right.

As people above have noted, of course the "randomization" of the deck is not perfect after 7 shuffles. But for lots of Markov processes, including this one, the distance of the shuffled deck to the uniform distribution on all decks tends to zero exponentially fast. So you get a quick change-over from "not random at all" to "very random". See table 3 of the paper.

Persi Diaconis (http://www-stat.stanford.edu/~cgates/PERSI/), to whom this result is partly due, is a legend in mathematical probability. How many math professors are bona fide magicians?

even if you're preserving blocks of 3, 17! is a big number. it's not 10^44, but still, 10^14 is pretty big.

How many amateurish shuffles would it take to randomize a deck?

It's a 10 letter password in [a-z]. 8 letter in [A-Za-z]. It's 47 fair coin flips.

I do use the cards metaphor for passwords: http://github.com/gaiustech/MkPasswd

Or 1 deck per day for 7 billion people for 40 years.

The first 10 or so shuffles of a new deck of cards may be relatively common, but after you put a deck of cards away you are not going to reorder it. Most aged decks are therefore going to be completely unique in their ordering.

The only people who use new decks frequently are casinos, and they have very good shuffling machines. It is likely that every deck dealt in a casino is unique.

I don't know, I end up reordering cards often enough when trying to figure out which card is missing, or because I just won a game of solitaire or what not.

If that's the case, which orders are more common? Do decks come in a set order? Assuming they do, I guess imperfect shuffling would result in orderings influenced by that original order. Of course, once you cut the deck a few times, I would think any statistical influence from the original ordering would be nullified.

What I meant was that after shuffling, all orders are not equally likely. The ones that are "close" to the previous one will be a lot more likely. That probably doesn't change the conclusion that it's "very unlikely" that two independent decks are shuffled into the same seqeunce, but it sure means that the chance of getting the same sequence back again after shuffling the same deck is a lot larger than 1e-89.

> Of course, once you cut the deck a few times, [...]

Do you mean to do the cuts one after another?

Reply on news.ycombinator.com