title: Shuffling algorithm analysis
body: <p>I came across this following analysis of shuffling algorithms:</p>
  <blockquote>
  <p>Q: Given an array of distinct integers, give an algorithm to randomly
  reorder the integers so that each possible reordering is equally
  likely. In other words, given a deck of cards, how can you shuffle
  them such that any permutation of cards is equally likely?</p>
  <p>Good answer: Go through the elements in order, swapping each element with a
  random element in the array that does not appear earlier than the
  element. This takes O(n) time. Note that there are several possible
  solutions to this problem, as well as several good‐looking answers
  that are incorrect. For example, a slight modification to the above
  algorithm whereby one switches each element with any element in the
  array <strong>does not give each reordering with equally probability</strong>.</p>
  </blockquote>
  <p>What I would like to know is why switching each element with any other element in the array does not produce a good shuffle as opposed to using the Knuth shuffle (which is described). Also, how does the Knuth shuffle select values with equal probability? Any math or proof is greatly appreciated.</p>