Probability

Probability
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Our Starting Point

What is "Probability"?
- Everyone has some intuition
- Most people can't define it
An Example:
- What is the probability that a coin comes up heads?

Our Starting Point (cont.)

The Process:
- We will conduct a thought experiment in which we know all of the outcomes
Probabilities:
- We will, essentially, assign probabilities to each of the outcomes (i.e., we will take an axiomatic approach)

Some Notation and Terminology

Sample Space:
- Each outcome of the thought experiment is called a sample point and is denoted by \(O_i\)
- The set of all sample points is called the sample space and is denoted by \(\mathcal{S}\)
Discrete Sample Space:
- There are a finite (or countably infinite) number of outcomes
Continuous Sample Space:
- The number of outcomes is uncountably infinite
Probabilities on Discrete Sample Spaces:
- The probability of a particular sample point, \(O_i\), is denoted by \(P\{O_{i}\}\)
- \(P\{O_{1}\} \geq 0, P\{O_{2}\} \geq 0, \ldots , P\{O_{n}\} \geq 0 \)
- \(P\{O_{1}\} + P\{O_{2}\} + \cdots + P\{O_{n}\} = 1\)

Examples with Discrete Sample Spaces

Coin Tossing:
- Two possible outcomes, heads (\(H\)) and tails (\(T\))
- Both outcomes are usually assumed to be equally likely
- This leads to the conclusion that \(P\{H\} = P\{T\} = 1/2\)
Rolling a Die:
- Six possible outcomes, one pip, two pips, ... six pips
- All outcomes are assumed to be equally likely
- The probability of each outcome is 1/6

More Notation and Terminology

Random Variable:
- A function that assigns a number to every element in the sample space (e.g., the payoffs in a coin tossing game)
- Random variables are often denoted with uppercase letters (e.g., \(X\)) and the possible values they can take as lowercase letters (e.g., \(x_1, x_2\))
Event:
- A set of sample points (from the range) or a set of values of a random variable (from the domain)
Probability of an Event:
- The sum of the probabilities of the sample points that are in that event (from the range) or the probability that a random variable takes on certain values (from the domain)

More Notation and Terminology (cont.)

Densities and Distributions on Discrete Sample Spaces:
- The probability that the random variable \(X\) takes on the value \(x\) is denoted by \(f(x)\), and \(f\) is called the probability density function
- The probability that the random variable \(X\) takes on some value less than or equal to \(x\) is denoted by \(F(x)\), and \(F\) is called the cumulative distribution function
Expected Value for Discrete Sample Spaces:
- \(E(X) = f(x_1) x_1 + f(x_2) x_2 + \cdots + f(x_n) x_n\) is called the expected value of the random variable \(X\)

Strong Law of Large Numbers

Setting:
- Let the random variable \(X_i\) equal 1 if the \(i\)th flip of a coin is a head and 0 otherwise
- Suppose the probability of a head is given by \(a\)
- Suppose we have a sequence of random variables, \(X_1, X_2, \ldots, X_n\)
- Let the random variable \(Z_n\) be defined as \(Z_n = X_1 + X_2 + \cdots + X_n\) (i.e., the number of heads obtained in \(n\) tosses)
The Question (Working Backwards):
- You toss a coin \(n\) times and it turns out that the number of heads is \(Z_n\), what can you conclude about \(a\)?
The Strong Law of Large Numbers:
- \( \lim_{n \rightarrow \infty} \frac{Z_n}{n} = a \)
- As \(n\) gets large, the fraction \(Z_n / n\) approaches the true probability

Examples with Continuous Sample Spaces

Guessing a Real Number in \([0,1]\):
- The number of outcomes is uncountably infinite
Throwing a Dart at a Wall:
- The number of outcomes is uncountably infinite

Assigning Probabilities in Continuous Sample Spaces

The Intuitive Approach:
- All probabilities must be greater than or equal to 0
- The probabilities must sum to 1
The Problem:
- If each probability is positive the sum is infinite
- If each probability is 0 the sum is 0

Densities and Distributions on Continuous Sample Spaces

Densities on Continuous Sample Spaces:
- \(f\) must always be greater than or equal to zero
- The area under (the curve representing) \(f\) must equal 1
Distributions on Continuous Sample Spaces:
- \(F(x)\) is the area under (the curve representing) \(f\) between \(0\) and \(x\)

Using Densities on Continuous Sample Spaces

Probability of an Interval:
- The probability of being between two numbers \(x_L\) and \(x_R\) is the area under (the curve representing) \(f\) between \(x_L\) and \(x_R\)
The Probability of Individual Values:
- The area under the curve at a point is 0, so the probability is 0

