Comportamiento asintótico de$a_{n+1}=\frac{a_n^2+1}{2}$

Question

Definir una secuencia como la siguiente: $$a_0=0$$ $$a_{n+1}=\frac{a_n^2+1}{2}$$ Me gustaría saber el comportamiento asintótico de $a_n$. Ya sé (por aproximadamente aproximar $a_n$ con una ecuación diferencial) que $$a_n\sim 1-\frac{2}{n}$$ como $n\to\infty$. Sin embargo, mi aproximación es muy crudo. ¿Cualquier persona puede encontrar un par de más términos? Espero (a partir de datos numéricos) que el siguiente término es algo como $\frac{\log(n)}{n^2}$.

En caso de que alguien quiera contexto de este problema, estoy tratando de encontrar la estrategia óptima para un juego con las siguientes reglas:

Hay $n$ ofertas de dinero, cuyos montos son oculto, y cuyas cantidades son al azar (de forma independiente y uniformemente distribuidos de $0$ a $1$). De una en una, las ofertas que se muestran a usted, y como a la vista de cada oferta, usted puede aceptarlo o rechazarlo. Una vez que usted acepta una oferta, el juego ha terminado y usted puede aceptar sin más ofertas.

Resulta que $a_n$ es el valor mínimo de la primera oferta para la que usted debe aceptar lo que ofrecen, en un juego con $n+1$ ofrece. Esta es la razón por la que estoy interesado en el comportamiento asintótico de $a_n$.

Answer 1

Escribir $a_n = 1 - \epsilon_n$ y el aviso de que $(\epsilon_n)$ soluciona

$$ \epsilon_{n+1} = \epsilon_n - \frac{\epsilon_n^2}{2}.$$

Para el propósito de uso en el futuro, nos permitir $\epsilon_0$ tomar cualquier valor en $(0, 1]$. Este tipo de secuencia es bien estudiado, y aquí es un método de extracción de asintótica formas hasta cierto orden en un arranque de forma.

1. Desde $0 \leq \epsilon_n \leq 1$ e $(\epsilon_n)$ es monótona decreciente, tenemos $\epsilon_n \to 0$ como $n\to\infty$.

2. Tenemos $ \frac{1}{\epsilon_{n+1}} - \frac{1}{\epsilon_n} = \frac{1}{2-\epsilon_n} $. Así que por Stolz–Cesàro teorema (un.k.una. L'Hospital del teorema de la secuencia),

   $$ \lim_{n\to\infty} \frac{1/\epsilon_n}{n} = \lim_{n\to\infty} \left(\frac{1}{\epsilon_{n+1}} - \frac{1}{\epsilon_n} \right) = 2.$$

   Esto demuestra que

   $$\epsilon_n = (1 + o(1))\frac{2}{n}. $$

3. Apoyando esta idea, se puede utilizar $ \frac{1}{\epsilon_{n+1}} - \frac{1}{\epsilon_n} = \frac{1}{2} + \frac{\epsilon_n}{2(2-\epsilon_n)} $. De nuevo, por Stolz–Cesàro teorema,

   $$ \lim_{n\to\infty} \frac{\frac{1}{\epsilon_n} - \frac{n}{2}}{\log n} = \lim_{n\to\infty} \frac{\frac{1}{\epsilon_{n+1}} - \frac{1}{\epsilon_n} - \frac{1}{2}}{\log (n+1) - \log n} = \frac{1}{2}, $$

   y así, $\frac{1}{\epsilon_n} = \frac{n}{2} + \frac{1 + o(1)}{2}\log n$. Esto a su vez implica

   $$ \epsilon_n = \frac{2}{n} - (2 + o(1)) \frac{\log n}{n^2}. $$

4. Finalmente, por escrito

   \begin{align*} \frac{1}{\epsilon_{n+1}} - \frac{1}{\epsilon_n} &= \frac{1}{2} + \frac{1}{2(n+1)} + \underbrace{\left( \frac{\epsilon_n}{2(2-\epsilon_n)} - \frac{1}{2(n+1)} \right)}_{=\mathcal{O}(n^{-2})}, \\ \end{align*}

   obtenemos

   \begin{align*}\frac{1}{\epsilon_n} &= \frac{1}{\epsilon_0} + \frac{n}{2} + \frac{H_n}{2} + \sum_{k=0}^{n-1} \left( \frac{\epsilon_k}{2(2-\epsilon_k)} - \frac{1}{2(k+1)} \right) \\ &= \frac{n}{2} + \frac{H_n}{2} + C\left(\epsilon_0\right) + \mathcal{O}_{\epsilon_0}\left(\frac{1}{n}\right). \tag{*} \end{align*}

   Aquí, $H_n = \sum_{k=1}^{n} \frac{1}{k}$ es el número armónico y $C(\epsilon_0)$ es una constante que depende sólo de $\epsilon_0$. También, el implícito obligado de $\mathcal{O}_{\epsilon_0}$ sólo depende de $\epsilon_0$. Por otra parte, $C(\cdot)$ admite una agradable propiedad. Deje $f(x) = x-x^2/2$ , de modo que $\epsilon_{n+1} = f(\epsilon_n)$. Entonces

   $$ C(x) = \frac{1}{\epsilon_0} + \sum_{k=0}^{\infty} \left( \frac{f^{\circ k}(x)}{2(2-f^{\circ k}(x))} - \frac{1}{2(k+1)} \right), $$

   donde $f^{\circ k}$ indica el $k$-función de plegado composición de $f$ junto con $f^{\circ 0} = \mathrm{id}$. A continuación, $\text{(*)}$ puede ser recrea

   $$ \frac{1}{f^{\circ n}(x)} = \frac{n}{2} + \frac{H_n}{2} + C(x) + \mathcal{O}_{x}\left(\frac{1}{n}\right). $$

   Luego de ello se sigue que

   \begin{align*} 0 &= \frac{1}{f^{\circ (n+1)}(x)} - \frac{1}{f^{\circ (n+1)}(x)} \\ &= \left( \frac{n+1}{2} + \frac{H_{n+1}}{2} + C(x) + \mathcal{O}\left(\frac{1}{n}\right) \right) - \left( \frac{n}{2} + \frac{H_n}{2} + C(f(x)) + \mathcal{O}\left(\frac{1}{n}\right) \right), \end{align*}

   y dejando $n\to\infty$ da

   $$ C(f(x)) = C(x) + \frac{1}{2}. $$

Resumiendo,

Deje $(\epsilon_n)$ ser una secuencia que resuelve $\epsilon_{n+1} = f(\epsilon_n)$, donde $\epsilon_0 \in (0, 1]$ e $f(x) = x - x^2/2$. Entonces existe una función de $C : (0, 1] \to \mathbb{R}$ tales que

$$ \frac{1}{\epsilon_n} = \frac{n}{2} + \frac{H_n}{2} + C(x) + \mathcal{O}_x\left(\frac{1}{n}\right), $$

y así,

$$ \epsilon_n = \frac{2}{n} - \frac{2H_n}{n^2} - \frac{4C(x)}{n^2} + \mathcal{O}_x\left( \frac{\log^2 n}{n^3} \right). $$

Por otra parte, $C$ resuelve $C(f(x)) = C(x) + \frac{1}{2}$.