ランダム・アルバイト・クイズについて（続き）

昨日書いた方法よりももっと単純な方法。
s人目までを無条件で控え室に入れ、 n人目（s<n）の応募者をs/nの確率で控え室に入れる。n人目の応募者を控え室に入れる場合は、替わりに控え室にいる人を一人ランダムで追い出す。
たとえばs人目までの応募者を無条件で控え室に入れ、それ以降の応募者には、現時点までのすべての応募者名が書かれたクジを引かせ、控え室にいる人の名前を引いたらその人と入れ替えする。
これだけで総数のわからないすべて応募者からs人を等確率で選ぶことができる。

証明のようなもの

この方式に従うとき場合の、各応募者が合格する確率を考える。

s: 採用する人数
N: 応募者の最終的な総数

すべての応募者が等しい確率(s/N)で合格するので、n番目の応募者がその時点で暫定合格をもらう(控え室に入ること)確率は、n番目が最後の人かもしれないので、
$\Large \frac{s}{n}$
である。

次に n 番目の応募者が n+1番目の人が来た後も暫定合格である確率は、
n番目の時点で暫定合格をもらう確率と、n+1番目の人が暫定合格をもらって替わりに自分が追い出されない確率の積になるので、
$\Large \frac{s}{n}\frac{n}{n+1}=\frac{s}{n+1}$
となり、N=n+1の場合になる。これはn>sのときに常に成り立つ。

最初のs人の人の場合も、
$\Large \frac{s}{s}\frac{s}{s+1}\frac{s+1}{s+2}\cdots\frac{N-1}{N}=\frac{s}{N}$
となり、合格する確率は等しい。

Perlで書くと

my $s = ($ARGV.shift or 5);
print "${s}人採用する。\n";

my $N = int(rand(1000))+$s; # $N人の応募者
my %keep; # 控え室

for($i=0;$i<$N;$i++) {
   $keep{$i} = "$i番" if($i<$s || delete $keep{int rand $i});
}
print "${N}人の応募者のうち、合格者は\n";
print join(',', values(%keep)), "である。\n";

ちなみにこれは

perlクイズの
http://blog.mag2.com/m/log/0000015670/105092316?page=1
http://blog.mag2.com/m/log/0000015670/105098367?page=1 (解答編)
を一般化したものとも言えますね。