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})$