ELEC 321

Probability

Updated 2017-09-13

Course Info

Office Hour: Monday 14:00 - 15:00 ESB 3134 [email protected]

Basics

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 )

Example

Sample space

Event occurs when where

Set Operations

Union (OR) - or

Intersection (AND) - or

Complement (NOT) -

Disjoint

Occurs when there is no intersection of events. Empty is usually denoted using

Sigma Fields

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:

  1. and

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:

Probability Function

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:

  1. ( will always occur)
  2. for all
  3. (assuming disjoint (i.e. is not intersecting ))

Probability Space: (, , )

The probability space is a tuple of the sample space, all possible events, and all defined probabilities of these events.

Example: proving

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.

Example: proving

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 .

Example: proving

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:

Example: proving

Same as above, this is using the inclusion-exclusion formula. See below for more.

Boole’s Inequality

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:

Proof of Boole’s Inequality

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.

Example: n=2

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…

Inclusion-Exclusion Formula

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.

Random Permutations

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:

Zero Fix Points

Problem: Calculate the probability of zero fix points in a random permutation.

Solution:

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 .

Any Fix Points

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).

Solution:

Notice that if , then the probability of fix points is 0.