Transcript Introduction to Database Systems

Discrete Mathematics
Ch. 6 Counting and Probability
Today we will review sections 6.1, 6.2, 6.3
we will start with the topic of probability which is used in many
different areas including insurance, science, marketing, government
and many other areas.
Instructor: Hayk Melikyan
[email protected]
Melikyan/DM/Fall09
1
Sample Space, Events, and PROBABILITY
we will study the topic of probability which is
used in many different areas including
insurance, science, marketing, government and
many other areas.
Department of Mathematics and CS
Melikyan/DM/Fall09
2
Blaise Pascal-father of modern probability
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Pascal.html
Blaise Pascal
Born: 19 June 1623 in Clermont (now Clermont-Ferrand), Auvergne,
France Died: 19 Aug 1662 in Paris, France
In correspondence with Fermat he laid the foundation for
the theory of probability. This correspondence consisted of
five letters and occurred in the summer of 1654. They
considered the dice problem, already studied by Cardan,
and the problem of points also considered by Cardan and,
around the same time, Pacioli and Tartaglia. The dice
problem asks how many times one must throw a pair of
dice before one expects a double six while the problem of
points asks how to divide the stakes if a game of dice is
incomplete. They solved the problem of points for a two
player game but did not develop powerful enough
mathematical methods to solve it for three or more players.
Melikyan/DM/Fall09
3
Pascal
Melikyan/DM/Fall09
4
Probability
1.
Important in inferential statistics, a branch of
statistics that relies on sample information to
make decisions about a population.
2. Used to make decisions in the face of uncertainty.
Melikyan/DM/Fall09
5
Terminology
1. Random experiment: is a process or activity which
produces a number of possible outcomes. The
outcomes which result cannot be predicted with
absolute certainty.
Example 1:
Flip two coins and observe the possible outcomes of
heads and tails
Melikyan/DM/Fall09
6
Examples
2.
Select two marbles without replacement from a bag
containing 1 white, 1 red and 2 green marbles.
3. Roll two die and observe the sum of the points on
the top faces of each die.
All of the above are considered experiments.
Melikyan/DM/Fall09
7
Terminology
Sample space: is a list of all possible outcomes of the
experiment. The outcomes must be mutually exclusive and
exhaustive. Mutually exclusive means they are distinct and
non-overlapping. Exhaustive means complete.
Event: is a subset of the sample space. An event can be classified
as a simple event or compound event.
Melikyan/DM/Fall09
8
Terminology
1. Select two marbles in succession without
replacement from a bag containing 1 red, 1 blue
and two green marbles.
2. Observe the possible sums of points on the top
faces of two dice.
Melikyan/DM/Fall09
9
3. Select a card from an ordinary deck of playing cards (no jokers) The sample
space would consist of the 52 cards, 13 of each suit. We have 13 clubs, 13
spades, 13 hearts and 13 diamonds.
A simple event: the selected card is the two of clubs. A compound event is the
selected card is red (there are 26 red cards and so there are 26 simple
events comprising the compound event)
4.
Select a driver randomly from all drivers in the age category of 18-25.
(Identify the sample space, give an example of a simple event and a
compound event)
Melikyan/DM/Fall09
10
More examples
Roll two dice.
Describe the sample space of this event.
You can use a tree diagram to determine
the sample space of this experiment. There
are six outcomes on the first die {1,2,3,4,5,6}
and those outcomes are represented by six
branches of the tree starting from the “tree
trunk”. For each of these six outcomes,
there are six outcomes, represented by the
brown branches. By the fundamental
counting principle, there are 6*6=36
outcomes. They are listed on the next slide.
Melikyan/DM/Fall09
11
Sample space of all possible outcomes when
two dice are tossed.
(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)
(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)
Quite a tedious project !!
Melikyan/DM/Fall09
12
Probability of an event
Definition: sum of the probabilities of the simple events that constitute
the event. The theoretical probability of an event is defined as the
number of ways the event can occur divided by the number of events of
the sample space. Using mathematical notation, we have
P(E) =
n( E )
n( S )
n(E) is the number of ways the event can occur and n(S) represents the
total number of events in the sample space.
Melikyan/DM/Fall09
13
Examples
Probability of a sum of 7 when two dice are rolled. First we must calculate
the number of events of the sample space. From our previous example,
we know that there are 36 possible sums that can occur when two dice
are rolled.
Of these 36 possibilities, how many ways can a sum of seven occur?
Looking back at the slide that gives the sample space we find that we can
obtain a sum of seven by the outcomes { (1,6), (6,1), (2,5), (5,2), (4,3), (3,4)}
There are six ways two obtain a sum of seven. The outcome (1,6) is
different from (6,1) in that (1,6) means a one on the first die and a six on
the second die, while a (6,1) outcome represents a six on the first die and
one on the second die.
The answer is P(E)=
Melikyan/DM/Fall09
6 1
n( E )

