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 coingets 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 coingets 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
Answer:24
Solution 1: (Dilhan Salgado) In all solutions, p = will denote the probability that the coin is 17
blown away. Let D = | H − T | . Note that if D 6 = 0, the expected value of D is not changed by a 25
coin flip, whereas if D = 0, the expected value of D increases by 1. Therefore E ( D ) can be computedas 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
( )
probability that D = 0 after the first n − 1 flips is . Thereforekk
( ) ( )4
∞
2 k
∑
1 − p 2 k
E ( D ) = (1 − p )
2 kk =0
1 − p
√
2=
1 − (1 − p )
using the generating function
( )
∞
∑
2 k 1
x = √ .kk
1 − 4 xk =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 thenlast throw) is p (1 − p ) .
Claim: Assuming Max made n > 1 throws, the expected value of | H − T | is given byb ( n − 1) / 2 c
∏
2 k + 1
.
2 kk =1
Proof. If n is odd then the expected value for n + 1 will be equal to that for n ; since | H − T | will benonzero, it will be equally likely to increase or decrease after the coin is flipped. Therefore, it sufficesto compute the expected value for the n odd case. This is
( ) ( )
∑ ∑
( n − 1) / 2 ( n − 1) / 2
n n
· ( n − 2 i ) · 2 ii =0 i =0
i i = n −
n − 1 n − 1
2 2
( )
( )
∑
( n − 3) / 2
n − 1
2 ·
i =0 = n · 1 −in − 1
( )2
n − 1
( n − 1) / 2 = n ·
n − 1
n !2
2=
( n − 1)!!
n !!
( n − 1)!!=
( n − 1) / 2
∏
2 k + 1 = ,
2 kk =1
as desired.
Using the claim, we have
b ( n − 1) / 2 c
∞
∑ ∏
2 k + 1
n
E ( | H − T | ) = p (1 − p )
2 kn =1
k =1
( )
∞ m
∑ ∏
2 k + 1
2 m = p (1 − p )(2 − p ) (1 − p )
2 km =0
k =1
( ) − 3 / 2 = p (1 − p )(2 − p ) 1 − (1 − p )2
1 − p
√
= .
p (2 − p )
Plugging in p = gives 1
24 5 2425
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 pnn n − 1 n +1
√
1 − p (2 − p )
for all n > 0. Now let α = < 1 be the smaller root of (1 − p ) x − 2 x + (1 − p ) = 0. From 2
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 nn =1 n =2
∞ ∞
∑ ∑
n n = α (1 − p ) E + (2 α − (1 − p )) E + 2 pnα + 2 α E ,
0 1 nn =1 n =2
we have
∞
∑
2 pαn
(1 − p ) E − α (1 − p ) E = 2 pnα = .
1 0
(1 − α )2
n =1
As E = (1 − p ) E , this gives
0 1
2 pα
E (1 − α (1 − p )) = .
(1 − α )20
1 3 24
Plugging in p = and α = gives E = .
25 4 70