整数パーティションのコンジュゲート

Question

nのすべてのパーティションのセットからランダムに選択された整数パーティションのコンジュゲートも均一なランダムサンプルですか？私の結果は「はい」を示唆しています。これは、長さがnのランダムなパーティションを素早く生成するために励みになりますが、なぜそうすべきか、そうでなければならないのか説明できません。 （< 70）の特定の長さのすべてのパーティションを生成します。2.各パーティションの分散をマクロステートディスクリプタとして計算し、3。すべての可能な集合（長さnのすべての区画）と小規模なランダムな標本（すなわち、長さがsに一致する共役長がsに一致するn個のランダムに生成された500個の区画）とのカーネル密度曲線を比較する。ランダムサンプルのカーネル密度曲線は、実行可能なセット全体（すなわち、n個のマッチングsのすべてのパーティション）のカーブと厳密に一致する。これは、大部分が共役パーティションであるランダムサンプルが、nおよびsベースの実行可能なセットのパーティション間の分散分布を捕捉することを視覚的に示す。私はなぜそれがそうするように働くべきであるか説明することができません。独創的な飛躍を挫折させる。

注：ランダムサンプルを生成するための多くの他の手順では、明確にバイアスされたサンプル（すなわち、異なる形状および高度に重なり合わないカーネル密度曲線）が得られる。

Answer 1

はい。共役は全単射操作であるため、各パーティションは固有の共役にマップされ、固有の共役は元のパーティションにマップされます。従って、ランダムに一様に選択された区画の共役をとることによって、いかなるバイアスも導入することができない。

これは、固定長パーティションをランダムに生成するのには役立ちませんが、これを正しく行うにはNijenhuis & Wilfのアルゴリズムを適応させるべきです。これは非常に難しいことではありません。なぜなら、nのk個の部分への分割数は簡単に計算でき、ランダム生成アルゴリズムは実際にはこれだけに依存しているからです。

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