素朴なシャッフルはどれほど漸近的に悪いですか？

Question

各アイテムをランダムに選択した別のアイテムと交換して配列をシャッフルするためのこの「素朴な」アルゴリズムが正しく機能しないことはよく知られています。

for (i=0..n-1)
  swap(A[i], A[random(n)]);

具体的には、$ n $ iterationsのそれぞれで、$ n $の選択肢の1つが（均一な確率で）行われるため、計算を介して$ n^n $ 'paths'があります。可能な順列$ n！$の数は、パス$ n^n $の数に均等に分割されないため、このアルゴリズムが$ n！$の各順列を等しい確率で生成することは不可能です。 （代わりに、いわゆるものを使用する必要があります フィッシャー - イェート Shuffleは、[0..n）から[0..n）から乱数を選択するための呼び出しを本質的に変更して、[i..n）から乱数を選択します。しかし、それは私の質問には言い直しです。）

私が疑問に思っているのは、素朴なシャッフルはどれほど「悪い」のでしょうか？より具体的には、$ p（n）$をすべての順列のセットと$ c（ rho）$とすることは、結果の順列$ rho in p（n）$を生成するナイーブアルゴリズムを介したパスの数になります。関数の漸近挙動です

$ qquad displaystyle m（n）= frac {n！} {n^n} max _ { rho in p（n）} c（ rho）$ $

と

$ qquad displaystyle m（n）= frac {n！} {n^n} min _ { rho in p（n）} c（ rho）$？

主要な要因は、これらの値を「正規化」することです。素朴なシャッフルが「漸近的に良い」場合、

$ qquad displaystyle lim_ {n to infty} m（n）= lim_ {n to infty} m（n）= 1 $。

私は（私が見たいくつかのコンピューターシミュレーションに基づいて）実際の値は1から離れて限定されているが、$ lim m（n）$が有限であるか、$ lim m（n）$であるかどうかさえ知られていますか0から離れていますか？これらの量の動作について何が知られていますか？

Answer 1

誘導により、順列$ rho_n =（2,3,4、 ldots、n、1）$は$ c（ rho_n）= 2^{n-1} $の例であることを示します。これが最悪の場合は、最初の数$ n $の場合と同様です（メモを参照してください OEISシーケンスA192053）、$ m（n） compx（2/e）^{n} $。したがって、正規化された最大値と同様に、正規化されたMINは「指数関数的に悪い」です。

基本ケースは簡単です。誘導ステップには、補題が必要です。

補題： $（2,3,4、 ldots、n、1）$（1,2,3、 ldots、n）$への任意のパスで、最初の動きは$ 1 $と$ n $、または$ n $をスワップします。最後の動きは、1ドルと$ n $の位置をスワップします。

証明スケッチ： そうでないとします。 $ n $ 'th位置を含む最初の動きを考えてください。それが$ i $ 'th move、$ i neq 1 $および$ i neq n $であると仮定します。この動きは、アイテムを$ i $ 'thの場所に1ドルに配置する必要があります。次に、アイテム$ 1 $に触れる次の動きを考えてみましょう。この動きが$ j $ 'thの動きであると仮定します。この動きは、$ i $と$ j $を交換し、$ 1 $を$ J $ 'th Placeに移動し、$ i <j $を移動する必要があります。同様の議論では、アイテム$ 1 $はその後右に移動することができると述べています。しかし、アイテム$ 1 $は、そもそも矛盾で終わる必要があります。 $ square $

ここで、最初の動きがポジション$ 1 $と$ n $を交換する場合、残りの動きは順列$（1、3,4,5、 ldots、n、2）$（1,2,3、2）を取得する必要があります。 4、 ldots、n）$。残りの動きが最初の位置に触れない場合、これは位置$ 2 ldots n $の順列$ rho_ {n-1} $です。 1}）= 2^{n-2} $これを行うパス。補題の証明に似た議論は、最初の位置に触れる道はないと言います。アイテム$ 1 $が誤った位置に終わる必要があるためです。

最後の動きがポジション$ 1 $と$ n $をスワップする場合、最初の$ n-1 $の動きは、順列$（2,3,4、 ldots、n、1）$を順列$（n、2）に並べ替える必要があります。 、3,4、 ldots、n-1、1）$。繰り返しますが、これらの動きが最後の位置に触れない場合、これは順列$ rho_ {n-1} $であり、誘導により$ c（ rho_ {n-1}）= 2^{n- 2} $それを行うパス。繰り返しますが、ここの最初の$ n-1 $の移動の1つが最後の位置に触れた場合、アイテム$ 1 $は正しい場所に終わることはできません。

したがって、$ c（ rho_n）= 2c（ rho_ {n-1}）= 2^{n-1} $。

Answer 2

MhumのOEISへのポインターのおかげで掘り下げた後、私はついに優れた分析と素晴らしい（比較的）基本的な議論を見つけました（私が知る限り、GoldsteinとMoews [1]） ）$は$ n $で上位に高速に増加します：

$ {1 ldots n } $ of $ iota $は、アルゴリズムが$ iota（ k）$およびその後、$ iota（k）$を$ k $と交換し、両方を変更しません。これは、アイデンティティの順列を生成するアルゴリズムの実行数が少なくとも関与$ q（n）$の数であることを意味します（実際、少しの考えは、対応が1-1であることを示しているため、正確に$ q（ n）$）、したがって、$ m（n）$の最大値は、$ q（n）$で下から除外されます。

$ q（n）$は、明らかに多くの名前で行われます。 電話番号 ： 見る http://oeis.org/a000085 と http://en.wikipedia.org/wiki/telephone_number_%28mathematics%29 。漸近性はよく知られており、$ q（n） comp left（ frac {n} {e} right）^{n/2} e^ sqrt {n} $;再発関係$ q（n）= q（n-1）+（n-1）q（n-2）$から、比率$ r（n）= frac {q（n）を誘導的に示すことができます。 } {q（n-1）} $ $ sqrt {n} lt r（n） lt sqrt {n+1} $を満たし、そこから基本的な分析では、$ n^{n/2} $を獲得します漸近的な用語ですが、他の用語ではより慎重な努力が必要です。 「スケールファクター」$ frac {n！} {n^n} $ $ m（n）$の定義は約$ c sqrt {n} e^{-n} $のみであるため、主要な用語$ q（n）$は支配し、（漸近的に）$ m（n） geq cn^{（n+1）/2} e^{ - 3n/2+ sqrt {n}} $を生み出します。

GoldsteinとMoewsは、実際には[1]で、アイデンティティの順列が大きな$ n $の可能性が最も高いことを示しています。 $は完全に解決されます。これにより、$ m（n）$ openの動作の問題が残ります。それが彼らの論文の分析にも屈したとしても、私はそれほど驚かないでしょうが、私は彼らの方法を本当に把握するためにまだそれを十分に読む機会がありませんでした、基本的な結果を把握するのに十分です。

1] Goldstein、D。and Moews、D。：「アイデンティティは、大きなnの最も可能性の高い交換シャッフルです」、 http://arxiv.org/abs/math/0010066