2.2 - tree diagrams and counting

Tree diagrams

Very useful in sequential experiments for:

  • Enumerating sample spaces;
  • weighting outcomes, especially when the experiment is sequential in nature.

The possible outcomes are at the end of each set of branches, and probabilities of outcomes in the sample space found by multiplying probabilities along tree branches.

Example: flipping a coin twice

  • Use a tree diagram to describe sample space and probabilities of outcomes for experiment “Flip a coin 2 times.”

  • Create two versions of the tree diagram:

  1. Assuming a fair coin;
  2. Assuming a weighted coin with \(P(H) = 2/3\).

Tree 1: a fair coin

Tree 2: an unfair coin

Example: drawing without replacement

  • An urn has 3 blue and 4 red chips:

  • Experiment: Draw 2 chips from urn, without replacement.

  • Let \(A=\){red on first draw, blue on second draw}, and \(B=\){At least one red chip is drawn}.

  • Find \(P(A)\) and \(P(B)\) using tree diagrams to help.

Tree for \(P(A)\)

  • \(A\) = {red on first, blue on second}

Tree for \(P(B)\)

  • \(B\) = {at least one red chip is drawn}

Motivating counting methods

  • Recall the Equally Likely Rule. If:
    • \(|\Omega| = n\);
    • \(|A| = m\);
    • \(P(\omega_i) = \frac{1}{n}\) for all \(i\);
    • \(\implies P(A) = \frac{m}{n}.\)
  • Easy enough if \(n\) is a small number, like 8 or 36!
  • Often, these event sizes are much larger.
  • We now consider some important methods of counting numbers of elements in sample spaces or events.

Multiplication principle

  • If there are \(p\) ways for one thing to happen, and \(q\) ways for a second thing to happen, and these “things” happen independently, there are \(p\times q\) ways for both things to happen.

  • More generally, suppose an experiment consists of a sequence of \(p\) trials \(\{a_1,a_2,...,a_p\}\). If there are \(k_1\) possible outcomes of the first trial, \(k_2\) possible values for the second trial, …, and \(k_p\) possible values for the \(p^{th}\) trial, then there are \(k_1\times k_2 \times ...\times k_p\) possible outcomes of the experiment.

Example: roll 2 different-sided dice

  • The experiment: roll 2 dice. One has 4 sides numbered 1-4, the other has 20 sides numbered 1-20.
  • How large is \(\Omega\), the sample space?
  • Sequence: {roll 4-sided die; roll 20-sided die}
  • Number of possibilities for each sequence element: {4, 20}
  • \(|\Omega| = 4\times 20 = 80\)

Example: flip a coin 4 times

If the experiment is flip a coin 4 times, find:

  1. \(p\)
  2. \(\{a_1, ..., a_p\}\)
  3. \(\{k_1,...,k_p\}\)
  4. \(|\Omega|\)
  1. Experiment consists of sequence of 4 trials. \(p=4\).
  1. \(\{a_1, a_2,a_3 a_4\}\) = {Result of first flip,Result of second flip, Result of third flip, Result of fourth flip}
  1. \(\{k_1,k_2,k_3,k_4\} = \{2,2,2,2\}\)
  1. \(|\Omega| = 2\times 2\times 2 \times 2 = 16\)

Example: license plates

License plates in Minnesota are issued with 3 letters from A-Z followed by 3 digits from 0-9.

  1. How many possible license plates are there?
  2. My license plate used to start with the letters NGJ. Let \(A\) ={license plate starts with NGJ}. What is \(P(A)\)? Assume all license plate sequences are equally likely (so all we have to do is count.)
  1. Counting \(|\Omega|\):
  • Sequence of “trials”: {Letter 1, Letter 2, Letter 3, Number 1, Number 2, Number 3}
  • Number of possibilities for each “trial” {26, 26, 26, 10, 10, 10}
  • \(|\Omega| = 26^3 \times 10^3 = 17,576,000\)
  1. Counting \(|A|\):
  • Sequence of “trials”: {N, G, J, Number 1, Number 2, Number 3}
  • Number of possibilities for each “trial”: {1, 1, 1, 10, 10, 10}
  • \(|A| = 10^3 = 1000\)

All plates equally likely \(\implies P(A) = \frac{|A|}{|\Omega|} = \frac{1000}{17,576,000}\)

Permutations: counting orderings

Consider the following questions:

  • How many ways can we arrange 10 students in a row?
  • How many ways can we sort the letters R-A-N-D-O-M?
  • How many ways can we order 5 books on a bookshelf?

The words arrange, sort, order are synonyms for permute.

Given a set with \(n\) elements, there are

\[n \times (n-1) \times ... \times 3 \times 2 \times 1 = n!\]

distinct permutations of the set. In R, use the function factorial() to calculate permutations.

Example: scrabble tiles

A bag contains 6 Scrabble tiles with the 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 will spell the word R-A-N-D-O-M?

  • \(|\Omega| = 6! = 720\)
  • \(|A| = 1\)
  • All orderings equally likely \(\implies P(A) = \frac{|A|}{|\Omega|} = \frac{1}{720}\)