=
36 6
n( S )
14
PROBABILITIES FOR SIMPLE EVENTS
Given a sample space S = {e1, e2, ..., en}.
To each simple event ei assign a real number denoted by P(ei),
called the PROBABILITY OF THE EVENT ei. These
numbers can be assigned in an arbitrary manner provided the
Following two conditions are satisfied:
(a) The probability of a simple event is a number between 0 and 1,
inclusive. That is,
0 ≤ p(ei) ≤ 1
(b) The sum of the probabilities of all simple events in the sample space
is 1. That is,
P(e1) + P(e2) + ... + P(en) = 1
Any probability assignment that meets these two conditions is
called an ACCEPTABLE PROBABILITY ASSIGNMENT.
Melikyan/DM/Fall09
15
PROBABILITY OF AN EVENT E
Given an acceptable probability assignment for the simple
events in a sample space S, the probability of an arbitrary
event E, denoted P(E), is defined as follows:
(a) P(E) = 0 if E is the empty set.
(b) If E is a simple event, then P(E) has already been assigned.
(c) If E is a compound event, then P(E) is the sum of the
probabilities of all the simple events in E.
(d) If E = S, then P(E) = P(S) = 1 .
Melikyan/DM/Fall09
16
STEPS FOR FINDING THE PROBABILITY OF
AN EVENT E
(a) Set up an appropriate sample space S for the
experiment.
(b) Assign acceptable probabilities to the simple
events in S.
(c) To obtain the probability of an arbitrary event E,
add the probabilities of the simple events in E.
Melikyan/DM/Fall09
17
EMPIRICAL PROBABILITY
If an experiment is conducted n times and event E occurs with
FREQUENCY f(E), then the ratio f(E)/n is called the RELATIVE
FREQUENCY of the occurrence of event E in n trials. The EMPIRICAL
PROBABILITY of E, denoted by P(E), is given by the number (if it exists)
that the relative frequency f(E)/n approaches as n gets larger and larger. For
any particular n, the relative frequency f(E)/n is also called the
APPROXIMATE EMPIRICAL PROBABILITY of event E:
(The larger n is, the better the approximation.)
Melikyan/DM/Fall09
18
PROBABILITIES UNDER AN EQUALLY LIKELY
ASSUMPTION
If, in a sample space
S = {e1, e2, ..., en},
each simple event ei is as likely to occur as any other, then
P(ei), for i = 1, 2, ..., n, i.e. assign the same probability, 1/n,
to each simple event. The probability of an arbitrary event E
in this case is:
Melikyan/DM/Fall09
19
Example of classical probability
Example: Toss two coins. Find the probability of at least one head
appearing.
Solution: At least one head is interpreted as one head or two heads.
Step 1: Find the sample space:{ HH, HT, TH, TT} There are four
possible outcomes.
Step 2: How many outcomes of the event “at least one head” Answer:
3:
{ HH, HT, TH}
Step 3: Use
Melikyan/DM/Fall09
n( E )
P(E)=
= ¾ = 0.75 = 75%
n( S )
20
Counting the elements of a set
Theorem:
If m and n are integers and m  n, then
there are n – m + 1 integers from m to n inclusive.
Example:
a) How many two digit numbers are divisible by 7?
b) What is the probability that a randomly chosen two digit
number is divisible by 7
Melikyan/DM/Fall09
21
Possibility Trees and The Multiplication Rule
Teams A and B are to play each other repeatedly
until one wins two games in a row or a total three
games.
– What is the probability that five games will be
needed to determine the winner?
Melikyan/DM/Fall09
22
Next Example
Suppose there are 4 I/O units and 3 CPUs. In how many
ways can I/Os and CPUs be attached to each other when
there are no restrictions
Melikyan/DM/Fall09
23
Multiplication Rule
Theorem ( The Multiplication Rule):
If an operation consists of k steps each of which can be
performed in ni ways (i = 1, 2, …, k), then the entire operation
can be performed in n1 n2 . . . nk ways.
Example: A PIN number is a sequence of any four
letters selected from 26 and the ten digits, with
repetition allowed.
a) How many PIN numbers are possible.
b) Number of PIN’s if no repetition
Melikyan/DM/Fall09
24
Multiplication Rule : Example
Three officers – a president, a treasurer and a secretary are to
be chosen from four people: Alice, Bob, Cindy and Dan. Alice
cannot be a president, Either Cindy or Dan must be a secretary.
How many ways can the officers be chosen?
Melikyan/DM/Fall09
25
Example (continue)
What if we reorder the steps of selections
Select first the secretary, then president, and the treasurer
Melikyan/DM/Fall09
26
Permutations
Definition: A permutation of a set of objects is an
ordering of these objects
Theorem: The number of permutations of a set of n
objects is n!
Consider a permutation as an n-step selection:
Melikyan/DM/Fall09
27
Example:
•
•
How many ways can the letters in the word COMPUTER be
arranged in a row?
How many ways can the letters in the word COMPUTER be
arranged if the letters CO must remain
next to each other.
Melikyan/DM/Fall09
28
Permutation of Selected Objects
Definition: An r-permutation of a set of n elements is
an ordered selection of r elements taken from a set of
n elements: P(n, r)
The number of r-permutations of a set of n elements
is denoted by P(n, r)
Theorem: If n and r are integers and 1  r  n, then
P(n, r) = n(n -1)(n - 2). . . (n – r +1) or
P(n, r) = n! / (n – r)!
Show that P(n, 2) + P(n, 1) = n2
Melikyan/DM/Fall09
29
The sketch of last theorems proof:
Formation of r-permutation can be thought as an r-step process:
It follows from the multiplication principle that
P(n, r) = n(n - 1)(n - 2)·...·(n - r + 1) = n!/(n -r)!
Melikyan/DM/Fall09
30
Addition Rule
Theorem: If a finite set A is a union of k mutually
disjoint sets A1, A2, …, Ak, then
n(A) = n(A1) + n(A2) + . . . + n(Ak)
Number of words of length no more than 3
Number of integers divisible by 5
Melikyan/DM/Fall09
31
Example: Counting three digit the number of integers
divisible by 5
Melikyan/DM/Fall09
32
The Difference Rule
Theorem: If A is a finite set and B is its subset, then
n(A \ B) = n(A) – n(B)
Formula for probability of the complement of an Event.
If S is a finite sample space and A is an event in S then
P(AC) = 1 – P(A)
How many students are needed so that the probability of
two of them having the same birthday equals 0.5?
Melikyan/DM/Fall09
33
Inclusion/Exclusion Rule
Theorem: If A, B, C are any finite sets, then
n(AB ) = n(A) + n(B) – n(AB)
and
n(AB C ) = n(A) + n(B) +n(C) – n(AB)- n(AC)- n(BC) +
n(AB C)
Melikyan/DM/Fall09
34
Examples:
How many integers from 1 through 1000 are
multiples of 3 or multiples of 5
How many integers from 1 through 1000 are
neither multiples of 3 nor multiples of 5?
Melikyan/DM/Fall09
35
Exercises
Suppose that out of 50 students, 30 know Java,18 know
C++, 26 know C#, 9 know both C++ and Java, 16 know both
Java and C#, 8 know C++ and C# and 47 know at least one
programming language.
– How many students know none of the three languages?
– How many students know all three languages
– How many students know exactly 2 languages?
Melikyan/DM/Fall09
36
Example (continue)
Melikyan/DM/Fall09
37
Exercises
How many integers from 1 to 100000 contain the digit
6 exactly once / at least once? What is a probability
that a random number from 1 to 100000 will contain
two or more occurrences of digit 6?
6 new employees, 2 of whom are married are
assigned 6 desks, which are lined up in a row.
What is the probability that the married couple will
have non-adjacent desks?
Melikyan/DM/Fall09
38
Exercises
Consider strings of length n over the set {a, b, c, d}:
– How many such strings contain at least one pair of
consecutive characters that are the same?
– If a string of length 10 is chosen at random, what is the
probability that it contains at least on pair of consecutive
characters that are the same?
How many permutations of abcde are there in which
the first character is a, b, or c and the last character
is c, d, or e?
How many integers from 1 through 999999 contain
each of the digits 1, 2, and 3 at least once?
Melikyan/DM/Fall09
39