NationMaster - Encyclopedia: Indicator function

In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics on Wiktionary, the free dictionary Wikimedia Commons has media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. Every set is a subset of itself. ...

Remark. The term "characteristic function" has an unrelated meaning in probability theory; see characteristic function. (For this reason, probabilists use the term indicator function for the function defined here almost exclusively, while mathematicians in other fields are more likely to use the term characteristic function to describe the function which indicates membership in a set.) Probability theory is the mathematical study of probability. ... Some mathematicians use the phrase characteristic function synonymously with indicator function. ... A probabilist is either a mathematician specializing in probability theory, or one who espouses probabilism in theology or philosophy. ...

The indicator function of a subset A of a set X is a function

$1_A : X to lbrace 0,1 rbrace$

defined as

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

The indicator function of A is sometimes denoted

$chi_A(x)$ or $I_A(x)$ or even $A(x).$

(The Greek letter χ because it is the initial letter of the Greek etymon of the word characteristic.) The Greek alphabet has been used to write the Greek language since about the 9th century B.C.. It was the first true alphabet, that is, one with a symbol for each vowel and consonant, and is the oldest alphabet in use today. ...

The Iverson bracket allows the notation $[x in A]$ . In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is defined as follows where P is a proposition. ...

Warning. The notation $1 A$ may signify the identity function. An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ...

Basic properties

The mapping which associates a subset A of X to its indicator function 1_A is injective; its range is the set of functions f:X →{0,1}. In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...

If A and B are two subsets of X, then

$1_{Acap B} = min{1_A,1_B} = 1_A 1_B,,$

$1_{Acup B} = max{{1_A,1_B}} = 1_A + 1_B - 1_A 1_B,$

$1_{Atriangle B} = 1_A + 1_B - 2(1_{Acap B}),$

and

$1_{A^complement} = 1-1_A.$

More generally, suppose A₁, ..., A_n is a collection of subsets of X. For any x ∈ X,

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

is clearly a product of 0s and 1s. This product has the value 1 at precisely those x ∈ X which belong to none of the sets A_k and is 0 otherwise. That is

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

Expanding the product on the left hand side,

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

where |F| is the cardinality of F. This is one form of the principle of inclusion-exclusion. In combinatorics, the inclusion-exclusion principle states that if A1, ..., An are finite sets, then where |A| denotes the cardinality of the set A. For example, taking n = 2, we get a special case of double counting: in words, we can count the size of the union of sets A...

As suggested by the previous example, the indicator function is a useful notational device in combinatorics. The notation is used in other places as well, for instance in probability theory: if X is a probability space with probability measure P and A is a measurable set, then 1_A becomes a random variable whose expected value is equal to the probability of A: Combinatorics is a odd branch of mathematics that studies collections (usually finite) then constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), with finding largest, smallest, or optimal objects (extremal combinatorics and combinatorial optimization), and with finding algebraic structures these objects may have (algebraic combinatorics). ... Probability theory is the mathematical study of probability. ... In mathematics, a probability space or probability measure is a set S, together with a Ïƒ-algebra X on S and a measure P on that Ïƒ-algebra such that P(S) = 1. ... In mathematics, a measure is a function that assigns a number, e. ... A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ... In probability theory (and especially gambling), the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects to win per bet if bets with identical...

$E(1_A)= int_{X} 1_A(x),dP = int_{A} dP = P(A).quad$

This identity is used in a simple proof of Markov's inequality. In probability theory, Markovs inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant. ...

References

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 0262032937. Section 5.2: Indicator random variables, pp.94–99.

Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...

Basic properties GA_googleFillSlot("encyclopedia_square");

References

See also

Basic properties