Number of picks to end the process I am encounter this question, I don't know how to start. Can you guys help me on this?
$N$ is a positive number. I randomly pick a number, $K$, from $[0, N-1]$. If $K = 0$, the process ends, otherwise we keep picking a number from $[0, K-1]$ until we pick $0$. What is the expected number of picks to end the game?
Let $T_n$ be the number of picks to end when we are picking from $[0,n-1]$.
Note that $E[T_1] = 1$ and if we pick $i$, then we need to look at $T_i$. Then $$E[T_n] = \frac{E[T_1] + \sum_{i=2}^{n-1} (E[T_i] + 1)}{n} = 1 + \frac{\sum_{i=2}^{n-1}E[T_i]}{n} = 1 + \frac{1}{n} + \frac{\sum_{i=2}^{n-2}E[T_i]}{n-1} = ... =\sum_{i=1}^{n}\frac{1}{i} = H(n)$$
Let $T_n$ be the number of picks to end when we are picking from $[0,n-1]$.
Note that $E[T_1] = 1$ and if we pick $i$, then we need to look at $T_i$. Then $$E[T_n] = \frac{E[T_1] + \sum_{i=2}^{n-1} (E[T_i] + 1)}{n} = 1 + \frac{\sum_{i=2}^{n-1}E[T_i]}{n} = 1 + \frac{1}{n} + \frac{\sum_{i=2}^{n-2}E[T_i]}{n-1} = ... =\sum_{i=1}^{n}\frac{1}{i} = H(n)$$