- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Discrete mathematics. Probability презентация
Содержание
- 1. Discrete mathematics. Probability
- 2. Probability---Introduction One of the
- 3. Probability---Introduction---Cont. But it
- 4. Probability Contents Basic definitions
- 5. Probability Let’s Make a Deal
- 6. Probability Precise Description The car is
- 7. Probability Precise Description The car is
- 8. Probability Solving Problems Involving
- 9. Probability Solving Problems Involving Probability
- 10. Probability Solving Problems Involving Probability
- 11. Probability Solving Problems Involving Probability
- 12. Probability Solving Problems Involving Probability
- 13. Probability Finding the Sample Space
- 14. Probability Finding the Sample Space
- 15. Probability Possibility Tree The
- 16. Probability Possibility Tree ---
- 17. Probability Possibility Tree ---
- 18. Probability Possibility Tree ---
- 19. Probability Possibility Tree --- Cont.
- 20. Probability Finding The Sample
- 21.
- 22. Probability Solving Problems Involving Probability
- 23. Probability Solving Problems Involving Probability
- 24. Probability Solving Problems Involving Probability
- 25. Probability Solving Problems Involving Probability
- 26.
- 27.
- 28. Probability Solving Problems Involving Probability
- 29. Probability Solving Problems Involving Probability---Cont.
- 30. Probability Solving Problems Involving Probability---Cont.
- 31. Probability Equally likely probability formula
- 32. Probability Solving Problems Involving Probability---Cont.
- 33. Probability Edge Probabilities
- 34. Probability Multiplication Rule The probability
- 35. Probability Outcome Probabilities
- 36.
- 37. Probability Summary To solve problems
- 38. Probability Uniform Sample Space
- 39. Probability Applying Four-Step Method
- 40.
- 41. Probability Applying Four-Step Method
- 42.
- 43. Probability Counting
- 44. Probability The Addition Rule
- 45. Probability The Addition Rule---Cont.
- 46.
- 47.
- 48. Probability The Difference Rule
- 49. Probability The Difference Rule---Cont.
- 50.
- 51. Probability The Difference Rule---Cont.
- 52. Probability The Difference Rule---Cont.
- 53. Probability The Difference Rule---Cont.
- 54. Probability The Difference Rule---Cont.
- 55. Probability The Difference Rule---Cont.
- 56.
- 57. Probability The Difference Rule---Cont.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64. Probability The Difference Rule---Cont.
- 65. Probability The Inclusion/Exclusion Rule The
- 66.
- 67.
- 68.
- 69.
- 70. Further Counting Counting Subsets of
- 71. Further Counting Counting Subsets of
- 72.
- 73. Why Count Subsets of Set? Example:
- 74. Counting Subsets of a Set:
Probability---Introduction One of the most important disciplines in Computer Science (CS). Algorithm Design and Game Theory Information Theory Signal Processing Cryptography
Слайд 1Discrete Mathematics
PROBABILITY-1
Adil M. Khan
Professor of Computer Science
Innopolis University
“Information: The Negative Reciprocal Value of Probability!” - Claude Shannon -
Слайд 2Probability---Introduction
One of the most important disciplines in Computer Science (CS).
Algorithm
Design and Game Theory
Information Theory
Signal Processing
Cryptography
Information Theory
Signal Processing
Cryptography
Слайд 3Probability---Introduction---Cont.
But it is also probably the least well understood
Human intuition
and Random events
Goal: To try our best to teach you how to easily and confidently solve problems involving probability
“What is the probability that … ?”
Goal: To try our best to teach you how to easily and confidently solve problems involving probability
“What is the probability that … ?”
Слайд 4Probability
Contents
Basic definitions and an elementary 4-step process
Counting
Conditional probability and the concept
of independence
Random Variable
Expected value and Standard Deviation
Random Variable
Expected value and Standard Deviation
Слайд 5Probability
Let’s Make a Deal
The famous game show (you might have
seen this problem in your books)
Participant is given a choice of three doors. Behind one door is a car, behind the others, useless stuff. The participant picks a door (say door 1). The host, who knows what is behind the doors, opens another door (say door 3) which has the useless stuff. He then asks the participant if he would like to switch (pick door 2)?
Is it to participant’s advantage to switch or not?
Participant is given a choice of three doors. Behind one door is a car, behind the others, useless stuff. The participant picks a door (say door 1). The host, who knows what is behind the doors, opens another door (say door 3) which has the useless stuff. He then asks the participant if he would like to switch (pick door 2)?
Is it to participant’s advantage to switch or not?
Слайд 6Probability
Precise Description
The car is equally likely to be hidden behind the
three doors.
Equally likely events are events that have the same likelihood of occurring. For example. each numeral on a die is equally likely to occur when the die is tossed.
Слайд 7Probability
Precise Description
The car is equally likely to be hidden behind the
three doors.
The player is equally likely to pick each of the doors.
After the player picks a door, the host must open a different door (with the useless thing behind it) and offer the player to switch.
When a host has a choice of which door to pick, he is equally likely to pick each of them.
Now here comes the question:
“What is the probability that a player who switches wins the car?”
The player is equally likely to pick each of the doors.
After the player picks a door, the host must open a different door (with the useless thing behind it) and offer the player to switch.
When a host has a choice of which door to pick, he is equally likely to pick each of them.
Now here comes the question:
“What is the probability that a player who switches wins the car?”
Слайд 8Probability
Solving Problems Involving Probability
Model the situation mathematically
Solve the resulting mathematical problem
Слайд 9Probability
Solving Problems Involving Probability
Step 1: Finding the sample space
Set of all
possible outcomes of a random process
To say that a process is random means that when it takes place, one outcome from a set of outcomes is sure to occur, but it is impossible to predict with certainty which outcome that will be.
For example: tossing a coin, choosing winners in state lotteries.
Слайд 10Probability
Solving Problems Involving Probability
Step 1: Finding the sample space
Set of all
possible outcomes of a random process
The set of all possible outcomes that can result from a random process is is called a sample space.
Слайд 11Probability
Solving Problems Involving Probability
Step 1: Finding the sample space
Set of all
possible outcomes of a random process
To find this, we must understand the quantities involve in the random process
To find this, we must understand the quantities involve in the random process
Слайд 12Probability
Solving Problems Involving Probability
Step 1: Finding the sample space
Set of all
possible outcomes of a random process
To find this, we must understand the quantities involve in the random process
Quantities in the above problem:
The door concealing the car
The door initially chosen by the player
The door that host opens to reveal the useless thing
To find this, we must understand the quantities involve in the random process
Quantities in the above problem:
The door concealing the car
The door initially chosen by the player
The door that host opens to reveal the useless thing
Слайд 13Probability
Finding the Sample Space
Every possible value of these quantities is called
an outcome.
And (as said earlier) the set of all possible outcomes is called the sample space
And (as said earlier) the set of all possible outcomes is called the sample space
Слайд 14Probability
Finding the Sample Space
Every possible value of these quantities is called
an outcome.
And (as said earlier) the set of all possible outcomes is called the sample space
A tree structure (Possibility tree) is a useful tool for keeping track of all outcomes
When the number of possible outcomes is not too large
And (as said earlier) the set of all possible outcomes is called the sample space
A tree structure (Possibility tree) is a useful tool for keeping track of all outcomes
When the number of possible outcomes is not too large
Слайд 15Probability
Possibility Tree
The first quantity in our example is the door concealing
the car
Represent this as a root of tree with three branches (three doors)
Represent this as a root of tree with three branches (three doors)
Слайд 17Probability
Possibility Tree --- Cont.
The car can be at any of
these three locations
For each possible location of the car, the player can choose any of the three doors
For each possible location of the car, the player can choose any of the three doors
Слайд 18Probability
Possibility Tree --- Cont.
The car can be at any of
these three locations
For each possible location of the car, the player can choose any of the three doors
Then the final possibility is regarding the host opening a door to reveal the useless thing
Overall tree turns out to be
For each possible location of the car, the player can choose any of the three doors
Then the final possibility is regarding the host opening a door to reveal the useless thing
Overall tree turns out to be
Слайд 20Probability
Finding The Sample Space
The leaves of the possibility tree represent
the outcomes of a random process
The set of all leaves represent the sample space
The set of all leaves represent the sample space
Слайд 23Probability
Solving Problems Involving Probability
Step 2: Defining the Events of Interest:
Remember, we want to answer the questions of type:
“What is the probability that … ?”
Слайд 24Probability
Solving Problems Involving Probability
Step 2: Defining the Events of Interest:
Remember, we want to answer the questions of type:
“What is the probability that … ?”
Replacing the “…” with some specific event. For example,
Слайд 25Probability
Solving Problems Involving Probability
Step 2: Defining the Events of Interest:
Remember, we want to answer the questions of type:
“What is the probability that … ?”
Replacing the “…” with some specific event. For example,
“What is the probability that the car is behind door C?”
Doing this reduces S to some specific outcomes, called event of interest.
Слайд 28Probability
Solving Problems Involving Probability
Coming back to our example
We want to know:
“What is the probability that the player will win by switching?”
This event can be represented as the following set
Слайд 29Probability
Solving Problems Involving Probability---Cont.
Notice: Half of the outcomes are checked. Does
this mean that the player wins by switching in half of all outcomes?
Слайд 30Probability
Solving Problems Involving Probability---Cont.
Step 3: Determining Outcome Probability
Assign Edge Probabilities
Compute Outcome
Probabilities
Слайд 32Probability
Solving Problems Involving Probability---Cont.
Step 3: Determining Outcome Probability
Assign Edge Probabilities
Compute Outcome
Probabilities
Слайд 33Probability
Edge Probabilities
To understand, let’s analyze the path leading to the
leaf node (A, A, B)!
Слайд 34Probability
Multiplication Rule
The probability that Events A and B both occur
is equal to the probability that Event A occurs times the probability that Event B occurs, given that A has occurred.
You will learn more about this when I will teach you about conditional probabilities next week. For now, let’s just use this rule!
Слайд 35Probability
Outcome Probabilities
To understand, let’s analyze the probability of the outcome
(A, A, B).
Слайд 37Probability
Summary
To solve problems involving probability, that is, “what is the probability
that … ?”
Perform the following four steps:
Find the sample space
Define event of interest
Compute outcome probabilities
Compute event probability
Perform the following four steps:
Find the sample space
Define event of interest
Compute outcome probabilities
Compute event probability
Слайд 38Probability
Uniform Sample Space
Strange Dice
If we picked dices (a) and
(b), rolled them once, what is the probability that (a) beats (b) (has a higher value)?
Слайд 39Probability
Applying Four-Step Method
When the probability of every outcome is the
same, we say such a sample space is uniform
Слайд 41Probability
Applying Four-Step Method
Example--- Cont.
What about the following:
(a) vs. (c)
(b)
vs. (c)
Homework!
Homework!
Слайд 44Probability
The Addition Rule
The basic rule underlying the calculation of the
number of elements in a union or difference or intersection is the addition rule.
This rule states that the number of elements in a union of mutually disjoint finite sets equals the sum of the number of elements in each of the component sets.
Theorem 9.3.1:
Suppose a finite set A equals the union of k distinct mutually disjoint subsets A1, A2, …., Ak. Then
N(A) = N(A1)+N(A2)+…+ N(Ak)
This rule states that the number of elements in a union of mutually disjoint finite sets equals the sum of the number of elements in each of the component sets.
Theorem 9.3.1:
Suppose a finite set A equals the union of k distinct mutually disjoint subsets A1, A2, …., Ak. Then
N(A) = N(A1)+N(A2)+…+ N(Ak)
Слайд 45Probability
The Addition Rule---Cont.
Example: A computer access password consists of from
one to three letters chosen from the 26 in the alphabet with repetitions allowed. How many different passwords are possible?
Solution: The set of all passwords can be partitioned into subsets consisting of those of length 1, those of length 2, and those of length 3 as shown in the figure below.
Solution: The set of all passwords can be partitioned into subsets consisting of those of length 1, those of length 2, and those of length 3 as shown in the figure below.
Слайд 48Probability
The Difference Rule
An important consequence of the addition rule is the
fact that if the number of elements in a set A and the number in a subset B of A are both known, then the number of elements that are in A and not in B can be computed.
Theorem 9.3.2: The Difference Rule:
If A is finite set and B is a subset of A, then
N(A-B) = N(A) – N(B)
Theorem 9.3.2: The Difference Rule:
If A is finite set and B is a subset of A, then
N(A-B) = N(A) – N(B)
Слайд 51Probability
The Difference Rule---Cont.
Example:
A typical PIN (personal identification number) is
a sequence of any four symbols chosen from the 26 letters in the alphabet and the ten digits, with repetition allowed.
a. How many PINs contain repeated symbols?
b. If all PINs are equally likely, what is the probability that a randomly chosen PIN contains a repeated symbol?
a. How many PINs contain repeated symbols?
b. If all PINs are equally likely, what is the probability that a randomly chosen PIN contains a repeated symbol?
Слайд 52Probability
The Difference Rule---Cont.
a. How many PINs contain repeated symbols?
Let’s use
the board to intuitively explain why the Difference Rule will work here!
Слайд 53Probability
The Difference Rule---Cont.
Example --- Cont.:
There are 364 = 1,679,616
PINs when repetition is allowed,
and there are 36 ⚫ 35 ⚫ 34 ⚫ 33 = 1,413,720
PINs when repetition is not allowed.
and there are 36 ⚫ 35 ⚫ 34 ⚫ 33 = 1,413,720
PINs when repetition is not allowed.
Слайд 54Probability
The Difference Rule---Cont.
Example --- Cont.:
There are 364 = 1,679,616
PINs when repetition is allowed,
and there are 36 ⚫ 35 ⚫ 34 ⚫ 33 = 1,413,720
PINs when repetition is not allowed.
Thus, by the difference rule, there are
1,679,616 – 1,413,720 = 265,896
PINs that contain at least one repeated symbol.
and there are 36 ⚫ 35 ⚫ 34 ⚫ 33 = 1,413,720
PINs when repetition is not allowed.
Thus, by the difference rule, there are
1,679,616 – 1,413,720 = 265,896
PINs that contain at least one repeated symbol.
Слайд 55Probability
The Difference Rule---Cont.
b. If all PINs are equally likely, what
is the probability that a randomly chosen PIN contains a repeated symbol?
So, how would you figure this out?
So, how would you figure this out?
Слайд 57Probability
The Difference Rule---Cont.
An alternative solution to Example 3(b) is based
on the observation that if S is the set of all PINs and A is the set of all PINs with no repeated symbol, then S – A is the set of all PINs with at least one repeated symbol.
Слайд 64Probability
The Difference Rule---Cont.
This solution illustrates a more general property of
probabilities: that the probability of the complement of an event is obtained by subtracting the probability of the event from the number 1.
Formula for the 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).
Formula for the 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).
Слайд 65Probability
The Inclusion/Exclusion Rule
The addition rule says how many elements are in
a union of sets if the sets are mutually disjoint. Now consider the question of how to determine the number of elements in a union of sets when some of the sets overlap.
For simplicity, begin by looking at a union of two sets A and B, as shown below.
For simplicity, begin by looking at a union of two sets A and B, as shown below.
Слайд 70Further Counting
Counting Subsets of a Set: Combinations:
Look at these examples:
In
how many ways, can I select 5 books from my collection of 100 to take on vacation?
How many different ways 13-card Bridge hands can be dealt from a 52-card deck?
In how many ways, can I select 5 toppings for my pizza if there are 14 available?
What is common in all these questions?
How many different ways 13-card Bridge hands can be dealt from a 52-card deck?
In how many ways, can I select 5 toppings for my pizza if there are 14 available?
What is common in all these questions?
Слайд 71Further Counting
Counting Subsets of a Set: Combinations:
Look at these examples:
In
how many ways, can I select 5 books from my collection of 100 to take on vacation?
How many different ways 13-card Bridge hands can be dealt from a 52-card deck?
In how many ways, can I select 5 toppings for my pizza if there are 14 available?
What is common in all these questions?
Each is trying to find “how many k-element subsets of an n-element set are there?”
How many different ways 13-card Bridge hands can be dealt from a 52-card deck?
In how many ways, can I select 5 toppings for my pizza if there are 14 available?
What is common in all these questions?
Each is trying to find “how many k-element subsets of an n-element set are there?”
Слайд 73Why Count Subsets of Set?
Example:
Suppose we select 5 cards at
random from a deck of 52 cards.
What is the probability that we will end up having a full house?
Doing this using the possibility tree will take some effort.
What is the probability that we will end up having a full house?
Doing this using the possibility tree will take some effort.
Слайд 74
Counting Subsets of a Set: Combinations---Cont.
How to calculate “n choose
k”??
Permutations
Division rule
Permutations
Division rule
We will continue from here in the next lecture!
