Asintótica diferencia entre una función y su binomio promedio

Question

El origen de esta pregunta es la identidad $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ donde $H_n$ $n$ésimo número armónico.

Dividiendo por $2^n$, tenemos $$2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = H_n - \sum_{k=1}^n \frac{1}{k 2^k}.$$

La suma de la izquierda ahora pueden ser interpretados como un promedio ponderado de la serie de los números a través de $H_n$ -- donde los pesos, por supuesto, son los coeficientes binomiales. Así, la diferencia entre el$H_n$, y el "binomio promedio" (supongo que no hay plazo para ello) es $$H_n - 2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = \sum_{k=1}^n \frac{1}{k 2^k}.$$

La suma de la derecha es conocido a converger a$\ln 2$$n \to \infty$. (Sustituto $-\frac{1}{2}$ en la serie de Maclaurin para $\ln (1+x)$.)

Esto me lleva a mi pregunta:

Podemos clasificar no negativo de las funciones de $f(n)$ para los que $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right)$$ es finito y distinto de cero?

Parecería que si $f$ aumenta con la suficiente rapidez, a continuación, el límite sería de $\infty$. Este es el caso con tanto $f(n) = a^n$$f(n) = n$. Si $f$ decrece o es constante, entonces el límite es cero. Si $f$ tiene básicamente logarítmica de crecimiento, luego parece que el límite podría comportarse como $H_n$. Pero esto puede ser demostrado? ¿Y qué acerca de otros sublinear, el aumento de las funciones?

Answer 1

La función de $f(n)$ debe $\Theta (\log n)$. Actualización: Como Didier Piau señala en los comentarios a la pregunta después de que me dijeran en Matemáticas de Desbordamiento, podemos decir algo más fuerte: $\frac{f(n)}{\log_2 n} \to L$$n \to \infty$. Ver la actualización en el fin de la discusión.

Supongamos que, para algunos positivos $L$ (en el caso negativo es similar), $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right) = L.$$ Así $$f(n) = L + r(n) + 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k)$$ for some function $r(n)$ such that $r(n) \a 0$ as $n \to \infty$. This gives us a recurrence relation for $f(n)$. Since $r(n) \a 0$, $L + r(n) > 0$ for all sufficiently large $n$. So, for all sufficiently large $n$, there exist positive constants $C$ and $D$ such that $C < L + r(n) < D$. Since the initial terms in the function eventually become negligible in determining the value of $f(n)$ via the recurrence relation, there exist functions $g(n)$ and $h(n)$ such that for all sufficiently large $n$, $g(n) \leq f(n) \leq h(n)$ and $g(n)$ and $h(n)$ satisfacer $$g(n) = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} g(k),$$ $$h(n) = D + 2^{-n} \sum_{k=0}^n \binom{n}{k} h(k).$$

Así el problema se reduce a mostrar que la $g(n)$$h(n)$$\Theta (\log n)$. El argumento es el mismo para ambos.

Hay algunas maneras diferentes de hacer esto; mi favorita es la de interpretar la $g(n)$ recurrencia probabilísticamente. Supongamos que comenzamos en el tiempo $g(0)$, lanzamos una serie de $n$ monedas simultáneamente en cada ronda, y se tarda $C$ unidades de tiempo para hacer una ronda de lanzamientos. Cuando una moneda se convierte cara por primera vez, dejamos de darle. Deje $T(n)$ a ser el momento en que la última moneda para lograr su primer jefe. Para encontrar $E[T(n)]$, condición en la que el número de monedas que lograr cabezas en la primera ronda de lanzamientos. Este rendimientos $$E[T(n)] = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} E[T(n-k)] = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} E[T(k)].$$ Thus $g(n) = E[E(n)]$.

Otra forma de ver el $T(n)$ es que el es $g(0) + C M_n$ donde $M_n = \max\{X_1, X_2, \ldots, X_n\}$ e las $X_i$'s son independientes e idénticamente distribuidas geométricas $(1/2)$ variables aleatorias. (Cada variable aleatoria geométrica de los modelos de la primera vez que un jefe). Por lo tanto $g(n) = g(0) + C E[M_n]$. Se sabe que $\frac{H_n}{\log 2} \leq E[M_n] \leq \frac{H_n}{\log 2} + 1$ y, más precisamente, que se $E[M_n]$ es de forma logarítmica summable a $\frac{H_n}{\log 2} + \frac{1}{2}$. (Véase, por ejemplo, Bennett Eisenberg del papel "En la expectativa de que el máximo de IID geométricas variables aleatorias," la Estadística y la Probabilidad Letras 78 (2008) 135-143. Ver también este MO pregunta, "¿Cuál es el Máximo Esperado de una Muestra (tamaño de la $n$) a partir de una Distribución Geométrica?")

Por lo tanto $g(n) = \frac{C}{\log 2} \log n + O(1)$, lo que significa que $h(n) = \frac{D}{\log 2} \log n + O(1)$$f(n) = \Theta (\log n)$.

Actualización: Dado $\epsilon > 0$, si tomamos $C > 0$ tal que $L - \epsilon \leq C < L$$D = L + \epsilon$, este argumento muestra que $$L - \epsilon + O\left(\frac{1}{\log n}\right) \leq \frac{f(n)}{\log_2 n} \leq L + \epsilon + O\left(\frac{1}{\log n}\right).$$

Por lo tanto, como $n \to \infty$, $\frac{f(n)}{\log_2 n} \to L.$

Para algunas otras ideas que se refieren a este resultado, incluyendo lo que efectivamente son algunas alternativas derivaciones, ver Pradipta reciente MO pregunta, "Moneda de mover de un Tirón y una Recurrencia de la Relación". De hecho, la lectura de Pradipta de la cuestión y algunas de sus respuestas me dio las ideas necesarias para la construcción de este argumento! Así, gracias a Pradipta, Didier Piau, Emil Jeřábek, y Louigi Addario-Berry.

Answer 2

He aquí una idea que podría llevar a alguna parte. Deje $F(x) = \sum_{n \ge 0} \frac{f(n)}{n!} x^n$, vamos a $g(n) = \frac{1}{2^n} \sum_{k=0}^{n} {n \choose n-k} f(k)$, y deje $G(x) = \sum_{n \ge 0} \frac{g(n)}{n!} x^n$. Entonces no es difícil ver que $G(x) = e^{\frac{x}{2}} F \left( \frac{x}{2} \right)$, por lo que estamos buscando funciones de $F$ tal que

$$F(x) - e^{\frac{x}{2}} F \left( \frac{x}{2} \right) = A(x)$$ para algunos $A(x)$ con coeficientes de Taylor tendiendo a una cierta distinto de cero en el límite. Deje $H(x) = e^x F(x)$. Ahora queremos $$H(x) - H \left( \frac{x}{2} \right) = e^{-x} A(x).$$

Esta condición es más fácil trabajar con la izquierda, pero ahora más difícil de trabajar en la derecha.

Answer 3

Una forma muy rápida y aproximada de enfoque:

Me parece probable que el particular pesos en el cálculo no son importantes, que las cosas iban a ser similar con un (por ejemplo) uniforme de promedio. En este supuesto, en el continuo, una simple analogía sería

$\displaystyle \lim_{x \to \infty } f(x) -\frac{\int_0^x f(x) dx }{x} = \lim_{x \to \infty }f(x) - \frac{F(x)}{x} = k \hspace{1cm}$ $f(x) >0 $ $0 <k <\infty$

Y $f(x) = a \log(x) + b $ (o de cualquier función que crece logarítmicamente) se ajusta a la ley. Y, en particular, la serie de los números, crece de esta manera.