-3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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 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 shows that the total variation distance 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}. $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.