HMMT 二月 2021 · 冲刺赛 · 第 28 题

HMMT February 2021 — Guts Round — Problem 28

[16] Caroline starts with the number 1, and every second she flips a fair coin; if it lands heads, she adds 1 to her number, and if it lands tails she multiplies her number by 2. Compute the expected number of seconds it takes for her number to become a multiple of 2021. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT Spring 2021, March 06, 2021 — GUTS ROUND Organization Team Team ID#

解析

[16] Caroline starts with the number 1, and every second she flips a fair coin; if it lands heads, she adds 1 to her number, and if it lands tails she multiplies her number by 2. Compute the expected number of seconds it takes for her number to become a multiple of 2021. Proposed by: Carl Schildkraut, Krit Boonsiriseth Answer: 4040 Solution: Consider this as a Markov chain on Z / 2021 Z . This Markov chain is aperiodic (since 0 can go to 0) and any number can be reached from any other number (by adding 1), so it has a unique stationary distribution π , which is uniform (since the uniform distribution is stationary). It is a well-known theorem on Markov chains that the expected return time from a state i back to i is equal to the inverse of the probability π of i in the stationary distribution. (One way to see this is to i take a length n → ∞ random walk on this chain, and note that i occurs roughly π of the time.) Since i 1 the probability of 0 is , the expected return time from 0 to 0 is 2021. 2021 After the first step (from 0), we are at 1 with probability 1 / 2 and 0 with probability 1 / 2, so the number of turns it takes to get from 1 to 0 on expectation is 2 · 2021 − 2 = 4040 .