¿Resolver una recurrencia para una probabilidad?

Question

Me encontré con la siguiente relación de recurrencia cuando se exploran las propiedades de un determinado tipo de aleatorizado perfecto árbol binario:

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

(En concreto, esto es la probabilidad de que un azar, completa árbol binario de altura $k$ con valores en las hojas y en el que cada nodo interno es una compuerta NAND evaluará a 1.)

Yo era capaz de obtener los valores de esta recurrencia por escrito una rápida secuencia de comandos de Python y se encontró que rápidamente se pone a oscilar entre valores muy cercanos a 0, y el 1 $k$ se hace grande. Sin embargo, no tengo una forma cerrada de la expresión para la recurrencia.

Nunca he encontrado una recurrencia como este antes de que (la mayoría de las recurrencias sé de venir a partir del análisis de algoritmos recursivos o estructuras de datos, que rara vez tienen términos cuadrados surgir). Existe una técnica estándar para la resolución de recurrencias de este tipo? Si es así, ¿cómo puedo utilizarlos para resolver esta recurrencia?

Gracias!

Answer 1

Las recurrencias no lineales son notoriamente difíciles de resolver ya veces muy sorprendentemente complejas (ver mapa logístico ).

En este caso, el comportamiento limitante se puede adivinar escribiendo la recursión en dos pasos:

ps

y, debido a que la gráfica$$x_{n+2} = x_n^2 \, (2 -x_n^2)$ está estrictamente por debajo de$y=x^2(2-x^2)$ para$y=x$ la recursión va a cero (esto implica que$x\in [0,1/2]$ tenderá a 1 para% #%).

Answer 2

De hecho, es la logística mapa!

Definir $\displaystyle{T\left(n\right) \equiv \mu\left(x_{n} - {1 \over 2}\right)}$ donde $\displaystyle{\mu \in {\mathbb R}}$ es una constante a determinar. $\displaystyle{x_{0} = {1 \over 2}\left(1 + {1 \over \mu}\right)}$. Entonces

$$ \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}$ tal que $\displaystyle{\mu_{\pm} = 1 \pm \sqrt{\,5\,}}$. Elegimos $\displaystyle{\mu = 1 + \sqrt{\,5\,}}$. Finalmente

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

Mediante el uso de propiedades ya conocidas de la Logística Mapa usted puede encontrar muchas propiedades interesantes de su sistema. Con los parámetros indicados anteriormente, $\displaystyle{T\left(n\right)}$ converge a 2 valores: $0$ $1$ que son puntos fijos. Además, $\displaystyle{\sqrt{\,5\,} - 1 \over 2}$ es otro punto fijo, además de la negativa de punto fijo $\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} $$