2
$\begingroup$

I have the following non-linear recurrence:

$$y_{n+1} = \sqrt{\frac{2}{1+y_n}}y_n,\quad y_0 \in[0,1]$$

Some basic thought shows that $0$ and $1$ are fixed points of this, and that $0$ is repelling and $1$ is attracting (I am solely concerned with the region $y_i\in[0,1]$).

Non-linear recurrences rarely have closed forms in terms of elementary functions, and I doubt that this one does. Fortunately, I don't particularly care about exact solutions, but solely close upper bounds. Note that there's a trivial upper bound of $y_i\leq 1$, but this is insufficient for my case.

This sequence tends to converge to $1$ fairly quickly (and in the region of interest appears to be quite ``regular''), so you can get a pretty good idea of what it looks like by choosing some arbitrary $y_0$ values and plotting it. I've included python code that does this here. You should be able to type plot(1/2) to see the plot for 1/2 (for example). Note that it continues to add lines to the plot --- to remove them, delete plot.png, and reload the page (hacky I know).

For those that just want to see some pictures, see below:Plots for various starting points

Here, the lines plotted correspond to $y_0 \in\{1/2, 1/4, 1/8, 1/16, 1/32\}$, from top to bottom. Note that this picture is slightly deceiving --- this is technically a discrete sequence. Still, this shows that it might have come reasonable continuous interpolation.

What techniques are there for getting upper bounds for monotonically-increasing non-linear recurrence relations? The only thought I have is approximating $y_n\sqrt{2/(1+y_n)}$ via some sort of Taylor series (which isn't hard using the Newton binomial theorem), and truncating this. This gives us a recurrence relation "inequality", which will likely still be non-linear if we don't want to incur much error in the remainder term.

I've looked into things like this paper, but was unable to get my recurrence to fit into their framework (although it's quite close). The related series: $$ z_{n+1} = \frac{1}{\sqrt{1+z_n}}z_n,\quad z_0\in[0,1]$$ Seems to fit in, although the results I got from applying the technique of that paper to this recurrence were spotty at best (likely due to computational errors on my part, but I don't want to chase them down without being able to apply this technique to my recurrence).

Since $y_n$ converges to $1$ fairly quickly, I'm more interested in a tight bound for lower values of $i$ (for higher values, the bound $y_n\leq 1$ becomes increasingly tight). It's unclear precisely what regime "low values" and "high values" mean, but interpreting it as "compared to $1/y_0$" (or potentially even $\log(1/y_0)$, I haven't done numerical investigations of this yet) is a safe bet.

I'm mostly interested in if there are any general techniques for bounding non-linear recurrence relations, in situations where the solutions appears to be highly "non-chaotic". I understand that it can be difficult to derive closed forms for non-linear recurrence relations, but I hope these dual relaxations (well-behaved solutions, and solely a close upper bound) make the problem more tractable.

$\endgroup$
  • $\begingroup$ How about $\ y_n <1- c (3/4)^n\ $ if $n>k$ for some $k$ and $c$? $\endgroup$ – Somos Apr 26 '19 at 0:55
  • $\begingroup$ @Somos this is the "opposite direction" of what I need --- If I could get some good approximation on $[0, k)$, or $[k, \infty)$, I'd prefer the former. It'd be better if $k$ wasn't some constant (at that point, I might as well just use the exact, numerically-computed values of $y_n$), but how $k$ varies is more overhead than this question probably needs. $\endgroup$ – Mark Apr 26 '19 at 1:01
  • $\begingroup$ If you you want "opposite direction" that I strongly suggestion you include details of that in the body of your question becuase right now it is not clear what you really are asking for and how close you have come already. $\endgroup$ – Somos Apr 26 '19 at 1:05
1
$\begingroup$

Expanding on the idea from Somos's comment: define $x_n=1-y_n$, so that you want a lower bound on $x_n$. The recurrence becomes $$ x_{n+1} = 1-y_{n+1} = 1-\sqrt{\frac{2}{1+y_n}}y_n = 1-(1-x_n)\sqrt{\frac{2}{2-x_n}}. $$ Note that the function $1-(1-x)\sqrt{2/(2-x)}$ is larger than $\frac34x$ for all $x\in(0,1)$. Therefore $x_{n+1} \ge \frac34x_n$, and so by induction $x_n \ge (\frac34)^n x_0$. In other words, $y_n \le 1 - (\frac34)^n (1-y_0)$.

Of course you can start at $y_7$ (for example) instead of $y_0$ and get $y_n \le 1 - (\frac34)^{n-7} (1-y_7)$ for $n\ge7$; this will be helpful if your $y_0$ is not close to $1$—calculating $y_7$ by hand will be less wasteful than the above argument.

$\endgroup$
0
$\begingroup$

I ended up settling on the bound below. It's difficult to explain the metric I'm using for evaluating bounds (the "loss" of a bound is a function depending on some algorithmic construction I have), but the bound itself is rather straightforward to show.

The key insight is to consider the reparametrization $z_n = 1/y_n$. It's fairly straightforward to show that: $$z_n^2 = \frac{z_{n-1}^2 + z_{n-1}}{2}$$ Moreover, since we want an upper bound on $y_n$, we want a lower bound on $z_n$. Now, if you stare at this for an embarrassingly long time, you see that you can apply the AGM to it to get: $$z_n^2 \geq \sqrt{z_{n-1}^3}$$ From here, it's straightforward to show that $z_n \geq z_0^{(3/4)^n}$. Switching back to $y_n$, you get that $y_n \leq y_0^{(3/4)^n}$. As I said, this bound ends up being better for my particular purposes, and the difference is fairly stark. Compared to the "true values" I can compute explicitly, the results I can prove with my bound are around 35% weaker, but the other bound end up being around 200% weaker. This might very well be dependent on my particular purposes, so I'll mark the other answer as accepted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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