最小熵的單調性
讓 $ Z^t = (Y_1,\ldots,Y_t) $ 是一系列隨機變數，每個變數取值 $ Y $ . 隨機變數不一定是獨立同分佈的，但我們知道聯合分佈。即對於每個 $ z = (z_1,…,z_t) $ 我們知道 $ P^{Z^t}(z) $
隨機變數的最小熵 $ X $ 定義為 $ -\log_2(\max P(x) ) $ 對於 x 在值集中 $ X $ .
最後，我們定義一個值序列 $ H^\infty(t) = -\log_2(\max P^{Z^t}(z)) $ 為了 $ Z^t $ 定義如上。
我們如何證明 $ H^\infty(t) $ 在 t 中單調遞增？即對於 $ t’ \geq t $ 情況是這樣的 $ H^\infty(t’) \geq H^\infty(t) $ .
我沒有成功的嘗試是證明 $ \max P^{Z^t}(z^t) \geq \max P^{Z^{t’}}(z^{t’}) $ 在哪裡 $ t \leq t’ $ .
讓我們通過證明沒有元組索引的兩個變數的情況來使它變得更簡單一些。修復兩個隨機變數 $ X $ 和 $ Y $ . 是 $ H_\infty[X] \leq H_\infty[(X, Y)] $ ?
對於每個 $ x $ ， 我們有$$ \Pr[X = x] = \sum_y \Pr[X = x, Y = y]. $$ 請注意，由於機率質量始終為正， $ \max \Pr[\cdots] \leq \sum \Pr[\cdots] $ ; 然後感覺會顛倒，因為 $ p \mapsto -\log p $ 是一個減函式：
$$ \begin{align} H_\infty[X] &= -\log \max_x \Pr[X = x] \ &= -\log \max_x \sum_y \Pr[X = x, Y = y] \ &\leq -\log \max_x \max_y \Pr[X = x, Y = y] \ &= -\log \max_{x,y} \Pr[X = x, Y = y] \ &= H_\infty[(X, Y)]. \end{align} $$
然後證明 $ t \mapsto H_\infty[(Z_1, \dots, Z_t)] $ 正在增加，採取 $ X = (Z_1, \dots, Z_t) $ 和 $ Y = Z_{t+1} $ .