Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


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.


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: