Math 154: Probability Theory

Homework 2
Lawrence Tyler Rush
<me@tylerlogic.com>
March 2, 2011

1 Feller II.10 Problem 10
Problem Statement. At a parking lot there are twelve places arranged in a row. A man observed that there were eight cars parked, and that the four empty places were adjacent to each other (formed one run). Given that there are four empty places, is this arrangement surprising (indicative of non-randomness)?

Problem Solution. I initially solved this problem by simple counting; there are nine possible ways to have four empty spots adjacent to each other (0,1,…,8 to the left of the empty spaces) and (12) 4 ways to arrange the four empty parking spaces, leaving us with

9 (12)-= 0.018182 4

as our probability, and indicating that this parking arrangement is slightly surprising. However, I assume that the problem is desired to be solved through the use of runs analysis, and of course, I would also like to understand it tha way. As I have been experiencing in my study for this course, there seems to always be more than one way to get the answer to a problem and nice little conversions between the ways that further one’s understanding. Awesome.

Looking at it from the perspective of runs, we have, in the language of Feller, four a’s and eight b’s with which we will always have a run of four a’s and nothing else. The different possible sequences in which we can have a run of four a’s amongst the b’s is three in number, corresponding to the a’s being all the way to the left, all the way to the right, and neither of those. 1 The number of distributions that result in these three scenarios is given by the following, making use Feller’s formula in II.5 for non-empty cell distributions.

( ) ( ) ( )( ) ( ) ( ) 4 - 1 8 - 1 4- 1 8- 1 4- 1 8- 1 1 - 1 1 - 1 + 1- 1 2- 1 + 1- 1 1- 1 = 1 ⋅1 + 1⋅8+ 1 ⋅1 = 9

Thus we see, as above, our probability will again be 0.018182

2 Feller II.10 Problem 13
Problem Statement. A Cornell professor got a ticket twelve times for illegal overnight parking. All twelve tickets were given either Tuesdays or Thursdays. Find the probability of this event. (Was his renting a garage only for Tuesdays and Thursdays justified?)

Solution. Assuming that we are not concerned with the distribution of the twelve tickets across the weekday on an individual basis, then we can examine the situation according to the counts of the tickets as they fall on the various days of the week. Thus we use what we learned from the discussion on ocupancy problems of II section five.

We think of the r = 12 tickets as the balls being placed in the n = 7 bins. As such, we have that the number of combinations are as follows (and I love Feller’s proof of this for the beauty of its simplicity, boiling it down to a simple arrangement of pipes and asterisks).

(n - 1+ r) (7- 1 + 12) r = 12 = 18564

Furthermore, since we don’t care to distinguish between the individual tickets, then we need to count the number of possible different distributions of the twelve tickets falling on only Tuesday and Thursday. The numbers are so small they can just straight-up be counted (my initial approach), but we can also recognize that this is just another case of the number of distributions of r balls among n bins, i.e. r = 12 tickets among n = 2 days. That is, there are

( ) ( ) ( ) 2- 1+ 12 13 13 12 = 12 = 1 = 13

ways to receive the tickets as specified, and thus a

--13- = 0.00070028 18564

probability of this situation happening to the professor.

Asking whether the professor’s renting a garage on the Tuesday and Thursdays is a little subjective, being dependent on how much the professor values his money and/or time (among other things, although there two seem most likely to me). It could simply cost less to just get the tickets than to always rent a garage, or similarly, the professor’s time could be so valuable that a closer, more financially costly, parking space could be worth the time gain that a cheaper farther away parking garage. It all depends on multiple (not specified here) variables.

3 Feller II.10 Problem 19
Problem Statement. Show that it is more probable to get at least one ace with four dice than at least one double ace with twenty-four throws of two dice each.

Solution. The probability of getting at least one ace when rolling four dice is simply one minus the probability of getting no ace at all. That is,

4 1 - 54 = 0.51775 6

since there are 54 ways to not roll any ones and 64 possible different outcomes.

Similarly, the probability of getting at least one snake-eyes in twenty-four rolls of two dice is one minus the probability of never getting a snake-eyes in twenty-four rolls of two dice. That is,

( 35)24 1- 36 = 0.49140

since one roll of two dice results in snake-eyes thrity-five out of thrity-six times and we do that twenty-four times (thus we raising to the twenty-fourth).

4 Feller II.10 Problem 31
Problem Statement. What is the probability that the bridge hands of North and South together contain exactly k aces, where k = 0,1,2,3,4.

Solution. Here again, as in the second problem, we are evaluating distributions. Hopefully being less winded: The total number of distribution of aces among the four players is for r = 4 (balls,aces) and n = 4 (bins,players) which results in

( ) ( ) 4 - 1+ 4 = 7 = 35 4 4

combinations. Thus for k aces being distributed among the North and South players together, we have that

