小波です。

原さん,いつもありがとうございます。あまり時間がないので簡単に
失礼しますが・・・。

Shin-ichiro HARA wrote:
> 突然ですが、このアルゴリズムの正当性を数学的帰納法で証明します。
> 
> (2) array[0..idx] のエントリを一つ固定する。スワップが平等な
> ので、帰納法の仮定より数 0,1,...,idx-1 がそこに出現する確率は
> 等しい。(1)よりその値は各々 (1-p)/idx = 1/(idx+1) である。

この辺のところです。アルゴリズムからイメージしていて「これでちゃんと
混ざるのかな?」と思ったのは。なるほどですね。

> 一方、よく使われるアルゴリズムの正当性は、検定によらず確率
> の計算よるべきではないでしょうか。計算可能な場合は。

正論ですね。まったくそうだと思います。もっとも,計算機実験で
おかしいかどうかを最初にチェックして,その結果を数学的論証
で確認するという流れ自体は問題がないのだけど,そこまで行かないで
やめるのは不十分ということですね。

なお,これは別の話題なんですが,私が
社会学系の学生に統計の授業をやっていて思うのは,定理を式の導出
で納得する学生はごく少数で,むしろシミュレーションをたくさんやら
せて,たとえば一様分布や二項分布から正規分布へといった極限操作を
扱わせると納得がいくという受容の仕方が,後まで印象として残るよう
だということです。
1万人の母集団からの無作為抽出というのは,現実にできる実験ではな
いけれど,シミュレーションでは容易にできるわけで,最近では
Ruby でその手のシミュレーションを書きまくっています。その中で
登場したのが,Ruby 的なランダマイズの書き方でした。