HMMT 二月 2019 · COMB 赛 · 第 4 题
HMMT February 2019 — COMB Round — Problem 4
题目详情
英文原题
- Yannick is playing a game with 100 rounds, starting with 1 coin. During each round, there is a n %
chance that he gains an extra coin, where n is the number of coins he has at the beginning of theround. What is the expected number of coins he will have at the end of the game?
解析
英文解析
- Yannick is playing a game with 100 rounds, starting with 1 coin. During each round, there is a n %
chance that he gains an extra coin, where n is the number of coins he has at the beginning of theround. What is the expected number of coins he will have at the end of the game?
Proposed by: Yuan Yao
Answer: 1 . 01100
Let X be the random variable which is the number of coins at the end of round i . Say that X = 1
i 0
for convenience. Fix i > 0 and some positive integer x . Conditioning on the event X = x , there arei − 1
only two cases with positive probability. In particular,
Pr[ X = x + 1 | X = x ] =xi i − 1
and 100
Pr[ X = x | X = x ] = 1 − .xi i − 1
Therefore 100
∑
E [ X ] = x · Pr[ X = x ]
i ix> 0
( )
( )
∑
x x − 1 = x · 1 − Pr[ X = x ] + Pr[ X = x − 1]
i − 1 i − 1
100 100
x> 0
∑ ∑
= x Pr[ X = x ] − x Pr[ X = x − 1]1
i − 1 i − 1
x> 0 x> 0100
∑ ∑
1 1
2 2 + x Pr[ X = x − 1] − x Pr[ X = x ]
i − 1 i
100 100
x> 0 x> 0
99 1 1 1 = E [ X ] − + E [ X ] +
i − 1 i − 1
100 100 50 100 = E [ X ] .101
i − 1
(A different way to understand this is that no matter how many coins Yannick has currently (as long 100
as he does not have more than 100 coins, which is guaranteed in this problem), the expected numberof coins after one round is always 1 . 01 times the current number of coins, so the expected value ismultiplied by 1 . 01 each round.)
Therefore
( )
101100
E [ X ] = E [ X ] = 1 . 01 .100
100 0
100