1 はじめに

学生に

「$N$ 個の要素のある配列のうち、乱数を使ってそのうちの $m$ 個 ($1\leq m\leq N$) をランダムに 1 に、残りを 0 にする」

というプログラムを書いてもらったところ、 どうも以下のように考えることが多いようであった (これを方法 A と呼ぶ):

1. 最初に $N$ 個全部を 0 にする
2. $k=0$ とし、$k=m$ になるまで以下を繰り返す:

   $N$ 個の一つをランダムに選び、 そこが 0 ならば 1 として $k$ を一つ増やすが、 そこが 1 ならば何もしない

しかしこの方法 A の場合、 既に 1 であるところにぶつかるとまた乱数を取ってやり直すので、 何回で終わるという保証はないし、 極端な話、乱数があまりよくない乱数である場合には、 かなりの回数がかかってしまう可能性もある。

よって以下のように考えるのがまだいいのではないかと思う (これを方法 B と呼ぶ):

1. 最初に $N$ 個全部を 0 にする
2. $k=0$ とし、$k=m$ になるまで以下を繰り返す:

   現在 0 の箇所の $(N-k)$ 個から一つをランダムに選び、 そこを 1 として $k$ を一つ増やす

この方法 B なら、もちろん丁度 $m$ 回で終わるし、 乱数も $m$ 回生成するだけで済む。

では、方法 A の場合は、終了するまでだいたい何回位かかるのであろうか。 本稿ではそれを考察してみることにする。