La convergencia de $np(n)$ donde $p(n)=\sum_{j=\lceil n/2\rceil}^{n-1} {p(j)\over j}$

Question

Hace algunos años yo estaba interesado en la siguiente cadena de Markov cuyo espacio de estado es de los enteros positivos. La cadena comienza en el estado "1", y del estado "n" la cadena de la siguiente salta a un estado uniforme seleccionados a partir de {n+1,n+2,...,2n}.

Como pasa el tiempo, esta cadena se extiende hacia el infinito, con ocasionales grandes saltos. En cualquier caso, la cadena es muy poco probable que golpeó a cualquier especialmente en los grandes n.

Si definimos p(n) la probabilidad de que esta cadena las visitas de estado "n", entonces p(n) tiende a cero como el c/n de algunos c constante. De hecho,

$$ np(n) \to c = {1\over 2\log(2)-1} = 2.588699. \tag1$$

Con el fin de demostrar esta convergencia, me refundición como una analítica problema. El uso de la propiedad de Markov, se puede ver que la secuencia satisface:

$$ p(1)=1\quad\mbox{ and }\quad p(n)=\sum_{\lceil n/2\rceil}^{n-1} {p(j)\over j}\mbox{ for }n>1. \tag2$$

Durante algunas semanas, mediante la generación de funciones, etc. He intentado y no ha podido encontrar una analítica de la prueba de la convergencia en (1). Finalmente, en una conferencia en 2003 Tom Mountford me mostró una (no trivial) probabilística de la prueba.

Por lo que el resultado es cierto, pero desde entonces he continuó pregunto si me he perdido algo obvio. Tal vez hay una técnica estándar para mostrar que (2) implica (1).

Pregunta: ¿hay un directo (corto?, analítica?) la prueba de (1)?

Tal vez alguien que entiende de las secuencias mejor que yo podría tomar una foto en esto.

Actualización: estoy cavando a través de mis viejas notas sobre este. Yo ahora recuerdo que tuve una prueba (mediante la generación de funciones) que si $\ np(n)$ converge, entonces el límite es de $1\over{2\log (2)-1}$. Fue la convergencia que huían de mí.

También encontré algunas curiosidades como: $\sum_{n=1}^\infty {p(n)\over n(2n+1)}={1\over 2}.$

Otra actualización: Aquí está el condicional resultado se mencionó anteriormente.

Como en Qiaochu la respuesta de definir $Q$ a la generación de la función de $p(n)/n$, es decir, $Q(t)=\sum_{n=1}^\infty {p(n)\over n} t^n$ $0\leq t<1$. La diferenciación de da $$Q^\prime(t)=1+{Q(t)-Q(t^2)\over 1-t}.$$ Esto es ligeramente diferente de la Qiaochu la expresión porque $p(n)\neq \sum_{j=\lceil n/2\rceil}^{n-1} {p(j)\over j}$ al $n=1$, de modo que $p(1)$ tiene que ser tratada por separado.

La diferenciación de nuevo y multiplicando por $1-t$, obtenemos $$(1-t)Q^{\prime\prime}(t)=-1+2\left[Q^\prime(t)-t Q^\prime(t^2)\right],$$ es decir, $$(1-t)\sum_{j=0}^\infty (j+1) p(j+2) t^j = -1+2\left[\sum_{j=1}^\infty (jp(j)) {t^j-t^{2j}\over j}\right].$$

Suponga que $\lim_n np(n)=c$ existe. Dejando $t\to 1$ por encima de la mano izquierda da $c$, mientras que el lado derecho es $-1+2c\log(2)$ y, por tanto,$c={1\over 2\log(2)-1}$.

Nota: $\sum_{j=1}^\infty {t^j-t^{2j}\over j}=\log(1+t).$

Nueva actualización: (Sept. 2)

He aquí una alternativa a la prueba de los condicional resultado de que mi colega Terry Gannon me mostró en 2003.

Empezar con la suma de $\sum_{n=2}^{2N}\ p(n)$, sustituir en la fórmula en el título, intercambio de las variables$j$$n$, y se reorganizan para establecer la identidad:

$${1\over 2}=\sum_{j=N+1}^{2N} {j-N\over j}\ {p(j)}.$$

Si $jp(j)\to c$, luego $1/2=\lim_{N\to\infty} \sum_{j=N+1}^{2N} {j-N\over j^2}\ c=(\log(2)-1/2)\ c,$ , de modo que $c={1\over 2\log(2)-1}$.

