Information Theory

By: Prof. Mohamed Hamada

Software Engineering Lab.
The University of Aizu
Evaluation

•  Attendance and class activities 20%

•  Midterm Exam 35%

•  Final Exam 45%

Contact

•  Send e-mail to
hamada@[Link]
•  Office: Room 346-C
•  Course materials at
[Link]/~hamada/[Link]

Check every week for update

Goals
•  Understand the concepts of information
entropy and channel capacity

•  Understand the digital communication model

and its components

•  Understand how the components operate

•  Understand data compression

•  Understand error detection and correction

 Course Outline

•  Introduction to set theory & probability

•  Introduction to information theory
•  Coding techniques & data compression
•  Information Entropy
•  Communication Channel
•  Error Detection and Correction
 Today’s Outline

Introduction to Set Theory and Probability

•  1. Sets, Operations on sets
•  2. Trial, Probability space, Events
•  3. Random variables, Probability distribution
•  4. Expected values, Variance
•  5. Conditional Probability
•  6. Bayes Theory
Sets
Sets
A set is a collection of objects without repetition.
The order of elements is irrelevant.

A set can be expressed by writing all elements

Example : even = { 0, 2, 4, 6, 8, 10 }

OR can be expressed by suing a common

property of its elements

Example : even = {x : 0 ≤ x ≤ 10 and x is even }

Sets
Elements of sets :
We use the symbols ∈ and ∉ to show that an element
belongs to a set or not
Example : even = { 0, 2, 4, 6, 8, 10 }
2 ∈ even
3 ∉ even

Subsets : A subset of a set A is a collection of elements

that all belongs to A
Example : S = {2,4} ⇒ S ⊂ even
T = {1, 4 } ⇒ T ⊄ even

Empty Set : is the set of no elements φ ={ }

Operations on sets

Set Union
A U B = { x | x ∈ A or x ∈ B }

Commutative A U B = B U A

Example : even = {0, 2, 4, 6 }

odd = {1, 3, 5 }

even U odd = {0, 1, 2, 3, 4, 5, 6}

Operations on sets

Set Intersection
A ∩ B = {x | x ∈ A and x ∈ B }

Commutative A ∩ B = B∩ A

Example: even = {0, 2, 4, 6 }

odd = {1, 3, 5 }

even ∩ odd = φ

even ∩ {1, 2, 3 } = {2}

Operations on sets

Set Subtraction
A – B = {x | x ∈ A and x ∉ B }

Non commutative A-B ≠ B–A

Example : even = {0, 2, 4, 6 }

odd = {1, 3, 5 }

even – odd = even

even – {1, 2, 3} = {0, 4, 6 }

Operations on sets

Power Set
Power Set: is the set of all subsets

P(A) = 2A = {B | B ⊆ A}

Example: odd = {1, 3, 5 }

