玉木 久夫 乱択アルゴリズム 読解メモ #1
概要
共立出版から出ている、玉木 久夫著 「乱択アルゴリズム」読解時のメモを記します。
この記事では、特に練習問題1-1の解答を記します。
というのは本に載ってある練習問題1-1の解が間違ってるような気がしたからです。
誰か詳しい人いましたら、実際あってるのかを教えて頂けると幸いです。
練習問題1-1
大きさnの整数配列aが与えられ、その要素はすべて相異なるものとする。aにおけるランク(aの要素で自分以下のものの個数)がn/3より大きく2n/3以下であるようなaの要素を一つ求める問題を考える。次の乱択アルゴリズムの成功確率を求めよ。nは3の倍数であると仮定してよい。
1. aの要素を一様乱択してx1とおく。
2. 上のステップとは独立に、aの要素を一様乱択してx2とおく。
3. 上の二つのステップとは独立に、aの要素を一様乱択してx3とおく。
4. x1, x2, x3を小さい順に並べたときに2番目に位置する値を答えとする。
解答
成功確率=13/27
説明のため、一様乱択して得た要素xのランクが、
rank(x) <= n/3のときA、
n/2 < rank(x) <=2n/3のときB、
2n/3 < rank(x)のときC
と書くとします。例えば、 2n/3 < rank(x1), rank(x2) <= n/3, rank(x3) <= n/3 の場合、CAAと書きます。
そうしますと上記アルゴリズムで得たx1,x2,x3の取りうるパターンは以下となり、太字にしたものが正解を得ます。
AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC,
BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC,
CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC,
それぞれのパターンの発生確率が一律なので、成功確率は13/27となります。
ちなみに本に記された解は19/27です。
正誤表
この本の正誤表はオフィシャルにはなさそうです。
有志で作られたこの本の正誤表があったみたいですが、もう見えなくなってました。ウェブアーカイブにも残ってないみたいです。
正誤表へのリンクが貼られたブログを見つけ、有志で作られた正誤表の存在を知りました。