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 event is equally likely. In other words each even has probability
1/|E|.
Basic finite probability is given by the formula P( E ) 
So for example, if we want the probability of tossing a coin four times 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/27/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/27/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. Since there are 13
different kinds of cards we have P(13,2) for choosing the suit. 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, and make
sure that those events in the union are not counted twice.
3/27/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.
3/27/2016
4
MATH 224 – Discrete Mathematics
Basics of 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?
But if Monty chooses a door at random, so that he may sometimes choose a door with the
prize behind it. The fact that he opened one door does not tell you any more other than
the prize is behind one of the two remaining doors. In that case there is no advantage to
changing doors. Each of the remaining doors has a ½ probability of being the one with
the prize.
Sometimes mathematicians have argued about the correct answer, because the original
statement of the problem was not clear. Did the game show host choose at random, or did
he specifically choose a door without a prize behind it?
3/27/2016
5
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 quicksometimes 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/27/2016
6
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.
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/27/2016
7
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 could decide that any grade within one standard deviation of the
average is a C.
3/27/2016
8