HMMT 十一月 2014 · 冲刺赛 · 第 21 题

HMMT November 2014 — Guts Round — Problem 21

[ 11 ] If you flip a fair coin 1000 times, what is the expected value of the product of the number of heads and the number of tails? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT NOVEMBER 2014, 15 NOVEMBER 2014 — GUTS ROUND Organization Team Team ID#

解析

[ 11 ] If you flip a fair coin 1000 times, what is the expected value of the product of the number of heads and the number of tails? Answer: 249750 We solve the problem for n coins. We want to find ( ) n ∑ 1 n E ( n ) = k ( n − k ) . n 2 k k =0 We present three methods for evaluating this sum. ( ) ( ) n n − 2 Method 1 : Discard the terms k = 0, k = n . Since k ( n − k ) = n ( n − 1) by the factorial k k − 1 definition, we may rewrite the sum as ( ) n − 1 ∑ n ( n − 1) n − 2 E ( n ) = · . n 2 k − 1 k =1 Guts Round ( ) ∑ n − 1 n ( n − 1) n − 2 n − 2 But clearly = 2 , so the answer is . k =1 k − 1 4 Method 2 : Let E [ · ] denote expected value. Using linearity of expectation, we want to find the expected value of 2 E [ X ( n − X )] = n E [ X ] − E [ X ] where X is the number of heads. Moreover, we have 2 2 Var( X ) = E [ X ] − E [ X ] . 1 n 2 1 2 n The variance of each individual coin flip is , so Var( X ) = . Hence E [ X ] = n + . Consequently 4 4 4 4 ( ) n 1 n n ( n − 1) 2 E [ X ( n − X )] = n · − n + = . 2 4 4 4 Method 3 : Differentiating the binomial theorem, we obtain ( ) ( ) n n ∑ ∑ ∂ ∂ ∂ ∂ n n n k n − k k − 1 n − k − 1 ( x + y ) = x y = k ( n − k ) x y . ∂x ∂y ∂x ∂y k k k =0 k =0 We also know that ∂ ∂ n n − 2 ( x + y ) = n ( n − 1)( x + y ) . ∂x ∂y n ( n − 1) Plugging in x = y = 1, we find that E ( n ) = . 4