HMMT 二月 2020 · COMB 赛 · 第 10 题
HMMT February 2020 — COMB Round — Problem 10
题目详情
- Max repeatedly throws a fair coin in a hurricane. For each throw, there is a 4% chance that the coin gets blown away. He records the number of heads H and the number of tails T before the coin is lost. (If the coin is blown away on a toss, no result is recorded for that toss.) What is the expected value of | H − T | ?
解析
- Max repeatedly throws a fair coin in a hurricane. For each throw, there is a 4% chance that the coin gets blown away. He records the number of heads H and the number of tails T before the coin is lost. (If the coin is blown away on a toss, no result is recorded for that toss.) What is the expected value of | H − T | ? Proposed by: Krit Boonsiriseth 24 Answer: 7 1 Solution 1: (Dilhan Salgado) In all solutions, p = will denote the probability that the coin is 25 blown away. Let D = | H − T | . Note that if D 6 = 0, the expected value of D is not changed by a coin flip, whereas if D = 0, the expected value of D increases by 1. Therefore E ( D ) can be computed as the sum over all n of the probability that the n th coin flip occurs when D = 0. This only occurs 2 k +1 when n = 2 k + 1 is odd, where the probability that the first n coin flips occur is (1 − p ) and the 2 k ( ) k probability that D = 0 after the first n − 1 flips is . Therefore k 4 ( ) ( ) ∞ 2 k ∑ 1 − p 2 k E ( D ) = (1 − p ) 2 k k =0 1 − p √ = 2 1 − (1 − p ) using the generating function ( ) ∞ ∑ 2 k 1 k x = √ . k 1 − 4 x k =0 1 24 Plugging in p = yields E ( D ) = . 25 7 Solution 2: For each n > 0, the probability that Max made n successful throws (not counting the n last throw) is p (1 − p ) . Claim: Assuming Max made n > 1 throws, the expected value of | H − T | is given by b ( n − 1) / 2 c ∏ 2 k + 1 . 2 k k =1 Proof. If n is odd then the expected value for n + 1 will be equal to that for n ; since | H − T | will be nonzero, it will be equally likely to increase or decrease after the coin is flipped. Therefore, it suffices to compute the expected value for the n odd case. This is ( ) ( ) ∑ ∑ ( n − 1) / 2 ( n − 1) / 2 n n · ( n − 2 i ) · 2 i i =0 i =0 i i = n − n − 1 n − 1 2 2 ( ) ( ) ∑ ( n − 3) / 2 n − 1 2 · i =0 i = n · 1 − n − 1 2 ( ) n − 1 ( n − 1) / 2 = n · n − 1 2 n ! = 2 ( n − 1)!! n !! = ( n − 1)!! ( n − 1) / 2 ∏ 2 k + 1 = , 2 k k =1 as desired. Using the claim, we have b ( n − 1) / 2 c ∞ ∑ ∏ 2 k + 1 n E ( | H − T | ) = p (1 − p ) 2 k n =1 k =1 ( ) ∞ m ∑ ∏ 2 k + 1 2 m = p (1 − p )(2 − p ) (1 − p ) 2 k m =0 k =1 ( ) − 3 / 2 2 = p (1 − p )(2 − p ) 1 − (1 − p ) 1 − p √ = . p (2 − p ) 1 Plugging in p = gives 25 24 5 24 E ( | H − T | ) = · 5 · = . 25 7 7 Solution 3: Let E be the expected value of | H − T + n | . By symmetry, E = E for all n . n − n n Considering what happens in the next throw gives 2 E = (1 − p ) E + (1 − p ) E + 2 pn n n − 1 n +1 √ 1 − p (2 − p ) 2 for all n > 0. Now let α = < 1 be the smaller root of (1 − p ) x − 2 x + (1 − p ) = 0. From 1 − p ∞ ∞ ∑ ∑ n n 2 α E = α ((1 − p ) E + (1 − p ) E + 2 pn ) n n − 1 n +1 n =1 n =1 ∞ ∞ ∑ ∑ ( ) 2 n n − 1 n +1 = α (1 − p ) E + α (1 − p ) E + 2 pnα + (1 − p ) α + (1 − p ) α ) E 0 1 n n =1 n =2 ∞ ∞ ∑ ∑ n n = α (1 − p ) E + (2 α − (1 − p )) E + 2 pnα + 2 α E , 0 1 n n =1 n =2 we have ∞ ∑ 2 pα n (1 − p ) E − α (1 − p ) E = 2 pnα = . 1 0 2 (1 − α ) n =1 As E = (1 − p ) E , this gives 0 1 2 pα E (1 − α (1 − p )) = . 0 2 (1 − α ) 1 3 24 Plugging in p = and α = gives E = . 0 25 4 7