PUMaC 2014 · 团队赛 · 第 10 题

PUMaC 2014 — Team Round — Problem 10

[ 7 ] A gambler has $25 and each turn, if the gambler has a positive amount of money, a fair coin is flipped and if it is heads, the gambler gains a dollar and if it is tails, the gambler loses a dollar. But, if the gambler has no money, he will automatically be given a dollar (which counts as a turn). What is the expected number of turns for the gambler to double his money?

解析

[ 7 ] A gambler has $25 and each turn, if the gambler has a positive amount of money, a fair coin is flipped and if it is heads, the gambler gains a dollar and if it is tails, the gambler loses a dollar. But, if the gambler has no money, he will automatically be given a dollar (which counts as a turn). What is the expected number of turns for the gambler to double his money? Solution: If we let E be the expected number of turns for the gambler to reach $50 when he currently i E + E i − 1 i +1 has $ i , we have that E = 1 + E and E = + 1 for 1 ≤ i ≤ 49 with E = 0. 0 1 i 50 2 E + 1 + E E + 3 + E 2 1 3 2 So we have E = + 1 ⇒ E = E + 3 and E = + 1 ⇒ E = 1 1 2 2 2 2 2 E + 5. We claim that E = E + 2 ∗ i + 1 and by using induction, we have that E = 3 i i +1 i +1 E + 2 ∗ i + 1 + E i +1 i +2

1 ⇒ E = E + 2 ∗ i + 3 and so the result holds. i +1 i +2 2 2 2 2 2 Therefore, it becomes clear that E = E + i and so E + 25 = E + 50 = 50 ⇒ E = 0 i 25 50 25 1875 .