How to prove correctness of a shuffle algorithm?

Problem Detail: 

I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).

The first method I use is to construct the entire list of elements and then do a shuffle on it (say a Fisher-Yates shuffle). The second method is more of an iterative method which keeps the list shuffled at every insertion. In pseudo-code the insertion function is:

insert( list, item )     list.append( item )     swap( list.random_item, list.last_item ) 

I'm interested in how one goes about showing the fairness of this particular shuffling. The advantages of this algorithm, where it is used, are enough that even if slightly unfair it'd be okay. To decide I need a way to evaluate its fairness.

My first idea is that I need to calculate the total permutations possible this way versus the total permutations possible for a set of the final length. I'm a bit at a loss however on how to calculate the permutations resulting from this algorithm. I also can't be certain this is the best, or easiest approach.

Asked By : edA-qa mort-ora-y

Answered By : Raphael

First, let us make two maybe obvious, but important assumptions:

1. _.random_item can choose the last position.
2. _.random_item chooses every position with probability $\frac{1}{n+1}$.

In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:

• For the singleton list there is only one possibility, so it is uniformly chosen.
• Assuming that the list with $n$ elements was uniformly chosen (from all permutations), show that the one with $n+1$ elements obtained by your technique is uniformly chosen.

---

^{From here on, the proof is wrong. Please see below for a correct proof; I leave this here because both the mistake and the following steps (which are sound) might be educational.}

It is useful to derive a local (i.e. element-wise) property that has to hold, because arguing about the whole permutation is painful. Observe that a permutation is uniformly chosen if every element has equal probability of being at each position, i.e.

$\qquad \displaystyle \mathop{\forall}\limits_{\pi \in \mathrm{Perm}_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits_{i=1}^n\ \mathop{\forall}\limits_{j=1}^n \operatorname{Pr}(L_i = j) = \frac{1}{n} \qquad (1)$

where $n = |L|$ and we assume for the sake of notational simplicity that we insert $\{1,\dots,n\}$ into the list.

Now, let us see what your technique does when inserting the $n+1$st element. We have to consider three cases (after the swap):

1. One of the elements in the list, not swapped, i.e. $i \in \{1,\dots,n\}$ and $j \in \{1,\dots,n\}$
2. One of the elements in the list, swapped, i.e. $i = n+1$ and $j \in \{1,\dots,n\}$
3. The new element, i.e. $i \in \{1,\dots,n+1\}$ and $j = n+1$

For each case, we compute the probability of element $j$ being at position $i$; all have to turn out to be $\frac{1}{n+1}$ (which is sufficient because of $(1)$). Let $p_n = \frac{1}{n}$ be the probability of one of the first $n$ elements being at any position in the old list (induction hypothesis), and $p_s = \frac{1}{n+1}$ the probability of any position being chosen by random_item (assumptions 1, 2). Note that the coice of the list with $n$ elements and picking the swap position are independent events, so the probabilities of joint events factor, e.g.

$\qquad \displaystyle \operatorname{Pr}(L_i=j, i \text{ swapped}) = \operatorname{Pr}(L_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p_np_s$

for $i,j \in \{1,\dots,n\}$. Now for the calculations.

1. We only consider the old $n$ elements. Such an element $j$ is at position $i$ if and only if it was there before the last insertion and $i$ is not selected as swap position, that is

   $\quad \displaystyle \operatorname{Pr}(L_i = j) = p_n(1-p_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$.

2. Here we consider that one of the old elements is swapped to the last position. Element $j$ could have been at any of the old positions, so we sum over all probabilities that $j$ was at position $i$ and $i$ is chosen as swap position, that is

   $\quad \displaystyle \operatorname{Pr}(L_{n+1} = j) = \sum_{i=1}^n p_np_s = \sum_{i=1}^n \frac{1}{n}\cdot\frac{1}{n+1} = \frac{1}{n+1}$.

3. The new element ends up at position $i$ if and only if $i$ is chosen as swap position, that is

   $\quad \displaystyle \operatorname{Pr}(L_i = j) = p_s = \frac{1}{n+1}$.

All turned out well, your insertion strategy does indeed preserve uniformity. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

^{A word of warning: this proof breaks down if the inserted elements are not pairwise different resp. distinguishable, because then the very first equation is no longer valid. But your algorithm is still valid; every permutation with duplicates is generated by the same number of random executions. You can proof this by marking duplicates (i.e. making them distinguishable), perform above proof and remove the markings (virtually); the last step collapses equal sized sets of permutations to the same.}

---

As Steven has remarked correctly in the comments, above proof is fundamentally flawed as $(1)$ does not hold; you can construct distributions on the set of permutations that fulfill the right-hand, but not the left-hand side¹.

Therefore, we will have to work with probabilities of permutations, which turns out to be not that bad after all. The assumptions on random_item and the inductive structure outlined in the very beginning of the post remain in place, we continue from there. Let $L^{(k)}$ denote the list after $\{1,\dots,k\}$ have been inserted.

Let $\pi' \in \mathrm{Perm}_{n+1}$ an arbitrary permutation of $\{1,\dots,n+1\}$. It can be written uniquely as

$\qquad \displaystyle \pi' = (\pi(1), \pi(2), \dots, \pi(i-1), n+1, \pi(i+1), \dots, \pi(n), \pi(i))$

for some $\pi \in \mathrm{Perm}_n$ and $i \in \{1,\dots,n+1\}$. By induction hypothesis, $\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$. Furthermore, random_item picks position $i$ with probability $\frac{1}{n+1}$ by assumption. As the random choices of $\pi$ and $i$ are (stochastically) independent, we get

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

which we had to show. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

---

1. For example, assign every permutation in $\{(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)\}$ probability $\frac{1}{4}$ and all others $0$. There are also examples that assign every permutation a non-zero probability.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2152