CODEWITHSUNDEEP
algorithmrandom
Shankar Kamble
Shankar Kamble

Reputation: 3023

Riffle shuffle algorithm with randomness

The riffle shuffle algorithm is too mechanical and predictable. How would we add some randomness as if a real human was shuffling the cards but still using the riffle method?

Upvotes: 2

Views: 1252

Answers (1)

borrible
borrible

Reputation: 17346

In the paper Shuffling Cards and Stopping Times by Aldous and Diaconis (from the American Mathematical Monthly, 93:5, pp 333-348) the authors looked at how many shuffles are required to randomise a deck of cards. Section 4 of that paper is An Analysis of Riffle Shuffles and they discuss some equivalent formulations for (non-perfect) riffling of cards.

In particular, they quote a model for random riffling shuffling that simulates how "real" people riffle shuffle. Essentially, the deck is split in to two pieces according to a binomial distribution, leaving c cards in one hand and n-c in the other. The cards are then "dropped from a given hand with probability proportional to packet size".

So a simple application will be to assume that your deck is originally split in to two equal pieces and then repeatedly select from which piece the next card comes, with a / (a+b) probability of it coming from the piece of size a and b / (a+b) probability of the piece of current size b.

Upvotes: 4

Related Questions