劣加法的集合函数

劣加法的集合函数について

劣加法的集合函数とは、二つの集合の合併に対して、その評価がそれぞれの集合の評価の和と比較して上から抑えられるような集合関数を指します。この概念は、数学の分野において重要な役割を果たし、様々な応用があります。特に、劣モジュラーという特別なタイプの劣加法的関数や、より一般的な分割劣加法的な関数に関連しています。

定義

劣加法的集合函数は、集合Ωのすべての部分集合に対して次の条件を満たします。関数fがΩの冪集合2Ωを定義域とし、任意の集合SとTに対して次の不等式が成り立つ場合、fは劣加法的であるとされます:

$$
f(S ∪ T) ≤ f(S) + f(T) \\
(∀ S, T ⊂ Ω)
$$

この評価関数の終域Bは、多くの場合、実数直線Rまたは非負実数直線R+になります。

具体例

劣加法的集合函数の具体例としては、非負劣モジュラー集合函数があります。これは劣加法的集合函数の特殊なケースであり、劣加法的集合函数全体の中に含まれています。また、与えられた集合Sを完全に被覆するために必要な集合の数を数える関数f(S)も劣加法的です。具体的には、T1, …, Tmからなる部分集合で、これらの合併がΩを形成する場合、f(S)はその被覆に必要な最小の集合数を返します。

具体的には、次のように定義されます:

$$
f(S) := min \\
{ t ∣ ∃ i1, …, it s.t. S ⊂ ∪_{j=1}^t T_{ij} }
$$

この設定において、この関数fは劣加法的です。また、全ての非負値加法的集合函数、特に測度もこの特性を持っています。

性質

劣加法的集合函数は、一般に加法的な関数の集合から引数ごとに最大のものを取ることで生成されます。これにより、次のような関数f(S)が得られます:

$$
f(S) := max_{i=1,…,m} a_{i}(S) \\ (∀ S ⊂ Ω)
$$

このような関数は、分割的劣加法性の性質によって特徴づけられます。各部分集合Sに対し、他の部分集合X1, …, Xnと、それに対応する重みα1, …, αnがあれば、次の不等式が成り立ちます:

$$
1_S ≤ ∑_{i=1}^{n} α_i imes 1_{X_i} \\
⇒ f(S) ≤ ∑_{i=1}^n α_i imes f(X_i)
$$

分割的劣加法集合函数は、劣モジュラー集合函数の一般化であり、特に劣加法的集合函数の一種でもあります。

まとめ

劣加法的集合函数は、数学の中で非常に重要な概念であり、情報理論や最適化問題、ゲーム理論などの分野でも応用されています。これらの関数が持つ特性は、計算の効率性を保ちながら、もっとも求められる結果を導くための鍵となります。

もう一度検索