更好的最小熵下限
在Dodis、Ristenpart 和 Vadhan 撰寫的“用於有效採樣、依賴於種子的源的隨機性冷凝器”（PDF）中，我看到了以下聲明：
任何分佈元組 $ (X,Z) $ 是 $ \varepsilon $ -相近 $ (X′, Z) $ 這樣$$ H_\infty(X′\mid Z) ≥ H_2(X\mid Z) − \log (1/\varepsilon) $$提供一個可能優於最小熵的界限 $ H_\infty(X′\mid Z) ≥ H_2(X\mid Z)/2 $ .
我不明白為什麼會這樣。有人可以解釋一下嗎？它是否涉及剩餘雜湊引理！？
證明（由 M. Skorski 提供）依賴於所謂的“平滑”技術
$$ Cac97,RW,Sko15 $$. 對於一些 $ 0<\epsilon<1 $ ， 讓 $ B $ 是最重點的子集 $ X $ 其質量加起來 $ \epsilon $ - IE：
$$ \sum_{x\in B} p_X(x)=\epsilon, \text{ and } \min_{x\in B}p_X(x)\geq\max_{x\in\bar{B}}p_X(x). $$ 讓 $ X’ $ 表示條件分佈 $ X $ 上 $ \bar{B} $ - IE： $$ p_{X’}(x):= \begin{cases} 0 & x\in B,\ \frac{p_{X}(x)}{(1-\epsilon)} & x\in\bar{B}. \end{cases} $$ 注意之間的統計距離 $ X $ 和 $ X’ $ , $ \Delta(X,X’)=\epsilon $ . $ ^1 $ 讓 $ m:=\max_{x\in\bar{B}}p_X(x) $ . 現在，讓我們考慮碰撞熵 $ X $ : $$ H_2(X):=-\log\sum_{x\in X} p_X^2(x)\leq-\log\sum_{x\in B} p_X^2(x)\leq^2-\log (m\epsilon). $$ 它遵循 $ -\log(m)\geq H_2(X)-\log(1/\epsilon) $ , 結果如下 $ H_\infty(X’)=-\log(m/(1-\epsilon)) $ . 對於聯合分佈也可以提出類似的論點。
參考：
$$ Cac97 $$: C.卡欽。平滑熵和 Renyi 熵，EUROCRYPT'97。 $$ RW $$: R. Renner 和 S. Wolf。平滑仁義熵及其應用。 $$ Sko15 $$: M.斯科爾斯基。如何平滑熵？SOFSEM'16 腳註：1.證明：
$$ \begin{align} \Delta(X,X’) &=\frac{1}{2}\cdot\sum_{x\in X}\left|p_X(x)-p_{X’}(x)\right|\ &=\frac{1}{2}\cdot\sum_{x\in B}\left|p_X(x)\right|+\sum_{x\in \bar{B}}\left|p_X(x)-p_{X’}(x)\right|\ &=\frac{1}{2}\cdot\left(\epsilon+ \sum_{x\in \bar{B}}p_X(x)\left|1-\frac{1}{1-\epsilon}\right|\right)\ &=\frac{1}{2}\cdot\left(\epsilon+ (1-\epsilon)\left|1-\frac{1}{1-\epsilon}\right|\right)=\epsilon \end{align} $$ 2.證明： $ \sum_{x\in B} p_X^2(x)\geq \sum_{x\in B}m\cdot p_X(x)= m\cdot\epsilon $