MUN Computer Science 1002 - Lab 9

Combinatorics and probability

Review:

• Lectures 28-30.

Vocabulary

• Combinations, permutation (with or without repetition)
• Binomial theorem, Pascal identity, Pascal triangle
• Experiment, outcome, sample space, event
• Probability, distribution, uniform distribution
• Conditional probability, independent events, Bayes theorem

Individual work

Solve each of the following exercises.

1. Suppose that pair of dice is biased so that in the first die, probability of 3 appearing is three times the probability of any other number, and in the second die, the probability of both 2 and 4 appearing is twice the probability of any other number (that is, 2 is twice as likely as 1, 3, 5 or 6, and as likely as 4).
   1. What are the probabilities of each number from 1 to 6 coming up on the first die? On the second die?
   2. Suppose both dice are thrown simultaneously. What is the probability of the first die rolling 2 and the second rolling 4?
   3. What is the probability that sum of the rolls is an even number? Hint: consider different disjoint cases, and take a sum.
2. Consider permutations of numbers 1,2,3,4. Suppose we are selecting a random such permutation (i.e., 2134 or 4123); assume all such permutations are equally likely.
   1. What is the experiment here? What are its outcomes? What is the sample space?
   2. How large is the sample space? What is the probability of drawing a permutation 1234, if all are equally likely?
   3. What is the probability that in a randomly drawn permutation 1 comes before 4? I.e., 1234 or 2143 are OK, but not 2431).
   4. What is the probability that in a randomly drawn permutation 1 comes immediately before 4? I.e., 2143 is OK, but not 1234. Hint: use combinatorics to compute the number of such permutations.
3. (Combinations with repetitions).
   Let $x_1+x_2 + \dots +x_n = b$ be an equation over natural numbers (that is, $b$ and all possible values for variables are natural numbers starting with 0).
   1. How many different solutions that are natural numbers are there for n=5 and b=8?
   2. How many different solutions that are natural numbers are there if n=5, b=8, and each variable takes a value at least 1?
4. (Binomial theorem)
   1. Find expansion of $(x+y)^5$ using Binomial theorem. What is the coefficient of $xy^4$? Of $x^2y^3$?
   2. Use Pascal's identity to compute $\binom{6}{2} + \binom{6}{3}$.

   Group exercises

   For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

   Topic 1: Balls & bins

   Suppose that Alena selects a ball by first picking one uniformly at random and then selecting a ball from this box at random. The first box contains two white balls and three blue balls, and the second box contains four white balls and one blue ball.
   • What is the probability that Alena picked a blue ball if she selected the first box?
   • What is the probability that Alena selected a blue ball overall?
   • What is the probability that she picked a ball from the first box given that she selected a blue ball?

   Topic 2: Sensitivity and specificity

   Recall that sensitivity of a test is the percentage of correctly identified positives (that is, 100% minus % of false negatives) and specificity is the percentage of correctly identified negatives (100% minus % of false positives). Suppose that 5% of soccer players use steroids, and that in a certain test, 98% of soccer players who do take steroids test positive, and 12% of soccer players who do not take steroids test positive.

   • What are specificity and sensitivity of this test? What are the false positive and false negative rates?
   • What is the probability that a test will come positive for a random soccer player (picked uniformly at random)?
   • What is the probabililty that a soccer player who tests positive takes steroids?

   Topic 3: Generalized Bayes theorem

   In class, we defined Bayes theorem for two events $A$ and $B$. However, the theorem holds for an arbitrary number of events which form a partition of the sample space. In that case, if there are events $B_1, \dots, B_n$ forming a partition of the sample space (that is, they are mutually disjoint and their union is all of sample space $S$), and an event $A$, then for each $B_j$, $Pr(B_j | A) = Pr(A | B_j) Pr(B_j) / \Sigma_{i=1}^n Pr(A | B_i) Pr(B_i)$

   • Suppose that A, $B_1, B_2, B_3$ are events over sample space S such that $B_1, B_2, B_3$ are mutually disjoint and $B_1 \cup B_2 \cup B_3 =S$. What is $Pr(B_1 | A)$, if $Pr(A | B_1) = 1/8$, $Pr(A | B_2) = 1/4$, $Pr(A|B_3)=1/6$, $Pr(B_1)=1/4$, $Pr(B_2)=1/4$, $Pr(B_3)=1/2$?
   • Suppose that you have 12 coins in your purse: 6 dimes (10c coins), 2 quarters (25c) and 4 loonies (1\$ coins). Let event A be picking a coin from a purse, and events $B_1, B_2$ and $B_3$ be that a coin is a dime, quarter or loonie, respectively. Also, smaller coins have respectively smaller probability of being picked. What is $Pr(B_2 | A)$, that is, that if you picked a coin it is a quarter, if $Pr(A | B_1) = 1/4$, $Pr(A | B_2) = 3/8$ and $Pr(A|B_3)=1/2$?

   Review after the group exercises

   Suppose you have two boxes of apples from a suspect area near an industrial spill. One box contains three good apples and four contaminated ones, and the second box contains five good apples and six contaminated.

   1. Suppose that you select a box at random, and then pick a random apple out of the box. Given that you got a good apple, what is the probability that you've chose the second box?
   2. Now suppose that the test for contamination has false positive rate 1/5 and false negative rate 1/3. You randomly pick one of the apples from box 2. If the test is positive, what is the probability that the apple is contaminated?
   3. Suppose that out of 11 apples in the second box, 4 are ripe, 2 are unripe and 3 are overripe. As you can tell a little bit by touch which is which, probability of picking a ripe apple is 2/3, of unripe is 1/12 and overripe is 1/4. What is the probability that an apple is ripe given that you picked it?