最小エントロピー

• 最小エントロピー
  • 概要
  • 定義
  • シャノンエントロピーとの関係
  • 性質
  • 応用例

概要

最小エントロピー(min-entropy)は, シャノンエントロピーよりも保守的な不確実性の測度です. ランダムネス抽出器や暗号学において重要な役割を果たし, 最悪の場合の不確実性を測る指標として用いられます.

定義

定義 (最小エントロピー)

有限集合$\calX$上に値をとる確率変数$X$に対して, 以下で定義される量$\minentropy(X)$を$X$の最小エントロピー (min-entropy)という:

\[\begin{align*} \minentropy(X) = \min_{x\in\calX} \qty{ \ln\frac{1}{\Pr[X=x]} }. \end{align*}\]

最小エントロピーは, 確率変数$X$の最も確率の高い値の情報量を表します. つまり, 最悪の場合の不確実性を測る指標です.

シャノンエントロピーとの関係

最小エントロピーはシャノンエントロピーよりも保守的な測度です.

確率変数$X$に対して

\[\begin{align*} \minentropy(X) \le \entropy(X). \end{align*}\]

この不等式は, 最小エントロピーがシャノンエントロピーを下回ることを示しています. これは, 最小エントロピーが最悪の場合の不確実性を測るのに対し, シャノンエントロピーが平均的な不確実性を測るためです.

性質

有限集合$\calX$上に値をとる確率変数$X$に対して

\[\begin{align*} 0 \le \minentropy(X) \le \ln \vert\calX\vert. \end{align*}\]

特に, $\minentropy(X) = 0$となるのは$X$が一点分布のとき, $\minentropy(X) = \ln \vert\calX\vert$となるのは$X$が一様分布のときである.

応用例

最小エントロピーは以下の分野で重要な役割を果たします:

• ランダムネス抽出器: 低最小エントロピーな乱数源から高品質な乱数を生成
• 暗号学: 暗号学的に安全な乱数生成のための条件
• プライバシー保護: 差分プライバシーにおけるプライベートな情報の保護
• 符号理論: エラー訂正符号の設計

最小エントロピーは, シャノンエントロピーでは捉えきれない最悪の場合の不確実性を評価する際に特に有用です.