Skip to content

Forgetful singer restarting a countdown song

Question

A countdown song has verses that mention N,N−1,…,1N, N-1, \dots, 1 bottles in that order, and the song ends after the verse for 11 bottle. Each time he sings a verse, a singer independently forgets his place with probability 1N\tfrac1N; when that happens he completes the current verse and then restarts from the NN-bottle verse. Let KK be the expected total number of verses he sings. The limit lim⁡N→∞K/N\lim_{N\to\infty}K/N equals ae−bae-b for integers a,ba,b. Compute a2+b2a^2+b^2.

Short answer

22. Let q=1−1Nq=1-\tfrac1N. Writing first-step equations for the expected verses remaining from each verse and unrolling them gives K=1−qN−1(1−q) qN−1+qN−1K=\tfrac{1-q^{N-1}}{(1-q)\,q^{N-1}}+q^{N-1}. Since qN−1→e−1q^{N-1}\to e^{-1}, K/N→e−1K/N\to e-1, so a=b=1a=b=1 and a2+b2=2a^2+b^2=2.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free