17/09/17 17:08:10.68 gMyUTi3U.net
ある非常に有名な本に以下のような内容の記述があります。
でも、 n > 1 のとき、 H が universal になることは決してないですよね。
u = v のとき、常に、 h(u) = h(v) なので、問題の確率は 1 ですから。
--------------------------------------------------
U を要素数の非常に多い有限集合とする。
H を U から {0, 1, ..., n-1} へのすべての写像の集合のある部分集合とする。
u, v ∈ U に対して、ランダムに選んだ h ∈ H が h(u) = h(v) を満たす確率はたかだか 1/n であるとき、
H は universal であるという。