このシャッフルアルゴリズムに問題があるとすれば、それは何ですか、どうすれば分かりますか？

2023-09-29 18:21:12

質問

背景として、私が認識しているのはフィッシャー・イェーツという完全シャッフルを知っています。これは O(n) の複雑さと保証された均一性を持つ素晴らしいシャッフルであり、私はこれを使わないのは馬鹿だと思います...配列のインプレース更新が可能な環境 (すべてではないにしても、ほとんどの環境) では、このシャッフルを使用します。必須プログラミング環境では）。

悲しいかな、関数型プログラミングの世界では、ミュータブルな状態にアクセスすることはできません。

しかし、Fisher-Yatesのために、シャッフルアルゴリズムを設計する方法について多くの文献を見つけることができません。それを扱っている数少ない場所は、事実上、「これがあなたが知るべきシャッフリングのすべてである Fisher-Yates です」と言う前に、簡単にそうしています。結局のところ、私は自分自身のソリューションを考え出す必要がありました。

私が考え出した解決策は、データのリストをシャッフルするために次のように動作します。

リストが空の場合、空集合を返します。
リストに単一の項目がある場合、その単一の項目を返します。
リストが空でない場合、乱数発生器を用いてリストを分割し、各分割に対して再帰的にアルゴリズムを適用し、結果を集計します。

Erlangのコードではこのようになります。

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(これが錯乱したクイックソートに見えるなら、まあ、基本的にはそういうことです)

Fisher-Yatesではないシャッフルアルゴリズムを見つけるのが難しいのと同じ状況で、次のようなツールを見つけるのが難しいのです。 を分析する を分析するツールを見つけることも同様に困難です。 PRNGの一様性や周期性などを分析する文献はたくさんありますが、シャッフルを分析する方法についてはあまり情報がありません。 (実際、私が見つけたシャッフルの分析に関する情報のいくつかは、単純なテクニックで簡単に騙される、単なる間違いでした)。

そこで、私の質問はこうです: 私のシャッフルアルゴリズムをどのように分析すればよいのでしょうか? random:uniform() の呼び出しが良い特性を持つ適切な乱数を生成するタスクに適していると仮定します)。例えば、1 から 100 までの整数のリストに対してシャフラーを 100,000 回実行し、もっともらしい良いシャフリング結果を得たかどうかを判断するために、私が自由に使える数学的ツールは何でしょう? 私は自分自身でいくつかのテスト (たとえば、シャッフルの増分と減分を比較するなど) を行いましたが、さらにいくつかのことを知りたいと思います。

そして、そのシャッフルアルゴリズム自体への洞察があれば、それもありがたいことです。

どのように解決するのですか？

一般的な注意事項

確率を利用したアルゴリズムの正しさについての私の個人的なアプローチ：もしあなたが を証明します。 を証明する方法を知っているならば、それはおそらく正しいでしょうし、そうでないならば、それは確実に間違っています。

別の言い方をすれば、思いつく限りのアルゴリズムを分析しようとするのは、一般に絶望的です。
できるを見つけるまで探し続けなければなりません。

分布を計算することによってランダムアルゴリズムを分析する

私は、単純な「たくさんのテストを投げて均一性をチェックする」よりも強力な、シャッフル (またはより一般的にはランダムな使用アルゴリズム) を自動的に分析する方法を 1 つ知っています。アルゴリズムの各入力に関連する分布を機械的に計算することができます。

