Chapter 3 - Combinatorics

3.2 Combinations

Main:	Index
Previous:	3.1 Permutations
Next:	4.1 Discrete Conditional Probability

Results

Imagine a set A with n elements. A combination of size k can be thought of as the all subsets of A with length k. Example: A = {a, b, c}. Then the set of all possible subsets are: $$ \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}. $$ All possible combinations of length 2 are: {a, b}, {a, c} or {b, c}. For combinations the order doesn't matter; {a, b} and {b, a} are the same subset.




For integers n and k with 0 < k < n, the binomial coefficients satisfy: $$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}. \tag{3.1} $$ We use the initial condition: $$ \binom{n}{0} = \binom{n}{n} = 1 $$ which uniquely determines Pascal's triangle.




The binomial coefficients are given by the formula: $$ \binom{n}{k} = \frac{n!}{k!(n-k)!}. \tag{3.2} $$ It immediately follows that: $$ \binom{n}{k} = \binom{n}{n-k} $$




A Bernoulli trials process is a sequence of n chance experiments such that






Given n Bernoulli trials with probability p of success on each experiment, the probability of exactly k successes is $$ b(n, p, k) = \binom{n}{k}p^kq^{n-k} $$ where q = 1-p.




Let n be a positive integer and let p be a real number between 0 and 1. Let B be the random variable which counts the number of successes in a Bernoulli trials process with parameters n and p. Then the distribution b(n, p, k) of B is called the binomial distribution.




The quantity (a + b)ⁿ can be expressed in the form $$ (a + b)^n = \sum_{k=0}^n\binom{n}{k}a^kb^{n-k}. $$

Exercise 1

Compute the following:

(a) binom(6, 3)
(b) b(5, .2, 4)
(c) binom(7, 2)
(d) binom(26, 26)
(e) b(4, .2, 3)
(f) binom(6, 2)
(g) binom(10, 9)
(h) b(8, .3, 5)


Answer


(a)
binom(6, 3) = 20

(b)
$$ b(5, .2, 4) = \binom{5}{4}(0.2)^4(0.8) = 5(0.2)^4(0.8) = 0.0064. $$

(c)
binom(7, 2) = 21

(d)
binom(26, 26) = 1

(e)
$$ b(4, .2, 3) = \binom{4}{3}(0.2)^3(0.8) = 4(0.2)^3(0.8) = 0.0256. $$

(f)
binom(6, 2) = 15

(g)
binom(10, 9) = 10

(h)
$$ b(8, .3, 5) = \binom{8}{5}(0.3)^5(0.7)^3 = 56(0.3)^5(0.7)^3 = 0.04667544. $$

Exercise 2

In how many ways can we choose five people from a group of ten to form a committee?

Answer
How many possible subsets of 5 elements can be drawn from a set with 10 elements. $$ \binom{10}{5} = \frac{10!}{5!5!} = 252. $$

Exercise 3

How many seven-element subsets are there in a set of nine elements?

Answer
binom(9,7) = 9!/(2!7!) = 36.

Exercise 4

Using the relation Equation 3.1 write a program to compute Pascal’s triangle, putting the results in a matrix. Have your program print the triangle for n = 10.

Answer


Code:

Output:

    1
    1     1
    1     2     1
    1     3     3     1
    1     4     6     4     1
    1     5    10    10     5     1
    1     6    15    20    15     6     1
    1     7    21    35    35    21     7     1
    1     8    28    56    70    56    28     8     1
    1     9    36    84   126   126    84    36     9     1
    1    10    45   120   210   252   210   120    45    10     1

Exercise 5

Write a program to find the probability that, in 100 tosses of a fair coin, the number of heads that turns up lies between 35 and 65, between 40 and 60, and between 45 and 55.

Answer


Code:

Output:

> # Probabilities
> prob1
[1] 0.9982101
> prob2
[1] 0.9647998
> prob3
[1] 0.728747

Exercise 6

Charles claims that he can distinguish between beer and ale 75 percent of the time. Ruth bets that he cannot and, in fact, just guesses. To settle this, a bet is made: Charles is to be given ten small glasses, each having been filled with beer or ale, chosen by tossing a fair coin. He wins the bet if he gets seven or more correct. Find the probability that Charles wins if he has the ability that he claims. Find the probability that Ruth wins if Charles is guessing.

