Asintótica de una función tipo número Bernoulli

Question

Tony Lezard me hizo la siguiente pregunta, que parece que no debería ser demasiado difícil, pero que no vi inmediatamente cómo responder. Defina $f(n,k)$ recursivamente por $f(1,k) = 1$ y

$$f(n,k) = \frac{1}{1-(1-1/k)^n} \sum_{r=1}^{n-1} \binom{n}{r} \left(\frac{1}{k}\right)^{n-r} \left(1 - \frac{1}{k}\right)^r f(r,k).$$

¿Qué podemos decir sobre $\lim_{n\to\infty} f(n,k)$ ? Incluso el caso especial $k=2$ sería interesante:

$$f(n,2) = \frac{1}{2^n-1} \sum_{r=1}^{n-1} \binom{n}{r} f(r,2).$$

Answer 1

[ Revisado y ampliado para dar la respuesta para todos $k>1$ e incorporar más términos de una expansión asintótica como $n \rightarrow \infty$ ]

Arreglar $k>1$ y escribir $a_1=f(1,k)=1$ y $$ a_n = f(n,k) = \frac1{1-q^{-n}} \sum_{r=1}^{n-1} {n \choose r} (1/k)^{n-r} (1/q)^r a_r \phantom{for}(n>1), $$ donde $q := k/(k-1)$ Así que $(1/k) + (1/q) = 1$ . Establecer $$ a_\infty := \frac1{k \log q}. $$ Por ejemplo, si $k=2$ entonces $a_\infty = 1 / \log 4 = 0.72134752\ldots$ , que $a_n$ parece acercarse para grandes $n$ y lo mismo para $k=6$ (el caso del lanzamiento de dados) con $a_\infty = 1/(6 \log 1.2) = 0.9141358\ldots$ . De hecho, como $n \rightarrow \infty$ tenemos " $a_n \rightarrow a_\infty$ por término medio", en el sentido de que (por ejemplo) $\sum_{n=1}^N (a_n/n) \sim a_\infty \phantom. \sum_{n=1}^N (1/n)$ como $N \rightarrow \infty$ . Pero, como sugieren las respuestas respuestas publicadas a la pregunta de Tim Chow, $a_n$ no converge, aunque se mantiene bastante cerca de $a_\infty$ Tenemos $$ a_n = a_\infty + \epsilon^{\phantom.}_0(\log_q n) + O(1/n) $$ como $n \rightarrow \infty$ , donde $\epsilon^{\phantom.}_0$ es una función suave función del periodo $1$ cuya media sobre ${\bf R} / {\bf Z}$ desaparece pero no es idénticamente cero; para grandes $k$ (ya $k=2$ es lo suficientemente grande suficiente), $\epsilon^{\phantom.}_0$ es una onda sinusoidal casi perfecta con una amplitud ínfima $\exp(-\pi^2 k + O(\log k))$ , a saber $$ \frac2{k\log q}\left|\phantom.\Gamma\bigl(1 + \frac{2\pi i}{\log q}\bigr)\right| \phantom.=\phantom. \frac2{k \log q} \left[\frac{(2\pi^2/ \log q)}{\sinh(2\pi^2/ \log q)}\right]^{1/2}. $$ Por ejemplo, para $k=2$ la amplitud es $7.130117\ldots \cdot 10^{-6}$ , de acuerdo con la observación numérica (véanse las respuestas publicadas anteriormente y el gráfico de abajo). Para $k=6$ la amplitud es sólo $8.3206735\ldots \cdot 10^{-23}$ por lo que hay que calcular mucho más allá de la "doble precisión" habitual para ver las oscilaciones.

Más concretamente, existe una expansión asintótica $$ a_n \sim a_\infty + \epsilon^{\phantom.}_0(\log_q n) + n^{-1} \epsilon^{\phantom.}_1(\log_q n) + n^{-2} \epsilon^{\phantom.}_2(\log_q n) + n^{-3} \epsilon^{\phantom.}_3(\log_q n) + \cdots, $$ donde cada $\epsilon^{\phantom.}_j$ es una función suave del periodo $1$ cuya media sobre ${\bf R} / {\bf Z}$ desaparece, y - aunque la serie no tiene por qué converger - truncándola antes del término $n^{-j} \epsilon^{\phantom.}_j(\log_q n)$ se obtiene una buena aproximación con una precisión de $O(n^{-j})$ . Los primeros $\epsilon^{\phantom.}_j$ siguen teniendo amplitudes exponencialmente pequeñas pero mayores que las de $\epsilon^{\phantom.}_0$ por un factor $\sim C_j k^{2j}$ para algunos $C_j > 0$ por ejemplo, la amplitud de $\epsilon^{\phantom.}_1$ supera a la de $\epsilon^{\phantom.}_0$ por cerca de $2(\pi / \log q)^2 \sim 2 \pi^2 k^2$ . Así que $a_n$ debe ser calcular hasta un múltiplo algo grande de $k^2$ antes de que sea experimentalmente plausible que la oscilación residual $a_n - a_\infty$ no tenderá a cero en el límite como $n \rightarrow \infty$ .

