0

Let's say I implement an algorithm that shuffles a deck by simply swapping any 2 cards. How many times do I need to swap in order to have an even number of chances for any order.

Assume the following pseudocode:

for n=0: n<num_iterations:
  r1 = random(52)
  r2 = random(52)
  swap(card[r1],card[r2])

Assume that the random() function returns a value between 0 and 51 inclusively, with perfectly normal distribution. What value should num_iterations be in order to have the deck with even probabilities across all permutations?

Does it make a difference if r1 and r2 are possibly identical any number of times?

To be clear, the question is not about the algorithm in particular or how to improve it. It is about how to calculate the value num_iterations, such that any bias is statistically insignificant. I understand this is not a good algorithm but if num_iterations where n² say, I'm sure any bias would statistically vanish, but there is likely a lower value than n². What is it? How can it be calculated?

Octopus
  • 111
  • 6
  • Not a duplicate. The answer was edited to clarify. – Octopus Oct 24 '17 at 00:47
  • 1
    The top answer in the linked thread provides "an approximate solution" to the number of iterations required "to make the error acceptably small". AFAICT, that is what you are asking for here. This remains a duplicate. – gung - Reinstate Monica Oct 24 '17 at 01:03

1 Answers1

3

This will actually never converge completely. This process can be modelled as a Markov chain. While asymptotically, the distribution of the orderings will converge to the stationary distribution, which has equal distribution to all card orderings, it will not, after any finite shuffling, be completely random. A simplified version of this problem is included in parts in https://galton.uchicago.edu/~lalley/Courses/313/ConvergenceRates.pdf.

Gijs
  • 3,409
  • 11
  • 18
  • Hmm okay. Even if num_iterations is larger than the size of the *deck* (52) I can see that some cards might remain unshuffled, but surely there is a number where this becomes statistically insignificant, or roughly stated as the odds of a card not being shuffled are the same as a card being shuffled back into place which I know is 1 in 52 for this example. – Octopus Oct 23 '17 at 21:03
  • Yes, there is an upper bound you can prove on for example the total variation between the probability distribution after `n` steps, and the stationary distribution. This is also in the link. – Gijs Oct 23 '17 at 21:12