Answer
This is a binomial experiment. If Charles has the ability to distinguish beer from ale his success rate is 0.75. Let X be the number of correct guesses, then we have: $$ P(X = k) = \binom{10}{k}(0.75)^k(0.25)^{10-k} $$ Charles wins if: $$ P(X\geq 7) = P(X = 10) + P(X = 9) + P(X = 8) + P(X = 7) $$ Calculating in R.

# Using b() from previous exercise
# Between 7 and 10
probCharles = 0
for (correct in 7:10) {
  probCharles = probCharles + b(10, 0.75, correct)
}
> probCharles
[1] 0.7758751

If Charles is guessing, his probability of success falls to 0.5. Calculating the probability.

# Using b() from previous exercise
# Between 0 and 6
probRuth = 0
for (correct in 0:6) {
  probRuth = probRuth + b(10, 0.5, correct)
}
> probRuth
[1] 0.828125

Exercise 7

Show that $$ b(n, p, k) = \frac{p}{q}\left(\frac{n - k + 1}{k}\right)b(n, p, k-1) $$ for j greater or equal to 1. Hint: Consider the successive ratios as j increases. Note: This is a fraction and not a binomial coefficient! :)

Answer
\begin{align} b(n, p, k) &= \binom{n}{k}p^kq^{n-k} \\&\\ &= \frac{n!}{(n-k)!k!}\cdot p^{k-1}q^{n-k+1}\cdot\frac{p}{q} \\&\\ &= \frac{p}{q}\cdot\frac{n!}{(n-k)!k!}\cdot\frac{(n-k+1)!(k-1)!}{n!}\cdot\binom{n}{k-1}\cdot p^{k-1}q^{n-(k-1)} \\&\\ &= \frac{p}{q}\cdot\frac{n!}{(n-k)!k!}\cdot\frac{(n-k+1)!(k-1)!}{n!}\cdot b(n, p, k-1) \\&\\ &= \frac{p}{q}\cdot\frac{(n-k+1)!(k-1)!}{(n-k)!k!}\cdot b(n, p, k-1) \\&\\ &= \frac{p}{q}\left(\frac{n-k+1}{k}\right)b(n, p, k-1) \end{align}

Exercise 8

A die is rolled 30 times. What is the probability that a 6 turns up exactly 5 times? What is the most probable number of times that a 6 will turn up?

Answer
Another binomial experiment where X is the number of sixes with a success rate of p = 1/6. $$ P(X = 5) = \binom{30}{5}(1/6)^5(5/6)^{25} = 0.1921081. $$

The distribution of binomial experiments are quite symmetrical around the expected value, which in this case is (30)(1/6) = 5, so this is the most probable outcome. We can check this by calculating the values for 4 and 6 sixes. We see that this is correct below.

> choose(30, 6)*(1/6)**6*(5/6)**24
[1] 0.1600901

> choose(30, 4)*(1/6)**4*(5/6)**26
[1] 0.1847194

Exercise 9

Find integers n and r such that the following equation is true: $$ \binom{13}{5} + 2\binom{13}{6} + \binom{13}{7} = \binom{n}{r}. $$

Answer
This is just applying Theorem 3.5 several times. \begin{align} \binom{13}{5} + 2\binom{13}{6} + \binom{13}{7} &= \binom{13}{5} + \binom{13}{6} + \binom{13}{6} + \binom{13}{7} \\&\\ &= \binom{14}{6} + \binom{14}{7} \\&\\ &= \binom{15}{7}. \end{align}

Confirming in R.

> choose(13, 5) + 2*choose(13, 6) + choose(13,7)
[1] 6435

> choose(15, 7)
[1] 6435

Exercise 10

In a ten-question true-false exam, find the probability that a student gets a grade of 70 percent or better by guessing. Answer the same question if the test has 30 questions, and if the test has 50 questions.

Answer
Binomial experiment, where we need at least 7, 21 and 35 correct to get at least 70%. (The probabilities get progressively worse as the size of the test increases). \begin{align} P(T_1 \geq 7) &= \sum_{k=7}^{10}\binom{10}{k}(0.5)^{k}(0.5)^{10-k} \\&\\ P(T_2 \geq 21) &= \sum_{k=21}^{30}\binom{30}{k}(0.5)^{k}(0.5)^{30-k} \\&\\ P(T_3 \geq 35) &= \sum_{k=35}^{50}\binom{50}{k}(0.5)^{k}(0.5)^{50-k} \end{align}

Will calculate in R.

Code:

Output:

> probT1
[1] 0.171875

> probT2
[1] 0.02138697

