HMMT 二月 2017 · 冲刺赛 · 第 26 题

HMMT February 2017 — Guts Round — Problem 26

[ 15 ] Kelvin the Frog is hopping on a number line (extending to infinity in both directions). Kelvin 1 1 starts at 0. Every minute, he has a chance of moving 1 unit left, a chance of moving 1 unit right 3 3 1 and chance of getting eaten. Find the expected number of times Kelvin returns to 0 (not including 3 the start) before getting eaten.

解析

[ 15 ] Kelvin the Frog is hopping on a number line (extending to infinity in both directions). Kelvin 1 1 starts at 0. Every minute, he has a chance of moving 1 unit left, a chance of moving 1 unit right 3 3 1 and chance of getting eaten. Find the expected number of times Kelvin returns to 0 (not including 3 the start) before getting eaten. Proposed by: Allen Liu First we compute probability that the mouse returns to 0 before being eaten. Then probability that ( ) 2 n 1 it is at 0 in 2 n minutes without being eaten is given by . Therefore, the overall expectation is 2 n 3 n given by ( ) ( ) ∑ ∑ 2 n 2 n − n − n 9 = − 1 + 9 n n n ≥ 1 n ≥ 0 √ 1 3 3 5 − 5 = − 1 + √ = − 1 + √ = 5 5 1 − 4 / 9 where we use the well known fact that ( ) ∑ 2 n 1 n √ x = . n 1 − 4 x n ≥ 0 1 for x = . 9