小波です。

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

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

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

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

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

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