-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$

closed as off-topic by Emil Jeřábek, Andrej Bauer, Aryeh, Kaveh, Hsien-Chih Chang 張顯之 Nov 25 '17 at 5:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Andrej Bauer, Aryeh, Kaveh, Hsien-Chih Chang 張顯之
If this question can be reworded to fit the rules in the help center, please edit the question.

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.