HMMT-Feb 2019 comb, 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?

Solution: Let $X_{i}$ be the random variable which is the number of coins at the end of round $i$. Say that $X_{0}=1$ for convenience. Fix $i>0$ and some positive integer $x$. Conditioning on the event $X_{i-1}=x$, there are only two cases with positive probability. In particular, \[ \operatorname{Pr}\left[X_{i}=x+1 \mid X_{i-1}=x\right]=\frac{x}{100} \] and \[ \operatorname{Pr}\left[X_{i}=x \mid X_{i-1}=x\right]=1-\frac{x}{100} \] Therefore \[ \begin{aligned} \mathbb{E}\left[X_{i}\right]= & \sum_{x>0} x \cdot \operatorname{Pr}\left[X_{i}=x\right] \\ = & \sum_{x>0} x \cdot\left(\left(1-\frac{x}{100}\right) \operatorname{Pr}\left[X_{i-1}=x\right]+\frac{x-1}{100} \operatorname{Pr}\left[X_{i-1}=x-1\right]\right) \\ = & \sum_{x>0} x \operatorname{Pr}\left[X_{i-1}=x\right]-\frac{1}{100} \sum_{x>0} x \operatorname{Pr}\left[X_{i-1}=x-1\right] \\ & \quad+\frac{1}{100} \sum_{x>0} x^{2} \operatorname{Pr}\left[X_{i-1}=x-1\right]-\frac{1}{100} \sum_{x>0} x^{2} \operatorname{Pr}\left[X_{i}=x\right] \\ = & \frac{99}{100} \mathbb{E}\left[X_{i-1}\right]-\frac{1}{100}+\frac{1}{50} \mathbb{E}\left[X_{i-1}\right]+\frac{1}{100} \\ = & \frac{101}{100} \mathbb{E}\left[X_{i-1}\right] \end{aligned} \] (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 \[ \mathbb{E}\left[X_{100}\right]=\left(\frac{101}{100}\right)^{100} \mathbb{E}\left[X_{0}\right]=1.01^{100} \] $\fbox{1.1^{100}}$.

Answer: 1.1^{100}