1
$\begingroup$

The following problem was presented:

We want to start a game with a uniform random permutation of a deck of cards.

Each permutation should appear with probability $1/52!$.

If we want to do it efficiently, it is clear that we can't just choose a random number in range $[1,52!]$ and take the appropriate permutation.

They offered to design a Markov Chain that will simulate some technique of mixing cards.

For example: riffle shuffle or moving card to the top of the deck.

Then because the special Markov chain is irreducible, a-periodic and double stochastic, the stationary distribution will be the uniform one.

My question is why can't we just randomly pick the first card in the permutation (out of 52), then pick the second card (out of 51) and so on. Will it not be a uniformly picked permutation?

$\endgroup$
2
  • $\begingroup$ Google random permutation algorithm. And see stackoverflow.com/questions/7902391/… $\endgroup$ Jun 25, 2017 at 16:53
  • $\begingroup$ What you propose in your last paragraph will give you a uniformly distributed random permutation. Since I have R on this machine, I'd do this: a <- rank(runif(52)) $\qquad$ $\endgroup$ Jun 25, 2017 at 17:14

1 Answer 1

1
$\begingroup$

I'm not sure who "they" refers to in your question, but you're right that just randomly picking the cards one by one will work. This is essentially the Fisher-Yates shuffle in its historic, paper-and-pencil form. For computer use the improvements given at the Wikipedia article (due to Durstenfeld originally, and popularized by Knuth - I've heard this called the "Fisher-Yates-Knuth shuffle") is better (i. e. faster).

A Markov chain method is not really necessary here - the Markov chain methods for sampling random objects from some set are useful when you don't have an explicit algorithm for generating the objects, and are only approximate (although you can get an approximation as good as you want if you wait long enough).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .