# Closed forms for Monotonic polynomial recurrences?

I have a monotonic polynomial recurrence of the following form: c_n = 1-p + p*(c_n-1)^2

This comes from the probability that a specific branching process (Galton-Watson) will be extinct before the nth generation. It's generalization is:

c_n = 1-p_1-p_2-...-p_n + p_1(c_n-1) + p_2(c_n-1)^2 + ... + p_n(c_n-1)^n

Where p_1*1+p_2*2+...+p_n*n < 1, and c_1 << 1;

I know that polynomial recurrences have no general solution, but the monotonic case seems like it should be MUCH easier. A basic approximation for my specific c_n is easily done: d_n = 1-c_n =1- (1-p + p*(1-c_n-1)^2) d_n = 2p*d_n-1 - p*(d_n-1)^2 < 2p*(d_n-1) = (2p)^(n-1)*(d_1);

A cobweb plot also gives strong indication of the behavior.

My problem is, however, that although asymptotic behavior is easy to figure out, I need to be able to determine, with a fair degree of accuracy, d_i for arbitrary i.

Is there any information out there on monotonic recurrences of polynomial form?

Update: Any sort of approximation that's more general and useful than mine is also useful to me. Also, I'm only interested in real numbers. For instance, d_1 in the specific case I'm looking at is p, where p is < 0.5. Looking at cobweb plot with y = x and y = 2p*x - p*x^2 = px(2 - x), it is clear that the recurrence is monotonic and has no chaotic behavior. Is this not a strong enough of a condition to give it a (somewhat) clean form? If so, why not?

-
I'm doubtful these things have nice closed forms for all p. Don't their dynamics generate Julia sets? –  Qiaochu Yuan Dec 24 '09 at 7:27

A lot depends of what you mean by "fair accuracy" and on what exactly you are going to do with your formula. If a 30% upside error in each $d_n$ is tolerable, you can do the following.

We look at the recursion $d_{n+1}=qd_n(1-d_n)$ with $0<q=2p<1$ starting with some $d_1\in[0,1]$. It'll be convenient to do the first step separately, so we have $d_2=q d_1(1-d_1)$. The reason is that $q^{-1}d_2\in[0,1/4]$. Now, denote $b_n=q^{-(n-1)}d_n$ and rewrite the recurrence as $b_{n+1}^{-1}=b_n^{-1}+q^{n-1}\frac{b_n}{b_{n+1}}$. Note now that the ratio of each term to the next is between $1$ and $4/3$ and tends to $1$, so, replacing it by $1$, we get $b_n^{-1}\approx b_2^{-1}+\frac{q-q^{n-1}}{1-q}$ with accuracy 30% and being sure that it is an underestimate. Putting all this stuff together, we get $$d_n\approx q^{n-1}\left[\frac 1{d_1(1-d_1)}+\frac{q-q^{n-1}}{1-q}\right]^{-1}$$ for $n\ge 2$.

Note also that 30% is a very rough estimate for the accuracy. In practice, I've never seen it being worse that 6% (though I haven't done too many simulations).

P.S. The estimate $$d_n\approx q^{n-1}\left[\frac 1{d_1(1-d_1)}+\frac{q-q^{n-1}}{1-q} +\log\left(1+d_1(1-d_1)\frac{q^2-q^{2(n-1)}}{1-q^2}\right)\right]^{-1}$$ is even better (3% accuracy for small $n$ and about 0.5% accuracy for large $n$) but noticeably uglier. As several people have already mentioned, there is no exact formula, so the higher precision you want, the longer and uglier the approximation gets.

P.P.S. The main idea behind the second approximation is that if $B_n=b_{n}^{-1}$, then we make an error $q^{n-1}\frac{B_{n+1}-B_n}{B_n}\approx \frac{q^{2(n-1)}}{B_n}$ during each step that led us to the first approximation. To compensate, we would like to take the partial sums of that series. We also know that $B_n\approx \frac 1{d(1-d)}+q+q^2+\dots+q^{n-2}$. Unfortunately, we cannot sum the resulting series nicely. But if we double all the exponents in the approximate formula for $B_n$ (which will lead only to a small error when $q\approx 1$), then we'll get the Riemann sum type expression, which we can replace by the corresponding integral. Clearly, it may overshoot on the long run but to my own surprise, it not only corrects the first few terms nicely, but also corrects the asymptotics giving an error below 0.5% for large $n$ in the entire range of parameters (well, at least that is so for all values I looked at and I tried quite a few). Why it works this way remains a mystery, but it does. It can be shown rigorously that the total relative overshot coming from all steps after $n$ is at most $n^{-1}$ and I've never seen the overshots of more than 0.1% up to $n=300$.

-
These approximations look like they might be just what I'm looking for. Could you give me a link to some resource that talks about how you can get things like the second approximation. Also, is it proven that there is no exact formula, or has it simply evaded researchers so far? –  DoubleJay Dec 26 '09 at 5:12
Unfortunately there is no link: it is just some ad-hoc thing resulting from my attempt to correct the obvious error in the first formula. I can explain why it has this particular shape, if you want, but that's about it. Note also that the second approximation is no longer a guaranteed estimate from above; for large $n$ it can be a bit below the true value. Also I haven't carried out the formal error analysis, so my 0.5% claim is based on numerical simulations. As to the exact formula, it should work for all $q$ simultaneously and the behavior for $q>1$ is incompatible with being elementary. –  fedja Dec 26 '09 at 18:28
A walkthrough of how you derived the correction would be great. The fact that it gives an asymptotic bound alone is terrific. Also, this is a complete shot in the dark, but do you know if continued fractions could be at all applicable (sorry if that's a silly question). –  DoubleJay Dec 26 '09 at 21:58
OK, I outlined briefly how I got it and why I believe it works. Now, if not a secret, why do you need a high precision elementary formula? I mean, the 6% error should be good enough for all theoretical purposes and for all practical purposes, you get a huge error just from knowing $q$ approximately (of course, if you need $b_n$ rather than $d_n$, it is a completely different story). –  fedja Dec 27 '09 at 3:14
Well, I'm actually trying to figure out an exact formula. The recurrence there represents the probability that a specific Galton-Watson process will have terminated by a given depth of its tree. knowing this, the expected height of the tree can be approximated. Your approximation indicates ways to generally approximate a much broader variety of Galton-Watson processes, and could have actual application in modeling population dynamics. Your method is also generally really interesting to me. I'd have been floudering with much cruder methods for a long time without this. Thank you! –  DoubleJay Dec 28 '09 at 6:10

In general as Qiaochu commented non-linear recurrences almost never have closed forms (your question included). On the other hand a lot can be said about your special recurrence. The substitution $d_n=\frac{1-c_n}{2}$ brings the recurrence in the form $$d_n=2pd_{n-1}(1-d_{n-1})$$

And this is known as the Logistic map

-
Do you know any literature or links about logistic map behavior for small r (i.e. = 1)? Everyone seems excited about r > 3, but I haven't seen anything for this special case. The general case of my recurrence will similarly be non-chaotic, so if there's a successful analysis of logistic map for r=1 out there, I hope it (and expect) that it can be applied to any the recurrence as a whole. –  DoubleJay Dec 24 '09 at 9:18