Характеристична функція

Графік характеристичної функції двовимірної підмножини квадрата.

Характеристична функція (індикаторна функція, індикатор) підмножини $A \subseteq X$ — функція, визначена на множині $X$, яка визначає належність елемента $x \in X$ підмножині $A$.

Термін характеристична функція в теорії ймовірностей використовується в іншому значенні (див. Характеристична функція випадкової величини).

Тому в теорії ймовірностей описана в цій статті функція називається індикаторною функцією.

Визначення

Нехай $A\subseteq X$ — деяка підмножина довільної множини $X$. Функція $\mathbf{1}_A:X\to\{0,1\}$, визначена таким чином:

$\mathbf{1}_A(x) = \left\{\begin{matrix} 1, &x \in A, \\ 0, &x \notin A, \end{matrix}\right.$

називається характеристичною функцією або індикатором множини $A$.

Альтернативними позначеннями індикатора множини $A$ є: $\chi_A\,$ або $\mathbf{I}_A$, а іноді навіть $\ A(x)$. Нотація Айверсона дозволяє позначення $[x \in A]$.

(Грецька літера $\ \chi$ походить від початкової букви грецького написання слова характеристика.)

Замітка. Позначення $\mathbf{1}_A$ може означати тотожну функцію.

Основні властивості

Відображення, яке пов'язує підмножину $A \subseteq X$ з його індикатором $\mathbf{1}_A$ є ін'єкцією. Якщо $A$ і $B$ — дві підмножини $X \$, то

$\mathbf{1}_{A\cap B} = \min\{\mathbf{1}_A,\mathbf{1}_B\} = \mathbf{1}_A \mathbf{1}_B,$

$\mathbf{1}_{A\cup B} = \max\{{\mathbf{1}_A,\mathbf{1}_B}\} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \mathbf{1}_B,$

$\mathbf{1}_{A\triangle B} = \mathbf{1}_A + \mathbf{1}_B - 2(\mathbf{1}_{A\cap B}),$

$\mathbf{1}_{A^c} = 1-\mathbf{1}_A.$

Більш загально, припустимо $A_1,\ldots, A_n$ — множина підмножин $X$. Ясно, що для довільного $x \in X$

$\prod_{k \in I} ( 1 - \mathbf{1}_{A_k}(x))$

— добуток нулів і одиниць. Цей добуток приймає значення 1 для тих $x \in X$, які не належать жодній множині $A_k$ і 0 в іншому випадку. Тому

$\prod_{k \in I} ( 1 - \mathbf{1}_{A_k}) = \mathbf{1}_{X - \bigcup_{k} A_k} = 1 - \mathbf{1}_{\bigcup_{k} A_k}.$

Розкладаючи ліву частину, одержуємо

$\mathbf{1}_{\bigcup_{k} A_k}= 1 - \sum_{F \subseteq \{1, 2, \ldots, n\}} (-1)^{|F|} \mathbf{1}_{\bigcap_F A_k} = \sum_{\emptyset \neq F \subseteq \{1, 2, \ldots, n\}} (-1)^{|F|+1} \mathbf{1}_{\bigcap_F A_k},$

де $|F|$ — потужність $F$. Це одна з форм запису принципу включення-виключення. Отже індикатор — корисне позначення в комбінаториці, яке використовується також і в інших областях, наприклад в теорії ймовірностей: якщо $X$ — ймовірнісний простір з ймовірнісною мірою $\mathbf{P}$, а $A$ — вимірна множина, то індикатор $\mathbf{1}_A$ стає випадковою величиною величиною, чиє математичне очікування рівне ймовірності $A:$

$E(\mathbf{1}_A)= \int\limits_{X} \mathbf{1}_A(x)\,d\mathbf{P} = \int\limits_{A} d\mathbf{P} = \mathbf{P}(A).\quad$

Варіація і коваріація для цієї випадкової змінної визначаються за формулами:

$\operatorname{Var}(\mathbf{1}_A (\omega)) = \operatorname{P}(A)(1 - \operatorname{P}(A))$

$\operatorname{Cov}(\mathbf{1}_A (\omega), \mathbf{1}_B (\omega)) = \operatorname{P}(A \cap B) - \operatorname{P}(A)\operatorname{P}(B)$

Див. також

• Характеристична функція випадкової величини
• Характеристична функція (теорія ігор)

Література

• Folland, G.B.; Real Analysis: Modern Techniques and Their Applications, 2nd ed, John Wiley & Sons, Inc., 1999.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 5.2: Indicator random variables, pp.94–99.