シャッフルアルゴリズムの正しさを証明する方法は？

Question

アイテムのリストをランダムな順序で作成する2つの方法があり、それらが等しく公平であるかどうかを判断したいと思います（公平ではありません）。

私が最初に使用する方法は、要素のリスト全体を作成してからシャッフルを行うことです（たとえば、フィッシャーイエートシャッフルなど）。 2番目の方法は、挿入ごとにリストをシャッフルし続ける反復方法です。擬似コードでは、挿入関数は次のとおりです。

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

この特定のシャッフルの公平性を示す方法に興味があります。使用されているこのアルゴリズムの利点は、たとえわずかに不公平であっても大丈夫であっても十分です。私はその公平性を評価する方法が必要です。

私の最初のアイデアは、最終長さのセットで可能な合計順列と比較して、この方法で可能な総順列を計算する必要があるということです。しかし、私はこのアルゴリズムから生じる順列を計算する方法について少し途方に暮れています。また、これが最良の、または最も簡単なアプローチであることを確信することはできません。

Answer 1

まず、おそらく2つの明白であるが重要な仮定を作ってみましょう。

1. _.random_item 最後の位置を選択できます。
2. _.random_item 確率$ frac {1} {n+1} $ですべての位置を選択します。

あなたのアルゴリズムの正確性を証明するために、あなたは使用されたものと同様の誘導的な議論が必要です ここ:

• シングルトンリストには可能性は1つだけなので、均一に選択されます。
• $ n $要素のリストが均一に選択されたと仮定すると（すべての順列から）、手法によって取得された$ n+1 $要素のあるリストが均一に選択されていることを示しています。

---

^{これから、証拠は間違っています。正しい証明については、以下をご覧ください。間違いと次の手順（音）の両方が教育的である可能性があるため、私はこれをここに残します。}

順列全体について議論することは苦痛であるため、保持しなければならないローカル（つまり要素ごとの）プロパティを導き出すことは有用です。すべての要素が各位置にある可能性が等しい場合、つまり、順列が均一に選択されることに注意してください。

$ qquad displaystyle mathop { forall} limits _ { pi in mathrm {perm} _n} operatorname {pr}（l = pi）= frac {1} {n！ quad mathop { forall} limits_ {i = 1}^n mathop { forall} limits_ {j = 1}^n operatorname {pr}（l_i = j）= frac {1} {{{ n} qquad（1）$

ここで、$ n = | l | $そして、表記の単純さのために、$ {1、 dots、n } $をリストに挿入すると想定します。

次に、$ n+1 $ st要素を挿入するときにあなたのテクニックが何をするかを見てみましょう。 （スワップ後）3つのケースを考慮する必要があります。

1. リスト内の要素の1つは、スワップされていません、すなわち$ i in {1、 dots、n } $および$ j in {1、 dots、n } $
2. リスト内の要素の1つ、スワップ、すなわち$ i = n+1 $および$ j in {1、 dots、n } $
3. 新しい要素、すなわち$ i in {1、 dots、n+1 } $および$ j = n+1 $

各ケースについて、要素$ j $が位置$ i $にある確率を計算します。すべてが$ frac {1} {n+1} $であることが判明する必要があります（$（1）$のために十分です）。 $ p_n = frac {1} {n} $は、最初の$ n $要素の1つが古いリスト（誘導仮説）の任意の位置にある確率となり、$ p_s = frac {1} {n+ 1} $によって任意の位置が選択される確率 random_item （仮定1、2）。 $ n $要素とスワップ位置を選ぶリストのコースは 独立したイベント, 、したがって、共同イベント要因の確率、例：

$ qquad displaystyle operatorname {pr}（l_i = j、i text {swapped}）= operatorname {pr}（l_i = j） cdot operatoroname {pr}（i text {swapped}）= p_np_s $

$ i、j in {1、 dots、n } $の場合。計算のために。

1. 古い$ n $要素のみを考慮します。そのような要素$ j $は、最後の挿入の前にそこにあった場合にのみ位置$ i $にあり、$ i $はスワップ位置として選択されていません。

   $ quad displaystyle operatorname {pr}（l_i = j）= p_n（1-p_s）= frac {1} {n} cdot frac {n} {n+1} = frac {1} {{{{n+1} = frac {1} { n+1} $。

2. ここでは、古い要素の1つが最後の位置に交換されると考えています。要素$ j $は古い位置のいずれかにある可能性があるため、$ j $がポジション$ i $にあり、$ i $がスワップ位置として選択されているという確率、つまり、

   $ quad displaystyle operatorname {pr}（l_ {n+1} = j）= sum_ {i = 1}^n p_np_s = sum_ {i = 1}^n frac {1} {n} cdot frac {1} {n+1} = frac {1} {n+1} $。

3. 新しい要素は、$ i $がスワップ位置として選択されている場合にのみ位置$ i $になります。

   $ quad displaystyle operatorname {pr}（l_i = j）= p_s = frac {1} {n+1} $。

すべてがうまくいきました、あなたの挿入戦略は実際に均一性を維持します。誘導の力により、アルゴリズムが均一に分布した順列が作成されることを証明します。

^{警告の単語：挿入された要素がペアワイズ異なるRESPではない場合、この証明は崩壊します。最初の方程式はもはや有効ではないため、区別可能です。しかし、あなたのアルゴリズムはまだ有効です。 毎日 複製による順列は、同じ数のランダム実行によって生成されます。これを証明します（つまり、それらを区別できるようにする）、上記の証明を実行し、マーキングを（実質的に）削除することができます。最後のステップは、同じサイズの順列セットを同じものに崩壊させます。}

---

として スティーブン コメントで正しく発言していますが、上記の証拠は$（1）$が保持されないために根本的に欠陥があります。左側ではなく、右手を満たす一連の順列に分布を構築できます。

したがって、順列の確率で作業する必要がありますが、結局はそれほど悪くないことが判明しました。の仮定 random_item そして、投稿の最初の概要に概説されている帰納的構造は、そこから続きます。 $ l^{（k）} $は、$ {1、 dots、k } $が挿入された後にリストを示します。

$ pi ' in mathrm {perm} _ {n+1} $ $ {1、 dots、n+1 } $の任意の順列とします。書くことができます ユニークに なので

$ qquad displaystyle pi '=（ pi（1）、 pi（2）、 dots、 pi（i-1）、n+1、 pi（i+1）、 dots、 pi （n）、 pi（i））$

いくつかの$ pi in mathrm {perm} _n $および$ i in {1、 dots、n+1 } $。誘導仮説により、$ operatorname {pr}（l^{（n）} = pi）= frac {1} {n！} $。さらに、 random_item 確率$ frac {1} {n+1} $を使用して$ i $を選択します。 $ pi $と$ i $のランダムな選択が（確率的に）独立しているため、私たちは取得します

$ qquad displaystyle operatorname {pr}（l^{（n+1）} = pi '）= operatorname {pr}（l^{（n）} = pi） cdot operatorname {pr} （i text {swapped}）= frac {1} {（n+1）！} $

私たちが見せなければならなかった。誘導の力により、アルゴリズムが均一に分布した順列が作成されることを証明します。

---

1. たとえば、すべての順列を$ {（1、2、3、4）、（2、3、4、1）、（3、4、1、2）、（4、1、2、3）に割り当てます。 } $確率$ frac {1} {4} $およびその他すべて$ 0 $。すべての順列を非ゼロ確率を割り当てる例もあります。