Nueva actualización: (Sept. 8) a Pesar de la agradable respuestas y discusión interesante a continuación, todavía estoy esperando por una (agradable?, corto?) la analítica de la prueba de convergencia. Básica Tauberian teoría está permitido :)

Nueva actualización: (Septiembre 13) he publicado un boceto de la probabilística de la prueba de convergencia bajo ", Un divertido y frustrante de la recurrencia de la secuencia" en la sección de "Publicaciones" de mi página de inicio.

Última Actualización: (15 de Septiembre) La fecha límite se acerca, así que ha decidido otorgar la recompensa a T.. Modulo los detalles(!), parece que el probabilístico es el enfoque más probable que conduzca a una prueba.

Mi más sincero agradecimiento a todos los que trabajaron en el problema, incluyendo a aquellos que lo he probado pero no publicar nada.

En un sentido, me hizo llegar una respuesta a mi pregunta: no parece ser fácil, o estándar prueba a manejar esta secuencia en particular.

Answer 1

Actualización: el siguiente argumento probabilístico yo había publicado anteriormente sólo muestra que $p(1) + p(2) + \dots + p(n) = (c + o(1)) \log(n)$, y no, como se había afirmado, la convergencia $np(n) \to c$. Hasta que la prueba está disponible [editar: George ha proporcionado una en otra respuesta] no está claro si $np(n)$ converge o tiene alguna oscilación, y por el momento no hay evidencia en ambas direcciones. Log-periódicas o de otros oscilación lenta, se sabe que se producen en algunos de los problemas que la recursividad de los accesos de muchos de los términos anteriores. En realidad, todo lo que se puede calcular en unos $np(n)$ es consistente con, y en algunos aspectos sugestivos de registro-fluctuaciones periódicas, con la convergencia de ser el caso especial donde los límites de alguna manera podría ser fortalecida y la fluctuación de la escala así reducida a cero.

---

$p(n) \sim c/n$ es [editar: sólo en promedio] equivalente a $p(1) + p(2) + \dots + p(n)$ asintótica $c \log(n)$. La suma de hasta $p(n)$ es el tiempo de espera de la caminata pasa en el intervalo [1,n]. Para esta cantidad no es una simple probabilístico argumento que explica (y se puede demostrar rigurosamente) la asymptotics.

Esta cadena de Markov es un discreto aproximación a una log-normal de paseo aleatorio. Si $X$ es la posición de la partícula a, $\log X$ se comporta como un simple paseo aleatorio con pasos $\mu \pm \sigma$ donde$\mu = 2 \log 2 - 1 = 1/c$$\sigma^2 = (1- \mu)^2/2$. Esto es cierto debido a que la cadena de Markov es acotada entre dos analizado fácilmente al azar camina con pasos continuos.

(Deje X ser la posición de la partícula y $n$ el número de pasos; el paseo se inicia en X=1, n=1.)

Límite inferior paseo $L$: en cada paso, multiplicar X por un número aleatorio uniforme en [1,2] y reemplazar n por (n+1). $\log L$ aumenta, en promedio, por $\int_1^2 log(t) dt = 2 \log(2) - 1$ a cada paso.

Cota superior de a pie $U$: en cada paso, salto de X para el uniforme número aleatorio en [X+1,2 X+1] y reemplazar n por (n+1).

$L$ $U$ tienen los medios y las desviaciones que son las mismas dentro de las $O(1/n)$, donde el $O()$ constantes pueden hacerse explícitas. Pasos de $L$ son yo.yo.d y pasos de $U$ son independientes, asintóticamente idénticas distribuidas. Por lo tanto, el teorema del Límite Central muestra que $\log X$ después $n$ pasos es de aproximadamente una Gaussiana con media de $n\mu + O(\log n)$ y la varianza $n\sigma^2 + O(\log n)$.

El número de pasos de la partícula para escapar del intervalo de $[1,t]$ por lo tanto $({\log t})/\mu$ con fluctuaciones de tamaño $A \sqrt{\log t}$ tener probabilidad de que se desintegra rápidamente en Un (delimitada por $|A|^p \exp(-qA^2)$ para el adecuado constantes). Por lo tanto, la suma de p(1) + p(2) + ... p(n) es asintóticamente equivalente a $(\log n)/(2\log (2)-1)$.

