3. Probability -- Counting Techniques

Some probability problems can be attacked by specifying a sample space MATH in which each simple event has probability $\frac{1}{n}$ (i.e. is "equally likely"). Thus, if a compound event $A$ consists of $r$ simple events, then $P(A)=\frac{r}{n}$. To use this approach we need to be able to count the number of events in $S$ and in $A$, and this can be tricky. We review here some basic ways to count outcomes from "experiments". These approaches should be familiar from high school mathematics.

General Counting Rules

There are two basic rules for counting which can deal with most problems. We phrase the rules in terms of ``jobs" which are to be done.

  1. The Addition Rule:

    Suppose we can do job 1 in $p$ ways and job 2 in $q$ ways. Then we can do either job 1 or job 2, but not both, in $p+q$ ways.

For example, suppose a class has 30 men and 25 women. There are $30+25=55$ ways the prof. can pick one student to answer a question.

  1. The Multiplication Rule:

    Suppose we can do job 1 in $p$ ways and an unrelated job 2 in $q$ ways. Then we can do both job 1 and job 2 in $p\times q$ ways.

For example, to ride a bike, you must have the chain on both a front sprocket and a rear sprocket. For a 21 speed bike there are 3 ways to select the front sprocket and 7 ways to select the rear sprocket.

This linkage of OR with addition and AND with multiplication will occur throughout the course, so it is helpful to make this association in your mind. The only problem with applying it is that questions do not always have an AND or an OR in them. You often have to play around with re-wording the question for yourself to discover implied AND's or OR's.

Example: Suppose we pick 2 numbers at random from digits 1, 2, 3, 4, 5 with replacement. (Note: "with replacement" means that after the first number is picked it is "replaced" in the set of numbers, so it could be picked again as the second number.) Let us find the probability that one number is even. This can be reworded as: "The first number is even AND the second is odd, OR, the first is odd AND the second is even." We can then use the addition and multiplication rules to calculate that there are MATH ways for this event to occur. Since the first number can be chosen in 5 ways AND the second in 5 ways, $S$ contains $5\times5=25$ points. The phrase "at random" in the first sentence means the numbers are equally likely to be picked. MATH

When objects are selected and replaced after each draw, the addition and multiplication rules are generally sufficient to find probabilities. When objects are drawn without being replaced, some special rules may simplify the solution.



