# How to find a proper decay rate from an iterative inequality

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

-

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.

-
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

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.

-