73

有名な Fisher-Yates シャッフル アルゴリズムを使用して、長さ N の配列 A をランダムに並べ替えることができます。

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

私が何度も何度も犯してはいけないと言われたよくある間違いは次のとおりです。

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

つまり、k から N までのランダムな整数を選択する代わりに、1 から N までのランダムな整数を選択します。

この間違いを犯したらどうなりますか？結果の順列が一様に分布していないことはわかっていますが、結果の分布がどうなるかについてどのような保証があるかはわかりません。特に、要素の最終的な位置に対する確率分布の式を持っている人はいますか?

4

10 に答える 10

55

経験的アプローチ。

Mathematicaで誤ったアルゴリズムを実装しましょう： 

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]

次に、各整数が各位置にある回数を取得します。 

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]

結果の配列で3つの位置を取り、その位置の各整数の度数分布をプロットしてみましょう。

位置1の場合、周波数分布は次のとおりです。

ここに画像の説明を入力してください

ポジション5（中央）の場合

ここに画像の説明を入力してください

そして、ポジション10（最後）の場合：

ここに画像の説明を入力してください

ここに、すべての位置の分布が一緒にプロットされています。

ここに画像の説明を入力してください

ここでは、8つのポジションにわたるより良い統計があります。

ここに画像の説明を入力してください

いくつかの観察：

  • すべての位置で、「1」の確率は同じです（1 / n）。
  • 確率行列は、大きな反対角に対して対称です。
  • したがって、最後の位置にある任意の数の確率も均一です（1 / n）

同じポイント（最初のプロパティ）と最後の水平線（3番目のプロパティ）からのすべての線の始点を見て、これらのプロパティを視覚化できます。

2番目のプロパティは、次のマトリックス表現の例からわかります。ここで、行は位置、列は占有者番号、色は実験確率を表します。

ここに画像の説明を入力してください

100x100マトリックスの場合：

ここに画像の説明を入力してください

編集

楽しみのために、2番目の対角要素（最初は1 / n）の正確な式を計算しました。残りはできますが、大変な作業です。

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

n = 3から6まで検証された値（{8 / 27、57 / 256、564 / 3125、7105 / 46656}）

編集

@wnoise answerで一般的な明示的な計算を少し実行すると、もう少し情報を得ることができます。

1 /nをp[n]に置き換えると、計算は未評価のままになります。たとえば、n = 7の行列の最初の部分を取得します（クリックすると大きな画像が表示されます）。

ここに画像の説明を入力してください

これは、nの他の値の結果と比較した後、マトリックス内のいくつかの既知の整数シーケンスを識別しましょう。 

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

これらのシーケンス（場合によっては異なる符号が付いている）は、すばらしいhttp://oeis.org/にあります。

一般的な問題を解決することはより困難ですが、これが始まりであることを願っています

于 2011-02-27T04:27:43.577 に答える
31

あなたが言及する「よくある間違い」は、ランダムな転置によるシャッフルです。この問題は、Diaconis と Shahshahani によって、Generating a random permutation with random transpositions (1981)で詳細に研究されました。停止時間と均一性への収束を完全に分析します。論文へのリンクが見つからない場合は、私に電子メールを送ってください。コピーを転送できます。これは実際に読むのが楽しいものです (ほとんどの Persi Diaconis の論文と同様)。

配列に繰り返しエントリがある場合、問題は少し異なります。恥知らずなプラグインとして、このより一般的な問題は、私自身、Diaconis と Soundararajan によって、A Rule of Thumb for Riffle Shuffle (2011) の付録 B で取り上げられています。

于 2011-03-16T02:35:41.290 に答える
15

まあ言ってみれば

  • a = 1/N
  • b = 1-a
  • B i (k) は、番目の要素iのスワップ後の確率行列です。つまり、「スワップ後kはどこですか?」という質問に対する答えです。たとえば、B 0 (3) =および B 1 (3) = . 必要なのは、すべての k に対する B N (k) です。ki(0 0 1 0 ... 0)(a 0 b 0 ... 0)
  • K iは NxN 行列で、i 番目の列と i 番目の行に 1 があり、それ以外はゼロです。例:

カッパ_2

  • I iは恒等行列ですが、要素 x=y=i はゼロです。たとえば、i=2 の場合:

I_2

  • A iは

アイ＝ビイ＋アキ

それで、

B_n

しかし、B N (k=1..N) は恒等行列を形成するため、特定の要素 i が最後に位置 j にある確率は、行列の行列要素 (i,j) によって与えられます。

ソリューション マトリックス

たとえば、N=4 の場合:

B_4

N = 500 の図 (色レベルは 100*確率):

B_500

パターンはすべての N>2 で同じです。

  • k 番目の要素の最も可能性の高い終了位置は k-1です。
  • 最も可能性の低い終了位置は、k < N*ln(2)の場合は k 、それ以外の場合は1です。
于 2011-03-22T00:07:17.243 に答える
13

以前にこの質問を見たことがあることを知っていました...

「この単純なシャッフル アルゴリズムが偏った結果を生成するのはなぜですか?単純な理由とは何ですか?」には、回答に多くの優れた内容が含まれています。特に、コーディング ホラーに関する Jeff Atwood のブログへのリンクです。

@belisarius の回答に基づいて、すでに推測されているように、正確な分布は、シャッフルされる要素の数に大きく依存します。アトウッドの 6 要素デッキのプロットは次のとおりです。

ここに画像の説明を入力

于 2011-03-15T22:32:12.680 に答える
9

素敵な質問ですね！私は完全な答えがあればいいのにと思います。

