Coin Tosses, Dealing Cards...Date: 12/08/98 at 13:15:58 From: Greg Subject: Discrete Math (Probability and Combination) 1) A fair coin is tossed 4 times. What is the probability that at least 2 heads will occur, given that at least 1 of the first 2 tosses is a head? What is the probability that at least 2 heads will occur given that at least one head occurs? Do the results agree with your intuition? 2) 5 cards are dealt from a perfectly shuffled deck. What is the probability of being dealt exactly 2 aces, given that you were dealt the ace of spades? What is the probability of being dealt exactly 2 aces, given that you were dealt at least 1 ace? Do the results agree with your intuition? 3) A fair coin is tossed until the number of heads and the number of tails differ by 2. What is E, the expected number of tosses? (Hint: Imagine that N of your friends play this game simultaneously. Count the total number of tosses. By the definition of E, this total should be approximately N*E. Further, after 2 tosses some of your friends have completed their experiment because they got either 2 heads or 2 tails. Some of your friends got TH or HT and, for these friends, the experiment is beginning again; i.e., each of these friends should get approximately E more tosses.) 4) The experiment consists of tossing a fair coin 1000 times. What is the expected number of times that a head will be immediately followed by a tail? Does the result agree with your intuition? (Hint: The ith toss is a winner provided that the (i-1)th toss was a head and the ith toss is a tail. What is the expected number of winners on the ith toss?) Final Hint: (3) and (4) require almost no calculation. Date: 12/08/98 at 17:00:28 From: Doctor Anthony Subject: Re: Discrete Math Hi Greg - (1) The problem asks what is the probability of getting at least two heads in four coin flips, given that at least one of the first two flips is heads. We must calculate Prob(at least 1 head in first 2 flips and at least 2 heads in 4 flips) ---------------------------------------------------------------------- Prob(at least 1 head in first 2 flips) The probability of at least 1 head in first 2 flips = 1 - Pr(no heads in first 2 flips) = 1 - (1/2)(1/2) = 3/4 (This is the denominator of above expression) We now find the numerator of the expression quoted above. Prob at least 2 H's in 4 throws P(2) = C(4,2) x (1/2)^2 x (1/2)^2 = C(4,2) x (1/2)^4 P(3) = = C(4,3) x (1/2)^4 P(4) = = C(4,4) x (1/2)^4 -------------------- Total = 11 x (1/2)^4 From this we subtract the probability of the one excluded case, namely, 2 T's in the first two throws with the 2 H's in the second 2 throws. Prob = (1/2)^4 So the required probability = 11/16 - 1/16 = 10/16 And so the final required probability 10/16 = ------- 3/4 = 5/6 This agrees with intuition, because the given of at least 1 H in the first two has a lower probability than at least 1 in 4 tosses. So in the former case, we are given something that has a lower probability and this imposes a greater restriction. (2) Given that you have the ace of spades you must select 1 ace from 3 and 3 non-aces from 48 other cards. C(3,1) x C(48,3) 3 x 17296 Prob = ---------------- = ----------- = 0.207635 C(51,4) 249900 The probability of getting at least 1 ace = 1 - Prob(no ace) C(48,5) Prob. no ace = -------- = 0.658842 C(52,5) So the probability of at least 1 ace = 0.341158 C(4,2) x C(48,3) Prob(2 aces) = ----------------- = 0.0399298 C(52,5) So the required probability = 0.0399298/0.341158 = 0.117042 (3) Let E be the expected number of tosses. You toss at least twice but there is a probability of 1/2 (if you get TH or HT) that you will return to the initial position. So we have E = 2 + (1/2)E (1/2)E = 2 E = 4 Answer to the 4th question: Let a be expected number of tosses to get a sequence HT just after H. Let b be expected number of tosses to get HT just after T. E = 1 + (1/2)a + (1/2)b a = 1 + (1/2)a (1/2)a = 1 so a = 2 b = 1 + (1/2)a + (1/2)b b = 1 + 1 + (1/2)b (1/2)b = 2 and b = 4 So E = 1 + 1 + 2 = 4 And in 1000 tosses we expect to get 1000/4 = 250 cases with the sequence HT. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 02/13/99 at 17:10:43 From: Greg Beck Subject: Discrete Math (Probability and Combination) 1) There are 2 kinds of particles inside a nuclear reactor. After each second, an A-particle will split into 3 b-particles and a b-particle will split into an a-particle and 2 b-particles. How many particles of each kind are inside the reactor after n seconds? (Initially there are 2-a particles and 3 b-particles.) Deduce a recurrence relation (you are not required to solve the recurrence relation). 2) How many strings of length n, consisting only of a, b, c, have an even number of a's? Deduce but you need not solve a recurrence relation. 3) How many subsets of {1,2...,n} do not contain two consective integers? Deduce but do not solve a recurrence relation. 4) In how many ways can a set of size n be written as the union of non-empty disjoint sets? Suppose when n = 3, there are 5 ways: {1} {2} {3}, {1 2}{3}, {2 3}{1}, {1 2}{3}, and {1 2 3}. Deduce but do not solve a recurrence relation. Date: 02/26/99 at 10:43:17 From: greg beck Subject: Discrete Math (Probability and Combination) (1) Solve : a(n) + 3*a(n-1) + 2*a(n-2) = 10 (n >= 2) a(0) = 2 a(1) = 1 (2) Solve : a(n) = 2*a(n-1) + 8*a(n-2) + 3*n (n >= 2) a(0) = 1 a(1) = 4 (3) Solve : n a(n) = a(n-2) + 2 (n >= 2) a(0) = 1 a(1) = 3 (4) Solve : a(n) = -a(n-1) + 2*a(n-2) + 1 (for n >= 2) a(0) = 0 a(1) = 1 Date: 02/27/99 at 07:33:32 From: Doctor Anthony Subject: Re: Discrete Math (Probability and Combination) You have a transition matrix as shown: (1) FROM a b TO a [ 0 1] b [ 3 2] If you multiply this out a couple of times or use the eigen values technique for getting the power of a matrix, this tends to the value 3^n[1/4 1/4] [3/4 3/4] If you start with a = 2, b = 3 then the number of either sort after n generations is 3^n[1/4 1/4]*[2] = 3^n[ 5/4] = 5*3^n[1/4] [3/4 3/4] [3] [15/4] [3/4] (2) If f(n) is the number of strings with an even number of a's for strings of length n, then for example: Strings Number -------- -------- f(2) = aa 1 f(3) = aab, aac 2 f(4) = aabb, aacc, aabc, aaaa 4 f(5) = aabbb, aabbc, aaccb, 6 aaccc, aaaab, aaaac f(6) = aabbbb, aabbbc, aabbcc, 9 aabccc, aacccc, aaaabb, aaaabc, aaaacc, aaaaaa If one examines the pattern, we can see that the number of strings with two a's goes up by 1 as n increases by 1, and the number of strings with 4 a's goes up by 1 as n increases by 1. Similarly, the number of strings with 6 a's goes up by 1 as n increases by 1. In going from f(4) to f(5), we have 3 strings with 2 a's going up to 4 strings with 2 a's, and 1 string with 4 a's that goes up to 2 strings with 4 a's. So, the increase from f(4) to f(5) equals the number of even numbers that are less than 5. That is two numbers 2 and 4, and we get f(5) = f(4) + 2 In going from f(5) to f(6) there is an increase of 1 in number of strings with 2 a's, 4 a's and of course 6 a's. So the total increase is the number of even numbers less than or equal to 6. There are 3 such numbers 2, 4 and 6 and so f(6) = f(5) + 3 The general recurrence formula for this pattern is f(n) = f(n-1) + Integer value of (n/2) Try the rest using the concepts I have applied above. I will look at the others when time permits. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 02/27/99 at 10:40:21 From: Doctor Anthony Subject: Re: Discrete Math (Probability and Combination) (1) The difference equation is u(n+2) + 3u(n+1) + 2 u(n) = 10 We let u(n) = v(n) + w(n) where v(n+2) + 3v(n+1) + 2v(n) = 0 This corresponds to the 'complementary' function in normal differential equations. The solution is given by solving x^2 + 3x + 2 = 0 (x+1)(x+2) = 0 x = -1 and x = -2 So the C.F. is v(n) = A(-1)^n + B(-2)^n For w(n) we use a trial solution w(n) = p.n + q, where p and q are constants, and substituting into w(n+2) + 3w(n+1) + 2w(n) = 10 p(n+2)+q + 3p(n+1)+3q + 2p.n+2q = 10 n(p+3p+2p) + 2p+3p + 6q = 10 6p.n + 5p + 6q = 10 and so 6p = 0, p = 0, 6q = 10, q = 10/6 = 5/3 and the solution is w(n) = 5/3 The general solution is u(n) = A(-1)^n + B(-2)^n + 5/3 u(0) = 2 so 2 = A + B + 5/3 A + B = 1/3 u(1) = 1 so 1 = -A - 2B + 5/3 A + 2B = 2/3 ---------------- Subtracting B = 1/3 and so A = 0 Therefore the solution is u(n) = (1/3)(-2)^n + 5/3 (2) u(n+2) - 2u(n+1) - 8u(n) = 3^n Solve x^2 - 2x - 8 = 0 (x-4)(x+2) = 0 x = 4 or -2 v(n) = A(-2)^n + B.4^n Use a trial solution of the form w(n) = p.3^n + q Substitute into w(n+2) - 2w(n+1) - 8w(n) = 3^n p.3^(n+2) + q - 2p.3^(n+1) - 2q - 8p.3^n - 8q = 3^n 3^n[9p - 6p - 8p] - 9q = 3^n So, q = 0, -5p = 1, and p = -1/5 Therefore, w(n) = -(1/5)3^n The general solution is u(n) = A(-2)^n + B.4^n - (1/5).3^n u(0) = 1 -> 1 = A + B - 1/5 -> A + B = 6/5 u(1) = 4 -> 4 = -2A + 4B - 3/5 -> -2A+4B = 17/5 So 2A + 2B = 12/5 -2A + 4B = 17/5 ----------------- 6B = 29/5 and B = 29/30 A = 6/5 - 29/30 = 7/30 Therefore, u(n) = (7/30)(-2)^n + (29/30)4^n - (1/5).3^n The others can be done in exactly the same way, so give them a try. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/