Aquí hay un gráfico que muestra $a_n$ para $k=2$ (así también $q=2$ ) y $2^6 \leq n \leq 2^{13}$ y se compara con la aproximación periódica $a_\infty + \epsilon^{\phantom.}_0(\log_q n)$ y la aproximación refinada $a_\infty + \sum_{j=0}^2 n^{-j} \epsilon^{\phantom.}_j(\log_q n)$ . (Ver http://math.harvard.edu/~elkies/mo11255+.pdf para el gráfico original en PDF, que se puede "ampliar" para ver los detalles). La página web coordenada horizontal es $\log_2 n$ la coordenada vertical está centrada en $a_\infty = 1/(2 \log 2)$ , mostrando también las líneas $a_\infty \pm 2|a_1|$ ; negro en forma de cruz, que finalmente se funden visualmente en una curva continua, muestran los valores numéricos de $a_n$ y los contornos rojo y verde muestran las aproximaciones suaves.

Para obtener esta expansión asintótica, empezamos por generalizar la fórmula de R.Barton de $k=2$ a la arbitrariedad $k>1$ : $$ a_n = \frac1k \sum_{r=0}^\infty \phantom. n q^{-r} (1-q^{-r})^{n-1}. $$ [La prueba es la misma, pero nótese el exponente $n$ se ha corregido a $n-1$ ya que queremos $n-1$ jugadores eliminados en el $r$ -en el paso, no todos $n$ ; esto no afecta al comportamiento limitador $a_\infty+\epsilon^{\phantom.}_0(\log_q n)$ pero es necesario para conseguir $\epsilon^{\phantom.}_m$ derecho a $m>1$ .] Nos gustaría aproximar la suma por una integral, que puede ser evaluada por el cambio de variable $q^{-r} = z$ : $$ \frac1k \int_{r=0}^\infty \phantom. n q^{-r} (1-q^{-r})^{n-1} = \frac1{k \log q} \int_0^1 \phantom. n (1-z)^{n-1} dz = \left[-a_\infty(1-z)^n\right]_{z=0}^1 = a_\infty. $$ Pero hay que hacer un esfuerzo para llegar al error de esta aproximación.

Comenzamos comparando $(1-q^{-r})^{n-1}$ con $\exp(-nq^{-r})$ : $$ \begin{eqnarray} (1-q^{-r})^{n-1} &=& \exp(-nq^{-r}) \cdot \exp \phantom. [nq^{-r} + (n-1) \log(1-q^{-r})] \cr &=& \exp(-nq^{-r}) \cdot \exp \left[q^{-r} - (n-1) \left( \frac{q^{-2r}}2 + \frac{q^{-3r}}3 + \frac{q^{-4r}}4 + \cdots \right) \right]. \end{eqnarray} $$ Los dos pasos siguientes requieren una justificación (como señaló R.Barton para los pasos correspondientes al final de su análisis), pero la justificación debería ser sencilla. Ampliar el segundo factor en potencias de $u := nq^{-r}$ y recoger los poderes similares de $n$ , obteniendo $$ \exp(-nq^{-r}) \cdot \left( 1 - \frac{u^2-2u}{2n} + \frac{3u^4-20u^3+24u^2}{24n^2} - \frac{u^6-14u^5+52u^4-48u^3}{48n^3} + - \cdots \right). $$ Cada trimestre $n^{-j} \epsilon_j(\log_q(n))$ ( $j=0,1,2,3,\ldots$ ) surgirá de la $n^{-j}$ término en esta expansión.

Comenzamos con el término principal, para $j=0$ , que es el único que no decae con $n$ . Definir $$ \varphi_0(x) := q^x \exp(-q^x), $$ que como observó Reid decae rápidamente tanto como $x \rightarrow \infty$ y como $x \rightarrow -\infty$ . Nuestra aproximación de orden cero a $a_n$ es $$ \frac1k \sum_{r=0}^\infty \phantom. \varphi_0(\log_q(n)-r), $$ que como $n \rightarrow \infty$ se acerca rápidamente $$ \frac1k \sum_{r=-\infty}^\infty \varphi_0(\log_q(n)-r). $$ Para $k=q=2$ Esto es equivalente a la fórmula de Reid para $R(n)$ , aunque lo escribió en términos de la parte fraccionaria de $\log_2(n)$ , porque la suma es claramente invariante bajo la traslación de $\log_q(n)$ por números enteros.

A continuación aplicamos la suma de Poisson. Como $\sum_{r \in {\bf Z}} \phantom. \varphi_0(t+r)$ es un suave ${\bf Z}$ -función periódica de $t$ tiene una expansión de Fourier $$ \sum_{m\in{\bf Z}} \phantom. c_m e^{2\pi i m t} $$ donde $$ c_m = \int_0^1 \left[ \sum_{r \in {\bf Z}} \phantom. \varphi_0(t+r) \right] \phantom. e^{-2\pi i m t} dt = \int_{-\infty}^\infty \varphi_0(t) \phantom. e^{-2\pi i m t} dt = \hat\varphi_0(-m). $$ Cambiando la variable de integración de $t$ a $q^t$ nos permite reconocer la transformada de Fourier $\hat\varphi$ como $1/\log(q)$ por una integral Gamma: $$ \hat\varphi_0(y) = \frac1{\log q} \Gamma\Bigl(1 + \frac{2 \pi i y} {\log q}\Bigr). $$ Esto nos da los coeficientes $a_m$ en forma cerrada. El coeficiente constante $a_0 = 1 / (\log q)$ puede interpretarse de nuevo como la aproximación de la suma de Riemann $\sum_{r \in {\bf Z}} \phantom. \varphi_0(t+r)$ por una integral; los términos oscilantes $a_m e^{2\pi i m t}$ para $m \neq 0$ son las correcciones de esta aproximación, y son pequeñas debido a la exponencial de la función Gamma en las franjas verticales - de hecho podemos calcular la magnitud $|a_m|$ en forma cerrada elemental utilizando la fórmula $|\Gamma(1+i\tau)| = (\pi\tau / \sinh(\pi\tau))^{1/2}$ . Así que tenemos $$ \frac1k \sum_{r \in \bf Z} \phantom. \varphi_0(\log_q(n)-r) = \frac1k \sum_{m \in \bf Z} \phantom. \hat\varphi_0(-m) e^{2\pi i \log_q(n)} = a_\infty + \epsilon_0(\log_q(n)) $$ donde $a_\infty = a_0 / k = 1 / (k \log q)$ como en el caso anterior, y $\epsilon^{\phantom.}_0$ definido por $$ \epsilon^{\phantom.}_0(t) = \left[ \sum_{r\in\bf Z} \phantom. \varphi_0(t+r) \right] - a_\infty, $$ tiene la serie de Fourier $$ \epsilon^{\phantom.}_0(t) = \frac1k \sum_{m \neq 0} \hat\varphi_0(-m) e^{2\pi i m t}. $$ Tomando $m = \pm 1$ recupera la amplitud $2|a_1|/k$ expuesta arriba; el $m = \pm 2$ y los términos posteriores producen oscilaciones más rápidas pero más pequeñas, por ejemplo, para $k=2$ el $m=\pm 2$ términos oscilan el doble de rápido pero con amplitud sólo $6.6033857\ldots \cdot 10^{-12}$ .

Las funciones $\epsilon^{\phantom.}_j$ que aparecen en los términos adicionales $n^{-j} \epsilon^{\phantom.}_j(\log_q(n))$ de la expansión asintótica de $a_n$ se definen de forma similar por $$ \epsilon^{\phantom.}_j(t) = \frac1k \sum_{r\in\bf Z} \phantom. \varphi_j(t+r), $$ donde $$ \varphi_j(x) = P_j(q^x) \varphi_0(x) = P_j(q^x) q^x \exp(-q^x) $$ y $P_j$ es el coeficiente de $n^{-j}$ en nuestra serie de potencia $$ (1-q^r)^{n-1} = \exp(-nq^{-r}) \phantom. \sum_{j=0}^\infty \frac{P_j(nq^{-r})}{n^j}. $$ Así, $ P_0(u)=1, \phantom+ P_1(u) = -(u^2-2u)/2, \phantom+ P_2(u) = (3u^4-20u^3+24u^2)/24 $ etc. De nuevo aplicamos Poisson para expandir $\epsilon^{\phantom.}_j(\log_q(n))$ en una serie de Fourier: $$ \epsilon^{\phantom.}_j(t) = \frac1k \sum_{m \in \bf Z} \hat\varphi_j(-m) e^{2\pi i m t}, $$ y evaluar la transformada de Fourier $\hat\varphi_j$ integrando con respecto a $q^t$ . Esto da lugar a una combinación lineal de Gamma evaluadas en $1 + (2\pi i y / \log q) + j'$ para enteros $j' \in [j,2j]$ , dando $\hat\varphi_j$ como título- $2j$ múltiplo polinómico de $\hat\varphi_0$ . El primer caso es $$ \begin{eqnarray*} \hat\varphi_1(y) &=& \frac1{\log q} \left[ \Gamma\Bigl(2 + \frac{2 \pi i y} {\log q}\Bigr) - \frac12 \Gamma\Bigl(3 + \frac{2 \pi i y} {\log q}\Bigr) \right] \\ &=& \frac1{\log q} \frac{\pi y}{\log q} \left(\frac{2 \pi y}{\log q} - i\right) \phantom. \Gamma\Bigl(1 + \frac{2 \pi i y} {\log q}\Bigr) \\ &=& \frac{\pi y}{\log q} \left(\frac{2 \pi y}{\log q} - i\right) \phantom. \hat\varphi_0(y). \end{eqnarray*} $$ Tenga en cuenta que $\varphi_1(0) = 0$ por lo que el coeficiente constante de la serie de Fourier para $\epsilon^{\phantom.}_1(t)$ se desvanece; esto es cierto en el caso de $\epsilon^{\phantom.}_j(t)$ para cada $j>0$ , porque $\hat\varphi_j(0) = \int_{-\infty}^\infty \phi_j(x) \phantom. dx$ es el $n^{-j}$ coeficiente de una serie de potencias en $n^{-1}$ que ya hemos identificado ya con la constante $a_\infty$ . Por lo tanto (como también puede en el gráfico de arriba) ninguna de las correcciones en decadencia $n^{-j} \epsilon^{\phantom.}_j(\log_q n)$ sesga la media de $a_n$ lejos de $a_\infty$ incluso cuando $n$ es lo suficientemente pequeño como para que esas correcciones son una fracción sustancial de la oscilación residual $\epsilon_0(\log_q n)$ . Esto deja $\hat\varphi_j(\mp1) e^{\pm 2 \pi i t} / k$ como los términos principales en la expansión de cada $\epsilon^{\phantom.}_j(t)$ Así que vemos, como se prometió, que que $\epsilon^{\phantom.}_j$ sigue siendo exponencialmente pequeño pero con un factor extra cuyo término principal es un múltiplo de $(2\pi / \log q)^{2j}$ .

Answer 2

Sospecho que el límite no existe, lo creas o no. Parece que debería existir. Pero el trazado $f(n,2)$ para n de, digamos, 30 a 2000, parece que tenemos

$$ f(n) = C + \omega(n) + o(1) $$

donde $C \approx 0.721347$ y $\omega(n)$ es una determinada función que es "log-periódica" en el sentido de que $\omega(n) = \omega(2n)$ . $\omega(n)$ nunca es más grande que $8 \times 10^{-6}$ así que tienes que mirar muy de cerca para verlo.

Este tipo de fluctuación logarítmica muy pequeña aparece en ciertas cuestiones de la matemática del análisis de algoritmos. Por ejemplo, la longitud media del recorrido más largo de una palabra binaria aleatoria de longitud $n$ es $\log_2 n + C + P(\log_2 n) + O(n^{-1/2} \log^2 n)$ , donde $P$ es una función periódica continua de período 1; véase Flajolet y Sedgewick, Combinatoria analítica , la proposición V.1. También he visto resultados similares para problemas con árboles binarios.

Algo similar parece ocurrir con $f(n,3)$ excepto que las fluctuaciones log-periódicas parecen ser del orden de $10^{-9}$ y las fluctuaciones son ``más rápidas''; si dejamos que $\omega$ denotan la función logarítmica-periódica como arriba, entonces tenemos algo como $\omega(n) = \omega(1.5 n)$ (Escribo 1,5, no $3/2$ porque no estoy nada seguro de que la constante relevante sea $3/2$ ; no estoy haciendo los cálculos con suficiente precisión para estar seguro).

Answer 3

Esto no es riguroso, pero creo que se justifica Michael Lugo observaciones que f diverge y el comportamiento es asintóticamente registro periódico.

Para hacer la recursividad más intuitiva, tenga en cuenta que f(n,k) es un promedio ponderado de f(1,k)...f(n-1,k). El peso es de aproximadamente Gaussiana, y está concentrada cerca de la modalidad de la expansión binomial de (a + b)^n donde a=1/k y b=1-1/k, lo que ocurre aproximadamente en el a^[n/k]b^(n-[n/k]) plazo, de modo que los términos cerca de f(n-[n/k],k) son los que se recurre.

El peso disminuye rápidamente lejos del modo m=n-[n/k] como una distribución normal con desviación estándar sobre sqrt(1/k (1-1/k))*sqrt(n).

Intuitivamente, el comportamiento debe ser similar a una función continua la satisfacción de

f(x) = valor promedio de f en el intervalo [(1-1/k)x - c sqrt(x),(1-1/k)k + c sqrt(x)].

Revisión de t grande. Para x, incluso más grande, f(x) puede ser expresada como un promedio ponderado (convolución) de f en cualquier intervalo [t,t*k/(k-1)]. Si se multiplica x por k/k-1, entonces usted convolución con un poco más amplia de la función, pero es más amplia por una exponencial decreciente de la cantidad. Así, el apoyo no se extienden para cubrir todos los de [t,t*k/(k-1)], y no sea invariante bajo el resto cuando se divide log x log k/(k-1).

Que dice que ciertas condiciones iniciales, se iba a producir oscilaciones. No prueba que estas condiciones.

Para t pequeño, el intervalo [m +- c sqrt(x)] puede envolver alrededor de [t,t*k/(k-1)], lo que explica por qué f casi se vuelve constante.

Answer 4

Douglas, hola, espero que estés bien. Esta vez no se trata de un problema de backgammon, sino que surge de un juego en el patio de recreo al que jugó mi hijo hace poco: n niños eligen al azar una de las k esquinas del patio y se colocan en ella. Un profesor selecciona al azar una de las esquinas y todos los niños de esa esquina son eliminados del juego. El juego continúa así hasta que todos los niños son eliminados o queda un único ganador. f(n,k) es la probabilidad de que el juego tenga un ganador. En el ejemplo real k era 4 y n era aproximadamente 30, pero me interesó el comportamiento asintótico a medida que n crece. Me sorprende que el consenso parece ser que f diverge. El gráfico de f(n,k) hasta aproximadamente n=1000 muestra la naturaleza log-periódica de f, pero la amplitud disminuye y parece que se asienta hacia un límite. Por supuesto, no es riguroso.

Answer 5

Si mi cálculo es correcto, entonces f(n, 2) debería ser aproximadamente

$$\frac12 \sum_{k \in \mathbb{Z}} 2^{k+s} e^{-2^{k+s}}$$

donde s = la parte fraccionaria de $\log_2 n$ . (Nótese que los términos de la suma decaen rápidamente tanto como $k \to \infty$ y $k \to -\infty$ .)

---

Bien, este es el argumento.

Para n ≥ 2, f(n, 2) es igual al valor medio sobre todos los subconjuntos S de {1, ..., n} de f(|S|, 2) (incluyendo S = {1, ..., n}). Así que podemos imaginar un proceso en el que empezamos con {1, ..., n} y en cada paso elegimos un subconjunto uniformemente al azar de nuestro subconjunto actual. f(n, 2) es la probabilidad de que la última vez antes de llegar al conjunto vacío, nuestro conjunto contenía un solo elemento.

Consideremos lo que ocurre con cada elemento de {1, ..., n} en este proceso. En cada etapa, si sigue en nuestro subconjunto, lo mantenemos con probabilidad 1/2 y lo echamos con probabilidad 1/2. Por tanto, la probabilidad de que permanezca después de r etapas es de 2 -r . Así, tenemos n variables independientes X ₁ , ..., X _n , cada uno con esta distribución exponencial, y lo que buscamos es la probabilidad de que entre ellos haya un único máximo.

Podemos expresar esta probabilidad como una suma sobre el valor de este máximo r. La probabilidad de que esto ocurra para cualquier r dado es

$$n(2^{-r} - 2^{-(r+1)})(1 - 2^{-r})^n = \frac 12 n 2^{-r} (1 - 2^{-r})^n.$$

Así que, $$f(n,2) = \sum_{r \ge 0} \frac 12 n 2^{-r} (1 - 2^{-r})^n.$$

Escribe $r = \log_2 n + u$ . Entonces el rº sumando se convierte en

$$\frac 12 2^{-u} (1 - 2^{-u}/n)^n.$$

A partir de aquí la derivación no es del todo rigurosa, pero como $n$ aumenta, este valor es aproximadamente

$$\frac 12 2^{-u} e^{-2^{-u}}.$$

Ahora u varía sobre valores de la forma $r - \log_2 n$ para $r$ un número entero no negativo, por lo que -u abarca valores de la forma $k + s$ s = la parte fraccionaria de $\log_2 n$ , para $-\infty < k \le \lfloor \log_2 n \rfloor$ un número entero. A medida que n llega a ∞, obtenemos la suma entera que se muestra en la parte superior.