week3day2

Permutation: an ordering of the elements of the set.

• ex: a set {a,b,c}, (abc) (acb) (cab) (cba) …
  • Each different order is called a permutation of the set.
• Counting Permutations: Give a set of n different elements
  • n! = nx(n-1)x(n-2)x…x permutations

  ex. 1.16 A bag contains 6 scrabble tiles with letters A-D-M-N-O-R. You reach into the bag and take out tiles one at a time. What is the probability that you spell out R-A-N-D-O-M

  1. using the permutation rule. \(6! = 6 * 5 * 4 * 3 * 2 * 1 = 720\)

  2. A = {Random}

  3. \(P(A) = \frac{1}{720}\) = 0.001388889

  ex 1.17 A bag contains 6 scrabble tiles with letters A-D-M-N-O-R. After you pick a tile from the bag, write downt he letter and then return the tile into the bag. What is the probability that you will get the word “R-A-N-D-O-M”

  1. Using the multiplication rule,. \(6 * 6 * 6 * 6 * 6 * 6 = 6^6\)

  2. A = {RANDOM}

  3. \(P(A) = \frac{1}{46656}\)

Sampling with and without replacement.

When sampling with replacement, a unit that is selected from a population is returned to the population before another unit is selected

When sampling without replacement, the unit is not returned to the population after being selected.

1.8 Problem - Solving Strategies: Complements, Inclusion-Exclusion

Consider a sequence of events, \(A_1, A_2, ..., A_n\) Find the probability that at least one of the events occurs, where \[P(\cup_{i=1}^n A_1\cup A_2 ... \cup A_n)\]

\[(A \cup B)^c = A^c B^c\ (or\ A^c \cap B^c)\]

\[(A \cap B)^c = A^c \cup B^c\]

Given \(A_1, A_2, ...\)

\[(\cup_{i=1}^\infty A_i)^c = \cap_{i=1}^\infty (A_i)^c\]

1. Define

2. Venn-Diagram

3. English

4. Proof

\[(\cap_{i=1}^\infty A_i)^c = \cup_{i=1}^\infty (A_i)^c\]

Example 1.19 Four dice are rolled. Find the probability of getting at least one 6

The sample space \(\Omega\) is

\(\Omega = {(1,1,1,1), (1,1,1,2), .... (6,6,6,6)}\)

\(6 * 6 * 6 * 6 = 6^4 = 1296\) Equally likely outcomes.

Let A be the event of getting one 6.

\(P(A) = \frac{A}{1296}\)

\(A:={(6,1,1,1)(6,2,1,1,)....., (6,6,6,6)}\)

\(A^c = {getting\ no\ 6}\)

\(5x5x5x5 = 5^4 = 625\)

\(P(A) = 1 - P(A)^c = 1- \frac{625}{1296} = 0.5177\)

Inclusion-Exclusion (ex. 1.20)

Given events \(A_1, ..., A_n\)

\(p(A_1, \cup A_2 ..., \cup A_n) = \sum_{i=1}^n P(A_i) - \sum_{1 \le i \le j \le n} P(A_i A_j) + \sum_{1\le i \le j \le k \le n} P(A_i A_j A_k) ... + (-1)^(n+1) P(A_1 \cap ... A_n)\)

Remarks: \(A_1, A_2, n=2\)

\[P(A_1 \cup A_2) = \sum_{i=1}^n P(A_i) - \sum_{1 \le i \le j \le 2} P(A_i A_j) \\ = P(A_1) + P(A_2) - P(A_1 A_2)\]

Proof: Mathematical induction

1. n=1

2. N=n levels

3. 1N = n+1

\(A_1, A_2, A_3,\ \ n = 3\)

\(P(A_1 \cup A_2 \cup A_3) = \sum_{i=1}^3 P(Ai) - \sum_{1 \le i \le j \le 3} P(A_i A_j) + \sum_{1 \le i \le j \le k \le 3} P(A_i A_j A_k)\)

\(=P(A_1) + P(A_2) + P(A_3) - P(A_1 A_2) - P(A_2 A_3) - P(A_1 A_3) + P(A_1 A_2 A_3)\)

Bonferroni Inequality

\(P(\cup_{j=1}^n A_j) \le \sum_{j=1}^n P(Aj)\)

(ex. Multiple testing problem in statistics.)

Method 3

Decomposing an event into a union of mutually exclusive subsets.

Example 1.21 : Consider a random experiment that has k equally likely outcomes, one of which we call success. Let A be the event that at least one of the n outcomes is a success.

ex. Rolling a dice 10 times, where success means rolling a three. If n=10, k=6, and A is the event of rolling at least one 3.

Define a sequence of events \(A_1, A_2, ... A_n\) Where \(A_i\) is the event that the ith trial is a success.

Then \(A=\cup_{i=1}^n A_i\) and \(P(A)= P(\cup_{i=1}^n A_i)\)

Now define \(B_i\) to be the event that the first success occurs on the ith trial, i = 1,2,…,n.

\(B_i\)’s are mutually exclusive

\(B_2 : {N Y N N ...., N Y Y N ...}\)

Success occurs at the second attempt, and every other occurrence of such

\(B_3 : {N N Y N ...., N N Y Y ...}\)

Success occurs at the third, and every other occurrence of such

\(B_2 \cap B_3 = 0\)