Math 154: Probability Theory

Homework 1

Lawrence Tyler Rush

<me@tylerlogic.com>

February 24, 2011

1 Feller I.8 Problem 4

Problem Statement. A coin is tossed until for the first time the same result appears in succession. To every possible outcome requiring n tosses, attribute the probability 1∕2^n-1. Describe the sample space. Find the probability of the following events: (a) the experiment ends before the sixth toss, (b) an even number of tosses is required.

Sample Space Description. The sample space, as described for a similar problem by Feller [1, pg 18], is the union of these strings

HH	HTT	HTHH	HTHTT	…
TT	THH	THTT	THTHH	…

and the following “never have two in a row” possibilities.

HTHTHTHTHT... THTHTHTHTH...

This space is of course countably infinite as we can (again in the fashion of Feller) order the sample points like this,

HTHTHTHTHT..., THTHTHTHTH..., HH, TT, HTT, THH, HTHH, THTT, ...

which is akin to mapping 1 and 2 to the two infinite sequences and then continuing the mapping in a zig-zag pattern across the finite sequences listed above.

Part (a) solution. The probability that the experiment ends prior to the sixth toss is the probability of the event corresponding to the union any of the events described by, pardon the regular expression, “the experiemnt ends on the (second—third—fourth—fifth)”. Hence because none of the events in such a union can occur at the same time, we simply add their respective probabilities, yielding to use that the experiment ends before the sixth toss with probability

5 ∑ --1- = 1∕2+ 1∕4+ 1∕8+ 1∕16 = 15∕16. i=22n-1

Part (b) solution. The probability that the experiment ends on an even number of tosses is just the sum of all the probabilities for every “ending on an even number of tosses”,

∞∑ 1 -2i-1- i=1 2

Now I’m not really great at seeing infinite series and knowing the total, but I was able to spot that the probabilities of the events “ending on odd” and the ones “ending on even” are going to be disjoint, which in turn lead me to the following form of the probability of the event that “an odd number of tosses are required“.

∑∞ ∑∞ (∑∞ ) ---1----= -1-= 1∕2 --1-- i=1 2(2i+1)-1 i=122i i=122i-1

Hence we know that P(Odd) = 1∕2P(Even), which indicates, since these two events partition the sample space, that the probability that an even number of tosses is required is 2∕3.

2 Feller I.8 Problem 15

Problem Statement. Find simple expressions for (a) (A ∪ B)(A ∪ B′), (b) (A ∪ B)(A′∪ B)(A ∪ B′), and (A ∪ B)(B ∪ C).

Taking S to be the entire space, we have the following.

(A ∪ B)(A∪ B ′) = (A ∪ B)A ∪(A ∪ B)B′ ′ ′ = AA ∪BA ∪AB ∪ BB = A ∪ BA ∪ AB ′ ∪ ∅ = A ∪ BA ∪ AB ′ = A (S ∪ B ∪B ′) = AS = A

′ ′ ′ ′ ′ ′ (A ∪B )(A ∪ B)(A∪ B ) = (A ∪ B)(A A∪ A B ∪BA ∪BB ) = (A ∪ B)(A′B′ ∪ BA ) = AA ′B′ ∪ ABA ∪BA ′B′ ∪ BBA = AA ′B′ ∪ AB ∪ BA ′B ′ ∪ BA ′ ′ ′ = AA B ∪ AB ∪ BAB = AB

And again with S.

(A ∪B )(B ∪ C) = AB ∪ AC ∪ BB ∪ BC = AB ∪ AC ∪ B ∪BC = B(A ∪S ∪ C)∪ AC = BS ∪AC = B ∪ AC

3 Feller II.10 Problem 1

Problem. How many different sets of initials are there if everybody has one surname and (a) exactly two given names, (b) at most two given names, (c) at most three given names.

Having exactly two given names and one surname makes three name each with twenty-six possible starting letters, resulting in

263 = 17576

possible initial combinations.

With one surname and “at most” two given names, i.e. either zero, one, or two, a person can possibly have one, two, or three initials. That is there are

3 2 26 + 26 + 26 = 18278

initial combinations.

When there are at most three given names and one surname, we simply follow suit of the previous solution and find our answer to be

264 + 263 + 262 + 26 = 475254

possible combinations of initials.

4 Feller II.10 Problem 3

Problem Statement. Each domino piece is marked by two numbers. The peices are symmetrical so that the number-pair is not ordered. How many different pieces can be made using the numbers 1,2,…,n?

Solution. Since there is no order to the dominoes, then we shall count possible sets of the numbers 1,2,…,n. Sets of size two would correspond to a domino with two distinct numbers and a set of size one would correspond to a domino with two of the same numbers. Hence the total number of possible dominos are the total number of sets of size two and of size one. Hence the total number of dominos is

(n ) (n) n(n + 1) + = -------- 2 1 2

5 Feller II.10 Problem 4

Problem Statement. The numbers 1,2,…,n are arranged in random order. Find the probability that the digits (a) 1 and 2, (b) 1, 2, and 3, appear as neighbors in the order named.

The digits 1 and 2 can be arranged in order, as neighbors in n - 1 ways, corresponding 1 and 2 being at the first and second position, the second and third, the third and fourth, and so on, respectively. These are the only ways that 1 can be a neighbor of 2 in order, and for each of these ways, there are (n - 2)! orderings of the remaining elements. Hence

(n- 1)(n - 2)! = (n - 1)!

are the number of ways that 1 and 2 apper in order as neighbors.

Similarly to 1 and 2, there are n - 2 positions for 1, 2, and 3 to be in order as neighbors, and for each of these, the other numbers can be arranged in (n - 3)! ways. Thus the total number of ways are the following.