An Example: The Uniform Density Function on \([0,1]\)

The Density Function
images/uniform-density.gif

The Probability of \(0.125 \leq X \leq 0.750\)
images/uniform-density_example.gif

Relationships Between Events

The Questions:
- What is the probability that \(A\) or \(B\) (or both) occurs?
- What is the probability that both \(A\) and \(B\) occur?
The Key Observation:
- These are questions about sets of sample points

Relationships Between Events (cont.)

Two Examples

Relationships Between Events (cont.)

The First Question:
- \( P(A \mbox{ or } B \mbox{ or both}) = P(A \cup B) = P(A) + P(B) - P(A \mbox{ and } B) \)
- Mutually exclusive events are just a special case
The Second Question:
- Two random variables are said to be independent if \(P(X_1 = a_1 \mbox{ and } X_2 = a_2) = P(X_1 = a_1) \cdot P(X_2 = a_2)\)
- For the general case, we need to do a little work

Conditional Probabilities

The Notion:
- The conditional probability is the probability that one event occurs given that another occurs
A Definition:
- The conditional probability of \(A\) given \(B\) is denoted by \(P(A|B)\) and is defined as a number in \([0,1]\) that satisfies:
  \( P(A \mbox{ and } B) = P(A|B) \cdot P(B) \)
A Question:
- Why not use the definition \(P(A|B) = \frac{P(A \mbox{ and } B)}{P(B)}\)?
- What happens when \(P(B)=0\)?
- \(P(A|B)\) can be any number in \([0,1]\) (i.e., the probability of \(A\) given \(B\) when \(B\) doesn't occur is not uniquely defined)

Conditional Probabilities and Independence

Assume:
- The two random variables, \(X_1\) and \(X_2\), are independent
It Follows That:
- \( P(X_1 = a_1 \mbox{ and } X_2 = a_2) = P(X_1 = a_1 | X_2 = a_2) \cdot P(X_2 = a_2) \)
Hence:
- \( P(X_1 = a_1 | X_2 = a_2) = P(X_1 = a_1) \)

Conditional Probabilities - Nerd Humor

Seashell

(Courtesy of xkcd)

An Example

The Thought Experiment:
- There are two flights from SHD to IAD (Flight 0 and Flight 00)
- For each flight there are two possible outcomes, "On Time" and "Late"
- \(P(\text{On Time}) = 0.8\) and \(P(\text{Late}) = 0.2\)
- The flights are independent
The Question:
- What is the probability that one or the other (or both) flights are on time?
Setup:
- A is the event "0 is on time"
- B is the event "00 is on time"

An Example - An Incorrect Approach

Don't do the following:
- \(P(\text{A or B}) = P(\text{A}) + P(\text{B}) = 0.8 + 0.8 = 1.6\)
How do you know this is wrong?

An Example - One Correct Approach

What was Wrong?
- \(P(\text{A or B}) \neq P(\text{A}) + P(\text{B})\)
The Correct Equation:
- \(P(\text{A or B}) = P(\text{A}) + P(\text{B}) - P(\text{A and B}) \)
The Correct Answer:
- \(P(\text{A or B}) = 0.8 + 0.8 - (0.8 \cdot 0.8) = 1.60 - 0.64 = 0.96 \)

An Example - Another Correct Approach

Complements of Events:
- C is the event 0 is late (which is the complement of A; \(C = \overline{A}\))
- D is the event 00 is late (which is the complement of B; \(D = \overline{B}\))
DeMorgan:
- In logic: \(\neg (P \vee Q) \equiv (\neg P \wedge \neg Q)\)
- In set theory: \(\overline{A \cup B} \equiv (\overline{A} \cap \overline{B})\)
Because of Independence:
- \(P(\text{C and D}) = P(\text{C}) \cdot P(\text{D}) = 0.2 \cdot 0.2 = 0.04 \)
The Correct Answer:
- \(P(\text{A or B}) = 1 - P(\text{C and D}) = 1 - 0.04 = 0.96 \)

Be Careful!

An Example Involving a Single Event:
- In roulette, the event "Green" consists of the two sample points 0 and 00 (i.e., \(\text{Green} = \{0, 00\}\))
- So, \(P(\text{Green}) = P\{0\} + P\{00\}\)
An Example Involving Multiple Events:
- \(P(\text{0 is late or 00 is late}) = P(\text{0 is late}) + P(\text{00 is late}) - P(\text{0 is late and 00 is late}) \)