Some questions concerning a random number process

Question

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?

Answer 1

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.

Answer 2

Regarding the secondary question: If we start the process from a large $N$, it will always reach 1 sooner or later. The probability that it passes through the number 2 is $1/2$, since as long as the numbers are larger than 2, going in the next step to 2 is as likely as going to 1, and when the process reaches 1 or 2 for the first time, where it went decides whether it ever passes through 2. Similarly the probability that the process ever visits a number $n$ is $1/n$, since this happens precisely when the first visit to any of $1,\dots,n$ is to $n$.

Now it's easy in principle to see what the inverse is: For each pair of numbers $m < n$, the probability that a process starting at a larger $N$ will include a step from $n$ to $m$ is $$\frac1{n(n-1)},$$ since it will reach $n$ with probability $1/n$, and the next number distinct from $n$ is uniform on $1,\dots,n-1$. In particular, for "infinite $N$", the last number visited before reaching 1 is $n$ with this probability.

For $m>1$, the probability that $m$ was reached from $n$ given that the process reached $m$ is $m/(n(n-1))$, since we get a factor $m$ from conditioning on the process ever reaching $m$. It might be easier to sort out the details if we assume that the process never repeats the same number.

ADDED: The inverse process constructed this way has the property that at any $m$, the expectation of the next (previous in the original process) step is infinite. But it does have the nice property that the probability of going from $m$ to a number $\leq 2m$ is $1/2$, so the median growth factor over one step is 2.

NEW UPDATE: If we discard repetitions, then one way to understand the inverse is that from a number $m$, the next step is $$m\mapsto \left\lceil\frac{m}{U}\right\rceil,$$ where $U$ is uniform on the interval $[0,1]$. When $m$ is large, the growth factor is therefore asymptotically the reciprocal of a uniform $[0,1]$, which is the same thing as an "exponential of an exponential" ($e$ to an exponential variable). The median growth factor over one step is 2, but over a large number of steps approaches $e$.

Answer 3

Using Markov chain theory, it is not hard to show that the expected time until the process hits state "1" starting at $N_0$ is $1+1+1/2+\cdots+1/(N_0-1)$.

---

Correction

In my previous answer, I mistakenly chose a new state uniformly from $[1,\dots, N_i]$ instead of $[1,\dots, N_{i-1}]$. The expected hitting time of state "1" for the OP's model starting at $N_0$ is $1+1/2+\cdots+1/(N_0-1)$. This is one less than my first answer.

Answer 4

The average you want in the main question is the geometric mean, as Mikael de la Salle has already alluded to.

About the secondary question: I'd start by looking for a random variable $X$, which always takes value at least 1, which has expectation 2 and geometric mean $e$. Let $X_1, X_2, \ldots$ be independent, and let each have the distribution of $X$. Then take $M_i$ to be $M_{i-1} X_i$ rounded to the nearest integer. Unfortunately there is no such random variable, by the arithmetic-geometric mean inequality. So it seems very likely to me that there is no such process.

Answer 5

The process described is also known as the stick-breaking process for sampling the cycle type of a uniformly chosen permutation in $S_n$. So we have the set $[n]$ and we want to choose a uniformly random permutation $\sigma$ in $S_n$, viewed as an automorphism of $[n]$. So we can choose $n$ target values for $\sigma(1)$ and $n-1$ values for $\sigma(\sigma(1))$ etc. This process stops when $\sigma^k(1) = 1$ for some least $k > 0$. It's an easy computation to show that the chance that the process stops at step $k$ is always $1/n$ regardless of what $k$ is: for instance, if $k = 1$, then that means $1$ has to map to itself, which if done uniformly has chance $1/n$, and if $k=2$, then there are $n-1$ out of $n$ choices for $\sigma(1)$ (because we have to exclude $1$), and $1$ out of $n-1$ choices for $\sigma(\sigma(1))$, namely it has to be $1$. So the probability in that case is $\frac{n-1}{n} \frac{1}{n-1} = 1/n$ again! This corresponds to a uniform "cut" in $[n]$ such that everything to the left of that cut gives the length of the cycle containing $1$. Now we continue by picking a number not in the first cycle, and the process is indeed self-similar by inspection.

The number of cycles of a ramdom permutation is concentrated at $\log n$ with variance $\log n$ and satisfies a Central limit theorem. Therefore we expect $\log n$ on average for the finishing time of the original problem.