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 the round. 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 the round. What is the expected number of coins he will have at the end of the game? Proposed by: Yuan Yao 100 Answer: 1 . 01 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 are i − 1 only two cases with positive probability. In particular, x Pr[ X = x + 1 | X = x ] = i i − 1 100 and x Pr[ X = x | X = x ] = 1 − . i i − 1 100 Therefore ∑ E [ X ] = x · Pr[ X = x ] i i x> 0 ( ) ( ) ∑ x x − 1 = x · 1 − Pr[ X = x ] + Pr[ X = x − 1] i − 1 i − 1 100 100 x> 0 ∑ ∑ 1 = x Pr[ X = x ] − x Pr[ X = x − 1] i − 1 i − 1 100 x> 0 x> 0 ∑ ∑ 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 101 = E [ X ] . i − 1 100 (A different way to understand this is that no matter how many coins Yannick has currently (as long as he does not have more than 100 coins, which is guaranteed in this problem), the expected number of coins after one round is always 1 . 01 times the current number of coins, so the expected value is multiplied by 1 . 01 each round.) Therefore ( ) 100 101 100 E [ X ] = E [ X ] = 1 . 01 . 100 0 100