一般的な考え方は、ランダムを使用するアルゴリズムは、可能性の世界の一部を探索することです。アルゴリズムがセット内のランダムな要素を要求するたびに、 ({ true , false コインをはじくとき)、アルゴリズムには2つの可能な結果があり、そのうちの1つが選択されます。アルゴリズムを変更して、可能な結果の1つを返す代わりに、次のことを調べるようにすることができます。 すべて の解を並列に探索し、すべての可能な結果を関連する分布とともに返すようにアルゴリズムを変更することができます。

一般的に、それはあなたのアルゴリズムを深く書き直す必要があります。もしあなたの言語が区切られた継続をサポートしているならば、その必要はありません。ランダム要素を求める関数の内部で、quot;可能なすべての結果の探索を実装することができます（アイデアは、ランダム生成器が結果を返す代わりに、あなたのプログラムに関連付けられた継続を捕らえ、すべての異なる結果でそれを実行することです）。このアプローチの例として、olegのハンセイ .

中間的な、そしておそらくより難解ではない解決策は、この「起こりうる結果の世界」をモナドとして表現し、モナドプログラミングの機能を持つHaskellのような言語を使用することです。以下は、あなたのアルゴリズムのvariant¹の実装例で、Haskellの確率モナドを使用しています。確率パッケージの確率モナドを用いたHaskellでの実装例です。

import Numeric.Probability.Distribution

shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
        (left, right) <- partition li
        sleft <- shuffleM left
        sright <- shuffleM right
        return (sleft ++ [pivot] ++ sright)
  where partition [] = return ([], [])
        partition (x:xs) = do
                  (left, right) <- partition xs
                  uniform [(x:left, right), (left, x:right)]

与えられた入力に対して実行し、出力の分布を得ることができます。

*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
  [([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
   ([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]

このアルゴリズムは、サイズ2の入力では一様ですが、サイズ3の入力では非一様であることがわかります。

テストベースのアプローチとの違いは、有限のステップ数で絶対的な確実性を得ることができることです。それは可能性の世界の徹底的な探索に相当するので、非常に大きくなることがありますが（しかし一般的には同様の結果の因数分解があるので、2^Nより小さい）、もし非一様分布を返すなら、アルゴリズムが間違っていることを確実に知ることができます。もちろん、一様な分布を返すのであれば [1..N] と 1 <= N <= 100 である場合、アルゴリズムがサイズ100のリストまで均一であることを知るだけで、まだ間違っているかもしれません。

このアルゴリズムはErlangの実装の変種です。もし私があなたのケースのようにピボットを使わなければ、入力サイズはもう各ステップで減少しません：このアルゴリズムはすべての入力が左リスト（または右リスト）にあるケースも考慮し、無限ループに迷い込みます。これは確率モナドの実装の弱点であり (アルゴリズムが非終了の確率 0 を持つ場合、分布計算はまだ発散する可能性があります)、修正する方法をまだ知りません。

ソートベースのシャッフル

私が正しいことを証明できると確信している簡単なアルゴリズムがここにあります。

コレクション内の各要素に対してランダムなキーを選択します。
キーがすべて明確でない場合、ステップ1からやり直します。
これらのランダムなキーでコレクションをソートします。

衝突（選ばれた2つの乱数が等しい）の確率が十分に低いことがわかっている場合は、手順2を省略することができます。しかし、これをしないとシャッフルが完全に均一になりません。

キーを [1..N] (N はコレクションの長さ) で選んだ場合、多くの衝突が発生します ( 誕生日問題 ). キーを 32 ビット整数で選ぶと、実際には衝突の確率は低くなりますが、それでも誕生日問題の対象となります。

有限長のキーではなく、無限（遅延評価）のビット列をキーとして使用する場合、衝突の確率は0になり、明確性のチェックはもはや必要ではありません。

OCamlでのシャッフル実装を紹介します。

type 'a stream = Cons of 'a * 'a stream lazy_t

let rec real_number () =
  Cons (Random.bool (), lazy (real_number ()))

let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
    compare_real a' b'

let shuffle list =
  List.map snd
    (List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
       (List.map (fun x -> real_number (), x) list))

純粋なシャッフリングには、他のアプローチもあります。素晴らしいものは、apfelmusのマージソートベースの解決策です。 .

アルゴリズムの考察：先ほどのアルゴリズムの複雑さは、すべてのキーが別個である確率に依存します。32 ビット整数として選んだ場合、特定のキーが他のキーと衝突する確率は 40 億分の 1 になります。これらのキーによるソートは O(n log n) であり、乱数のピックが O(1) であると仮定すると、O(1) となります。

ビットストリングを無限大にすれば、ピッキングを再開する必要はありませんが、そのときの複雑さは、ストリームのどれだけの要素が平均的に評価されるか"に関連します。私は、それが平均で O(log n) であると推測していますが (したがって、合計でまだ O(n log n)) 、証明はありません。

... そして、私はあなたのアルゴリズムが動作すると思います。

さらに熟考した結果、私は（douplepと同様に）あなたの実装が正しいと思います。以下は非公式な説明です。

あなたのリストの各要素は がテスト済み 複数の random:uniform() < 0.5 によってテストされます。要素に、これらのテストの結果のリストを、ブール値のリストとして、または { 0 , 1 }. アルゴリズムの最初では、これらの番号のいずれかに関連付けられたリストを知らない。最初の partition を呼び出すと、各リストの最初の要素がわかるなど。アルゴリズムが戻ってきたとき、テストのリストは完全に既知であり、その要素は ソートされた に従って（辞書順にソートされるか、実数の二進表現とみなされます）。

つまり、このアルゴリズムは、無限のビット列のキーでソートすることと同じなのです。リストを分割する動作は、ピボット要素上のクイックソートの分割を連想させますが、実際には、ビット文字列の任意の位置で、評価値付き要素 0 を持つ要素と、評価 1 .

ビット列がすべて異なるので、ソートは一様です。実際、実数が最大で等しい2つの要素は n -の間に発生するパーティションの同じ側にあります。 shuffle の深さの呼び出し n . アルゴリズムは、パーティションから得られるリストがすべて空かシングルトンであるときのみ終了します：すべての要素は少なくとも1つのテストによって分離されており、したがって1つの異なる2進数を持っています。

確率的終了

あなたのアルゴリズム（または私の同等のソートベースの方法）の微妙な点は、終了条件が 確率的 . Fisher-Yatesは常に既知のステップ数（配列の要素数）の後に終了します。あなたのアルゴリズムでは、終了は乱数生成器の出力に依存します。

あなたのアルゴリズムでは、以下のような出力が考えられます。発散となるような出力が考えられます。例えば、乱数発生器が常に 0 を出力する場合、それぞれの partition を呼び出すと、入力リストが変更されずに返され、それに対して再帰的に shuffle を呼び出すと、無限にループすることになります。

しかし、乱数生成器が公正であると確信しているのであれば、これは問題ではありません：乱数生成器は不正行為をせず、常に独立した一様分布の結果を返します。その場合、テストが成功する確率は random:uniform() < 0.5 が常に true (または false ) はちょうど 0 です。

が返される確率は、最初の N 回の呼び出しが true は 2^{-N} です。
すべてのコールが返す確率 true は、すべての N に対して、最初の N 個のコールが 0 2^{-N} の infimum limit¹ であり、これは 0 です。

¹: 数学的な詳細については http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

より一般的には、いくつかの要素が同じブーリアンストリームに関連付けられる場合のみ、アルゴリズムは終了しません。これは、少なくとも2つの要素が同じブーリアンストリームを持つことを意味します。しかし、2つのランダムなブーリアンストリームが等しい確率は、再び0です：位置Kの桁が等しい確率は1/2で、N個の最初の桁が等しい確率は2^{-N}で、同じ分析が適用されます。

したがって、あなたは自分のアルゴリズムが は確率 1 で終了することがわかります。 . これは，Fisher-Yates アルゴリズムよりも若干弱い保証です． 常に終了する . 特に、乱数生成器を操るような邪悪な敵の攻撃には弱いです。

もっと確率論があれば、与えられた入力長に対するアルゴリズムの実行時間の分布を計算することもできます。これは私の技術的能力を超えていますが、私はそれが良いと仮定します。すべての N の怠惰なストリームが異なることを確認するために、平均して O(log N) の最初の桁を見るだけでよく、はるかに高い実行時間の確率が指数関数的に減少すると仮定します。