Transcript Basic Principles

Basic Principles
(continuation)
1
A Quantitative Measure of Information
• As we already have realized, when a statistical
experiment has n eqiuprobable outcomes, the
average amount of information associated
with an outcome is log n
2
A Quantitative Measure of Information
• Let us consider a source with a finite number of
messages and their corresponding transmission
probabilities
x1, x2 ,..., xk 
• The source selects at random each one of these
messages. Successive selections are assumed to
be statistically independent.
• P{xk} is the probability associated with the
selection of message xk:
P{x1}, P{x2},..., P{xk }
3
A Quantitative Measure of Information
• The amount of information associated
with the transmission of message xk is
defined as
I k   log P xk 
• Ik is called the amount of self-information
of the message xk.
• The average information per message for
the source is
I  statistical average of I   P  x  log P  x 
n
k
k 1
k
k
4
A Quantitative Measure of Information
• If a source transmits two symbols 0 and 1 with
equal probability then the average amount of
information per symbol is
 1
1 1
1 
I     log    log    1 bit
2 2
2 
 2
• If the two symbols were transmitted with
probabilities α and 1- α then the average
amount of information per symbol is
I   log   (1   ) log(1   )
5
ENTROPY
• The average information per message I is also
referred to as the entropy (or the
communication entropy) of the source. It is
usually denoted by the letter H.
• The entropy of a just considered simple source
is
H  p1 , p2 ,..., pn     p1 log p1  p2 log p2  ...  pn log pn 
• (p1, p2, …, pn) refers to a discrete complete
probability scheme.
6
Basic Concepts of Discrete
Probability
Elements of the Theory of Sets
7
Background
• Up to 1930s a common approach to the
probability theory was to set up an
experiment or a game to test some intuitive
notions.
• This approach was very contradictory because
it was not objective, being based on some
subjective view.
8
Background
• Suppose, two persons, A and B, play a game of
tossing a coin. The coin is thrown twice. If a
head appears in at least one of the two
throws, A wins; otherwise B wins.
• Solution?
9
Background
• The simplest intuitive approach leads to the 4
possible outcomes: (HH), (HT), (TH), (TT). It
follows from this that chances of A to win are
3/4, since a head occurs in 3 out of 4 cases.
• However, the different reasoning also can be
applied. If the outcome of the first throw is H,
A wins, and there is no need to continue. Then
only 3 possibilities need be considered:
(H), (TH), (TT), and therefore the probability
that A wins is 2/3.
10
Background
• This example shows that a good theory must
be based on the axiomatic approach, which
should not be contradictory.
• Axiomatic approach to the probability theory
was developed in 1930s-1940s. The initial
approach was formulated by A. Kolmogorov.
• To introduce the fundamental definitions of
the theory of probability, the basic element of
the theory of sets must first be introduced.
11
Sets
• The set, in mathematics, is any collection of
objects of any nature specified according to a
well-defined rule.
• Each object in a set is called an element (a
member, a point). If x is an element of the set
X, (x belongs to X) this is expressed by
•
x X
x X
means that x does not belong to X
12
Sets
• Sets can be finite (the set of students in the
class), infinite (the set of real numbers) or
empty (null - a set of no elements).
• A set can be specified by either giving all its
elements in braces (a small finite set) or
stating the requirements for the elements
belonging to the set.
• X={a, b, c, d}
• X={x}|x is a student taking the “Information
theory” class
13
Sets
•
•
•
•
•
•
Z
Q
R
C
is the set of integer numbers
is the set of rational numbers
is the set of real numbers
is the set of complex numbers
 is an empty set
X   is a set whose single element is an
empty set
X
X
X
X
14
Sets
• What about a set of the roots of the equation
2 x 2  1  0?
• The set of the real roots is empty: 
• The set of the complex roots is i / 2, i / 2 ,
where i is an imaginary unity
15
Subsets
• When every element of a set A is at the same
time an element of a set B then A is a subset
of B (A is contained in B):
• For example,
A B
BA
Z  Q, Z  R, Q  R, R  C
16
Subsets
• The sets A and B are said to be equal if they
consist of exactly the same elements.
• That is, A  B, B  A  A  B
• For instance, let the set A consists of the roots
of equation
2
x( x  1)( x  4)( x  3)  0
B  2, 1, 0, 2,3
C   x | x  Z,| x | 4
• What about the relationships among A, B, C ?
17
Subsets
AC
BC
A  B
 A B
B  A
18
Universal Set
• A large set, which includes some useful in
dealing with the specific problem smaller sets,
is called the universal set (universe). It is
usually denoted by U.
• For instance, in the previous example, the set
of integer numbers Z can be naturally
considered as the universal set.
19
Operations on Sets: Union
• Let U be a universal set of any arbitrary
elements and contains all possible elements
under consideration. The universal set may
contain a number of subsets A, B, C, D, which
individually are well-defined.
• The union (sum) of two sets A and B is the set
of all those elements that belong to A or B or
both:
A B
20
Operations on Sets: Union
A  {a, b, c, d }; B  {e, f }; A  B  {a, b, c, d , e, f }
A  {a, b, c, d }; B  {c, d , e, f }; A  B  {a, b, c, d , e, f }
A  {a, b, c, d }; B  {c, d }; A  B  {a, b, c, d }  A
Important property:
B  A  A B  A
21
Operations on Sets: Intersection
• The intersection (product) of two sets A and B
is the set of all those elements that belong to
both A and B (that are common for these
sets):
A B
• When A  B   the sets A and B are said to
be mutually exclusive.
22
Operations on Sets: Intersection
A  {a, b, c, d }; B  {e, f }; A  B  
A  {a, b, c, d }; B  {c, d , f }; A  B  {c, d }
A  {a, b, c, d }; B  {c, d }; A  B  {c, d }  B
Important property:
B  A  A B  B
23
Operations on Sets: Difference
• The difference of two sets B and A (the
difference of the set A relative to the set B ) is
the set of all those elements that belong to
the set B but do not belong to the set A:
B / A or B  A
24
Operations on Sets: Complement
• The complement (negation) of any set A is the
set A’ ( A ) containing all elements of the
universe that are not elements of A.
25
Algebra of Sets
• Let A, B, and C be subsets of a universal set U.
Then the following laws hold.
• Commutative Laws: A  B  B  A; A  B  B  A
• Associative Laws: ( A  B)  C  A  ( B  C )
( A  B)  C  A  ( B  C )
• Distributive Laws:
A  ( B  C )  ( A  B)  ( A  C )
A  ( B  C )  ( A  B)  ( A  C )
26
Algebra of Sets
• Complementary:
A  A  U
A  A  
A U  U
A U  A
A  A
A  
(
A

B
)

(
A

B
)

A
• Difference Laws:
( A  B)  ( A  B)  
A  B  A  B
27
Algebra of Sets
• De Morgan’s Law (Dualization):

A

B

  A  B
 A  B   A  B
• Involution Law:  A   A
• Idempotent Law: For any set A:
A A  A
A A  A
28