¿En qué momento el crecimiento exponencial de dominar el polinomio de crecimiento?

Question

Es bien sabido que el crecimiento exponencial finalmente alcanza el polinomio de crecimiento (enlace, enlace).

Así que para cualquier entero no negativo, $d$ positiva y $\epsilon$ existe $t^* \ge 0$ para los que

$$ 1 + t + \frac{t^2}{2!} + \ldots + \frac{t^d}{d!} \le e^{\epsilon t} $$

para todos los $t \ge t^*$.

En otras palabras, se requiere $t^*$ segundos para que la exponencial de ponerse al día con el polinomio.

Me gustaría saber si hay una forma cerrada de expresión para $t^*$ en términos de$d$$\epsilon$. Algo como

$$ t^* = d/\epsilon. $$

Los pensamientos?

Answer 1

En general no existe tal forma cerrada de expresión, pero de forma cerrada, los límites son posibles.

EDITAR: Por supuesto, si $\epsilon \ge 1$, la desigualdad se cumple para todos los $t \ge 0$, por lo que considere el caso en $0 < \epsilon < 1$. Voy a indicar el lado izquierdo como $M_d(t)$. Podemos considerar esto como $e^{t} \mathbb P[X \le d]$ donde $X$ es una variable aleatoria tener distribución de Poisson con parámetro de $t$. Ahora para cualquier $\mu > 0$, $$\mathbb P[X \le d] = \mathbb P\left[e^{-\mu X} \ge e^{-\mu d}\right] < e^{\mu d} \mathbb E\left[ e^{-\mu X}\right] = e^{\mu d} e^{-t + t \exp(-\mu)} $$ Por lo tanto basta $ \mu d + t \exp(-\mu) \le \epsilon t $, es decir, $\exp(-\mu) < \epsilon$ con $$ t \ge \dfrac{\mu d}{\epsilon-\exp(-\mu)}$$ No es la óptima, pero por ejemplo, podría tomar $\mu = -\ln(\epsilon/2)$, y, a continuación, el obligado es $$ t \ge \dfrac{2 d \ln(2/\epsilon)}{\epsilon} $$

Answer 2

Es suficiente para tomar $t^* = e(d+1)!/\epsilon^{d+1}$.

Prueba:

El lado izquierdo de la desigualdad es, en la mayoría de las $t^d/0! + t^d/1! + \cdots t^d/d! \le et^d$ (asumiendo $t\ge 1$ lo cual está bien).

El lado derecho de la desigualdad es, al menos,$(\epsilon t)^0/0! + \cdots + (\epsilon t)^{d+1}/(d+1)! \ge (\epsilon t)^{d+1}/(d+1)!$.

Por tanto, es suficiente si nos aseguramos de que $et^d \le (\epsilon t)^{d+1}/(d+1)!$. Pero esto es equivalente a $t\ge e(d+1)!/\epsilon^{d+1}$.

Con más esfuerzo que uno podría presumiblemente mejorar la dependencia de la $t^*$$d$$\epsilon$.