Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
About the main question: $e^{-1}=\lim_{n\to \infty}(1-1/n)^n$: if $N_i$ is close to $N_{i-1}$ then the process takes longer. –  Mark Sapir Oct 28 '11 at 12:09
    
When I answered this question I didn't realize I knew its author. Hi! –  Michael Lugo Oct 28 '11 at 13:50
    
Thanks for the various explanations everyone... the $e$ appearing as the result of geometric means is obvious in retrospect. –  ARupinski Oct 28 '11 at 23:02
add comment

5 Answers

up vote 9 down vote accepted

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.

share|improve this answer
1  
Mikael: If the roughly can easily be made more precise, why do you omit the proof? This reminds of the old warning that when a mathermatician declares something is trivial but does not prove it, something is amiss... :-) (Nice post, by the way.) –  Did Oct 29 '11 at 16:47
    
Didier: I did not have time to expand my answer (and check the details) when I first wrote it. But this is now done. –  Mikael de la Salle Oct 30 '11 at 20:26
    
I agree with you that sentences containing "can easily be made more precise" can look suspicious... but I believe that my answer was enough for MO, which is meant for research-level questions (and I am sure that any researcher with some interest in the question could have made the roughly more precise). :-) –  Mikael de la Salle Oct 30 '11 at 20:34
    
On $[k(N)=i]=[N_i<1\leqslant N_{i-1}]$, $\widetilde{N}_i<i+1$ and $1\leqslant \widetilde{N}_{i-1}$, hence $\widetilde{k}(N)\geqslant i$ is all one can be sure of. It seems $\widetilde{k}(N)$ may be quite larger than $k(N)$ when $N$ is large hence this comparison is not enough to characterize the asymptotic behaviour of $\widetilde{k}(N)$. Or maybe you know how to bound the difference between $k(N)$ and $\widetilde{k}(N)$, using arguments not in the post... –  Did Nov 2 '11 at 20:58
    
I agree with you. If one wants to prove with this method that $a_N := E(\widetilde k(N))\sim\ln N$, there is some more work: what follows from the coupling argument is that $a_N \leq E(k(N)+a_{k(N)})$. One then uses some a priori bound on $a_N$ (as $a_N\leq 2N$). But I think that the shortest way to prove that $a_N \sim \ln N$ is using Markov's property to express $a_N$ in term of the $a_n$'s for $n < N$ as Byron Schmuland explains. My answer was more meant as an informal explanation for the $1/e = \exp(E(ln U))$ appearing instead of $1/2 = E(U)$. –  Mikael de la Salle Nov 3 '11 at 0:33
add comment

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$.

share|improve this answer
    
The first paragraph also shows that the expected number of steps is exactly $1 + (1/2) + (1/3) + \cdots + (1/N) = H_N = \log(N) + C + O(1/N)$ where $C = 0.5772157\ldots$ is the Euler(-Mascheroni) constant. This explains the OP's observation that $E(N)$ looks like $\log N$ but the convergence in $N^{1/E(N)} \rightarrow e$ is slow. –  Noam D. Elkies Oct 30 '11 at 1:33
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Expectation is actually supposed to be the harmonic mean of [0,1], not the arithmetic mean. The harmonic mean is, of course, infinite. Such a random variable exists, and can, in fact, be derived from the above solution by Johan. –  Will Sawin Oct 28 '11 at 17:35
    
You're right! My proof of nonexistence didn't feel right to me, but I think I hadn't had coffee yet. –  Michael Lugo Oct 28 '11 at 18:41
add comment

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.

share|improve this answer
    
+1, but you should explain your answer. –  Ori Gurel-Gurevich Oct 31 '11 at 1:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.