Tal vez esto es equivalente a la de 2003 argumento de la conferencia. Si el objetivo es obtener una prueba de la generación de función, sugiere que la división por $(1-x)$ puede ser útil para suavizar la p(n)'s.

Answer 2

Después de conseguir un poco de perspicacia mirando algunos cálculos numéricos para ver qué np(n)-c se parece a la gran n, ahora puedo describir la convergencia en algunos detalles. En primer lugar, los resultados de las simulaciones sugieren fuertemente la siguiente.

• para n impar, np(n) converge a c desde abajo en la tasa de O(1/n).
• para n es un múltiplo de 4, np(n) converge a c desde arriba en la tasa de O(1/n²).
• para n es un múltiplo de 2, pero no de 4, np(n) converge a c desde abajo en la tasa de O(1/n²).

Esto sugiere la siguiente forma asintótica para p(n). $$ p(n)=\frac{c}{n}\left(1+\frac{a_1(n)}{n}+\frac{a_2(n)}{n^2}\right)+o\left(\frac{1}{n^3}\right) $$ donde un₁(n) tiene periodo 2, con un₁(0) = 0, ₁(1) < 0 y₂(n) tiene período de 4 con₂(0) > 0 y₂(2) < 0. De hecho, podemos expandir p(n) a la orden arbitrario [Edit: en Realidad, no es del todo cierto. Ver más abajo] $$ \begin{array} {}p(n)=c\sum_{r=0}^s\frac{a_r(n)}{n^{r+1}}+O(n^{-s-2})&&(1) \end{array} $$ y el término de una_r(n) es periódica en n, con período 2^r. Aquí, me han normalizado un₀(n) a ser igual a 1.

Se pueden calcular todos los coeficientes en (1). Como p satisface la relación de recurrencia $$ \begin{array} \displaystyle p(n+1)=(1+1/n)p(n)-1_{\lbrace n\textrm{ even}\rbrace}\frac2np(n/2) -1_{\lbrace n=1\rbrace}.&&(2) \end{array} $$ podemos simplemente el tapón (1) en este, ampliar los términos de $(n+1)^{-r}=\sum_s\binom{-r}{s}n^{-r-s}$ en el lado izquierdo, y comparar los coeficientes de 1/n. $$ \begin{array} \displaystyle a_r(k+1)-a_r(k)=a_{r-1}(k)-\sum_{s=0}^{r-1}\binom{-s-1}{r-s}a_{s}(k+1)-1_{\lbrace k\textrm{ even}\rbrace}2^{r+1}a_{r-1}(k/2).&&(3) \end{array} $$ Dejar ā_r es el promedio de un_r(k) como k varía, podemos promedio (3) a través de k para obtener una relación de recurrencia para ā_r. Alternativamente, la función f(n) = Σ_r * _rn^-r-1 debe cumplir f(n+1) = (1+1/n)f(n) - f(n/2)/n el cual es resuelto por f(n) = 1/(n+1) = Σ_r≥0(-1)^rn^-r-1, así que tenemos ā_r = (-1)^r. A continuación, (3) puede ser aplicado de forma iterativa para obtener un_r(k+1)-_r(k) en términos de un_s(k) para s < r. Junto con ā_r, esto le da un_r(k) y se puede observar que el período de un_r(k) se duplica en cada paso. Hacer esto te da una_r ≡ (_r(0),...,_r(2^r-1)) de la siguiente manera $$ \begin{align} & a_0=(1),\\\\ & a_1=(0,-2),\\\\ & a_2=(7,-3,-9,13)/2 \end{align} $$ Estas de acuerdo con la simulación numérica se mencionó anteriormente.

---

Actualización: he intentado otra simulación numérica para la comprobación de estos asymptotics, sucesivamente, restando el líder en términos de orden. Usted puede ver converge perfectamente a los niveles de un₀, un₁, un₂ , pero, entonces...

... parece que después de un₂n^-3 parte, hay un resonador de plazo! No me esperaba eso, pero hay un asintótica del formulario cn^-rpecado(sobre+θ), donde se puede resolver a liderar el fin de obtener r ≈ 3.54536, una ≈ 10.7539.

---

