show/hide this revision's text 4 added 1 characters in body

For the main question, your process is "roughly" the same as the one starting at $N_0=N$, and defined by $N_{i+1} = U_{i+1} N_{i}$, where $U_i$ are iid uniform in $[0,1]$. I guess that the "roughly" can be easily made more precise.

For this modified process, your question becomes: what is $k(N)$, the smallest $k$ such that $U_1\dots U_k < 1/N$, or equivalently $\ln U_1 + \dots + \ln U_k < -\ln N$?

But the expected value of $\ln U$ is $-1$, so that by the law of large numbers $\ln U_1 + \dots + \ln U_k$ is equivalent to $-k$, which give that $k(N) \sim \ln N$.

--

Edit: the following coupling argument makes the "roughly" more precise, as requested in the comments.

Given $(U_i)_{i \geq 1}$ an iid sequence of uniform variables in $[0,1]$ and an integer $N$, consider the two processes $N_i$ and $\widetilde N_i$ defined by $N_0 = \widetilde N_0 = N$, and $N_{i+1} = U_{i+1} N_i$, and $\widetilde N_{i+1} = 1+E(U_{i+1} \widetilde N_i)$, where $E(\cdot)$ is the integer part. The inequalities $N_i \leq \widetilde N_i \leq N_i+i$ are obvious, and the process $\widetilde N$ has the same law as the process described in the question.
show/hide this revision's text 3 added 580 characters in body

For the main question, your process is "roughly" the same as the one starting at $N_0=N$, and defined by $N_{i+1} = U_{i+1} N_{i}$, where $U_i$ are iid uniform in $[0,1]$. I guess that the "roughly" can be easily made more precise.

For this modified process, your question becomes: what is $k(N)$, the smallest $k$ such that $U_1\dots U_k < 1/N$, or equivalently $\ln U_1 + \dots + \ln U_k < -\ln N$?

But the expected value of $\ln U$ is $-1$, so that by the law of large numbers $\ln U_1 + \dots + \ln U_k$ is equivalent to $-k$, which give that $k(N) \sim \ln N$.

--

Edit: the following coupling argument makes the "roughly" more precise, as requested in the comments.

Given $(U_i)_{i \geq 1}$ an iid sequence of uniform variables in $[0,1]$ and an integer $N$, consider the two processes $N_i$ and $\widetilde N_i$ defined by $N_0 = \widetilde N_0 = N$, and $N_{i+1} = U_{i+1} N_i$, and $\widetilde N_{i+1} = 1+E(U_{i+1} \widetilde N_i)$, where $E(\cdot)$ is the integer part. The inequalities $N_i \leq \widetilde N_i \leq N_i+i$ are obvious, and the process $\widetilde N$ has the same law as the process described in the question.
show/hide this revision's text 2 added 7 characters in body

For the main question, your process is "roughly" the same as the one starting at $N_0=N$, and defined by $N_{i+1} = U_{i+1} N_{i}$, where $U_i$ are iid uniform in $[0,1]$. I guess that the "roughly" can be easily made more precise.

For this modified process, your question becomes: what is $k(N)$, the smallest $k$ such that $U_1\dots U_k < 1/N$, or equivalently $ln \ln U_1 + \dots + \ln U_k < -ln \ln N$?

But the expected value of $ln \ln U$ is $-1$, so that by the law of large numbers $ln \ln U_1 + \dots + \ln U_k$ is equivalent to $-k$, which give that $k(N) \sim \ln N$.
show/hide this revision's text 1