1 (2 - 1+ k)(2 - 1+ (4- k)) 1(k + 1) (5- k) (5 - k )(k+ 1) -- = -- = ------------ 35 k 4- k 35 k 4- k 35

is the probability such a distribution occurs, where the binomial (2- 1+k) k is the number of distributions with k aces between North and South and (2-1+(4-k)) 4-k is the number of distributions with the 4 - k remaining aces between East and West. Thus for k = 0,1,2,3,4 we have the probabilities 5 35, 8 35, 9 35, 8 35, and 5 35, respectively. Supporting our argument is the fact that the previous probabilities sum to one.

5 Feller II.10 Problem 38
Problem Statement. Misprints. Each page of a book contains N symbols, possibly misprints. The book contains n = 500 pages and r = 50 misprints. Show that (a) the probability that pages number 1,2,…,n contain, respectively, r1,r2,…,rn misprints equals
( ) ( ) ( ) ∕ ( ) N N ⋅⋅⋅ N nN r1 r2 rn r

(b) for large N this probability may be approximated by (5.3). Conclude that the r misprints are distributed in the n pages approximately in accordance with a random distribution of r balls in n cells.

Problem Solution.

 
A:

I’m unsure if there is another angle to use in getting this answer, some other type of analysis desired by Feller, but I’m just going to count.

For the ith page, i ∈{1,2,⋅⋅⋅,n} there are N characters from which to “choose” to be misprints. Hence

(N ) r i

possible combinations of misprints. Thus over the n pages there are

( ) ( ) ( ) N N N r1 r2 ⋅⋅⋅ rn

different misprints resulting in the occupancy numbers r1,r2,⋅⋅⋅,rn. Since we know that there are a total of r = r1 + r2 + ⋅⋅⋅ + rn misprints over the n pages, each with N characters, this yields a total of

( ) nN r

possible combinations of misprints. Hence we see that the occupany numbers of r1,r2,…,rn can arise with probability

(N )(N ) (N ) ∕ (nN ) r r ⋅⋅⋅ r r . 1 2 n

 
B:

Since the following limit approaches one, then Feller’s 5.3 formula approimates the above formula as N becomes large.
( )( ) ( ) n -Nr1--Nr2-⋅⋅⋅-Nrn-r1!r2!⋅⋅⋅rn!nr -r1!(N--r1)N!⋅!⋅⋅rn!(N--rn)!r1!r2!⋅⋅⋅rn!nr Nli→m∞ (nN) r! = --(nN)!- r! r r!(nnN -r)! -(N--r1)N!⋅!⋅⋅(N--rn)! = -(nN)! (nN-r)! = ------N-!n(nN----r)!------ (N - r1)!⋅⋅⋅(N - rn)!(nN )! N-!n(nN-)! ≈ N !n(nN )! ≈ 1
Note the dropping off of r’s in the terms above since their subtraction is negligible when N is large.

6 Feller II.11 Problem 1
Problem Statement. A population of n elements contains np red ones and nq black ones (p + q = 1). A random sample of size r is taken with replacement. Show that the probability of its including k red elements is
(r) k pkqr-k

Problem Solution. We first note that, since we are replacing with each pick, the probability of choosing a red element each time is np∕n = p and similarly for black elements, nq∕n = q. Hence for a given sequence of r elements, the probability of choosing such a sequence is the probability of choosing the first times the probability of choosing the second times... etc. However, because of the commutivity of multiplication, we can simply count the number of red elements that were chosen, k, and the number of black elements, r -k and multiply that many p’s times that many q’s. Thus ALL sequences of choices that have the same number of red elements is a possible result with the same probability, namely pkqr-k for k red elements. Finally, multiplying this probability by the number of ways to choose the k red elements of the r choosen gives us

(r) k r-k k pq

and the answer for which we were looking.

7 Feller II.11 Problem 5
Problem Statement. The probability pk that a given cell contains exactly k balls is given by the binomial distribution (4.5). Prove that the most probable number is the integer v such that (r - n + 1)∕n < v ≤ (r + 1)∕n.

Problem Solution. From 4.5 of Feller chapter two, we get the following form of the binomial formula.

( ) ( ) ( )r-k pk = r -1r (n - 1)r-k = r 1k- 1- -1 k n k n n

Thus we can attempt to maximize this equation in order to find k that yields the greatest probability. Our normal approach here would be to simply take the derivative, and we’re off to the plug-and-chug races, however, we’re in discrete world here. Hence we use a finite difference approximation to the derivative to find the maximum value, looking for where the slope of the difference is near zero. We take our difference magnitude here to be one since we are dealing with integers. Great! That makes it easier on us. So for the backward approximation we have

