随机算法 (Fall 2011)/Probability Space

From EtoneWiki
Jump to: navigation, search

Axioms of Probability

The axiom foundation of probability theory is laid by Kolmogorov, one of the greatest mathematician of the 20th century, who advanced various very different fields of mathematics.

Definition (Probability Space)

A probability space is a triple .

  • is a set, called the sample space.
  • is the set of all events, satisfying:
    (K1). and . (The certain event and the impossible event.)
    (K2). If , then . (Intersection, union, and diference of two events are events).
  • A probability measure is a function that maps each event to a nonnegative real number, satisfying
    (K3). .
    (K4). If (such events are call disjoint events), then .
    (K5*). For a decreasing sequence of events of events with , it holds that .

The sample space is the set of all possible outcomes of the random process modeled by the probability space. An event is a subset of . The statements (K1)--(K5) are axioms of probability. A probability space is well defined as long as these axioms are satisfied.

Example
Consider the probability space defined by rolling a dice with six faces. The sample space is , and is the power set . For any event , its probability is given by
Remark
  • In general, the set may be continuous, but we only consider discrete probability in this lecture, thus we assume that is either finite or countably infinite.
  • In many cases (such as the above example), , i.e. the events enumerates all subsets of . But in general, a probability space is well-defined by any satisfying (K1) and (K2). Such is called a -algebra defined on .
  • The last axiom (K5*) is redundant if is finite, thus it is only essential when there are infinitely many events. The role of axiom (K5*) in probability theory is like Zorn's Lemma (or equivalently the Axiom of Choice) in axiomatic set theory.

Laws for probability can be deduced from the above axiom system. Denote that .

Proposition
.
Proof.

Due to Axiom (K4), which is equal to 1 according to Axiom (K3), thus . The proposition follows.

Exercise: Deduce other useful laws for probability from the axioms. For example, .

Notation

An event can be represented as with a predicate .

The predicate notation of probability is

.
Example
We still consider the probability space by rolling a six-face dice. The sample space is . Consider the event that the outcome is odd.
.

During the lecture, we mostly use the predicate notation instead of subset notation.

The Union Bound

We are familiar with the principle of inclusion-exclusion for finite sets.

Principle of Inclusion-Exclusion
Let be finite sets. Then

The principle can be generalized to probability events.

Principle of Inclusion-Exclusion for Probability
Let be events. Then

We only prove the basic case for two events.

Lemma
For any two events and ,
.
Proof.
The followings are due to Axiom (K4).

The lemma follows directly.

A direct consequence of the lemma is the following theorem, the union bound.

Theorem (Union Bound)
Let be events. Then

The name of this inequality is Boole's inequality. It is usually referred by its nickname the "union bound". The bound holds for arbitrary events, even if they are dependent. Due to this generality, the union bound is extremely useful in probabilistic analysis.

Independence

Definition (Independent events)
Two events and are independent if and only if

This definition can be generalized to any number of events:

Definition (Independent events)
Events are mutually independent if and only if, for any subset ,

Note that in probability theory, the "mutual independence" is not equivalent with "pair-wise independence", which we will learn in the future.