> probT3
[1] 0.003300224

Exercise 11

A restaurant offers apple and blueberry pies and stocks an equal number of each kind of pie. Each day ten customers request pie. They choose, with equal probabilities, one of the two kinds of pie. How many pieces of each kind of pie should the owner provide so that the probability is about .95 that each customer gets the pie of his or her own choice?

Answer
Start with 10 pies of one kind, and remove them one at a time until we pass the 0.95 mark. Calculating in R. As we see, if we remove 3 pies, there is a 95% that there won't be enough pies. So the restaurant should have 8 of each.

# Binomial Distribution
b <- function(n, p, k) {
    q = 1 - p
    prob = choose(n, k)*p**k*q**(n-k)
    return(prob)
}

1 - b(10, 0.5, 10)
1 - (b(10, 0.5, 10) + b(10, 0.5, 9))
1 - (b(10, 0.5, 10) + b(10, 0.5, 9) + b(10, 0.5, 8))

> 1 - b(10, 0.5, 10)
[1] 0.9990234
> 1 - (b(10, 0.5, 10) + b(10, 0.5, 9))
[1] 0.9892578
> 1 - (b(10, 0.5, 10) + b(10, 0.5, 9) + b(10, 0.5, 8))
[1] 0.9453125

Exercise 12

A poker hand is a set of 5 cards randomly chosen from a deck of 52 cards. Find the probability of a

(a) royal flush (ten, jack, queen, king, ace in a single suit).
(b) straight flush (five in a sequence in a single suit, but not a royal flush).
(c) four of a kind (four cards of the same face value).
(d) full house (one pair and one triple, each of the same face value).
(e) flush (five cards in a single suit but not a straight or royal flush).
(f) straight (five cards in a sequence, not all the same suit). (Note that in
straights, an ace counts high or low.)

Answer
In all cases the possible hands is binom(52, 5). We just have to count the number of ways each of the hands can be attained to find the probability. (A lot easier than directly calculating probabilities!)

(a)
There are only 4 ways of getting a royal flush. So the probability is 4/binom(52, 5) = 0.00000153907.

(b)
We can get a straight flush in all 4 suits. In each suit, we can get a straight from A to 5 up to and including 10 to A, so 10 straights, but the last type is a royal flush, which we disregard. So 9 straights in each suit for a total of 4·9 = 36 possibilities. The probability is 36/binom(52, 5) = 0.00001385169. (Exactly 9 times more likely than the royal flush).