Actualización 2: yo estaba re-pensar esta pregunta hace un par de días, y de repente se produjo cómo no sólo se puede demostrar que el uso de métodos analíticos, pero dan una completa expansión asintótica a la orden arbitrario. La idea consiste en algo muy fresco matemáticas! (si se me permite decirlo). Disculpas que esta respuesta ha crecido y crecido, pero creo que vale la pena. Es una pregunta muy interesante y he aprendido mucho por pensar en ello. La idea es que, en lugar de utilizar el poder de la serie de la generación de la función como en Qiaochu la respuesta de utilizar una de Dirichlet de la serie que puede ser invertida con la Escalinata de la fórmula. En primer lugar, la expansión es la siguiente, $$ \begin{array}{ccc} \displaystyle p(n)=\sum_{\Re[r]+k\le \alpha}a_{r,k}(n)n^{-r-k}+o(n^{-\alpha}),&&(4) \end{array} $$ para cualquier α. La suma es de más de números enteros no negativos k y números complejos r con parte real de al menos 1 y la satisfacción de r+1 = 2^r (el líder plazo, siendo r=1), y_r,k(n) es una función periódica de n, con un periodo de 2^k. La razón por la que los exponentes es que la diferencia de la ecuación (2) tiene el continuo límite de tiempo p'(x) = p(x)/x - p(x/2)/x, que tiene soluciones de p(x) = x^-r para, precisamente, tal exponentes. La división en partes real e imaginaria r = u+iv, todas las soluciones a r+1 = 2^r mentira en la línea (1+u)²+v² = 4^u y, otros que el principal término u=1, v=0, no es precisamente una solución compleja con parte imaginaria 2nn ≤ vlog2 ≤2nn+π/2 (entero positivo n) y, junto con los complejos conjugados, esta es una lista de todas las posibles exponentes r. Entonces, _r,k(n) es determinado (como un múltiplo de una_r,0) para k > 0 sustituyendo esta expansión de vuelta a la diferencia de la ecuación de como lo hice anteriormente. Llegué a esta expansión después de la ejecución de las simulaciones trazado sobre (y T..'s mención de los complejos de los exponentes de la n ayudaron). A continuación, el de la serie de Dirichlet idea clavado.

Definir el Dirichlet de la serie con los coeficientes de p(n)/n $$ L(s)=\sum_{n=1}^\infty p(n)n^{-1-s}, $$ que converge absolutamente para la parte real de s lo suficientemente grande (mayor que 0, ya que p está limitada por 1). Se puede observar que L(s) - 1 es de orden 2^-1-s en el límite de la parte real de s tiende a infinito. Multiplicando (2) por n^-s, y la suma de la expansión de n^-s en términos de (n+1)^-s en el lado izquierdo da la ecuación funcional $$ \begin{array} \displaystyle (s-1+2^{-s})L(s)=s+\sum_{k=1}^\infty(-1)^k\binom{-s}{k+1}(L(s+k)-1).&&(5) \end{array} $$ Esto se extiende a L a función de meromorphic en todo el plano complejo con simple polos precisamente en los puntos de r con la parte real de al menos uno y r+1 = 2^r, y, a continuación, a -r-k para los números enteros no negativos k. El polo con mayor componente real es en s = -1 y ha residuo $$ {\rm Res}(L,-1)={\rm Res}(s/(s-1+2^{s}),-1)=\frac{1}{2\log 2-1}. $$ Si podemos definir p'(n) por el truncado de expansión (4) para algunos adecuadamente grandes α, entonces se satisface la relación de recurrencia (2) hasta un término de error de tamaño S(n^-α-1) y su Dirichlet de la serie va a satisfacer la funcional de la ecuación (5) hasta un término de error que será una analítica de la función en R[s] > -α (siendo una de Dirichlet de la serie con los coeficientes de o(n^-α-1)). De ello se sigue que p' ha simple polos en los mismos lugares, como p en el dominio de R[s] > -α y, por la elección de un_r,0 adecuadamente, tendrá los mismos residuos. A continuación, el de la serie de Dirichlet asociados con p(n) = p'(n) - p(n) será la analítica en R[s] > -α podemos utilizar la Escalinata de la fórmula para demostrar que p(n) es de tamaño O(n^β) para cualquier β > -α y, haciendo α tan grande como nos gusta, este será el asintótica de expansión (4). Diferenciadas, Escalinata de la fórmula da $$ dQ(x)/dx = \frac{1}{2\pi i}\int_{\beta-i\infty}^{\beta+i\infty}x^sL(s)\,ds $$ donde Q(x) = Σ_n≤xp(n) y β > -α. Esta expresión es la intención de ser tomado en el sentido de las distribuciones (es decir, se multiplican ambos lados por una función suave con soporte compacto en (0,∞) e integrar). Si θ es una función suave de tamaño compacto en (0,∞), entonces $$ \begin{array} \displaystyle\sum_{n=1}^\infty q(n)\theta(n/x)/x&\displaystyle=\int_0^\infty\theta(y)\dot Q(xy)\,dy\\\\ &\displaystyle=\frac{1}{2\pi i}\int_{\beta-i\infty}^{\beta+i\infty}x^sL(s)\int\theta(y)y^s\,dy\,ds=O(x^\beta)\ \ (6) \end{array} $$ Obtenemos el final obligado, porque por integración por partes, la integral de θ(y)y^s puede ser demostrado para ir a cero más rápido que cualquier potencia de 1/s, por lo que el integrando es, de hecho, integrable y el x^β término puede ser tiró afuera. Esto es suficiente para demostrar que p(n) es de O(n^β). Tratando de terminar esta respuesta sin demasiado detalle, el argumento es como sigue. Si p(n)n^-β era ilimitado, a continuación, mantenga la superación de su máximo anterior y, por la relación de recurrencia (2), tomaría tiempo, al menos, Ω(n) para volver cerca de cero. Por lo tanto, si θ tiene soporte en [1,1+ε] para lo suficientemente pequeño ε, la integral de la $\int\theta(y)\dot Q(ny)\,dy$ será de orden q(n) en el momento y, como esto sucede infinitamente a menudo, contradiría (6). Ufff! Yo sabía que esto se podía hacer, pero tomó un poco de trabajo! Posiblemente no como simple o directo que estaban pidiendo, pero de Dirichlet de la serie son bastante estándar (más comúnmente en la teoría analítica de números, en mi experiencia). Sin embargo, tal vez no es realmente más difícil que el método de probabilidades y que te dan un montón de cosas más. Este enfoque debería funcionar también para otros tipos de relaciones de recurrencia y ecuaciones diferenciales.

