Solving a recurrence for a probability?

Question

I came across the following recurrence relation when exploring properties of a certain type of randomized perfect binary tree:

$$ T(0) = \frac{1}{2} $$ $$ T(k + 1) = 1 - T(k)^2 $$

(Specifically, this is the probability that a random, complete binary tree of height $k$ with values at the leaves and where each internal node is a NAND gate will evaluate to 1.)

I was able to get values for this recurrence by writing a quick Python script and found that it quickly starts to oscillate between values very close to 0 and 1 once $k$ gets large. However, I don't have a closed-form expression for the recurrence.

I have never encountered a recurrence like this one before (most recurrences I know of come from the analysis of recursive algorithms or data structures, which rarely have squared terms arise). Is there a standard technique for solving recurrences of this sort? If so, how can I use them to solve this recurrence?

Thanks!

Answer 1

Nonlinear recurrences are notoriously difficult to solve and sometimes quite surprisingly complex (see logistic map).

In this case, the limiting behaviour can be guessed by writing the two-step recursion:

$$x_{n+2} = x_n^2 \, (2 -x_n^2)$$

and, because the graph $y=x^2(2-x^2)$ is strictly below $y=x$ for $x\in [0,1/2]$ the recursion goes to zero (of course, this implies that $x_n$ will tend to 1 for odd $n$).

Answer 2

Indeed, it's the logistic map!

Define $\displaystyle{T\left(n\right) \equiv \mu\left(x_{n} - {1 \over 2}\right)}$ where $\displaystyle{\mu \in {\mathbb R}}$ is a constant to be determined. $\displaystyle{x_{0} = {1 \over 2}\left(1 + {1 \over \mu}\right)}$. Then

$$ \mu\left(x_{n + 1} - {1 \over 2}\right) = 1 - \left\lbrack\mu\left(x_{n} - {1 \over 2}\right)\right\rbrack^{2} = 1 - {1 \over 4}\,\mu^{2} + \mu^{2}x_{n}\left(1 - x_{n}\right) $$

$$ x_{n + 1} = {1 \over 2} + {1 \over \mu} - {1 \over 4}\,\mu + \mu x_{n}\left(1 - x_{n}\right) $$

Set $\displaystyle{{1 \over 2} + {1 \over \mu} - {1 \over 4}\,\mu = 0}$ such that $\displaystyle{\mu_{\pm} = 1 \pm \sqrt{\,5\,}}$. We choose $\displaystyle{\mu = 1 + \sqrt{\,5\,}}$. Finally

$$ \left\lbrace% \begin{array}{rcl} \\[3mm]&& \\ x_{n + 1} & = & \mu\,x_{n}\left(1 - x_{n}\right) \\[4mm] \mu & = & 1 + \sqrt{\,5\,} \approx 3.2360679775 \\[4mm] x_{0} & = & {1 \over 2}\,\left(1 + {1 \over \mu}\right) = {3 + \sqrt{\,5\,} \over 8} \approx 0.65450849718 \\[4mm] T\left(n\right) & = & \mu\left(x_{n} - {1 \over 2}\right) \quad\Longrightarrow\quad -\,{1 \over 2}\,\mu <\ T\left(n\right)\ < {1 \over 2}\,\mu \\[3mm]&& \end{array}\right. $$

By using well known properties of the Logistic Map you can find many interesting properties of your system. With the parameters given above, $\displaystyle{T\left(n\right)}$ converges to 2 values: $0$ and $1$ which are fixed points. In addition, $\displaystyle{\sqrt{\,5\,} - 1 \over 2}$ is another fixed point besides the negative fixed point $\displaystyle{-\,{\sqrt{\,5\,} + 1 \over 2}}$.

$$ \begin{array}{rcl} T(0) & = & 0.5\\ T(1) & = & 0.75\\ T(2) & = & 0.4375\\ T(3) & = & 0.808594\\ T(4) & = & 0.346176\\ T(5) & = & 0.880162\\ T(6) & = & 0.225315\\ T(7) & = & 0.949233\\ T(8) & = & 0.0989562\\ T(9) & = & 0.990208\\ T(10) & = & 0.0194888\\ T(11) & = & 0.99962\\ T(12) & = & 0.00075948\\ T(13) & = & 0.999999\\ T(14) & = & 1.15362e-06\\ T(15) & = & 1\\ T(16) & = & 2.66151e-12\\ T(17) & = & 1\\ T(18) & = & -1.79638e-16 \end{array} $$