リストのシャッフル
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p04
の正しさについてしばし考えた。
リストの各要素について[0,1]区間の一様乱数を振って、その値でsortしていると理解してみた。もっと単純な解釈はないだろうか。
追記
これを実装したのが、上記のアルゴリズムだという解釈です。任意の順列に付いて容易に出現する確率が計算できて、正しいシャッフルだと証明できます。
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051025#p01 より
- 直感的には「平等」なのですが、全ての順列が等確率で出現するかどうかとは距離があります。例えば、出現しない順列があるかもしれない。
- 小学生はしばしば騙されるので:-)、ちゃんと理解しようとするとややこしいことが沢山あるように思います。
- 「決まるまでジャンケン/コイン投げをする」というそのままのモデル化だと、単純な確率空間の一つの事象というわけにいかないように思います。
