# ランダムな並べ替えジェネレータが公平でないことを証明する

``````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.
``````

ベストアンサー

\$ m \$が固定されていて、\$ n
\$が無限大になると、このアルゴリズムが均一にランダムな順列を生成しないことが容易に分かります。バブルソート距離は最大\$ m
\$ですが、ランダム置換はアイデンティティからの距離\$ frac {n} {2} \$を期待しています。

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}、 \$\$

どこで

\$\$ c = frac {m – frac12 n log n} {n}。 \$\$