P(odd) = 2odd = { φ, {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, odd }

Cardinality
Cardinality is the number (#) of elements in a set

Example: # (odd) = 3 , # (2odd) = 8 = 23 = 2#(odd)

Trials

Many problems in probabilities and statistics involve

situations in which an experiment with the possible
outcomes is repeated several times.

Each repetition of the experiment is called a trail.

Example : throw a dice

Probability
Probability:
A probability is a number associated with or assigned to a set in
order to measure it in some sense

Probability Space:
Consider the symbols Ω and P where
Ω : universal set ;
P : is a probability function mapping power set to reals in the
interval [0,1]; i.e. P: 2Ω → [0,1]
With the following 3 properties:
(1) P(Ø) = 0
(2) P(Ω) = 1
(3) ∀ A = {a1, a2, …, am } ⊂ Ω ,

m
P(A) = ∑ P (an),
n=1
where P(an) = P({an})
Event

The subset of Ω to which a probability has been

assigned is called an event

An event is a classification of trial outcome.

Example :

The set of events of throwing a dice is {1,2,3,4,5,6}

 Random Variables

Random Variable is a numerical quantity whose value depends on

chance.
Example : A person to be selected at random

For a universal set Ω and a ∈ Ω

The function X : Ω → set of numerical values is called a random
variable
Example : Throwing 2 dice we get
(1,1), (1,2), (1,3), (1,4), (1,5), (1,6)
(2,1), (2,2), (2,3), (2,4), (2,5), (2,6)
Ω = (3,1), (3,2), (3,3), (3,4), (3,5), (3,6)
Ω = { (m,n) | m,n ∈ {1,2,…, 6} } (4,1), (4,2), (4,3), (4,4), (4,5), (4,6)
(5,1), (5,2), (5,3), (5,4), (5,5), (5,6)
(6,1), (6,2), (6,3), (6,4), (6,5), (6,6)
Random Variables

Proposition

If X and Y are random variables then

X+Y, X-Y, XY and X/Y (Y ≠0)
are random variables
 Probability Distribution

The probability that the random variable X takes the value an is

pn = P(X = an )
pn ≥0, ∑ pn = 1

If certainty is 100% then probability = 1 (unity)

In general ∀n 0 ≤ pn ≤1

Example : fair coin front ↑ back ↓ ⎛↑ ↓ ⎞

⎝ ½ ½ ⎠
Probability Distribution
Example : fair dice
⎛ 1 2 3 4 5 6 ⎞
⎝ 1/6 1/6 1/6 1/6 1/6 1/6 ⎠

Example of random variable : sum of two dice throws

Consider the random variable X1 as outcome of the first dice:
X1 ((m, n)) = m
Consider the random variable X2 as outcome of the second dice:
X2 ((m, n)) = n
Consider the random variable X3 as sum of X1 and X2 (X3=X1+X2):
X3 ((m, n)) = m + n
+ 1 2 3 4 5 6 Probability distribution of X1
1 2 3 4 5 6 7

Probability distribution of X2 2 3 4 5 6 7 8
3 4 5 6 7 8 9
4 5 6 7 8 9 10 Probability distribution of X3
5 6 7 8 9 10 11
6 7 8 9 10 11 12
 Expected value ( mean or average value )

The Expected value is designed as fallows :

Take the value of (the random variable ) X at each

point a ∈ Ω , multiply it by the probability of that point
(i.e P(a)) and sum over all a ∈ Ω

E (X) = ∑ X(a) P(a)

a∈Ω

Note that:
E (X + Y) = E (X) + E (Y)
E (cX) = c E (X) (for constant c)
Expected value ( mean or average value )
E (X) = ∑ X(a) P(a)
a∈Ω

Example
Consider a land with 100 acre with 50% of price $150 per acre,
30% of price $100 per acre and 20% of price $50 per acre. 30% 20%
$100 $50

What is the average (expected or mean) price per acre for 50% $150
the whole land?

Answer:
Ω = {50%, 30%, 20% } = {50/100, 30/100, 20/100}

E (X) = 150 * 50/100 + 100 * 30/100 + 50 * 20/100 = 115 $ per acre

 Variance

The Variance of a variable X (denoted by V(X) or σ2 (X) is defined by

V(X) = E [ ( X – E(X))2 ]

Note that: for a constant c

V (c) = E [(c – E (c))2 ] V (cX) = E [ (cX – E(cX))2]

= E [(c – c)2 ] = E [ (cX – cE(X))2]
=0 = E [ c2(X – E(X))2]
= c2 E [ (X – E(X))2]
= c2 V(X)
 Variance
Example:
For a fair coin toss (with front denoted by ↑ and back denoted by ↓) we have

(↑‚↑) (↑‚↓) (↓‚↑ ) (↓‚↓) ∑

p ¼ ¼ ¼ ¼ 1

x=#(↑) 2 1 1 0 4

x P(x) 2/4 ¼ ¼ 0/4 E[X] = 1

(x- E[x])2 P(x) (2-1)2 /4 (1-1)2 /4 (1-1)2 /4 (0-1)2 /4 V[X] = 1/2

Exercise

Prove this equality

V(X) = E(X2) – E(X)2

Exercise: Answer
Prove this equality V(X) = E(X2) – E(X)2

Answer:

V (X) = E [ (X – E (X))2]
= E [ (X – E (X ))( X – E(X))]
= E [ X2 – 2XE(X) + E(X)2]
= E(X2 ) - 2E(X)2 + E(X)2
= E(X2 ) - E(X)2
 Conditional Probability
Conditional probability is the probability of A when B is known

P(A∩B)
P(A|B) =
P( B )

Example:
If a dice is rolled:
Let an event A = the dice comes up with 5 = {5}
Let an event B = the dice comes up odd = {1,3,5}
Then: P(A)=1/6, P(B)=P({1,3,5})=P({1})+ P({3})+ P({5})=1/6+ 1/6+ 1/6=1/2
A ∩ B = {5}, P(A ∩ B)=P({5})=1/6

Hence P(A | B) = P(A ∩ B) / P(B)= (1/6) / (1/2) = 1/3

 Conditional Probability
Note that : A B

A-B A∩B B-A

P(B) = P(A ∩ B) + P(B – A) ≥ P (A ∩ B) ⇒ P (A | B) ≤ 1

If B ⊆ A ⇒ A ∩ B = B ⇒ P ( A | B ) = 1
Bayes Theorem
P(B) P(A | B)
P(B|A) =
P(A)

Knowing the outcome of a particular situation, one (using

Bayes theorem) can find the probability that the outcome
occurred as a result of a particular previous event.

Note that:
1. in general P(A | B) ≠ P(B | A)
2. P(A | B) = P(B | A) only if P(A) = P(B)
 Bayes Theorem
Example: Throw a single dice: let A = { x | x odd }, B = { 1,2 }

P(A∩B) 1/6
P(A|B) = = = 1/2
P( B ) 2/6

P(B) P(A | B) (2/6) (1/2)

P(B|A) = = = 1/3
P(A) 3/6
 Bayes Theorem
Properties:
P (φ ∩ B) P (φ) 0
1. P (φ|B) = = = = 0
P(B) P(B) P(B)

P (Ω ∩ B) P(B)
2. P (Ω |B) = = =1
P(B) P(B)

P(A ∩ B) ∑a∈A P({a} ∩ B) P({a} ∩ B)

3. P (A|B) = = = ∑a∈A = ∑a∈A P({a} |B)
P(B) P(B) P(B)
Independence of Random Variables

Two discrete random variables, X1 and X2 are independent if

∀ value j, k P(X1 = j ∩ X2 = k) = P (X1 = j) P (X2 = K)

Note that:
If X1 and X2 are independent random variables then it is easy to
show that:

P (X1 = j | X2) = P (X1 = j)

END