<p>If $m$ is fixed while $n$ grows to infinity, then it's easy to see this algorithm doesn't produce a uniformly random permutation: it produces a permutation whose <a href="https://en.wikipedia.org/wiki/Kendall_tau_distance" rel="nofollow noreferrer">bubble-sort distance</a> from the identity is at most $m$, while a random permutation has expected distance $\frac{n}{2}$ from the identity. </p>

<p><em>However</em>, when $m$ is allowed to grow with $n$, this algorithm samples from a distribution on permutations which quickly gets very close to uniform. Indeed, this algorithm takes $m$ steps from a natural reversible Markov chain on the symmetric group whose stationary distribution is the uniform distribution. A classical result of <a href="https://statistics.stanford.edu/sites/default/files/EFS%20NSF%20149.pdf" rel="nofollow noreferrer">Diaconis and Shahshahani</a> shows that the <a href="https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures" rel="nofollow noreferrer">total variation distance</a> between the distribution $\mathbb{P}_m$ on the permutation output by the algorithm after $m$ steps, and the uniform distribution $\mathbb{P}_U$ is </p>

<p>$$
2\left(\frac1e - e^{-e^{-2c}}\right) + o(1) \le \frac12 \|\mathbb{P}_m - \mathbb{P}_Y\|_1 \lesssim e^{-2c},
$$</p>

<p>where </p>

<p>$$
c = \frac{m - \frac12 n\log n}{n}.
$$</p>

CC BY-SA 3.0
2017-11-23T21:18:23.733Z
2017-11-23T21:18:23.733Z
Sasho Nikolov
<p>If I'm generating random permutations using the following algorithm:</p>

<pre><code>start with p = identity permutation.
at each iteration, 
pick two random numbers i,j from {1,2... n}
swap p(i) with p(j). 
repeat m times, and m is large as you wish. 
</code></pre>

<p>My guess is that this method is not fair. Namely, not all permutations are chosen with probability of 1/n!. </p>

<p>Because for simpler permutations, there is greater room for choice, 
but I just cannot prove it</p>

<p>Any idea? 
thanks!</p>

<co.combinatorics><randomized-algorithms>
Proving that a random permutation generator is not fair
liam g
# Proving that a random permutation generator is not fair

(Asked by: username_0 on 2017-11-23)

If I'm generating random permutations using the following algorithm:
start with p = identity permutation.
at each iteration, 
pick two random numbers i,j from {1,2... n}
swap p(i) with p(j). 
repeat m times, and m is large as you wish. 

My guess is that this method is not fair. Namely, not all permutations are chosen with probability of 1/n!. 
Because for simpler permutations, there is greater room for choice, 
but I just cannot prove it
Any idea? 
thanks!

**Tags:** co.combinatorics, randomized-algorithms


---

## 1 answers

### Answer by username_1 on 2017-11-23. Score: 3

If $m$ is fixed while $n$ grows to infinity, then it's easy to see this algorithm doesn't produce a uniformly random permutation: it produces a permutation whose [bubble-sort distance](https://en.wikipedia.org/wiki/Kendall_tau_distance) from the identity is at most $m$, while a random permutation has expected distance $\frac{n}{2}$ from the identity.

*However*, when $m$ is allowed to grow with $n$, this algorithm samples from a distribution on permutations which quickly gets very close to uniform. Indeed, this algorithm takes $m$ steps from a natural reversible Markov chain on the symmetric group whose stationary distribution is the uniform distribution. A classical result of [Diaconis and Shahshahani](https://statistics.stanford.edu/sites/default/files/EFS%20NSF%20149.pdf) shows that the [total variation distance](https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures) between the distribution $\mathbb{P}\_m$ on the permutation output by the algorithm after $m$ steps, and the uniform distribution $\mathbb{P}\_U$ is

$$
2\left(\frac1e - e^{-e^{-2c}}\right) + o(1) \le \frac12 \|\mathbb{P}\_m - \mathbb{P}\_Y\|\_1 \lesssim e^{-2c},
$$

where

$$
c = \frac{m - \frac12 n\log n}{n}.
$$


---

