Random Experiment
A process, or an experiment is random means that
•
when it takes place, one outcome from some set of outcomes is sure to occur,
•
but it is impossible to predict with certainty which outcome that will be.
Sample space (표본 공간)
• E.g. Coin toss → {heads, tails} ({앞면, 뒷면})
Event (사건)
• E.g. 2 head obtained
Equally likely probability Formula
Possibility Trees
Possibility trees (가능성 트리)
• A tree structure is a useful tool for keeping systematic track of all possibilities in situations in which events happen in order.
• The following example shows how to use such a structure to count the number of different
outcomes of a tournament.
Q. Teams A and B play until one wins two games in a row or a total of three games.
a. How many ways can the tournament be played?
b. Assuming that all the ways of playing the tournament are equally likely, what is the probability that five games are needed to determine the tournament winner?
The multiplication rule
Consider the following example.
•
a computer installation has four I/O units (A, B, C, and D) and 3 CPUs (X, Y, and Z).
•
Any I/O unit can be paired with any CPU.
How many ways are there to pair an input/output unit with a central processing unit?
⇒ As shown in the possibility tree, the same as the number of branches, 3 · 4 = 12
When the multiplication rule is difficult or impossible to apply
Consider the following problem:
•
3 officers—a president, a treasurer, and a secretary—are to be chosen from among 4 people:
Ann, Bob, Cyd, and Dan.
•
Ann cannot be president
•
Either Cyd or Dan must be secretary.
How many ways can the officers be chosen?
The number of ways to choose the secretary varies depending on who is chosen for president and treasurer.
•
For instance, if Bob is chosen for president and Ann for treasurer, then there are two choices for secretary: Cyd and Dan.
•
But if Bob is chosen for president and Cyd for treasurer, then there is just one choice for secretary: Dan.
The clearest way to see all the possible choices is to construct the possibility tree.
Conditions:
• 3 officers—a president, a treasurer, and a secretary—are to be chosen from among 4 people: Ann, Bob, Cyd, and Dan.
• Ann cannot be president.
• Either Cyd or Dan must be secretary.
From the tree it is easy to see that there are only 8 ways to choose a president, treasurer, and secretary so as to satisfy the given conditions.
Birthday Paradox
The birthday paradox shows
• how likely it is for two people in a group to share the same birthday, even in relatively small groups.
What is the minimum number of people who need to be in a room so that the probability that at least two of them have the same birthday is greater than 1/2?
• In a group of just 23 people, there is a 50% chance that two people share the same birthday.
• In a group of 50 people, the probability of a shared birthday rises to 97%!
Monty Hall Paradox
The Monty Hall problem paradox
•
Consider a game show where a prize (a car) is behind one of three doors
•
The other two doors do not have prizes (goats instead)
•
After picking one of the doors, the host (Monty Hall) opens a different door to show you that
the door he opened is not the prize
•
Do you change your decision?
Your initial probability to win (i.e. pick the right door) is 1/3
What is your chance of winning if you change your choice after Monty opens a wrong door?
After Monty opens a wrong door, if you change your choice, your chance of winning is 2/3
•
Thus, your chance of winning doubles if you change
Consider 100 doors
• You choose one
• Monty opens 98 wrong doors
• Do you switch?
Your initial chance of being right is 1/100
Right before your switch, your chance of being right is still 1/100
• Just because you know more info about the other doors doesn’t change your chances
– You didn’t know this info beforehand!
Your final chance of being right is 99/100 if you switch
• You have two choices: your original door and the new door
• The original door still has 1/100 chance of being right
• Thus, the new door has 99/100 chance of being right
• The 98 doors that were opened were not chosen at random!
– Monty Hall knows which door the car is behind
Addition Rule, Difference Rule
The basic rule underlying the calculation of the number of elements in a union or difference or
intersection is the addition rule.
(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.
(서로 교집합이 없는 유한 집합들의 합집합을 A라 할 때, A 의 원소의 개수는 각 부분집합의 원소 개수 합과 같음)
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.
The difference rule holds for the following reason:
•
If B ⊆ A, then the two sets B and A − B have no elements in common and B ∪ (A − B) = A.
•
Hence, by the addition rule, N(B) + N(A − B) = N(A).
•
Subtracting N(B) from both sides gives the equation N(A − B) = N(A) − N(B).
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.
•
Here, we need to subtract A ∩ B when counting A ∪ B.
The pigeonhole principle
The pigeonhole principle states that if n pigeons fly into m pigeonholes and n > m,
then at least one hole must contain two or more pigeons
Generalized pigeonhole principle
A generalization of the pigeonhole principle states that
if n pigeons fly into m pigeonholes and, for some positive integer k, km < n,
then at least one pigeonhole contains k + 1 or more pigeons.
You may find it natural to use the contrapositive form of the generalized
pigeonhole principle in certain situations.
For instance, the result of Example 5 can be explained as follows:
•
Suppose no 4 people out of the 85 had the same last initial.
Then at most 3 would share any particular one.
•
By the generalized pigeonhole principle (contrapositive form),
this would imply that the total number of people is at most 3 26 = 78.
•
But this contradicts the fact that there are 85 people in all.
Hence at least 4 people share a last initial.
Permutations
A permutation (순열) of a set of objects is an ordering of the objects in a row.
•
For example, the set of elements a, b, and c has six permutations: abc, acb, cba, bac, bca, cab
Given a set of n objects, how many permutations does the set have?
Imagine forming a permutation as an n-step operation:
•
Step 1: Choose an element to write first.
•
Step 2: Choose an element to write second.
⋮ ⋮
•
Step n: Choose an element to write nth.
At the point when the nth element is chosen, there is only one element left, so there is only one way to perform step n. Hence, by the multiplication rule, there are n(n– 1)(n– 2) · · · 2 1 = n! ways to perform the entire operation.
r-permutation
Given the set {a, b, c}, there are six ways to select two letters from the set and write them in order.
ab ac ba bc ca cb
Each such ordering of two elements of {a, b, c} is called a 2-permutation of {a, b, c}.
r-combinations
Given a set S with n elements, how many subsets of size r can be chosen from S?
•
The number of subsets of size r that can be chosen from S equals the number of subsets of
size r that S has. Each individual subset of size r is called an r-combination of the set.
(S로부터 r개의 원소를 선택하는 방법 수는, S의 부분집합 중에서 크기가 r인 부분집합의 개수와 같음)
Relationship between permutations and combinations
To form an r-permutation of a set of n elements ( P(n, r) )
•
First, choose a subset of r of the n elements
•
And then choose an ordering for the r elements. (r !)
r-combinations with repetition allowed
Then each r-combination with repetition allowed can be represented as a string of n – 1 vertical bars (|) (to separate the n categories) and r crosses (×) (to represent the r elements to be chosen).
•
The number of strings of n – 1 |'s and r ×'s is equal to the number of ways to choose r positions into which to place the r ×'s out of r + (n – 1) positions, leaving the remaining positions for the |’s.
(즉 총 (n– 1 + r) 개의 자리에, (n– 1) 개의 막대 (|) 와 r개의 선택 (×)을 배치하는 문제임)