Problems:

      1. A course has 4 sections with no limit on how many can enrol in each section. 3 students each randomly pick a section. Find the probability:

        1. they all end up in the same section

        2. they all end up in different sections

        3. nobody picks section 1.

      2. Repeat (a) in the case when there are $n$ sections and $s$ students $(n \geq s)$.

    2. Canadian postal codes consist of 3 letters alternated with 3 digits, starting with a letter (e.g. N2L 3G1). For a randomly constructed postal code, what is the probability:

      1. all 3 letters are the same?

      2. the digits are all even or all odd? Treat 0 as being neither even nor odd.

    3. Suppose a password has to contain between six and eight digits, with each digit either a letter or a number from 1 to 9. There must be at least one number present.

      1. What is the total number of possible passwords?

      2. If you started to try passwords in random order, what is the probability you would find the correct password for a given situation within the first 1,000 passwords you tried?

    Permutation Rules

    Suppose that $n$ distinct objects are to be ``drawn" sequentially, or ordered from left to right in a row.
    (Order matters; objects are drawn without replacement)

    1. The number of ways to arrange $n$ distinct objects in a row isMATH

      Explanation: We can fill the first position in $n$ ways. Since this object can't be used again, there are only $(n-1)$ ways to fill the second position. So we keep having 1 fewer object available after each position is filled.

    Statistics is important, and many games are interesting largely because of the extraordinary rate of growth of the function $n!$ in $n.$For example

    $n$ 0 1 2 3 4 5 6 7 8 9 10
    $n!$ 1 1 2 6 24 120 720 5040 40320 362880 3628800

    which means that for many problems involving sampling from a deck of cards or a reasonably large population, counting the number of cases is virtually impossible. There is an approximation to $n!$ which is often used for large $n,$ called Stirling's formula which says that $n!$ is asymptotic to MATH Here, two sequences $a_{n}$ and $b_{n}$ are called asymptotically equal if MATH as $n\rightarrow\infty$ (intuitively, the percentage error in using Stirling's approximation goes to zero as MATHFor example the error in Stirling's approximation is less than 1% if $n\geq8.$

    1. The number of ways to arrange $r$ objects selected from $n$ distinct objects is MATH using the same reasoning as in #1, and noting that for the $r^{\QTR{rm}{th}}$ selection, $(r-1)$ objects have already been used. Hence there are
      MATH ways to make the $r^{\QTR{rm}{th}}$ selection. We use the symbol $n^{(r)}$ to represent MATH and describe this symbol as "$n$ taken to $r$ terms". E.g. MATH.

    While $n^{(r)}$ only has a physical interpretation when $n$ and $r$ are positive integers with $n\geq r$, it still has a mathematical meaning when $n$ is not a positive integer, as long as $r$ is a non-negative integer. For example MATH

    We will occasionally encounter such cases in this course but generally $n$ and $r$ will be non-negative integers with $n \geq r$. In this case, we can re-write $n^{(r)}$ in terms of factorials.

    MATH Note thatMATH

    The idea in using counting methods is to break the experiment into pieces or ``jobs'' so that counting rules can be applied. There is usually more than one way to do this.


    Example: We form a 4 digit number by randomly selecting and arranging 4 digits from 1, 2, 3,...7 without replacement. Find the probability the number formed is (a) even (b) over 3000 (c) an even number over 3000.


    Solution: Let $S$ be the set of all possible 4 digit numbers using digits 1, 2, ..., 7 without repetitions.

    Then $S$ has $7^{(4)}$ points. (We could calculate this but it will be easier to leave it in this form for now and do some cancelling later.)

    1. For a number to be even, the last digit must be even. We can fill this last position with a 2, 4, or 6; i.e. in 3 ways. The first 3 positions can be filled by choosing and arranging 3 of the 6 digits not used in the final position. i.e. in $6^{(3)}$ ways. Then there are $3\times6^{(3)}$ ways to fill the final position AND the first 3 positions to produce an even number.
      MATH

      Another way to do this problem is to note that the four digit number is even if and only if (iff) the last digit is even. The last digit is equally likely to be any one of the numbers 1, ..., 7 so MATH

    2. To get a number over 3000, we require the first digit to be 3, 4, 5, 6, or 7; i.e. it can be chosen in 5 ways. The remaining 3 positions can be filled in $6^{(3)}$ ways.MATH

      Another way to do this problem is to note that the four digit number is over 3000 iff the first digit is one of 3, 4, 5, 6 or 7. Since each of 1, ..., 7 is equally likely to be the first digit, we get $P$(number $>$ 3000) = $\frac {5}{7}$.

      Note that in both (a) and (b) we dealt with positions which had restrictions first, before considering positions with no restrictions. This is generally the best approach to follow in applying counting techniques.

    3. This part has restrictions on both the first and last positions. To illustrate the complication this introduces, suppose we decide to fill positions in the order 1 then 4 then the middle two. We can fill position 1 in 5 ways. How many ways can we then fill position 4? The answer is either 2 or 3 ways, depending on whether the first position was filled with an even or odd digit. Whenever we encounter a situation such as this, we have to break the solution into separate cases. One case is where the first digit is even. The positions can be filled in 2 ways for the first (i.e. with a 4 or 6), 2 ways for the last, and then $5^{(2)}$ ways to arrange 2 of the remaining 5 digits in the middle positions. This first case then occurs in MATH ways. The second case has an odd digit in position one. There are 3 ways to fill position one (3, 5, or 7), 3 ways to fill position four (2, 4, or 6), and $5^{(2)}$ ways to fill the remaining positions. Case 2 then occurs in MATH ways. We need case 1 OR case 2.

      MATH

      Another way to do this is to realize that we need only to consider the first and last digit, and to find $P$(first digit is $\geq$ 3 and last digit is even). There are $7\times6=42$ different choices for (first digit, last digit) and it is easy to see there are 13 choices for which first digit $\geq3$, last digit is even ( $5\times3$ minus the impossible outcomes (4, 4) and (6, 6)). Thus the desired probability is $\frac{13}{42}$.


    Exercise: Try to solve part (c) by filling positions in the order 4, 1, middle. You should get the same answer.


    Exercise: Can you spot the flaw in the following?
    There are $3\times6^{(3)}$ ways to get an even number (part (a))
    There are $5\times6^{(3)}$ ways to get a number $\geq$ 3000 (part (b))
    By the multiplication rule there are MATH ways to get a number which is even and $>$ 3000. (Read the conditions in the multiplication rule carefully, if you believe this solution.)

    Here is another useful rule.

    1. The number of distinct arrangements of $n$ objects when $n_{1}$ are alike of one type, $n_{2}$ alike of a $2^{\QTR{rm}{nd}}$ type, ..., $n_{k}$ alike of a $k^{\QTR{rm}{th}}$ type MATH is MATH

    For example: We can arrange $A_{1}A_{2}B$ in $3!$ ways. These are MATH

    However, as soon as we remove the subscripts on the MATH, the second row is the same as the first row. I.e., we have only 3 distinct arrangements since each arrangement appears twice as the $A_{1}$ and $A_{2}$ are interchanged. In general, there would be $n!$ arrangements if all $n$ objects were distinct. However each arrangement would appear $n_{1}!$ times as the $1^{\QTR{rm}{st}}$ type was interchanged with itself, $n_{2}!$ times as the $2^{\QTR{rm}{nd}}$ type was interchanged with itself, etc. Hence only MATH of the $n!$ arrangements are distinct.


    Example: 5 men and 3 women sit together in a row. Find the probability that

    1. the same gender is at each end

    2. the women all sit together.

    What are you assuming in your solution? Is it likely to be valid in real life?


    Solution: If we treat the people as being 8 objects -- 5$M$ and 3$W$, our sample space will have $\frac{8!}{5!3!}=56$ points.

    1. To get the same gender at each end we need either
      MATH OR MATH
      The number of distinct arrangements with a man at each end is $\frac{6!}{3!3!}=20$, since we are arranging $3M$'s and $3W$'s in the middle 6 positions. The number with a woman at each end is $\frac {6!}{5!1!}=6$. ThusMATH assuming each arrangement is equally likely.

    2. Treating $WWW$ as a single unit, we are arranging 6 objects -- 5$M $'s and 1 $WWW$. There are $\frac{6!}{5!1!}=6$ arrangements. Thus, MATH

      Our solution is based on the assumption that all points in $S$ are equally probable. This would mean the people sit in a purely random order. In real life this isn't likely, for example, since friends are more likely to sit together.



    Problems:

    1. Digits 1, 2, 3, ..., 7 are arranged at random to form a 7 digit number. Find the probability that

      1. the even digits occur together, in any order

      2. the digits at the 2 ends are both even or both odd.

    2. The letters of the word EXCELLENT are arranged in a random order. Find the probability that

      1. the same letter occurs at each end.

      2. $X, C,$ and $N$ occur together, in any order.

      3. the letters occur in alphabetical order.

    Combinations

    This deals with cases where order does not matter; objects are drawn without replacement.

    The number of ways to choose $r$ objects from $n$ is denoted by MATH (called "$n$ choose $r$"). For $n$ and $r$ both non-negative integers with $n\geq r$, MATH

    Proof: From result 2 earlier, the number of ways to choose $r$ objects from $n$ and arrange them from left to right is $n^{(r)}$. Any choice of $r$ objects can be arranged in $r!$ ways, so we must have

    (Number of way to choose $r$ objects from $n$)MATH

    This gives MATH as the number of ways to choose $r$ objects.

    Note thatMATH loses its physical meaning when $n$ is not a non-negative integer $\geq r$. However it is defined mathematically, provided $r$ is a non-negative integer, by $n^{(r)}/r!$.

    MATH


    Example: In the Lotto 6/49 lottery, six numbers are drawn at random, without replacement, from the numbers 1 to 49. Find the probability that

    1. the numbers drawn are 1, 2, 3, 4, 5, 6 (in some order)

    2. no even number is drawn.


    Solution:

    1. Let the sample space $S$ consist of all combinations of 6 numbers from 1, ..., 49; there are $\binom{49 }{6}$ of them. Since 1, 2, 3, 4, 5, 6 consist of one of these 6-tuples, MATH, which equals about 1 in 13.9 million.

    2. There are 25 odd and 24 even numbers, so there are $\binom{25 }{6} $ choices in which all the numbers are odd.

      MATH (no even number) = $P$ (all odd numbers)
      = MATH

      which is approximately equal to 0.0127.


    Example: Find the probability a bridge hand (13 cards picked at random from a standard deck) has

    1. 3 aces

    2. at least 1 ace

    3. 6 spades, 4 hearts, 2 diamonds, 1 club

    4. a 6-4-2-1 split between the 4 suits

    5. a 5-4-2-2 split.


    Solution: Since order of selection does not matter, we take $S$ to have MATH points.

    1. We can choose 3 aces in MATH ways. We also have to choose 10 other cards from the 48 non-aces. This can be done in MATH ways. Hence MATH

    2. Solution 1: At least 1 ace means 1 ace or 2 aces or 3 aces or 4 aces. Calculate each part as in (a) and use the addition rule to get MATH


    3. Solution 2: If we subtract all cases with $0$ aces from the MATH points in $S$ we are left with all points having at least 1 ace. This gives MATH (The term MATH can be omitted since MATH, but was included here to show that we were choosing $0$ of the 4 aces.)


    4. Solution 3: This solution is incorrect, but illustrates a common error. Choose 1 of the 4 aces then any 12 of the remaining 51 cards. This guarantees we have at least 1 ace, so MATH

      The flaw in this solution is that it counts some points more than once by partially keeping track of order. For example, we could get the ace of spades on the first choice and happen to get the ace of clubs in the last 12 draws. We also could get the ace of clubs on the first draw and then get the ace of spades in the last 12 draws. Though in both cases we have the same outcome, they would be counted as 2 different outcomes.

      (c)

    1. Choose the 6 spades in MATH ways and the hearts in MATH ways and the diamonds in MATH ways and the clubs in MATH ways.

      MATH

    2. The split in (c) is only 1 of several possible 6-4-2-1 splits. In fact, filling in the numbers 6, 4, 2 and 1 in the spaces above each suit MATH defines a 6-4-2-1 split. There are 4! ways to do this, and then MATH ways to pick the cards from these suits.

      MATH

    3. This is the same as (d) except the numbers 5-4-2-2 are not all different. There are $\frac{4!}{2!}$ different arrangements of 5-4-2-2 in the spaces MATH.
      MATH $\bigskip$

    Problems:

    1. A factory parking lot has 160 cars in it, of which 35 have faulty emission controls. An air quality inspector does spot checks on 8 cars on the lot.

      1. Give an expression for the probability that at least 3 of these 8 cars will have faulty emission controls.

      2. What assumption does your answer to (a) require? How likely is it that this assumption holds if the inspector hopes to catch as many cars with faulty controls as possible?

    2. In a race, the 15 runners are randomly assigned the numbers $1,2, \cdots, 15$. Find the probability that

      1. 4 of the first 6 finishers have single digit numbers.

      2. the fifth runner to finish is the 3rd finisher with a single digit number.

      3. number 13 is the highest number among the first 7 finishers.0.2in

    Problems on Chapter 3

    1. Six digits from 2, 3, 4, ..., 8 are chosen and arranged in a row without replacement. Find the probability that

      1. the number is divisible by 2

      2. the digits 2 and 3 appear consecutively in the proper order (i.e. 23)

      3. digits 2 and 3 appear in the proper order but not consecutively.

    2. Suppose $r$ passengers get on an elevator at the basement floor. There are $n$ floors above (numbered 1, 2, 3, ..., $n$) where passengers may get off.

      1. Find the probability

        1. no passenger gets off at floor 1

        2. passengers all get off at different floors $(n \geq r)$.

      2. What assumption(s) underlies your answer to (a)? Comment briefly on how likely it is that the assumption(s) is valid.

    3. There are 6 stops left on a subway line and 4 passengers on a train. Assume they are each equally likely to get off at any stop. What is the probability

      1. they all get off at different stops?

      2. 2 get off at one stop and 2 at another stop?

    4. Give an expression for the probability a bridge hand of 13 cards contains 2 aces, 4 face cards (Jack, Queen or King) and 7 others. You might investigate the various permutations and combinations relating to card hands using the Java applet at MATH

    5. The letters of the word STATISTICS are arranged in a random order. Find the probability

      1. they spell statistics

      2. the same letter occurs at each end.

    6. Three digits are chosen in order from 0, 1, 2, ..., 9. Find the probability the digits are drawn in increasing order; (i.e., the first $< $ the second $<$ the third) if

      1. draws are made without replacement

      2. draws are made with replacement.

    7. The Birthday Problem. Note_1 Suppose there are $r$ persons in a room. Ignoring February 29 and assuming that every person is equally likely to have been born on any of the 365 other days in a year, find the probability that no two persons in the room have the same birthday. Find the numerical value of this probability for MATH. There is a graphic Java applet for illustrating the frequency of common birthdays at http://www-stat.stanford.edu/%7Esusan/surprise/Birthday.html

    8. You have $n$ identical looking keys on a chain, and one opens your office door. If you try the keys in random order then

      • what is the probability the $k$th key opens the door?

      • what is the probability one of the first two keys opens the door (assume $n\geq3$)?

      • Determine numerical values for the answer in part (b) for the cases $n=3,5,7$.

    9. From a set of $2n+1$ consecutively numbered tickets, three are selected at random without replacement. Find the probability that the numbers of the tickets form an arithmetic progression. [The order in which the tickets are selected does not matter.]

    10. The 10,000 tickets for a lottery are numbered 0000 to 9999. A four-digit winning number is drawn and a prize is paid on each ticket whose four-digit number is any arrangement of the number drawn. For instance, if winning number 0011 is drawn, prizes are paid on tickets numbered 0011, 0101, 0110, 1001, 1010, and 1100. A ticket costs $1 and each prize is $500.

      • What is the probability of winning a prize (i) with ticket number 7337? (ii) with ticket number 7235? What advice would you give to someone buying a ticket for this lottery?

      • Assuming that all tickets are sold, what is the probability that the operator will lose money on the lottery?

      • There are 25 deer in a certain forested area, and 6 have been caught temporarily and tagged. Some time later, 5 deer are caught. Find the probability that 2 of them are tagged. (What assumption did you make to do this?)

      • Suppose that the total number of deer in the area was unknown to you. Describe how you could estimate the number of deer based on the information that 6 deer were tagged earlier, and later when 5 deer are caught, 2 are found to be tagged. What estimate do you get?

    12. Lotto 6/49. In Lotto 6/49 you purchase a lottery ticket with 6 different numbers, selected from the set $\{ 1,2,...,49 \}$. In the draw, six (different) numbers are randomly selected. Find the probability that

      • Your ticket has the 6 numbers which are drawn. (This means you win the main Jackpot.)

      • Your ticket matches exactly 5 of the 6 numbers drawn.

      • Your ticket matches exactly 4 of the 6 numbers drawn.

      • Your ticket matches exactly 3 of the 6 numbers drawn.

    13. (Texas Hold-em) Texas Hold-em is a poker game in which players are each dealt two cards face down (called your hole or pocket cards), from a standard deck of 52 cards, followed by a round of betting, and then five cards are dealt face up on the table with various breaks to permit players to bet the farm. These are communal cards that anyone can use in combination with their two pocket cards to form a poker hand. Players can use any five of the face-up cards and their two cards to form a five card poker hand. Probability calculations for this game are not only required at the end, but also at intermediate steps and are quite complicated so that usually simulation is used to determine the odds that you will win given your current information, so consider a simple example. Suppose we were dealt 2 Jacks in the first round.

      1. What is the probability that the next three cards (face up) include at least one Jack?

      2. Given that there was no Jack among these next three cards, what is the probability that there is at least one among the last two cards dealt face-up?

      3. What is the probability that the 5 face-up cards show two Jacks, given that I have two in my pocket cards?