Fisher-Yates は、最初の要素を決定すると、そのままにしておくため、分析するのに適しています。偏ったものは、要素を任意の場所で繰り返し交換できます。

これは、マルコフ連鎖と同じように、確率分布に線形に作用する確率遷移行列としてアクションを記述することで分析できます。ほとんどの要素は放置され、対角線は通常 (n-1)/n です。パス k で、それらが放置されない場合、それらは要素 k (または要素 k の場合はランダムな要素) と交換されます。これは、k 行または k 列のいずれかで 1/(n-1) です。行と列 k の両方の要素も 1/(n-1) です。1 から n までの k について、これらの行列を乗算するのは簡単です。

最後のパスが最後の場所を他の要素と同じ確率で交換するため、最後の場所の要素が元の場所にあった可能性が等しいことはわかっています。同様に、最初の要素はどこにでも配置される可能性が等しくなります。この対称性は、転置が行列乗算の順序を逆にするためです。実際、行列は、行 i が列 (n+1 - i) と同じであるという意味で対称です。それを超えると、数字は明らかなパターンをあまり示しません。これらの正確な解は、belisarius によって実行されたシミュレーションとの一致を示しています。 j が n に達するまで減少します。

Mathematica では、各ステップを次のように生成しました

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

（どこにも文書化されていませんが、最初の一致ルールが使用されます。）最終的な遷移行列は次のように計算できます。

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot便利な可視化ツールです。

編集 (by ベリサリウス)

ただの確認。次のコードは、@Eelvex の回答と同じ行列を提供します。

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm
于 2011-02-27T09:28:14.367 に答える
3

これをさらに調べたところ、この分布が詳細に研究されていることがわかりました。興味深いのは、この「壊れた」アルゴリズムが RSA チップ システムで使用されている (または使用されていた) ためです。

Elchanan Mossel、Yuval Peres、Alistair Sinclair は、セミランダム転置によるシャッフルで、これとより一般的なクラスのシャッフルを研究しています。その論文の結論は、log(n)ほぼランダムな分布を達成するには壊れたシャッフルが必要であるということです。

The bias of three pseudorandom shuffles ( Aequationes Mathematicae , 22, 1981, 268-292) で、Ethan Bolker と David Robbins はこのシャッフルを分析し、1 回のパス後の均一性への合計変動距離が 1 であることを決定しました。まったくランダム。それらは漸近的な分析も行います。

最後に、Laurent Saloff-Coste と Jessica Zuniga は、不均一なマルコフ連鎖の研究で優れた上限を発見しました。

于 2011-09-23T01:39:26.023 に答える
3

ウィキペディアの Fisher-Yates shuffle のページには、その場合に何が起こるかについての説明と例があります。

于 2011-02-27T03:55:44.300 に答える
3

確率行列を使用して分布を計算できます。行列 A(i,j) は、もともと位置 i にあったカードが最終的に位置 j になる確率を表します。次に、k 番目のスワップには、すべてAk(i,j) = 1/N(他のすべてのカードが確率 (N-1)/N) であり、他のすべての要素はゼロです。i == kj == kAk(i,i) = (N - 1)/Ni != k

完全なシャッフルの結果は、行列の積によって与えられAN ... A1ます。

確率の代数的記述を探していると思います。上記の行列積を拡張することで取得できますが、かなり複雑になると思います。

更新：上記のwnoiseの同等の回答を見つけました！おっとっと...

于 2011-03-18T09:25:56.030 に答える
2

この質問は、言及された壊れたシャッフルのインタラクティブなビジュアルマトリックスダイアグラム分析を求めています。そのようなツールは、 Will It Shuffle?のページにあります。-マイク・ボストックによるランダムコンパレーターが悪い理由。

Bostock は、ランダムコンパレーターを分析する優れたツールをまとめました。そのページのドロップダウンで、ナイーブ スワップ (ランダム ↦ ランダム)を選択して、壊れたアルゴリズムとそれが生成するパターンを確認します。

彼のページは、ロジックの変更がシャッフルされたデータに与える直接的な影響を確認できるため、有益です。例えば：

非一様で非常に偏ったシャッフルを使用するこの行列図は、次のようなコードで単純なスワップ (「1 から N」まで選択) を使用して生成されます。

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

バイアスシャッフル

しかし、バイアスのないシャッフルを実装すると、"k から N" までを選択する場合、次のような図が表示されます。

ここに画像の説明を入力

ここで、分布は一様であり、次のようなコードから生成されます。

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}
于 2015-10-21T12:30:51.747 に答える
1

これまでの優れた回答はディストリビューションに集中していますが、「これを間違えるとどうなりますか?」という質問もありました。-これはまだ答えられていないので、これについて説明します。

Knuth-Fisher-Yates シャッフル アルゴリズムは、n 要素から 1 つを選択し、次に残りの n-1 要素から 1 つを選択します。

a1 から 1 つの要素を削除して a2 に挿入する 2 つの配列 a1 と a2 を使用して実装できますが、ここで説明されているように(Google: "シャッフル アルゴリズム Fisher-Yates DataGenetics") は非常にうまくいきます。

要素を削除しないと、それらが再びランダムに選択される可能性があり、偏ったランダム性が生成されます。これはまさに、あなたが説明している2番目の例が行うことです。最初の例である Knuth-Fisher-Yates アルゴリズムでは、k から N まで実行されるカーソル変数を使用します。これは、どの要素が既に取得されたかを記憶しているため、要素を複数回選択することを回避します。

于 2015-03-09T07:22:22.423 に答える