20/01/10 18:17:09.06 jmw8DMZb.net
まず式の設定。
≡は数列の同値類。
C(x)はxの属する類。
d(x)は列xの決定番号。
r(C)はCの代表元。
話を簡単にするため言い当てる確率を2/3以上にする。
各箱には0か1が確率1/2のベルヌーイ分布で入っているとする。
以上の設定において
-時枝の戦略-
与えられた列を３分割しx,y,zとする。
y,zを開けてd(y),d(z)を求めそれらより大きい番号Dを好きに選ぶ。
xのD番目以外を全部開けxの属する類Cを決定する。
そしてx[D]をr(C)[D]と推定する。
この時d(x)がDより大きい確率は高々1/3なので確率2/3以上でd(x)はD以下である。
特にi≧Dについてx[i]はr(C)[i]に一致する。