title: What, if anything, is wrong with this shuffling algorithm and how can I know?
body: <p>Just as background, I'm aware of the <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="noreferrer" title="Fisher-Yates shuffle">Fisher-Yates</a> perfect shuffle.  It is a great shuffle with its O(n) complexity and its guaranteed uniformity and I'd be a fool not to use it ... in an environment that permits in-place updates of arrays (so in most, if not all, <em>imperative</em> programming environments).</p>
  
  <p>Sadly the functional programming world doesn't give you access to mutable state.</p>
  
  <p>Because of Fisher-Yates, however, there's not a lot of literature I can find on how to design a shuffling algorithm.  The few places that address it at all do so briefly before saying, in effect, "so here's Fisher-Yates which is all the shuffling you need to know".  I had to, in the end, come up with my own solution.</p>
  
  <p>The solution I came up with works like this to shuffle any list of data:</p>
  
  <ul>
  <li>If the list is empty, return the empty set.</li>
  <li>If the list has a single item, return that single item.</li>
  <li>If the list is non-empty, partition the list with a random number generator and apply the algorithm recursively to each partition, assembling the results.</li>
  </ul>
  
  <p>In Erlang code it looks something like this:</p>
  
  <pre><code>shuffle([])  -&gt; [];
  shuffle([L]) -&gt; [L];
  shuffle(L)   -&gt;
    {Left, Right} = lists:partition(fun(_) -&gt; 
                                      random:uniform() &lt; 0.5 
                                    end, L),
    shuffle(Left) ++ shuffle(Right).
  </code></pre>
  
  <p>(If this looks like a deranged quick sort to you, well, that's what it is, basically.)</p>
  
  <p>So here's my problem: the same situation that makes finding shuffling algorithms that aren't Fisher-Yates difficult makes finding tools to <strong>analyse</strong> a shuffling algorithm equally difficult.  There's lots of literature I can find on analysing PRNGs for uniformity, periodicity, etc. but not a lot of information out there on how to analyse a shuffle.  (Indeed some of the information I found on analysing shuffles was just plain wrong -- easily deceived through simple techniques.)</p>
  
  <p>So my question is this: how do I analyse my shuffling algorithm (assuming that the <code>random:uniform()</code> call up there is up to the task of generating apropriate random numbers with good characteristics)?  What mathematical tools are there at my disposal to judge whether or not, say, 100,000 runs of the shuffler over a list of integers ranging 1..100 has given me plausibly good shuffling results?  I've done a few tests of my own (comparing increments to decrements in the shuffles, for example), but I'd like to know a few more.</p>
  
  <p>And if there's any insight into that shuffle algorithm itself that would be appreciated too.</p>