Por último, he añadido una forma mucho más detallada valoración crítica en mi blog, a desarrollarse algunos de los detalles que me desnatada por aquí. Ver Expansiones Asintóticas de una Relación de Recurrencia.

Answer 3

Aquí es el estándar de generación de función gruntwork. Deje $Q(x) = \sum_{n \ge 1} \frac{p(n)}{n} x^n$. Entonces

$$Q'(x) = \sum_{n \ge 1} p(n) x^{n-1} = \sum_{n \ge 1}^{\infty} x^{n-1} \sum_{j = \lceil \frac{n}{2} \rceil}^{n-1} \frac{p(j)}{j}.$$

Intercambiando el orden de la suma de da

$$Q'(x) = \sum_{j=1}^{\infty} \frac{p(j)}{j} \sum_{n=j+1}^{2j} x^{n-1} = \sum_{j=1}^{\infty} \frac{p(j)}{j} \frac{x^{2j} - x^j}{x - 1}.$$

Por lo que se deduce que

$$Q'(x) = \frac{Q(x^2) - Q(x)}{x - 1}$$

con las condiciones iniciales $Q(0) = 0, Q'(0) = 1$.

Ahora, como creo recordar que hay teoremas en Flajolet y Sedgewick de la Analítica de la Combinatoria que nos permiten deducir comportamiento asintótico acerca de los coeficientes de $Q$ a partir de estos tipos de relaciones; voy a buscar uno por ahora, y en tanto que otros puedan ver lo que se puede hacer con esto.

Answer 4

Aquí está una observación: Se parece a $(2n) p(2n) - c$ converge a $0$ mucho más rápido que $(2n+1) p(2n+1)-c$. Aquí es un gráfico de los puntos de $(\log n, n p(n) -c)$, con puntos azules para$n$ hasta y rojo puntos para $n$ impar.

Podría ser más fácil de probar primero el resultado de $n$, incluso, a continuación, utilizar el hecho de que $(2n) p(2n) - (2n-1) p(2n-1) = p(2n) + p(2n-1)$ a que el par e impar de puntos debe tener el mismo límite.

Answer 5

Creo que estas observaciones son, probablemente, ya en otras respuestas, o incluso demasiado simple que se han enumerado, pero yo quería añadir mi trabajo de todos modos:

p(2n+2)=(n+1)/n(p(2n)-2p(n)/(2n+1))

por lo tanto, si k(n)= np(n)

k(2n+2)=(n+1)^2/n^2/(2n+1)((2n+1)k(2n)-4k(n))