StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What about the following? Perform the same procedure as merge sort. When merging, instead of selecting an element (one-by-one) from the two lists in sorted order, flip a coin. Choose whether to pick an element from the first or from the second list based on the result of the coin flip.</p> <p><strong>Algorithm.</strong></p> <pre><code>shuffle(list): if list contains a single element return list list1,list2 = [],[] while list not empty: move front element from list to list1 if list not empty: move front element from list to list2 shuffle(list1) shuffle(list2) if length(list2) < length(list1): i = pick a number uniformly at random in [0..length(list2)] insert a dummy node into list2 at location i # merge while list1 and list2 are not empty: if coin flip is Heads: move front element from list1 to list else: move front element from list2 to list if list1 not empty: append list1 to list if list2 not empty: append list2 to list remove the dummy node from list </code></pre> <p>The key point for space is that splitting the list into two does not require any extra space. The only extra space we need is to maintain log n elements on the stack during recursion. </p> <p>The point with the dummy node is to realize that inserting and removing a dummy element keeps the distribution of the elements uniform. </p> <p><strong>Analysis.</strong> Why is the distribution uniform? After the final merge, the probability <code>P_i(n)</code> of any given number ending up in the position <code>i</code> is as follows. Either it was:</p> <ul> <li>in the <code>i</code>-th place in its own list, and the list won the coin toss the first <code>i</code> times, the probability of this is <code>1/2^i</code>;</li> <li>in the <code>i-1</code>-st place in its own list, and the list won the coin toss <code>i-1</code> times <em>including the last one</em> and lost once, the probability of this is <code>(i-1) choose 1</code> times <code>1/2^i</code>;</li> <li>in the <code>i-2</code>-nd place in its own list, and the list won the coin toss <code>i-2</code> times <em>including the last one</em> and lost twice, the probability of this is <code>(i-1) choose 2</code> times <code>1/2^i</code>;</li> <li>and so on.</li> </ul> <p>So the probability</p> <pre><code>P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2). </code></pre> <p>Inductively, you can show that <code>P_i(n) = 1/n</code>. I let you verify the base case and assume that <code>P_j(n/2) = 2/n</code>. The term <code>\sum_{j=0}^{i-1} (i-1 choose j)</code> is exactly the number of <code>i-1</code>-bit binary numbers, i.e. <code>2^{i-1}</code>. So we get</p> <pre><code>P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n = 2/n * 1/2^i * \sum_{j=0}^{i-1} (i-1 choose j) = 1/n * 1/2^{i-1} * 2^{i-1} = 1/n </code></pre> <p>I hope this makes sense. The only assumption we need is that <code>n</code> is even, and that the two lists are shuffled uniformly. This is achieved by adding (and then removing) the dummy node.</p> <p>P.S. My original intuition was nowhere near rigorous, but I list it just in case. Imagine we assign numbers between 1 and n at random to the elements of the list. And now we run a merge sort with respect to these numbers. At any given step of the merge, it needs to decide which of the heads of the two lists is smaller. But the probability of one being greater than the other should be exactly 1/2, so we can simulate this by flipping a coin.</p> <p>P.P.S. Is there a way to embed LaTeX here?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload