シャッフルシャッフル

http://d.hatena.ne.jp/scinfaxi/20070703/1183447623を眺めていて

(define (vector-shuffle! vec) ;; rui さんのコードのパクリ : http://d.hatena.ne.jp/rui314/20070118/p1
  (do ((i (- (vector-length vec) 1) (- i 1)))
      ((= i 0) vec)
    (vector-swap! vec i (random-integer (+ i 1)))))

は本当にランダムにシャッフルできてるのかなぁ、とぼんやり思う。Ruiさんの元ネタのほうでも3要素のリストがおおよそランダムにシャッフルされているらしいと実験的に確認してあるだけだ。(もちろんramdom-intergerのランダム性は大前提としておく)

やっている操作は結局のところ(線形代数の)置換の単位置換を順に生成しているだけ。上のコードでは、i が小さくなるにつれて置換の範囲が絞られてゆくから、vectorの長さを n とすると n → k の置換の k の値のランダム性は保証される。

あとは範囲が絞られていくにつれて、確率の分母と分子がうまく相殺して数学的にランダムになりそうなイメージはあるけど

省略されました。続きを読むにはシャッフルシャッフルと(ry

というのは冗談で、今日は実験で疲弊して頭が回らないのでここらでやめる。誰かカッコイイ証明してください。

あと do って使いかた知らんのだけど、上のだと i = 0 のとき body は実行されないってことでよいのでしょうか。