MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following iterative process $$a_n=a_{n-1}(1-\phi(a_{n-1})),\quad 0< a_0<1,$$ where $\phi(x)$ is a continuous increasing function, $\phi(0)=0$, and if $x\in(0,1)$ then $0< \phi(x)<1$. For instance, if $\phi(x)=x$, then this is just the logistic map.

Clearly, $a_n$ converges to $0$ as $n\to\infty$ for any function $\phi$, but the convergence rate depends on $\phi$.

My question is how we can estimate the convergence rate. Are there any standard methods which can be used here?


share|cite|improve this question
up vote 3 down vote accepted

The standard techniques is as follows. At first, we guess the growth rate by replacing the discrete dynamical system to ODE: $a_n-a_{n-1}=-a_{n-1}\phi(a_{n-1})$ is replaced to $A'(n)=-A(n)\phi(A(n))$, where function $A(n)$ imitates $a_n$. Nex, we solve this equation, rewriting it as $g(A(n))'=1$, where $g'(t)=-1/(t\phi(t))$. Our guess is that $g(A(n))$ behaves like $n$ (since it derivative behaves as 1), and the same for $g(a_n)$. For proving this guess rigorously we introduce a new sequence $b_n=g(a_n)$ and write down the formula $b_n-b_{n-1}=g(a_n)-g(a_{n-1})=(a_n-a_{n-1})g'(s)$ for some $s$ between $a_{n-1}$ and $a_n$. Next, $(a_n-a_{n-1})g'(s)=\frac{a_{n-1}\phi(a_{n-1})}{s\phi(s)}$. Assume that $\phi(x):\phi(y)$ tends to 1 when $x/y$ tends to 1 and $x,y$ tend to $+0$. Then we may conclude that our last fraction tends to $1$, and by usual Stolz theorem conclude that $b_n$ behaves like $n$.

Example: $\phi(x)=x$, $g(t)=1/t$, so we consider the sequence $b_n=1/a_n$. We get $b_{n}-b_{n-1}=\frac{a_{n-1}-a_{n}}{a_na_{n-1}}=\frac{a_{n-1}}{a_{n}}$, what clearly tends to 1, hence $b_n\sim n$.

share|cite|improve this answer
Fedor, thanks a lot! It was very helpful. – Oleg Aug 20 '12 at 20:28

If $\phi(x)=x^m$ your function is analytic at $0$, and convergence rate can be found with very high precision. Same happens if it is analytic in sufficiently large sector with vertex at $0$. See about this P. Fatou, Sur les equations fonctionnelles (1919-20). If $\phi(x)=x$, convergence is logarithmic, that is very slow. If $\phi(x)=x^m$ it is even slower, as you can see interating $\sin x$ on your calculator.

share|cite|improve this answer

Your Answer


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.