tailieunhanh - concrete mathematics a foundation for computer science phần 10

Trung bình của X được định nghĩa là các thiết lập của tất cả các x như vậy màà chế độ của X được định nghĩa là tập của tất cả các x như vậy là Pr (X = x) 3 Pr (X = x ') cho tất cả cácTrong ví dụ ném xúc xắc của chúng tôi, trung bình của S | A ANSWERS TO EXERCISES 563 values of X in a sequence of independent trials will be a median or mode of the random variable X. We can disprove the statement even in the special case that each variable is 0 or 1. Let Po Pr X Y -z 0 Pl Pr X Y - z - 0 . p7 Pr X Y z 0 where X 1 X. Then Po Pl P7 1 and the variables are independent in pairs if and only if we have P4 P5 P6 P7XP2 P3 P6 P7 pé p7 P4 P5 p 6 Pr pi p 3 P5 p7 P5 P7 p 2 p3 3 p 6 4 p 7 p 1 p3 p 5 p 7 p3 p7 But Pr X Y-Z 0i Pr X Y 0 Pr Z 0 fey Po Po Pi po 4 One solution is PO P3 P5 P6 1 4 Pl P2 p4 p7 0. This is equivalent to flipping two fair coins and letting X the first coin is heads Y the second coin is heads Z the coins differ . Another example with all probabilities is PO 4 64 PI P2 P4 5 64 Ps Pl p 10 64 p7 15 64. For this reason we say that n variables are independent if Pr Xi X1 and - and xn xn Pr Xi X1 .Pr Xn x pairwise independence isn t enough to guarantee this. See exercise 27 for notation. We have 6n n-1 n. 2 n n-2 n-3 i4 it follows that V VX K4 n 2k2 ti 1 . There are A -jL . 52 permutations with X Y and B p 52 permutations with X Y. After the stated procedure each permutation with X Y occurs with probability 1 because we return to step with probability Similarly each permutation with X Y occurs with probability jy l p l y p B . Choosing p L makes Pr X x and Y y for all x and tj We could therefore make two flips of a fair coin and go back to if both come up heads. 564 ANSWERS TO EXERCISES If m is even the frisbees always stay an odd distance apart and the game lasts forever. If m 21 1 the relevant generating functions are G m 4 1 j Al jzAi zA2 Ak ịzAk-i jzAk zAk i for 1 k I Al zAi-1 zAi 1 . The coefficient is the probability that the distance between frisbees is 2k after n throws. Taking a clue from the similar equations in exercise 49 we set 1 and X where X is to be determined. It follows by induction not using the equation for that X Therefore we want to choose X such that