シアラーの不等式

数学におけるシアラーの不等式、またはシアラーの補題は、情報理論における不等式であり、変数の集合のエントロピーと部分集合のエントロピーを 関連付けます。数学者ジェームズ・B・シアラーにちなんで名付けられました。

具体的には、X ₁、...、  X _{d が}ランダム変数であり、S ₁、...、  S _nが{1、2、...、  d }の部分集合であり、1からdまでのすべての整数がこれらの部分集合の少なくともrに含まれる場合、

${\displaystyle H[(X_{1},\dots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}H[(X_{j})_{j\in S_{i}}]}$

ここで、はエントロピーであり、はjの添字を持つランダム変数の直積である。^[1]${\displaystyle H}$${\displaystyle (X_{j})_{j\in S_{i}}}$${\displaystyle X_{j}}$${\displaystyle S_{i}}$

を [n] の部分集合の族（重複も含む）とし、それぞれが の少なくとも のメンバーに含まれるものとします。をの部分集合の別の集合とします。すると ${\displaystyle {\mathcal {F}}}$${\displaystyle i\in [n]}$${\displaystyle t}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle [n]}$

${\displaystyle {\mathcal {|}}{\mathcal {A}}|\leq \prod _{F\in {\mathcal {F}}}|\operatorname {trace} _{F}({\mathcal {A}})|^{1/t}}$

ここで の要素との可能な交差集合である。^[2]${\displaystyle \operatorname {trace} _{F}({\mathcal {A}})=\{A\cap F:A\in {\mathcal {A}}\}}$${\displaystyle {\mathcal {A}}}$${\displaystyle F}$

• ロヴァースの局所補題