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

次のアルゴリズムを使用してランダム置換を生成している場合:

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. 

私の推測では、この方法は公正ではありません。すなわち、すべての順列が1/n!の確率で選択されるわけではない。

単純な並べ替えのために、選択の余地が大きいので、 私はそれを証明できません

何か案が? ありがとう!

ベストアンサー

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

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です