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

Suppose we have the iterative inequality $\gamma_{k+1} \leq \gamma_k(1 - c \gamma_k^\alpha)$ with $c, \alpha \in (0, 1)$ and $(1 - c \gamma_k^\alpha)>0$ for all non-negative terms $\gamma_k$.

-- How could we show that $\gamma_k$ is polynomially decay, i.e., $\gamma_k \leq C (k+1)^{-\frac{1}{\alpha}}$ for some constant $C$?

-- Could we show that the above constant $C$ is uniformly bounded with respect to $\alpha$? If not, what is a good form to describe the decay rate of $\gamma_k$.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

From the iterative inequality (assuming $1-c\gamma_k^\alpha >0$ as said) $$\gamma_{k+1}^{-\alpha}\ge \gamma_k^{-\alpha}\big(1- c\, \gamma_k^\alpha\big)^{-\alpha}\ge \gamma_k^{-\alpha}+\alpha c\, , $$ the last inequality just coming from the convexity inequality $(1-x)^{-\alpha}\ge 1+\alpha x $, for $0 < x < 1$.

Therefore $\gamma_k^{-\alpha}\ge \gamma_0^{-\alpha}+ k\alpha c\ge(k+1) \alpha c$, and your polynomial bound follows with $C:=(\alpha c ) ^{-1/\alpha}$.

$$\bullet$$

As to the other question, there is no uniform constant for all $0<\alpha<1$, and the reason is that the above constant is indeed optimal. Precisely, for any iteration $\gamma_{k+1}= \gamma_k(1- c \gamma_k^\alpha)$ with $1-c\gamma_0^\alpha >0$ we have $$\gamma_k=Ck^{-1/\alpha}\big(1+o(1)\big)\, ,\quad\mathrm{for}\, k\to\infty \, .$$

Indeed, since $\gamma_k\to 0$, we have $$ \gamma_{k+1}^{-\alpha}= \gamma_k^{-\alpha}\big(1- c\, \gamma_k^\alpha\big)^{-\alpha}= \gamma_k^{-\alpha}+\alpha c+o(1)\, ,\quad\mathrm{for}\, k\to\infty \, , $$ because $(1-x)^{-\alpha}=1+\alpha x +o(x)$ for $x\to0$. Thus $\gamma_{k^{-\alpha}}=k\alpha c+o(k)=k\alpha c\big(1+o(1)\big)$, and the above asymptotic follows.

share|improve this answer
    
I don't see how you estimate $\gamma_0$ in terms of $c,\alpha$ in the endgame, but otherwise I like it. –  GH from MO Aug 2 '11 at 14:47
    
It's just the initial assumption in the OP, $1−c\gamma_k^\alpha > 0$ for all $k$, which indeed is ensured by $1−c\gamma_0^\alpha > 0$, and it is necessary for $\gamma_k$ to be well-defined for all $k$ (I've added the remark). –  Pietro Majer Aug 2 '11 at 16:15
add comment

I always obtain decay rates for iterative inequalities like that by comparing them with differential equations.

The particular difference equation you give can be compared to $\dot y=-cy^{1+\alpha}$. If you think of the right side as a "speed" then the speed is $cy^{1+\alpha}$ moving to the left and decreases over time. On the other hand if you think of the difference equation as moving to the left at speed $y^{1+\alpha}$ which stays constant for 1 unit of time, it is clear that the difference equation approaches 0 faster.

In other words, the solution to the differential equation is an upper bound for the solution to the difference equation. If you work a bit harder you can find another differential equation that serves as a lower bound for the difference equation so that you can get good bounds from above and below.

share|improve this answer
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.