Expected Time to Hit Zero April 5, 2026
Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!
Let D U ( 0 , n ) DU(0, n) D U ( 0 , n ) n − 1 n-1 n − 1
X 1 ∼ D U ( 0 , n ) X_1 \sim DU(0, n) X 1 ∼ D U ( 0 , n )
X i + 1 ∼ D U ( 0 , X i ) f o r i ≥ 1 X_{i+1} \sim DU(0, X_{i}) \ for \ i \ge 1 X i + 1 ∼ D U ( 0 , X i ) f or i ≥ 1 The above process is repeated until we get a random variable with the value zero.
What is the expected number of variables
(i.e., time to hit zero) in this process?
Let T n T_n T n
t n = E ( T n ) = E ( E ( T n ∣ X 1 ) ) = ∑ i = 0 n − 1 1 n E ( T n ∣ X 1 = i ) = ∑ i = 0 n − 1 1 n ( 1 + E ( T i ) ) = ∑ i = 0 n − 1 1 n ( 1 + t i ) \begin{align*}
t_n &=E(T_n) = E\left(E(T_n|X_1)\right) \\
&= \sum_{i=0}^{n-1} \frac{1}{n} E(T_n|X_1=i) \\
&= \sum_{i=0}^{n-1} \frac{1}{n} (1 + E(T_i)) \\
&= \sum_{i=0}^{n-1} \frac{1}{n} (1 + t_i)
\end{align*} t n = E ( T n ) = E ( E ( T n ∣ X 1 ) ) = i = 0 ∑ n − 1 n 1 E ( T n ∣ X 1 = i ) = i = 0 ∑ n − 1 n 1 ( 1 + E ( T i )) = i = 0 ∑ n − 1 n 1 ( 1 + t i ) n t n = n + ∑ i = 0 n − 1 t i nt_n = n + \sum_{i=0}^{n-1} t_i n t n = n + i = 0 ∑ n − 1 t i ( n − 1 ) t n − 1 = ( n − 1 ) + ∑ i = 0 n − 2 t i (n-1)t_{n-1} = (n-1) + \sum_{i=0}^{n-2} t_i ( n − 1 ) t n − 1 = ( n − 1 ) + i = 0 ∑ n − 2 t i n t n = n + t n − 1 + ( n − 1 ) t n − 1 − ( n − 1 ) = n t n − 1 + 1 nt_n = n + t_{n-1} + (n-1)t_{n-1} - (n-1)
= nt_{n-1} + 1 n t n = n + t n − 1 + ( n − 1 ) t n − 1 − ( n − 1 ) = n t n − 1 + 1 t n − t n − 1 = 1 n t_n - t_{n-1} = \frac{1}{n} t n − t n − 1 = n 1 ∑ i = 1 n ( t i − t i − 1 ) = ∑ i = 1 n 1 i \sum_{i=1}^n (t_i - t_{i-1}) = \sum_{i=1}^n \frac{1}{i} i = 1 ∑ n ( t i − t i − 1 ) = i = 1 ∑ n i 1 t n = ∑ i = 1 n 1 i t_n = \sum_{i=1}^n \frac{1}{i} t n = i = 1 ∑ n i 1