Consider the following Markov process: Start with an integer $N = N\_0$. Now repeatedly choose an $N\_i$ uniformly at random in the range $[1...N\_{i-1}]$ until $N\_i = 1$ at which point one terminates the process. This produces a nonincreasing integer sequence $\{N\_0,N\_1,\ldots,N\_{k-1},N\_k = 1\}$.


Experimental evidence shows that as $N\_0$ grows large, the expected length $E(N\_0)$ of such a sequence seems to approach $ln(N\_0)$. Equivalently, one expects that the average over many steps of $N\_i/N\_{i+1}$ is approximately $e$. Convergence to this expectation is slow however; for example if $N\_0$ is a 1000-bit integer one finds that $E(N\_0)$ satisfies roughly $2.71^{E(N\_0)} = N\_0$ and in particular the base agrees with $e$ to only around 2 decimal places.


Because the $N\_i$ were chosen uniformly at random, for any given $i$ the expectation of $N\_i/N\_{i+1}$ is 2, so this seems to contradict the above observation that the average of $N\_i/N\_{i+1}$ is approximately $e$. To understand this discrepancy, consider a toy example where $N\_1 = qN\_0$ and $N\_2 = (1-q)N\_1$ for some $0\leq q\leq 1$. One sees that $N\_2 \leq \frac{1}{4}N\_0$ with equality iff $q=\frac{1}{2}$; clearly the average of the step ratios $q$ and $1-q$ is equal to the expected single step ratio $\frac{1}{2}$, but the composition of the steps has led to an overall decrease in the sequence at a rate faster than division by 2. Hence the above observation that the overall step decrease rate is approximately division by $e$ is plausible.



> 
> 
> > 
> > **Main Question:** How does one understand the appearance of $e$ in the expected step down rate (as opposed to some other constant)? Presumably it should appear as a result of some averaging of all possible step ratios, but I can't seem to see what the correct average to be considering is.
> > 
> > 
> > **Secondary question:** At the risk of being vague, does anyone know what an inverse to this process looks like? That is, a process where $M\_0 = 1$ and at each step one chooses an $M\_i\geq M\_{i-1}$ at random such that the expected growth rate is roughly multiplication by $e$ but such that the expected growth at any step should be multiplication by 2. Clearly one cannot choose the next number uniformly at random since this would lead to infinite step and expected growth, so what probability distribution (if any) can be put on the integers greater than $N\_i$ so that choosing a next element will lead to a process which looks roughly like the original process in reverse?
> > 
> > 
> > 
> 
> 
> 



Some questions concerning a random number process
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.


