Transcript Discrete_Probability.. - SIUE Computer Science

MATH 224 – Discrete Mathematics
Basics of Discrete Probability
|E|
, where |E| is the
|S |
number of events and |S| is the total number of possible outcomes. This definition
assumes that each possibility is equally likely. In other words each possibility has
probability 1/|S|.
Basic finite probability is given by the formula P( E ) 
So for example, if we want the probability of four coin tosses where the first
two times the coin comes up heads followed by two tails, this set E has only
one element. The set of all possible 4-coin tosses is 24. So the probability of
two heads followed by two tails is 1/16.
On Page 394 of the textbook, there is a container with four blue balls and five
red balls. What is the probability of choosing a blue ball when selecting
one ball? The answer is 4/9.
3/29/2016
1
MATH 224 – Discrete Mathematics
Probability
Now consider what happens when rolling a fair die. The probability of rolling any of the
values between one and six is 1/6. When rolling two dice the probabilities are:
P(2) = P(12) = 1/36 since there is only one way to get a 2 (two ones).
P(3) = P(11) = 2/36 = 1/18 since there are two ways of getting a 3 (2 and 1 or 1 and a 2)
P(4) = P(10) = 3/36 = 1/12 What are the three ways of getting four?
P(5) = P(9) = 4/36 = 1/9
P(6) = P(8) = 5/36
P(7) = 6/36 = 1/6
Why is the denominator 36?
The sum of theses probabilities is 2(1/36)+2(2/36)+2(3/36)+2(4/36)+2(5/36)+(6/36) =
36/36 =1. Do the set of all probabilities always sum to 1?
3/29/2016
2
MATH 224 – Discrete Mathematics
Probability
Often counting the number of different events can be difficult or tricky. Consider Example
6 from our text. First determine the number of different 5-card hands in poker in order to
get the denominator |S|. Since there are 52 cards, |S| = C(52,5) = 2,598,960.
What is the probability of a full house, i.e. 3 of a kind plus 2 of a kind?
For three cards of a kind we have C(4,3) and C(4,2) for two of a kind once the kind of card
is fixed. Where does the 4 come from in these combinations? Since there are 13
different kinds of cards we have P(13,2) for choosing the kinds. P(13,2) = 13.12 = 146
permutations. Here we have permutations because which kind has three and which has two
matters, e.g., two aces and three kings is different than two kings and three aces. Then the
total number of ways of getting a full house is P(13,2)C(4,3)C(4,2) = 3744.
What is the probability of getting a full house? (3744/2,598,960 ≈ 0.0014)
If you want to determine the probability of, for example either a full house or at least two
aces, you cannot just add the probabilities together since it is possible for both to be true at
the same time. You have to count the number of events in E1U E2, the union.
3/29/2016
3
MATH 224 – Discrete Mathematics
Probability – Monty Hall Example
The Monty Hall example from the book is often confusing. Here is a common statement
of this puzzle.
There are three doors, two with nothing behind them and one with a prize. You
choose one and then the game show host opens one of the doors you did not choose
and nothing is behind it. Should you change doors?
Initially you have a 1/3 chance of choosing the prize. After Monty opens a door, how
do your odds change? If he always selects a door with no prize behind it, that is
equivalent to saying divide the doors into two sets. One with two doors and one with just
one door. Of the two door set, he shows one of the doors, always choosing one without a
prize. The two door set has a 2/3 probability of having the prize and you know which one
not to choose. You should change to the other unopened door.
What if he chooses a door at random? Does this have an effect on the probabilities?
3/29/2016
4
MATH 224 – Discrete Mathematics
Applications of Probability to Computer Science
Here are a few examples of the use of probability in computer science.
•
In problems involving computer simulations of real events, probabilities are involved
to specify events. For example, creating climate models.
•
In analyzing the results of computer simulations, statistics and probability are used.
•
In analyzing traffic and other parameters such packet sizes for computer networks,
probability comes into play.
•
Probability theory is essential in artificial intelligence. Often it is not possible to
determine the best treatment, e.g., in diagnosing a medical problem. But
probabilities can be used to help make a good choice of treatments.
•
Probabilities are used to design algorithms. Some algorithms such as quick-sort
sometimes use a probabilistic selection of an element. A data structure such as skip
lists use probabilistic choices.
•
Probability and statistics are used to analyze the average running time of algorithms.
3/29/2016
5
MATH 224 – Discrete Mathematics
First moment or Expected Value
The first moment, often called expected value, is used to find the average running
time for an algorithm. (This also referred to as the waited average.)
The expected value is defined as
E ( X )   p( s ) X ( s )
sS
, where X is the value at s.
So for example, to find the average running time for an algorithm we would have
A   p( s)T ( s)
sS
where A is the average time, T(s) is the time for input s, and p(s) the probability of
input s. As an example, let us consider insertion sort. We would need to know the
probabilities that the array is sorted to begin with, that exactly x elements are in the
wrong position, etc. Doing this precisely is difficult, but often since we only care
about Big-O or Theta, it is often possible to make simplifying assumptions.
3/29/2016
6
MATH 224 – Discrete Mathematics
Second Moment or Variance
The second moment, often called the variance, indicates how much individual
events vary from the average, and is given by
V ( X )   ( X ( s)  E ( X )) 2 p( s)
sS
The square root of the variance is called the standard deviation, which is a very
important concept in statistics and for probabilities that fit the mathematical definition
of a Normal distributions. For example, with this type of distribution just over 68% of
the events will have values between ± 1 standard deviation from the mean. As an
example, an instructor might decide that any grade within one standard deviation of
the average is a C.
3/29/2016
7