暗号理論の問題

$T$ の範囲。 出力は $6$ 通りしかないので、鳩の巣原理により $7$ 個目までには必ず衝突が起こる。よって $T$ は $2\le T\le 7$ の整数値をとる。

$P(T>k)$ を求める。 $T>k$ は「最初の $k$ 個のハッシュ値がすべて異なる」ことと同じである。各出力は独立に等確率なので、$1\le k\le 6$ に対して
$$P(T>k)=\frac{6}{6}\cdot \frac{5}{6}\cdots \frac{6-k+1}{6}=\frac{6!}{(6-k)!6^k}$$
であり、$P(T>0)=1$、$k\ge 7$ では $P(T>k)=0$ である。

期待値の公式。 $T$ は $0$ 以上の整数値をとる確率変数なので
$$E[T]=\sum _{k=0}^{\infty }P(T>k)$$
が成り立つ（$T={\sum }_{k\ge 0}1[T>k]$ の両辺の期待値をとればよい）。各項を計算すると
$$\begin{array}{rl}P(T>0)& =1,P(T>1)=1,\\ P(T>2)& =\frac{6\cdot 5}{6^2}=\frac{5}{6},P(T>3)=\frac{6\cdot 5\cdot 4}{6^3}=\frac{5}{9},\\ P(T>4)& =\frac{6\cdot 5\cdot 4\cdot 3}{6^4}=\frac{5}{18},P(T>5)=\frac{6\cdot 5\cdot 4\cdot 3\cdot 2}{6^5}=\frac{5}{54},\\ P(T>6)& =\frac{6!}{6^6}=\frac{720}{46656}=\frac{5}{324}.\end{array}$$
したがって、分母を $324$ にそろえて
$$E[T]=2+\frac{270+180+90+30+5}{324}=2+\frac{575}{324}=\frac{1223}{324}.$$

確かめ（分布から直接）。 $P(T=k)=P(T>k-1)-P(T>k)$ より、分母 $7776=6^5$ で
$$P(T=2)=\frac{1296}{7776},P(T=3)=\frac{2160}{7776},P(T=4)=\frac{2160}{7776},P(T=5)=\frac{1440}{7776},P(T=6)=\frac{600}{7776},P(T=7)=\frac{120}{7776}$$
（和は $7776/7776=1$）。よって
$$E[T]=\frac{2\cdot 1296+3\cdot 2160+4\cdot 2160+5\cdot 1440+6\cdot 600+7\cdot 120}{7776}=\frac{29352}{7776}=\frac{1223}{324}$$
となり一致する。

答え：$E[T]=\frac{1223}{324}$（約 $3.77$）

$T\ge 2$ であり、7 個目までには必ず衝突するので $T\le 7$。$E[T]={\sum }_{k\ge 0}P(T>k)$ を使う。$T>k$ は最初の $k$ 個のハッシュ値がすべて異なることと同値で、
$$P(T>k)=\prod _{i=0}^{k-1}\frac{6-i}{6}(k=0,1,\dots ,6),P(T>k)=0(k\ge 7).$$

• $k=0$: $1$
• $k=1$: $1$
• $k=2$: $\frac{5}{6}$
• $k=3$: $\frac{5}{6}\cdot \frac{4}{6}=\frac{5}{9}$
• $k=4$: $\frac{5}{9}\cdot \frac{3}{6}=\frac{5}{18}$
• $k=5$: $\frac{5}{18}\cdot \frac{2}{6}=\frac{5}{54}$
• $k=6$: $\frac{5}{54}\cdot \frac{1}{6}=\frac{5}{324}$

分母を $324$ にそろえて足すと $\frac{324+324+270+180+90+30+5}{324}=\frac{1253}{324}$。

検算: $P(T=k)=P(T>k-1)-P(T>k)$ より $P(T=2)=\frac{1}{6},P(T=3)=\frac{5}{6}-\frac{5}{9}=\frac{5}{18},P(T=4)=\frac{5}{9}-\frac{5}{18}=\frac{5}{18},P(T=5)=\frac{5}{18}-\frac{5}{54}=\frac{10}{54}=\frac{5}{27},P(T=6)=\frac{5}{54}-\frac{5}{324}=\frac{25}{324},P(T=7)=\frac{5}{324}$。確率の和は $\frac{54+90+90+60+25+5}{324}=\frac{324}{324}=1$。期待値は $\frac{2\cdot 54+3\cdot 90+4\cdot 90+5\cdot 60+6\cdot 25+7\cdot 5}{324}=\frac{108+270+360+300+150+35}{324}=\frac{1223}{324}$ ではなく計算し直すと、$108+270=378,378+360=738,738+300=1038,1038+150=1188,1188+35=1223$。${\sum }_{k\ge 0}P(T>k)$ の方は $P(T>0)=P(T>1)=1$ から始まるので、定義を合わせて検算し直す。$T$ は最小でも 2 なので $E[T]={\sum }_{k=0}^{6}P(T>k)$ で、$k=0,1$ の項がそれぞれ $1$ である。分子の和 $324+324+270+180+90+30+5=1223$ であり、$1253$ は足し間違いだった。

したがって $E[T]=\frac{1223}{324}\approx 3.775$。