給定一個雜湊函式；假設域 % codomain = 0 和均勻的碰撞分佈；碰撞（不是輸出截斷）如何失去熵？
假設我們的域和共域都有 4 個元素，輸入到輸出的均勻分佈意味著函式是單射的。人們普遍認為，隨機選擇域元素會導致選擇中的 log2(4) = 2 位熵，並且由於是單射的，因此輸入該選擇的所述函式的輸出也將包含 2 位熵。
如果我們將域元素計數加倍到 8，那麼隨機選擇將具有 log2(8) = 3 位熵。由於鴿巢原理存在衝突，但我們定義了均勻分佈，因此 4 個共域元素中的每一個都有兩個域元素映射到它。
在第二種情況下，顯然輸入的 3 位熵不能保留在輸出中，但為什麼會保留少於 2 位的熵呢？考慮到碰撞的均勻分佈所定義的缺乏偏差，它是否仍然只是從共域中選擇一個元素的可能性？
在這兩種情況下，是否都沒有將輸入的熵保留到輸出的位長度？即 log2(4) 涵蓋了 codomain 的 4 個元素。
假設我們的域和共域都有 4 個元素，輸入到輸出的均勻分佈意味著函式是單射的。
您似乎在以一種令人困惑的方式使用標準技術術語“均勻分佈”。通常是有限集上的均勻分佈 $ A $ 表示機率分佈 $ P $ 和 $ P(x) = 1/#A $ 對所有人 $ x \in A $ ， 在哪裡 $ #A $ 是元素的數量 $ A $ .
但是到目前為止您還沒有提到機率分佈；您似乎在濫用“均勻分佈”一詞來表示函式 $ f\colon A \to B $ 具有以下屬性：有一個數字 $ n $ 這樣對於每個 $ y \in B $ , 映射到的域中的元素數 $ y $ 是 $ #f^{-1}(y) = n $ . （人們可能會稱這樣的函式為“平衡”，特別是如果它是一個布爾函式——即，定義在輸出為單個位的位上的函式——但這種命名法不像機率論中的“均勻分佈”那樣標準。）
人們普遍認為，隨機選擇域元素會導致選擇中的 log2(4) = 2 位熵，
當您說“隨機選擇”時，並沒有指定您隨機選擇的機率分佈。但是如果選擇的熵是 log2(4)，那麼顯然你的意思是域上的均勻分佈。我建議您在談論隨機選擇時指定一個分佈。
並且由於是單射的，因此該選擇的所述函式輸入的輸出也將包含 2 位熵。
是的，如果 $ f $ 是內射的 $ H[f(X)] = H[X] $ 對於所有隨機變數 $ X $ 任何機率分佈，包括均勻分佈。
如果我們將域元素計數加倍到 8，那麼隨機選擇將具有 log2(8) = 3 位熵。
同樣，只有當隨機選擇均勻分佈在整個域上時。
由於鴿巢原理存在衝突，但我們定義了均勻分佈，因此 4 個共域元素中的每一個都有兩個域元素映射到它。
是的，如果“均勻分佈”是指具有相同數量原像的函式 $ #f^{-1}(y) \subseteq A $ 對於任何元素 $ y \in B $ 在圖像中。
在第二種情況下，顯然輸入的 3 位熵不能保留在輸出中，但為什麼會保留少於 2 位的熵呢？考慮到碰撞的均勻分佈所定義的缺乏偏差，它是否仍然只是從共域中選擇一個元素的可能性？
讓我們舉一個具體的例子。
定義 $ f(x) = x \bmod 4 $ 上 $ {0,1,2,\dotsc,15} $ . 您可以輕鬆地確認 $ f $ 具有你稱為“均勻分佈”的特性——圖像的每個元素 $ {0,1,2,3} $ 正好有四個原像。也就是說，在 $ f $ ，以下幾組輸入顯然會發生衝突：
- $ {0,4,8,12} $
- $ {1,5,9,13} $
- $ {2,6,10,14} $
- $ {3,7,11,15} $
考慮以下兩個在域上的機率分佈 $ f $ :
- $ P(x) = 1/4 $ 為了 $ x \in {0,1,2,3} $ ，否則為零。
- $ Q(x) = 1/4 $ 為了 $ x \in {0,4,8,12} $ ，否則為零。
清楚地 $ P $ 和 $ Q $ 具有相同的熵——2 位。有什麼作用 $ f $ 關於熵？
- 讓 $ X \sim P $ . 然後 $ f(X) $ 有四個可能的結果，每個結果的機率為 1/4，所以熵是相同的： $ H[f(X)] = H = 2,\mathrm{bits} $ .
- 讓 $ X \sim Q $ . 然後 $ f(X) = 0 $ 機率為 1。所以 $ H[f(X)] = 0 $ .
顯然兩者都沒有 $ P $ 也不 $ Q $ 是域上的均勻分佈 $ f $ . 如果我們定義 $ U $ 成為那個分佈——也就是說， $ U(x) = 1/16 $ 對於每個 $ x \in {0,1,2,\dotsc,15} $ , 並繪製 $ X \sim U $ ——那麼當然， $ H[f(X)] = 2,\mathrm{bits} $ , 最大可能。