Discrete probability

Lecture 9: Discrete Probability

• Presenter: Li Cheuk Ting (ctli@ie.cuhk.edu.hk)

Classical Probability

• Definition: Picking one element from a set ( \Omega ) (sample space) uniformly at random.

• Probability of event ( A ):

  • ( Pr(A) = \frac{#\text{ outcomes in } A}{#\text{ outcomes}} = \frac{|A|}{|\Omega|} )

  • Example: Rolling a die ( \Omega = {1, 2, 3, 4, 5, 6} ):

    • Probability of rolling a number ( \leq 2 ):

      • ( Pr({x \in \Omega | x \leq 2}) = \frac{2}{6} = \frac{1}{3} )

Example: Selecting Balls from a Bag

• Scenario: Picking 2 balls without replacement from a collection of 6 balls (3 black, 3 white).

• Sample Space: Combinations of 2 balls from 6, ( \Omega = {C \subseteq {1, 2, 3, 4, 5, 6} | |C| = 2} )

• Event ( A ): Picking both black balls ( A = {C \subseteq {1,2,3} | |C| = 2} )

• Probability Calculation:

  • ( Pr(A) = \frac{|A|}{|\Omega|} = \frac{3}{15} = \frac{1}{5} )

Coin Flipping Example: At least One Heads

• Method 1: Counting the number of heads.

• Sample Space: ( \Omega = {0, 1, 2, 3} ) (for 3 coins).

• Event ( A ): ( s \in \Omega: s \geq 1 ) ( A = {1, 2, 3} )

• Probability: ( Pr(A) = \frac{|A|}{|S|} = \frac{3}{4} )

• Method 2: Sequences representation of heads (1) and tails (0).

  • Sample Space: Length 3 sequences of {0,1},( \Omega = {0, 1}^3 )

  • Event ( A ): At least one head ( A = {(1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1)} )

  • Probability: ( Pr(A) = \frac{|A|}{|\Omega|} = \frac{7}{8} )

  • Method 2 is correct as distribution is not uniform.

Nonuniform Probability

• Assumption of uniform probability for all elements in ( \Omega ) is based on the Principle of Indifference (fairness in outcomes).

• Example: Winning the Nobel Prize - ( Pr(win) = \frac{|win|}{|win, not\ win|} = \frac{1}{2} ?) actually lower.

• Conclusion: Different outcomes can have different probabilities.

Probability Space

• Defined as a pair ( (\Omega, Pr) ).

  • Sample Space ( \Omega ): All possible outcomes.

  • Probability Function ( Pr: \Omega \rightarrow [0,1] ):

    • Nonnegative real number assigned to each outcome, summing to 1: ( \sum_{s \in \Omega} Pr(s) = 1 ).

  • Example: In coin flip, ( \Omega = {0,1}^3 ), ( Pr(s) = \frac{1}{8} ) for each outcome.

  • The probability of event ( A ): ( Pr(A) = \sum_{s \in A} Pr(s) )

Properties of Probability Space

• Empty event ( \emptyset ): ( Pr(\emptyset) = 0 )

• Whole sample space ( \Omega ): ( Pr(\Omega) = 1 )

Additivity and Complement Events

• If events ( A_1, \ldots, A_n ) are disjoint: ( Pr(\cup_{k=1}^{n} A_k) = \sum_{k=1}^{n} Pr(A_k) )

• For any event ( A ), ( Pr(A) + Pr(A^c) = 1 )

• General Union Bound: ( Pr(\cup_{k=1}^{n} A_k) \leq \sum_{k=1}^{n} Pr(A_k) )

• Law of Total Probability: If events partition ( \Omega ), ( Pr(B) = \sum_{k=1}^{n} Pr(B \cap A_k) ).

Independent Events

• Definition: Two events ( A, B ) are independent if ( Pr(A \cap B) = Pr(A) Pr(B) )

• Example with flipping coins:

  • Sample Space: ( \Omega = {0,1}^2 )

  • Probability calculations demonstrate independence.

Birthday Problem

• Concept: In a room with ( n ) people, what is the probability that at least two share a birthday?

• Utilizing the Pigeonhole Principle, if ( n = 366 ), at least two must share.

• Goal: Find minimum ( n ) so probability of sharing a birthday is ( \geq 50% ).

Random Variables

• Definition: A function ( X: \Omega \rightarrow \mathbb{R} ) mapping outcomes to real numbers.

• Example: With coin flips, ( X(s) = s_1 + s_2 + s_3 ) (count of heads).

• Probability events can be defined on random variables (e.g., ( X \geq 1 )).

Probability Mass Function (pmf)

• Definition: The pmf ( p_X(x) ) gives the probability that ( X = x ).

• Supports are the values for which the pmf is > 0.

• Joint pmf for multiple variables can be defined likewise.

Definition Summary

• Event: Subset ( A \subseteq \Omega ).

• Union of Events: ( A \cup B ) - either occurs.

• Intersection of Events: ( A \cap B ) - both occur.

• Complement of an Event: ( A^c = \Omega \ A ).

• Random Variable: A function mapping outcomes to numbers.

Independent Random Variables

• Two (discrete) random variables ( X, Y ) are independent if their joint probability equals the product of their marginals for all ( x, y ).

• Example involving poker cards reveals independence.

Monty Hall Problem

• Problem outline: Choose one of 3 doors, one conceals a car, the others goats.

• Switching gives better odds of winning (probability of winning if switch = ( 2/3 )).

Expectation and Variance

• Expectation: ( E(X) = \sum_{s \in \Omega} X(s) Pr(s) ).

• Variance: ( Var(X) = E(X^2) - (E(X))^2 ).

Bernoulli and Binomial Distribution

• Bernoulli: Experiments with a single trial. ( X \sim Bern(a) ) with parameters.

• Binomial: ( n ) independent Bernoulli trials, leading to number of successes ( X \sim Binom(n,a) ).

Geometric Distribution

• Random variable ( X ) representing the number of trials until the first success (heads).

• Example shows probability mass function characteristics based on successes.