(n- 2)(n - 3)! = (n - 2)!

6 Feller II.10 Problem 5

Problem Statement. A throws six dice and wins if he scores at least one ace. B throws twelve dice and wins if he scores at least two aces. Who has the greater probability to win.

Solution. To say that A wins if he scores at least one ace is to say that he does not win if no aces appear. So assuming that an ace is a one (or really just any single side of the die) then A will win with probability

56 1 - -6 = 0.66510 6

since there are 5⁶ possible ways to roll and not score no aces.

To say that B wins if he scores at least two aces, is to say that he loses if no aces appear or only a single ace appears. The number of these cases for a twelve-die roll are 5¹² and (121) 5¹¹, respectively. Thus the probability that B wins is given by the following.

( ) 512 +-112511 1- 612 = 0.61867

Therefore we have that A has the better chance of winning out of the two.

7 Feller II.10 Problem 9

Problem Statement. If n balls are placed into n cells at random, find the probability that exactly one cell remains empty.

Solution. Assuming that the balls are inditinguishable, then the total number of possible outcomes is (5.2) from Feller,

( ) n+ r- 1 r

or in our case,

( ) 2n- 1 n

Since we are counting the number of results with one and only one empty cell, then each cell can possibly be empty, i.e. n ways, and for each of those empty cells, there are n- 1 ways that the cell containing two balls can be arranged, since such a cell must exist when one and only one cell is empty. Hence we have that the probability that there will be one and only one cell left empty is

n(n- 1) -(2n--1)-- n

which to give some perspective, is 2/3, 0.6, 0.34286, and 0.15873 for two, three, four, and five, respectively.

8 Feller II.12 Problem 1

Problem Statement. Prove that for integrals n ≥ 2,

(n ) (n ) 1- 1 + 2 - + ⋅⋅⋅ = 0 ( ) ( ) ( ) n + 2 n + 3 n + ⋅⋅⋅ = n2n-1 ( 1) ( )2 ( )3 n n n 1 - 2 2 + 3 3 - + ⋅⋅⋅ = 0,and (n ) (n) (n ) 2⋅1 2 +3 ⋅2 3 + 4⋅3 4 + ⋅⋅⋅ = n(n- 1)2n-2

This is simply the binomial expansion of (1 - 1)ⁿ, which of course is zero. That is

∑n (n) ∑n (n ) (n ) (n) (1 - 1)n = (1)n-i(- 1)i = (- 1)i = 1- + - + ⋅⋅⋅ = 0 i=0 i i=0 i 1 2

The below uses, in part, the property n (n-1)
i

= (n - 1)

which is proved in the appendix.

n∑- 1(n - 1) n2n-1 = n i=0 i n∑-1 (n - 1) = n i i=0 n∑-1 (n) = (n- 1) i i=0 ( ) n∑-1 n = (n- 1) n - 1 i=n0 ( ) = ∑ i n i=1 i (n ) ( n ) (n ) = n + (n - 1) + ⋅⋅⋅+ ( n) ( ) (n-)1 1 = n + 2 n +3 n + ⋅⋅⋅ 1 2 3

By the above solution, we can attain the following, revealing how we can find our answer.

n-1 n n∑-1(n - 1) n- 1-i i n2 = n(1+ 1) - 1 = n i 1 1 i=0

Hence if we just stick in a negative one in place of the one on the right side, we arrive at

n∑-1(n - 1) (n ) (n ) (n ) 0 = n(1- 1)n - 1 = n i 1n-1-i(- 1)i = 1 - 2 2 + 3 3 - + ⋅⋅⋅ i=0

yielding to us the answer for which we are looking.

We can proceed much like we did in the second part of this problem, making use of the property, (n- 1) (n- 2)
i

= (n- 1 -i) (n-1)
i

, proved in the appendix, along with the similar property of n (n- 1)
i

= (n - i)

, as we used before. Hence we have the following.

n∑-2(n - 2) n(n - 1)2n-2 = n(n - 1) i=0 i n∑-2 (n - 2) = n(n - 1) i i=0 n∑-2 (n - 1) = n(n - 1- i) i i=0 ( ) n∑-2 n- 1 = (n - 1 - i)n i i=0 ( ) n∑-2 n = (n - 1 - i)(n- i) i ni=-02 ( ) = ∑ (n - i)(n- 1- i) n i=0 n - i ( ) ( ) ( ) = n(n - 1) n + (n - 1)(n - 2) n + ⋅⋅⋅+ 2⋅1 n ( ) n ( ) ( ) n- 1 2 = 2 ⋅1 n + 3⋅2 n +4 ⋅3 n + ⋅⋅⋅ 2 3 4

Naive Problem Solver’s Lament. It seems like there could some sort of awesome high level understanding that could be used in a much better way here to manifest a proof. I wish I knew what that was and could describe the progression that one can begin to see happening above in a “neat”, “different” way that reveals a great understanding of what is actually happening here, right in front of our eyes.

9 Feller II.12 Problem 6

Problem Statement. For arbitrary a and n ≥ 0, prove that

∑n ( ) ( ) (- 1)v a = (- 1)n a- 1 v=0 v n

Solution. Using the formula in (8.6) we have that the left hand side of the above equation is equal to

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) a - a + a - ⋅⋅⋅ = a - a- 1 - a- 1 + a - 1 + a- 1 - ⋅⋅⋅ 0 1 2 0 0 1 1 2

in which there are n + 1 terms on the left-hand side and 2n + 1 terms on the right. All the terms on the right-hand side now (obviously) cancel save for (a0) , (a-01) , and ± (a-n1) , of which the first two are the same since there is only one way to choose a set of zero, leaving us with