order analysis of recurrence relation

71 Views Asked by At

Given a fixed $\eta > 0$, consider the recurrence relation

$$ x_1 = 0 \quad \text{and} \quad x_{t+1} = x_t + \eta \cdot \frac{2}{(1+x_t)^2} \enspace. $$

Question: How can we establish that the recurrence satisfies $x_t = \mathcal{\Theta} \left( ( \eta \cdot t )^{1/3} \right)$ ?

I am looking for an approach that provides explicit constants here.

Here's my attempt so far: I have conducted some simulations to verify that

$$ \left[ ( 6 t \cdot \eta + 1 )^{1/3} - 1 \right] \leq x_t \leq C(\eta) \cdot \left[ ( 6 t \cdot \eta + 1 )^{1/3} - 1 \right] \enspace, $$

where $C(\eta)$ is a constant which depends on the fixed $\eta$. I obtained the guess of $( 6 t \cdot \eta + 1 )^{1/3} - 1$ by viewing the recurrence relation as the Euler discretization of the differential equation $\frac{\partial}{\partial s} x(s) = \frac{2}{(1 + x(s))}$ and $x(0) = 0$ with step size $\eta > 0$. But, the above inequality was obtained only through simulations and I don't have a formal proof. Here is some progress on obtaining a slightly weaker lower bound.

Proposition: The recurrence is lower bounded as $x_t \geq \left( 6 (t-1) \cdot \eta + 1 \right)^{1/3} - 1$.

Proof: Define $R_t = \frac{1}{\eta} \left( \left( x_t + 1 \right)^3 - 1\right)$. It suffices to show that $R_t \geq 6 (t-1)$. To this end, observe that

\begin{align*} R_t &= \sum_{s=1}^{t-1} \left( R_{s+1} - R_s \right) + R_1 &\text{(telescoping)} \\ &= \sum_{s=1}^{t-1} \left( R_{s+1} - R_s \right) &\text{($R_1 = 0$)} \\ &= \frac{1}{\eta} \sum_{s=1}^{t-1} \left( x_{s+1} + 1 \right)^3 - \left( x_s + 1 \right)^3 &\text{(def of $R_t$)} \\ &= \frac{1}{\eta} \sum_{s=1}^{t-1} \left( x_{s} + 1 + \eta \frac{2}{(1+x_s)^2} \right)^3 - \left( x_s + 1 \right)^3 &\text{(recurrence)} \\ &= \frac{1}{\eta} \sum_{s=1}^{t-1} \left[ 3 (x_s +1)^2 \cdot \left( \frac{2 \eta}{(1 + x_s)^2} \right) + 3 (x_s +1) \left( \frac{2 \eta}{(1+x_s)^2} \right)^2 + \left( \frac{2 \eta}{(1+x_s)^2} \right)^{3} \right] &\text{(expansion)}\\ &= \sum_{s=1}^{t-1} \left[ 6 + \frac{12 \eta}{(1+x_s)^3} + \frac{8 \eta^2}{(1+x_s)^6} \right] \\ &\geq 6 (t-1) \enspace. \end{align*}

But, I'm still stuck on proving an upper bound on the recurrence relation. I think it can be helpful to define the $R_t$ and consider a telescoping sum, but I'm not sure how to gracefully upper bound the other two terms that appear there.

2

There are 2 best solutions below

3
On

First, you can see that the sequence is non-increasing, since $x_{t+1}-x_t\geq 0$. Then two possibilities: Either it is bounded from above, or it's not. In the former case, it would have to converge to a limit $l$. That limit would have to verify $$l = l + \eta \cdot \frac{2}{(1+x_t)^2}$$ which has no solution. Thus the sequence diverges to infinity: $x_t\rightarrow+\infty$.

For convenience, define $y_t=\frac 1 {x_t}$. Then that sequence also verifies a recurrence relation: $$ y_{t+1} = \frac 1 { x_t + \eta \cdot \frac{2}{(1+x_t)^2}}=\frac 1 {x_t}\cdot\frac 1 {1+\eta\cdot\frac 2 {x_t^3(1+\frac 1 {x_t})^2}}=y_t\cdot\frac 1 {1+\eta\cdot y_t^3\frac 2 {(1+y_t)^2}} $$ Now consider $\alpha\in \mathbb R-\{0\}$. Since $y_t\rightarrow 0$, you can compute a Taylor expansion of $y_t^\alpha$ as $t\rightarrow+\infty$: $$\begin{split} y_{t+1}^\alpha &=y_t^\alpha\left(1+2\,\eta\, y_t^3(1+y_t)^{-2}\right)^{-\alpha}\\ &= y_t^\alpha\left(1+2\,\eta\, y_t^3(1+o(1))^{-2}\right)^{-\alpha}\\ &= y_t^\alpha\left(1+2\,\eta\, y_t^3+o(y_t^3)\right)^{-\alpha}\\ &= y_t^\alpha\left(1-2\,\alpha\,\eta \, y_t^3+o(y_t^3)\right)\\ &= y_t^\alpha -2\,\alpha\,\eta \,y_t^{\alpha+3}+o(y_t^{\alpha+3}) \end{split}$$ So if you choose $\alpha = -3$: $$y_{t+1}^{-3}=y_t^{-3} +6\,\eta+o(1)$$ Summing this down all the way to $t=0$ gives: $$y_t^{-3}\sim 6\,\eta\, t$$

$$\boxed{x_t \sim \left( 6\,\eta \,t\right)^{1/3}}$$

5
On

Enhance the equation to $$ 1+x_{t+1}=\underbrace{(1+x_t)}_{=a}+\underbrace{\frac{2\eta}{(1+x_t)^2}}_{=b} $$ Consider that with the cubic binomial expansion $$ (a+b)^3=a^3+3a^2b+3ab^2+b^3 $$ and $x_t$ large, the last two terms become negligible. Anyway, as long as the terms are positive, the first two terms give the lower bound $$ (1+x_{t+1})^3\ge (1+x_t)^3+6\eta $$ so that in solving the recursion $$ (1+x_t)^3\ge (1+x_0)^3+6\eta t. $$ Insert the initial condition $x_0=0$ (or shift the index for $x_1=0$) this gives $$ x_t\ge(1+6\eta t)^{1/3}-1, $$ which for large values of $t$ has the claimed behavior.