1

n のすべてのパーティションのセットから無作為に選択された整数パーティションの共役も、一様ランダム サンプルですか? 私の結果は、長さ s の n のランダムなパーティションを迅速に生成するためには励みになりますが、そうすべきかそうでないかを説明することはできません。

ところで、私の結果は 1.) 特定の長さ (s) の小さい n (<70) のすべてのパーティションを生成する 2.) 各パーティションの分散をマクロ状態記述子として計算する 3.) カーネルを比較する小さなランダム サンプル (つまり、長さが s に一致するか共役長が s に一致する n のランダムに生成された 500 個未満のパーティション) に対する実行可能なセット全体 (長さ s の n のすべてのパーティション) にわたる分散の密度曲線。ランダム サンプルのカーネル密度曲線は、実行可能なセット全体 (つまり、一致する n 個の s のすべてのパーティション) の曲線とよく一致します。これは、大部分が共役パーティションであるランダム サンプルが、n および s ベースの実行可能セットのパーティション間の分散の分布をキャプチャすることを視覚的に示しています。見た目どおりに機能する理由を説明することはできません。

注: ランダム サンプルを生成する他の多くの手順では、明らかに偏ったサンプル (つまり、形状が異なり、非常に重複しないカーネル密度曲線) が生成されます。

4

1 に答える 1

1

はい。コンジュゲーションは全単射操作であるため、各パーティションは一意のコンジュゲートにマップされ、次に元のパーティションにマップされます。したがって、ランダムに均一に選択されたパーティションの共役を取ることによって導入されるバイアスはありません。

ただし、これが固定長のパーティションをランダムに生成するのに役立つとは思いません。これを正しく行うには、おそらくNijenhuis&Wilfのアルゴリズムを適応させる必要があります。nからkの部分への分割の数は簡単に計算でき、ランダム生成アルゴリズムは実際にはこれにのみ依存するため、これを行うのはそれほど難しいことではありません。

Knuthには、TAOCPボリューム4Aのセクション7.2.4.1にランダムパーティションの生成に関する演習(47)が含まれています。これは、固定長のパーティションをランダムに均一に生成するための効率的なアルゴリズムの優れた出発点になります。

于 2012-05-04T15:24:43.270 に答える