Example: Bob’s bookshelves

Bob has 3 bookshelves. Each can hold 5 books. He has 15 books: 5 math books, and 10 novels. If the books are placed randomly on the shelves, and any arrangement is equally likely, what is \(P(\mbox{all math books are on the bottom shelf})\)?

  • \(|\Omega| =\) number of ways to arrange 15 books in any order =\(15!\)
  • To count \(|A|\), consider it as experiment consisting of sequence of two events: {5 math books on bottom shelf, 10 novels on top-2 shelves}
  • Count each element: {5! ways to arrange the math books on bottom shelf; 10! ways to arrange the novels on top-2 shelves)
  • \(|A| = 5! \times 10!\)

Apply equally likely rule:

\[P(A) = \frac{5! \times 10!}{15!} = 0.0003\]

Combinations: counting unordered sets and subsets

Motivating combinations

How many unique ways are there to arrange \(A_1\), \(A_2\), and \(B\)?

\[\color{red}{A_1 A_2 B}\] \[\color{red}{A_2A_1B}\] \[\color{blue}{BA_1 A_2}\] \[\color{blue}{BA_2A_1}\]

\[\color{orange}{A_1B A_2}\] \[\color{orange}{A_2BA_1}\]

Now what if we dropped the subscripts?

\[\color{red}{A A B}\] \[\color{blue}{BA A}\] \[\color{orange}{AB A}\]

I.e., \(3!\) over-counts by \(2! \times 1!\) (# of unique A orderings x # of unique B orderings)

Theorem

In general, the number of ways to arrange \(n\) items when there are only \(r\) unique kinds of items is:

\[\frac{n!}{n_1! n_2!...n_r!}\]

where \(n_1\) is the number of the first kind of item, \(n_2\) is the number of the second kind of item, etc.

Example: urn with 3 chip types

  • A jar contains 6 chips: 3 red, 2 blue, and 1 green.
  • You reach into the jar below and draw out all 6 chips, one at a time, without replacing them. You arrange them in order on the table in front of you in the order in which you drew them.
  • How many distinct orderings are there?

Sample ordering:

Number of such orderings:

\[\frac{6!}{3!2!1!}\]

Counting subsets

How many ways can we pick groups of 2 from these 5 students?

Of course, these two groups are equivalent:

Listing the ways 2 students are IN can be done using 1’s for “in” and 0’s for “out.” Number of ways to arrange 2 “ins” and 3 “outs”:

Note there are \(\frac{5!}{2!3!}=10\) such arrangements.

Theorem for counting subsets

The number of ways to form combinations of \(k\) items subset from \(n\) items (when order doesn’t matter) is

\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

In R, we use choose(n,k) to calculate this.

Example: STAT and DSCI

  • A classroom has 10 students: 6 DSCI and 4 STAT majors.
  • What are the number of ways to pick 3 DSCI and 2 STAT major for a project?

  • Sequence of elements: {pick 3 DSCI majors from 6; pick 2 STAT majors from 4}

  • # of possibilities for each element: \(\left\{\binom{6}{3};\binom{4}{2}\right\}\)

  • Applying multiplication principle: \(\binom{6}{3} \times \binom{4}{2}\)

Example: 20 coin flips

  • In 20 coin tosses of a fair coin, what is the probability of getting exactly 10 heads?
  • Count \(|\Omega|\): \(2^{20}\) possible sequences
  • Count \(|A|\): \(\binom{20}{10}\)
    • One example: {H,H,H,T,H,T,H,H,T,T,H,T,H,H,H,T,T,T,T,T}
    • Divide \(20!\) by \((10!\times 10!)\) since the Hs and Ts are not unique
  • Since all sequences are equally likely, \(P(A)=\frac{\binom{20}{10}}{2^{20}} =0.176\)

Example: full house

  • In poker, a “full house” is 3 of one kind and 2 of another kind (for example, K K K 9 9).
  • If you are dealt 5 cards from a standard deck, what is the probability you are dealt a full house?
  • Count \(|\Omega|\): # of 5-card hands is \(\binom{52}{5}\)
  • To count \(|A|\), consider the sequence of events that must take place:
    • {Choose 2 denominations out of 13 to be in the full house}: \(\binom{13}{2}\) possibilities.
    • {Of the 2 denominations chosen, choose 1 to be the “set of 3”}: \(\binom{2}{1}\) possibilities.
    • {From the 4 “set of 3” cards, draw 3 cards}: \(\binom{4}{3}\) possibilities.
    • {From the 4 “set of 2” cards, draw 2 cards}: \(\binom{4}{2}\) possibilities.
    • \(\implies |A| = \binom{13}{2}\times \binom{2}{1} \times \binom{4}{3} \times \binom{4}{2} = 3744\)
  • \(P(A) = \frac{3744}{\binom{52}{5}} = 0.00144\)