Office Hour: Monday 14:00 - 15:00 ESB 3134 [email protected]
Random Experiments - Outcome cannot be predicted
Sample Space - List of possible outcomes of a random experiment (usually denoted by )
Event - Subset of sample space (usually denoted by )
Event occurs when where
Union (OR) - or
Intersection (AND) - or
Complement (NOT) -
Occurs when there is no intersection of events. Empty is usually denoted using
Sigma field is a collection of events (denoted by -field or ). It is the domain for a probability function.
A sigma field must satisfy three conditions:
Example: rolling a dice
The sample space would be each side of the dice:
Let’s say we have the event A for rolling a low number, B for rolling even numbers, and C for rolling any number less than 5.
The number of subsets possible from the sample space is (the number of possible subsets of any set is 2 to the power of number of elements in the set).
We can say:
The probability function () operates on sets and we want the probability of events happening in a sample space.
There is three property / axiom with the probability function:
Probability Space: (, , )
The probability space is a tuple of the sample space, all possible events, and all defined probabilities of these events.
First, we know that (it is in or it is not) so we can apply the probability function which yields line 2. Since and is disjoint, we follow axiom 3 and add the probability of event and probability of not event together. This equals to the probability of the sample space which is 1. Thus, using algebra we show that the probability of is 100% minus the probability of not occurring.
Again, starting off with , we also know that (In fact, any event intersecting with the sample space is just the event itself).
Substituting with expression in line 1, we get line 2. We can then distribute the intersection (on the outside) and we get the line 3. We may also re-express it as which also equals to when expanded.
Now we operate the probability function on both sides (as shown in line 4). Rearranging the terms and we get and since the probability of any event (as described above) must be greater than or equal to 0, we can conclude that .
In this case, and are not necessary disjoint.
The union of two events equals to the union of one event plus the second event (inclusion) that’s not overlapping with the first event (subtract intersection)(hence because it means any part of that is not overlapping ). This is the inclusion-exclusion formula. See below for more.
Similarly, event can be broken down into the part that is exclusive and the part that overlaps with . We operate the probability function and get line 3. Rearrange and we can find the probability of exclusive or .
Combining line 2 and line 4 we get:
Same as above, this is using the inclusion-exclusion formula. See below for more.
Boole’s inequality is defined as follows:
This means that if there are a bunch of events that exist in the sigma field, the probability of any one event occurring must be less than or equal to the sum of the probability of each event. This is because the union of all events might contain overlap.
If all outcomes are equally likely, then the probability of an event is defined by number of outcomes in the event over number of outcomes in the sample space:
We use the inclusion-exclusion property: .
The probability of any of the events occurring is the probability of any of the events happening plus probability of the -th event occurring. Then exclude any overlap between any of the previous events and -th event.
We notice that the first term of the RHS can be broken down the same way.
Continuing the proof, we know that , so we can rewrite the expression to be
And for some fucking reason the first term of the RHS just becomes a summation…
Let be a sorted subset of the set . We write to denote the cardinality (number of elements) in . The , then:
This notation allows us to write the inclusion-exclusion formula:
Given is the size of a set, this formula expands to:
For complete proof, go to proof on course website.
Definition of Permutation: A permutation of a set is a one to one function from onto itself:
An example would be . Notice that the third element (3) did not change, this is a fix point (satisfies ).
There are number of all possible permutations. Since they are all equally likely, the probability of any given one is .
The probability of a single number () being a fix point is given by factorial of numbers left, divided by total possible permutations:
The probability of two numbers ( and , both being a fix point is similar:
Problem: Calculate the probability of zero fix points in a random permutation.
By using logic, we can conclude that , which basically says that all elements must not be fix points.
Using one of the axioms, we can say the probability of having equals to 1 minus the probability of not having :
Applying the inclusive-exclusive formula on the second term, and we get:
The nested summation term can be expressed as (IDK WHY DON’T ASK ME):
Putting all together, the probability of 0 fixed points can be evaluated. The probability as is . But of course, most of the time, we are dealing with a truncated series, so it’s not exactly .
Problem: (Identical to above), instead of looking for 0 fix points, we want to find the probability of fix points in a random permutation (more general).
Notice that if , then the probability of fix points is 0.