(kr-1)n-r(n- 1)r-k+1 + (rk)n-r(n- 1)r-k -------------------1----------------- = 0 (( r ) (r) ) n-r(n- 1)r- k (n - 1)- = 0 k- 1 k
at which point we can see that only that which is in the parenthesis can possibly be zero, yielding to us the following slew of equations.
( r ) (r) k- 1 (n - 1)- k = 0 ( ) ( ) r (n- 1) = r k - 1 k -------r!-------(n- 1) = ----r!--- (k - 1)!(r- k +1)! k!(r- k)! --n--1-- 1- r- k + 1 = k kn - k = r- k + 1 r-+-1 k = n
Since this is the backwards difference approximation (using x-h) then the slope will be possitive at this point, and thus we have
k < r+-1- n

In a similar manner the forward difference approximation results in the following equation

( ) ( ) r -r r-k-1 r -r r-k k + 1 n (n- 1) - k n (n- 1) = 0 (( r ) (r) ) n-r(n- 1)r- k-1 - (n - 1) = 0 k+ 1 k
in which we again see that only the term in the parenthesis can possibly be zero. Hence we obtain the following for k.
( r ) (r ) k + 1 - k (n - 1) = 0 ( r ) (r) = (n - 1) k+ 1 k -------r!------- = r!(n---1) (k+ 1)!(r - k - 1)! k!(r- k)! -1--- n--1- k+ 1 = r- k r- k = kn- k +n - 1 r--n-+1- k = n
Since this is the forward approximation we have that
k > r---n+-1 n

which of course, along with the previous result of the backward approximation, we get our nice result of the maximum of pk result for k such that 2

r - n + 1 r + 1 ---n---- < k <--n--

8 Feller II.11 Problem 6
Problem Statement. Let n →∞ and r →∞ so that the average number, λ = r∕n, of balls per cell remains constant. Prove that
pk → e-λλk∕k!

Problem Solution. With Feller’s equation 4.5 in hand we evaluate what happens to

(r ) 1 ( ) k nk- 1- 1∕n)r-k

as both n and r approach infinity, but “at the same speed”, i.e. λ = r∕n is constant as mentioned in the problem. Expanding the above expression, we get the more clunky form of

(r)k-(1---1∕n)r- k!nk (1- 1∕n)k.

Here we can see that an expansion of (r)k∕nk will result in

r(r- 1)⋅⋅⋅(r- k+ 1)∕nk = (r∕n)k + ⋅⋅⋅

the trailing terms of which we don’t really care about as they will of powers of r less than k being divided by nk, i.e. they “disappear”. Hence our form has dwindled to the following.

k r λ-(1--1∕n)- k!(1- 1∕n)k

At this point we can nix the right-most term of the denominator since it will be one, which results in

λk k!(1- 1∕n)r

Now with a little trickery and mathemagic, we can simplify this term further. Knowing that

( )n lim 1- -1 = 1∕e n→ ∞ n

we can morph (1 - 1∕n)r into

(( )n )r∕n 1 - 1- = e-λ n

leaving us with our final form of the initial term,

k -λ λ-e--- k!

9 Feller II.12 Problem 21
Problem Statement. Prove that for any positive integers a and b
(a + 1)⋅⋅⋅(a+ n ) b! a-b (b+-1)⋅⋅⋅(b+-n)-~ a!n .

Problem Solution. We can expand the numerator and denomenators to result in the following since they are a common result of diving some factorial of a number by the factorial of a lesser number, neglecting the reverse-ordering-trick with which Feller tried to “git us”.

(a+-1)⋅⋅⋅(a-+-n) (a-+-n)!b! -b!(a-+n-)! (b+ 1)⋅⋅⋅(b + n) = a!(b+ n)! = a!(b+ n )!

At this point, the direction of our simplification depends on the relative values of a and b. If a < b then we have this (minus the a!) b - a-factored-numerator term

b!-------------1------------- a!(b+ n)(b + n- 1)⋅⋅⋅(a + n+ 1)
(9.1)

or if b < a then our result is this term with, not counting the b!, a - b factors in the numerator

b!(a-+-n)(a-+-n--1)⋅⋅⋅(b-+-n+-1). a! 1
(9.2)

Thus equation 9.1 contains a product in the numerator that is always greater than or equal to na-b and equation 9.2 contains a product in its denominator which is always greater than or equal to nb-a. Hence we are given the following inequalities.

b!-------------1------------- b!--1-- b! b! a- b a!(b + n)(b+ n - 1)⋅⋅⋅(a +n + 1) ≤ a!nb- a and a!(a+ n)(a+ n- 1)⋅⋅⋅(b+ n+ 1) ≥ a!n

which of course gives us that

(a-+-1)⋅⋅⋅(a+-n-) b! a-b (b+ 1)⋅⋅⋅(b+ n) ~ a!n .

with its degree of similarity only being governed by the magnitude of the difference between a and b.

References

[1]   Feller, William. “An Introduction to Probability Theory and Its Applications” Volume I 3rd. Ed. John Wiley and Sons, Inc: 1968.

[2]   Some help with discrete approximations:
http://numericalmethods.eng.usf.edu/mws/gen/02dif/mws_gen_dif_txt_discrete.doc