(c)
As explained in the example, there are 13 ways of getting four of a kind, and for the last card there are 48 possible (all remaining cards). It can happen in 624 ways. The probability is 624/(binom(52, 5) = 0.000240096.

(d)
Also covered in the example. There are 13 ways of getting 3 of a kind, and out of those there are binom(4, 3) = 4 ways. For the remaining pair, there are 12 ways (one value has been discarded in the three of a kind), and binom(4, 2) = 6 ways of getting them, in total 13·4·12·6 = 3744 ways. The probability is 3744/binom(52, 5) = 0.001440576.

(e)
A flush can be attained for all 4 suits, and in each suit there are binom(13, 5) = 1287 ways to get the cards needed. For all four suits, we get 4·1287 = 5148, but this includes royal flush and straight flush, so we remove them and get 5108 total possibilities. The probability is: (5108)/binom(52, 5) = 0.001965402.

(f)
In this case we only care about consecutive cards and ignore suits. Counting low and high aces, we get 10 possible straights from A-5 up to 10-A. For 10 possible straights, each draw with 4 possible cards gives a total of 10·4·4·4·4·4 = 10240 possibilities. This includes royal flush and straight flush which we remove, and get 10200. The probability is 10200/binom(52, 5) = 0.003924647.

To verify results check here:
Wikipedia.

Exercise 13

If a set has 2n elements, show that it has more subsets with n elements than with any other number of elements.

Answer
The number of sets is determined by the binomial coefficient. $$ \binom{2n}{n} = \frac{(2n)!}{(2n - n)!n!} = \frac{(2n)!}{n!n!} $$ Recall that the binomial coefficient is symmetric, so we only have to verify that it gets smaller for n+1 and n-1. $$ \binom{2n}{n+1} = \frac{(2n)!}{(2n - (n+1))!(n+1)!} = \frac{(2n)!}{(n+1)!(n-1)!} $$ $$ \binom{2n}{n-1} = \frac{(2n)!}{(2n - (n-1))!(n-1)!} = \frac{(2n)!}{(n+1)!(n-1)!} $$ Note that both of these are equal. Now we show that both of these are smaller. We can start with either: \begin{align} \binom{2n}{n+1} &= \frac{(2n)!}{(n+1)!(n-1)!} \\&\\ &= \frac{(2n)(2n-1)\cdots(n+1)(n)(n-1)(n-2)\cdots(1)}{(n+1)(n)(n-1)\cdots(1)\times (n-1)(n-2)\cdots(1)} \\&\\ &= \frac{(2n)(2n-1)\cdots(n+1)(n)}{(n+1)(n)(n-1)\cdots(1)} \\&\\ &= \left(\frac{n}{n+1}\right)\frac{(2n)(2n-1)\cdots(n+1)}{(n)(n-1)\cdots(1)} \\&\\ &= \left(\frac{n}{n+1}\right)\frac{(2n)(2n-1)\cdots(n+1)}{(n)(n-1)\cdots(1)}\cdot\frac{n!}{n!} \\&\\ &= \left(\frac{n}{n+1}\right)\frac{(2n)!}{n!n!} \\&\\ &= \left(\frac{n}{n+1}\right)\binom{2n}{n} \\&\\ &< \binom{2n}{n} \end{align} since n/(n+1) < 1. Both sides are smaller, showing that binom(2n, n) is the largest value.

Exercise 14

Let b(2n, 0.5, n) be the probability that in 2n tosses of a fair coin exactly n heads turn up. Using Stirling’s formula (Theorem 3.3), show that $b(2n, 0.5, n) \sim 1/\sqrt{\pi n}$. Use a program to compare this with the exact value for n = 10 to 25.

Answer
Showing that the expressions are asymptotically equal. \begin{align} b(2n, 0.5, n) &= \binom{2n}{n}(0.5)^n(0.5)^{2n-n} \\&\\ &= \frac{(2n)!}{n!n!}\left(\frac{1}{2}\right)^{2n} \\&\\ &= \frac{(2n)!}{n!n!}\left(\frac{1}{2^{2n}}\right) \\&\\ &\sim \frac{(2n)^{2n}e^{-2n}\sqrt{4\pi n}}{(n^n e^{-n}\sqrt{2\pi n})(n^n e^{-n}\sqrt{2\pi n})}\left(\frac{1}{2^{2n}}\right) \\&\\ &= \frac{2^{2n}n^{2n}e^{-2n}2\sqrt{\pi n}}{n^{2n} e^{-2n}\cdot 2\pi n}\left(\frac{1}{2^{2n}}\right) \\&\\ &= \frac{\sqrt{\pi n}}{\pi n}\left(\frac{2^{2n}}{2^{2n}}\right) \\&\\ &= \frac{1}{\sqrt{\pi n}} \end{align}

Instead of all the values proposed, we will check programmatically for n=10, 25, 50. The approximations are very close.

Code:

Output:

> n = 10
> b(2*n, 0.5, n)
[1] 0.1761971
> 1/sqrt(pi*n)
[1] 0.1784124

> n = 25
> b(2*n, 0.5, n)
[1] 0.1122752
> 1/sqrt(pi*n)
[1] 0.1128379

> n = 50
> b(2*n, 0.5, n)
[1] 0.07958924
> 1/sqrt(pi*n)
[1] 0.07978846

Exercise 15

A baseball player, Smith, has a batting average of .300 and in a typical game comes to bat three times. Assume that Smith’s hits in a game can be considered to be a Bernoulli trials process with probability .3 for success. Find the probability that Smith gets 0, 1, 2, and 3 hits.

Answer
Binomial experiment with n=3, p=0.3. Calculating the probabilities in R.

Code:

Output:

> ##### Probability for hits
> b(n, p, 0)
[1] 0.343
> b(n, p, 1)
[1] 0.441
> b(n, p, 2)
[1] 0.189
> b(n, p, 3)
[1] 0.027

Exercise 16

The Siwash University football team plays eight games in a season, winning three, losing three, and ending two in a tie. Show that the number of ways that this can happen is: $$ \binom{8}{3}\binom{5}{3} = \frac{8!}{3!3!2!}. $$

Answer
They win 3 out of 8 games, which can be done in binom(8, 3) = 56 ways. Of the remaining 5 games they win 3 which can happen in binom(5, 3) = 10 ways, and finally the 2 draws can happen in binom(2, 2) = 1 way, so there are a total of 560 possible outcomes.

Deriving the equation: $$ \binom{8}{3}\binom{5}{3} = \frac{8!}{5!3!}\cdot\frac{5!}{3!2!} = \frac{8!}{3!3!2!}. $$

Exercise 17

Using the technique of Exercise 16, show that the number of ways that one can put n different objects into three boxes with a in the first, b in the second, and c in the third is n!/(a!b!c!).

Answer
Placing a objects in the first box can be done in binom(n, a) ways. Placing b in the second box can be done in binom(n-a, b) ways, and finally the c objects into the third box can be done in binom(n - a - b, c) ways. Expressing in factorials: \begin{align} \binom{n}{a}\binom{n-a}{b} \binom{n-a-b}{c} &= \frac{n!}{(n-a)!a!}\cdot\frac{(n-a)!}{(n-a-b)!b!}\cdot\frac{(n-a-b)!}{(n-a-b-c)!c!} \\&\\ &= \frac{n!}{a!}\cdot\frac{1}{b!}\cdot\frac{1}{0!c!} \\&\\ &= \frac{n!}{a!b!c!} \end{align}

Exercise 18

Baumgartner, Prosser, and Crowell are grading a calculus exam. There is a true-false question with ten parts. Baumgartner notices that one student has only two out of the ten correct and remarks, “The student was not even bright enough to have flipped a coin to determine his answers.” “Not so clear,” says Prosser. “With 340 students I bet that if they all flipped coins to determine their answers there would be at least one exam with two or fewer answers correct.” Crowell says, “I’m with Prosser. In fact, I bet that we should expect at least one exam in which no answer is correct if everyone is just guessing.” Who is right in all of this?

Answer
Finding the probabilities in R. For 2 or fewer points there should be several students who get 2 or fewer points when there are 340 students. Even for 1 or fewer there should be a few. A score of 0 is unlikely with 340 students. Prosser is correct.

Code:

Output:

> # Probability of 0, 1 or 2
> b(10, 0.5, 0) + b(10, 0.5, 1) + b(10, 0.5, 2)
[1] 0.0546875
> b(10, 0.5, 0) + b(10, 0.5, 1)
[1] 0.01074219
> b(10, 0.5, 0)
[1] 0.0009765625

Exercise 19

A gin hand consists of 10 cards from a deck of 52 cards. Find the probability that a gin hand has

(a) all 10 cards of the same suit.

(b) exactly 4 cards in one suit and 3 in two other suits.

(c) a 4, 3, 2, 1, distribution of suits.

Answer
The total combination of dealt cards is binom(52, 10) = 15820024220. Quite a few more possibilities than Poker. Now we just have to count the number of possibilities.

(a)
There are 4 suits, and for each suit we can get 10 cards in binom(13, 10) = 286 ways, 1144 ways in total.
The probability is 1144/15820024220 = 0.00000007231342.

(b)
For each suit, we draw 4 cards, so binom(13, 4) = 715. Next, for 2 of the remaining suits, i.e. binom(3, 2) = 3, we draw 3 cards: binom(13, 3) = 286 - which counts for BOTH suits. For all 4 suits, there are: 4·715·3·286·286 = 701809680 ways.
The probability becomes 701809680/15820024220 = 0.04436211.

(c)
For the first suit, there are binom(13, 4) = 715 possible draws. The next suit has binom(3, 1) = 3 possibilities, and there are binom(13, 3) = 286 possible draws. The third suit has binom(2, 1) = 2 possibilites, and there are binom(13, 2) = 78 possible draws. The last suit is determined automatically, and there are binom(13, 1) = 13 possible draws. All together, from 4 possible starting suits there are a total of: 4·715·3·286·2·78·13 = 4976468640 possible outcomes.
The probability becomes 4976468640/15820024220 = 0.3145677.

Exercise 20

A six-card hand is dealt from an ordinary deck of cards. Find the probability that:

(a) All six cards are hearts.

(b) There are three aces, two kings, and one queen.

(c) There are three cards of one suit and three of another suit.

Answer
The total number of possible combination of dealt cards is binom(52, 6) = 20358520. Now we simply count the possible outcomes.

(a)
How many ways can we draw 6 hears? binom(13, 6) = 1716.
The probability is 1716/20358520 = 0.00008428903.

(b)
We can select 3 out of 4 aces in binom(4, 3) = 4 ways. The kings in binom(4, 2) = 6 ways, and the single queen in 4 ways. A total of 4·6·4 = 96 ways.
The probability is 96/20358520 = 0.00000471547.

(c)
For each suit, we can select binom(13, 3) = 286. For the other suit, there are binom(3, 1) = 3 ways we can get it. And from that suit there are a total of binom(13, 3) = 286 possible hands. In total: 4·286·3·286 = 981552 possibilites.
The probability is 981552/20358520 = 0.04821333.

Exercise 21

A lady wishes to color her fingernails on one hand using at most two of the colors red, yellow, and blue. How many ways can she do this?

Answer
This is simply how many ways we can choose 2 from 3: binom(3, 2) = 3 ways. The fingers are irrelevant as the problem is stated.

Exercise 22

How many ways can six indistinguishable letters be put in three mail boxes? Hint: One representation of this is given by a sequence |LL|L|LLL| where the |’s represent the partitions for the boxes and the L’s the letters. Any possible way can be so described. Note that we need two bars at the ends and the remaining two bars and the six L’s can be put in any order.

Answer
Ignoring the borders and focusing on the inner portion, where we can place six Ls and two |s. If we only have two Ls and one |, there are three possible ways.

LL|
L|L
|LL

If we represent this as the set {a, b, c}, then if we select two values there are binom(3, 2) = 3 ways. {a, b}, {a, c} and {b, c}. This represents the case above - any missing values are replaced by a |.

With this reasoning, we can represent the |s as missing values and draw 6 from 8. So there are binom(8, 6) = 28 possible ways of putting the six letters into three boxes.

Exercise 23

Using the method for the hint in Exercise 22, show that r indistinguishable objects can be put in n boxes in $$ \binom{n + r - 1}{n - 1} = \binom{n + r - 1}{r} $$ different ways.

Answer
This is just a repetition of the reasoning with the set {a, b, c} in the previous exercise. Will not give a more formal argument than that.

Exercise 24

A travel bureau estimates that when 20 tourists go to a resort with ten hotels they distribute themselves as if the bureau were putting 20 indistinguishable objects into ten distinguishable boxes. Assuming this model is correct, find the probability that no hotel is left vacant when the first group of 20 tourists arrives.

Answer
Using the method from the previous exercises, we find the total number of ways that the customers can distribute themselves, which is applying the previous formula with n=20, r=10:
binom(20 + 10 - 1, 10) = binom(29, 10) = 20030010.

Two possible outcomes are displayed bellow.

§CCC|CC|CCC|CC|C|CC|C|CCC|C|CC§

§CCC|CCC||CC|CCC|CCC||CCC|C|CC§

In the first case, all hotels have some customers. In the second case, there are two vacant hotels which happens when two of the separators appear next to each other. The complement of the set we need is to count all outcomes where at least two of the separators are next to each other.

Listing all possible placements for how to divide the data, where the carets are all possible placements for the dividing box.

§C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C§

There are 19 possible placements for the divisors, and only 10 we have to place. So the number of possibilities where there are no empty hotels is given by binom(19, 10) = 92378.
The probability that this happens is: 92378/20030010 = 0.00461198.

Exercise 25

An elevator takes on six passengers and stops at ten floors. We can assign two different equiprobable measures for the ways that the passengers are discharged: (a) we consider the passengers to be distinguishable or (b) we consider them to be indistinguishable (see Exercise 23 for this case). For each case, calculate the probability that all the passengers get off at different floors.

Answer


(a)
The total number of ways they can exit: 10⁶ ways. The number of ways the passengers can exit is 10·9·8·7·6·5.
The probability becomes 10·9·8·7·6·5/10⁶ = 0.1512.

(b)
Using the method described above for indistinguishable objects, with n=10 and r=6, there are binom(19 + 6 - 1, 10) = binom(15, 6) = 5005 ways they can exit the elevator. To find how many ways they can exit, we simply count how many ways we can select 6 from 10: binom(10, 6) = 210.
The probability becomes 210/5005 = 0.04195804.

Exercise 26

You are playing heads or tails with Prosser but you suspect that his coin is unfair. Von Neumann suggested that you proceed as follows: Toss Prosser’s coin twice. If the outcome is HT call the result win. if it is TH call the result lose. If it is TT or HH ignore the outcome and toss Prosser’s coin twice again. Keep going until you get either an HT or a TH and call the result win or lose in a single play. Repeat this procedure for each play. Assume that Prosser’s coin turns up heads with probability p.

(a) Find the probability of HT, TH, HH, TT with two tosses of Prosser’s coin.

(b) Using part (a), show that the probability of a win on any one play is 1/2, no matter what p is.

Answer


(a)
Assume that the coin has p of becoming H, and q = 1-p of becoming T. The probability of HT becomes p(1-p) = p-p², the probability of TH is (1-p)p = p - p². The probability of HH is p² and TT is (1-p)².

(b)
Any double sequences are ignored, so we don't count them. Since HT and TH have the same probability, then they will occur at the same frequency, and will therefore each have a probability of 1/2 of happening.

Exercise 27

John claims that he has extrasensory powers and can tell which of two symbols is on a card turned face down (see Example 3.11). To test his ability he is asked to do this for a sequence of trials. Let the null hypothesis be that he is just guessing, so that the probability is 1/2 of his getting it right each time, and let the alternative hypothesis be that he can name the symbol correctly more than half the time. Devise a test with the property that the probability of a type 1 error is less than .05 and the probability of a type 2 error is less than .05 if John can name the symbol correctly 75 percent of the time.

Answer
This can be modeled as a binomial experiment. Defining the null-hypothesis and the alternative hypothesis.
We are going to find the critical value m so that we reject the null hypothesis if the number of correct guesses are higher than m. We calculate the probabilty of avoiding type 1 errors with the formula: $$ \alpha(p) = \sum_{m\leq k\leq n}b(n, p, k). $$ Using this we find that if we set n=100, we will require 68 successful tests in order to ensure less than 5% chance of both Type I and Type II errors. If we set n=1000 we require 773 successful tests.

There were no indications of what n should be, but apparently it should be as small as possible, which in this case is 42 (with 27 successes satisfying both error requirements).

Calculating the probabilities in R.

Code:

Output:

> n = 100
> alpha(n, p1, 68)
[1] 0.0002043886
> 1 - alpha(n, p2, 68)
[1] 0.04459633

> n = 1000
> alpha(n, p1, 727)
[1] 1.649466e-48
> 1 - alpha(n, p2, 727)
[1] 0.04409633

> n = 42
> alpha(n, p1, 27)
[1] 0.04421477
> 1 - alpha(n, p2, 27)
[1] 0.0416287

Exercise 28

Skipping - don't have code.

Exercise 29

A drug is assumed to be effective with an unknown probability p. To estimate p the drug is given to n patients. It is found to be effective for m patients. The method of maximum likelihood for estimating p states that we should choose the value for p that gives the highest probability of getting what we got on the experiment. Assuming that the experiment can be considered as a Bernoulli trials process with probability p for success, show that the maximum likelihood estimate for p is the proportion m/n of successes.

Answer
Let X~Bernoulli(p) for some unknown probability p. The maximum likelihood estimate gives us: \begin{align} L(p) &= P(X=s_1)P(X=s_2)\cdots P(X=s_n) \\&\\ &= p^m(1-p)^{n-m}. \end{align} The ML estimate is the p that makes this most likely. Differentiate this wrt. p and set equals to 0. $$ \frac{dL(p)}{dp} = mp^{m-1}(1-p)^{n-m} + p^m(n-m)(1-p)^{n-m-1}(-1) = 0 $$ \begin{align} mp^{m-1}(1-p)^{n-m} &= p^m(n-m)(1-p)^{n-m-1} \\&\\ m(1-p)^{n-m} &= p(n-m)(1-p)^{n-m-1} \\&\\ m(1-p) &= p(n-m) \\&\\ m-mp &= pn-mp \\&\\ m &= pn \\&\\ p &= \frac{m}{n}. \end{align}

Note: Why do they use MLE when it is not covered in the text??

Exercise 30

Skipping - don't have code.

Exercise 31

Each of the four engines on an airplane functions correctly on a given flight with probability .99, and the engines function independently of each other. Assume that the plane can make a safe landing if at least two of its engines are functioning correctly. What is the probability that the engines will allow for a safe landing?

Answer
This is a binomial experiment where the probability p of an engine failure is 0.01, and we want to calculate the probability that there have been a maximum of two engine failures, or, P(X ≤ 2) = P(X=0) + P(X=1) + P(X=2). From calculating in R, the probability is:
P(X ≤ 2) = 0.99999603.

Output:

> b(4, 0.01, 0) + b(4, 0.01, 1) + b(4, 0.01, 2)
[1] 0.99999603

Exercise 32

A small boy is lost coming down Mount Washington. The leader of the search team estimates that there is a probability p that he came down on the east side and a probability 1 − p that he came down on the west side. He has n people in his search team who will search independently and, if the boy is on the side being searched, each member will find the boy with probability u. Determine how he should divide the n people into two groups to search the two sides of the mountain so that he will have the highest probability of finding the boy. How does this depend on u?

Answer

Exercise 33

2n balls are chosen at random from a total of 2n red balls and 2n blue balls. Find a combinatorial expression for the probability that the chosen balls are equally divided in color. Use Stirling’s formula to estimate this probability.

Compare the exact value with Stirling’s approximation for n = 20.

Answer
First considering a simplified example where there are a total of 8 balls where 4 are red and 4 are blue. In this case there area total of binom(8, 4) = 70 ways of drawing 4 balls. There are binom(4, 2) = 6 ways of drawing red balls, and the same for drawing 6 blue balls. In total, there are binom(4,2)binom(4,2) = 36 ways of drawing 4 balls where 2 are blue and 2 are red.

The probability of this happening is 36/70 = 0.5142857 which can be confirmed with a simulation. Can easily verify a similar problem with 16 and 8 as can be seen in the code.

Let us call the event where there are an equal amount of red and blue balls for E. As shown, a combinatiorial expression for calculating this probability is: $$ P(E) = \frac{\binom{2n}{n}\binom{2n}{n}}{\binom{4n}{2n}} $$ Now we can use Stirling's formula (Theorem 3.3) to make an approximation. \begin{align} \frac{\binom{2n}{n}\binom{2n}{n}}{\binom{4n}{2n}} &= \left(\frac{(2n)!}{n!n!}\right)\left(\frac{(2n)!}{n!n!}\right)\bigg/\left(\frac{(4n)!}{(2n)!(2n)!}\right) \\&\\ &=\left(\frac{(2n)!}{n!n!}\right)\left(\frac{(2n)!}{n!n!}\right)\cdot\left(\frac{(2n)!(2n)!}{(4n)!}\right) \\&\\ &=\frac{[(2n)!]^4}{(4n)![(n)!]^4} \\&\\ &\sim \frac{[(2n)^{2n}e^{-2n}\sqrt{4\pi n}]^4}{((4n)^{4n}e^{-4n}\sqrt{8\pi n})[n^{n}e^{-n}\sqrt{2\pi n}]^4} \\&\\ &= \frac{2^{8n}n^{8n}e^{-8n}4^2\pi^2 n^2}{(4^{4n}n^{4n}e^{-4n}\sqrt{8\pi n})[n^{4n}e^{-4n}2^2\pi^2 n^2]} \\&\\ &= \frac{2^{8n}n^{8n}e^{-8n}2^4\pi^2 n^2}{(2^{8n}n^{4n}e^{-4n}\sqrt{2\pi n})[n^{4n}e^{-4n}2^3\pi^2 n^2]} \\&\\ &= \frac{2^{8n}n^{8n}e^{-8n}2^4\pi^2 n^2}{(2^{8n}n^{8n}e^{-8n}\sqrt{2\pi n})2^3\pi^2 n^2} \\&\\ &= \frac{2}{\sqrt{2\pi n}} \\&\\ &= \sqrt{\frac{2}{\pi n}} \end{align}

Comparing this approximation with exact results and simulated results show that it is quite accurate for n=20. It's actually not too bad for n=2, everything considered!

Code:

Output:

> ### Case 1: 8 total, 4 of each color, n=2
> mean(eq)
[1] 0.51523
> 36/70
[1] 0.51428571
> (factorial(4))**4/(factorial(8)*(factorial(2))**4)
[1] 0.51428571
> sqrt(2/(pi*n))
[1] 0.56418958

> ### Case 2: 16 total, 8 of each color, n=4
> mean(eq)
[1] 0.38003
> 4900/12870
[1] 0.38073038
> (factorial(2*n))**4/(factorial(4*n)*(factorial(n))**4)
[1] 0.38073038
> sqrt(2/(pi*n))
[1] 0.39894228

> ### Case 3: 80 total, 40 of each color, n=20
> mean(eq)
[1] 0.17607
> (choose(40, 20)*choose(40, 20))/choose(80, 40)
[1] 0.17674783
> (factorial(2*n))**4/(factorial(4*n)*(factorial(n))**4)
[1] 0.17674783
> sqrt(2/(pi*n))
[1] 0.17841241

Exercise 34-40

Skipped - combinatorics isn't THAT important.