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

英文解析

21. [ 11 ] If you flip a fair coin 1000 times, what is the expected value of the product of the number ofheads 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 ) .
    2 knk =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 factorialk k − 1
    definition, we may rewrite the sum as
    ( )
    n − 1
    ∑
    n ( n − 1) n − 2
    E ( n ) = · .
    2 k − 1 nk =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 expectedvalue of
    E [ X ( n − X )] = n E [ X ] − E [ X ]2
    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)
    E [ X ( n − X )] = n · − n + = .2
    2 4 4 4
    Method 3 : Differentiating the binomial theorem, we obtain
    ( ) ( )
    n n
    ∑ ∑
    ∂ ∂ ∂ ∂ n nn k n − k k − 1 n − k − 1
    ( x + y ) = x y = k ( n − k ) x y .
    ∂x ∂y ∂x ∂y k kk =0 k =0
    We also know that
    ∂ ∂
    n n − 2
    ( x + y ) = n ( n − 1)( x + y ) .
    ∂x ∂yn ( n − 1)
    Plugging in x = y = 1, we find that E ( n ) = . 4