Longitud esperada del bastón más largo en un proceso de rotura de bastón

Question

Partiendo de un solo palo de longitud unitaria, un punto $p \in (0, 1)$ se escoge uniformemente al azar a lo largo del palo y el palo se rompe, produciendo dos palos de longitud $p$ y $1-p$ .

En cada una de las siguientes etapas, se elige un palo al azar y un punto al azar a lo largo de la longitud de ese palo, y se lo rompe.

Pregunta: Después de n broches, ¿cuál es la longitud esperada del palo más largo que queda?

Observaciones:

Un amigo y yo hicimos algunas simulaciones y encontramos algunos resultados bastante inesperados. El valor esperado después de $500$ se divide es aproximadamente $0.2098$ que es enorme para tantas divisiones, al menos intuitivamente.

Por otro lado, se puede demostrar con bastante facilidad que el valor esperado sí va a $0$ como $n \to \infty$ . Pero la decadencia parece extremadamente lenta.

Answer 1

Parece que la longitud del palo más largo es del orden $n^{2\sqrt{2}-3} = n^{-0.171\ldots}$ como $n\to\infty$ . Esto se deduce de un análogo en tiempo discreto del proceso de fragmentación homogéneo, véase el capítulo 1.5 de J. Bertoin, Procesos de fragmentación y coagulación aleatorios . Vol. 102. Cambridge University Press, 2006.

Denotemos por $X_{n,0} \geq X_{n,1} \geq \cdots \geq X_{n,n}$ los tamaños ordenados de los palos después de $n$ broches de presión. El primer resultado que necesitamos es el siguiente.

Lema: $\chi_{n}(p) := \mathbb{E}\left[\sum_{i=0}^n X_{n,i}^p\right] = \frac{1}{n!}\left(\frac{2}{1+p}\right)_n,$ donde $(a)_n=a(a+1)\cdots (a+n-1)$ es el símbolo creciente de Pochhammer.

Prueba: Tenemos \begin{align*} \mathbb{E}\left[\sum_{i=0}^n X_{n,i}^p\middle| X_{n-1,0},\ldots\right] &= \frac{1}{n}\sum_{k=0}^{n-1}\Big(\mathbb{E}\left[x^p + (X_{n-1,k}-x)^p\middle|X_{n-1,k}\right]+\sum_{\substack{i=0\\i\neq k}}^{n-1}X_{n-1,i}^p\Big)\\ &= \frac{1}{n}\left(\frac{2}{p+1}+n-1\right)\sum_{i=0}^{n-1}X_{n-1,i}^p, \end{align*} donde $x$ es uniforme en $(0,X_{n-1,k})$ . Por lo tanto, $\chi_n(p) = \frac{1}{n}\left(\frac{2}{p+1}+n-1\right) \chi_{n-1}(p)$ . Junto con $\chi_0(p)=1$ Esto nos da la fórmula que se reclama para $\chi_n(p)$ . $\square$

Siguiendo el Corolario 1.4 del libro de Bertoin, observamos que \begin{equation} n^{\frac{p-1}{p+1}} \chi_n(p) = \frac{1}{\Gamma\left(\frac{2}{p+1}\right)} + O(n^{-1}). \end{equation} En particular, está acotado para cualquier $p>-1$ . Desde $X_{n,0}^p < \sum_{i=0}^n X_{n,i}^p$ deducimos que $n^{\frac{p-1}{p+1}}X_{n,0}^p$ está acotado como $n\to\infty$ . Por lo tanto, \begin{equation} \limsup_{n\to\infty} \frac{\log X_{n,0}}{\log n} \leq -\frac{1}{p}\frac{p-1}{p+1} \leq -\frac{1}{\bar{p}}\frac{\bar{p}-1}{\bar{p}+1} = 2\sqrt{2}-3, \end{equation} porque el máximo $\bar{p}$ de $-\frac{1}{p}\frac{p-1}{p+1}$ se consigue en $\bar{p} = 1+\sqrt{2}$ . Del mismo modo, se puede derivar una cota inferior de coincidencia observando que \begin{equation} X_{n,0}^\epsilon \geq \frac{\sum_{i=0}^{n}X_{n,i}^p}{\sum_{i=0}^{n}X_{n,i}^{p-\epsilon}} \end{equation} para cualquier $\epsilon>0$ , lo que implica \begin{equation} \liminf_{n\to\infty} \frac{\log X_{n,0}}{\log n} \geq - \frac{\frac{p-1}{p+1} - \frac{p-\epsilon-1}{p-\epsilon+1}}{\epsilon} \end{equation} para cualquier $\epsilon>0$ y $0<p<\bar{p}$ . Dejar $\epsilon$ acercarse a $0$ y $p$ acercarse a $\bar{p}$ Así pues, tenemos \begin{equation} \liminf_{n\to\infty} \frac{\log X_{n,0}}{\log n} \geq -\frac{2}{(1-\bar{p})^2}=2\sqrt{2}-3. \end{equation} Por lo tanto, podemos concluir que \begin{equation} \lim_{n\to\infty} \frac{\log X_{n,0}}{\log n} =2\sqrt{2}-3. \end{equation}

Answer 2

ACTUALIZACIÓN#2 . Sólo para ilustrar cómo crece la complejidad de las expresiones exactas, éstas son las tres primeras: \begin{split} n=1:~& \frac{3}{4} = 0.75\\ n=2:~& \frac38 + \log\frac43 = 0.662682072451781\ldots\\ n=3:~~~& \frac{5+4\pi^{2}}{24}-\log(2)^{2}+\frac{89 \log(2)}{18}-\frac{17 \log(3)}{6}+\frac{2 \log(3) \log(2)}{3}-\frac{2 \Re\,\mathrm{Li}_{2}(\tfrac{3}{2})}{3} = 0.612043787903219\ldots \end{split}

ACTUALIZACIÓN#1 . Como se señala en los comentarios, la recurrencia para $L(n)$ derivado a continuación sólo da un límite inferior.

---

Dejemos que $L(n)$ sea la longitud esperada del palo más largo después de $n$ chasquidos. Considera los dos palos resultantes del primer chasquido, llámalos izquierda y derecha. Observando que la probabilidad de exactamente $k\in\{0,1,\dots,n-1\}$ de los siguientes $n-1$ los chasquidos que se producen en los (descendientes de) el palo izquierdo son iguales $\frac1n$ obtenemos una fórmula de recurrencia a partir de $L(0)=1$ :

\begin{split} L(n) &= \frac1n \int_0^1 {\rm d}p\sum_{k=0}^{n-1} \max\{\ pL(k),\ (1-p)L(n-1-k)\ \}\\ &= \frac1n \sum_{k=0}^{n-1} L(k) - \frac{L(k)L(n-1-k)}{2(L(k)+L(n-1-k))}. \end{split} (simplificado por sugerencia de David E Speyer)

Aquí hay una ejemplo de código Sage informática $L(n)$ para $n=1..10$ .

Answer 3

He aquí algunos resultados empíricos que pueden ser útiles, sobre todo para dar credibilidad a algunas de las teorías sugeridas en otros posts. Realicé 10.000 simulaciones, y para cada una de ellas, rompí el palo 10.000 veces, siguiendo la porción más larga en cada paso. Aquí están los resultados:

y los mismos datos representados en una escala logarítmica:

Puede notar que se ha resaltado un $\pm 1 \sigma$ región mencionada en la leyenda; el intervalo de confianza correspondiente es tan estrecho que es difícil de ver.

He añadido dos líneas de puntos que corresponden a dos tasas de decaimiento mencionadas en otros posts: $d(n) \propto n^{2\sqrt{2}-3}$ y $d(n) \propto (1-\frac{1}{4n-4})d(n-1)$ .

Las dos hipótesis pretenden ser descripciones asintóticas, por lo que si las trazamos directamente, tienen desviaciones grandes y molestas. Lo he "arreglado" multiplicando por la constante adecuada para que los gráficos se crucen con la media empírica en $x=1000$ . (Por ejemplo, la línea verde punteada es en realidad $0.591 n^{2\sqrt{2}-3}$ .)

Por cierto, podemos calcular nuestra propia versión de la longitud esperada después de la 500ª división. He realizado 1 millón de simulaciones y he observado una media empírica de $0.2076537 \pm 0.0001231$ . (El $\pm$ parte es una desviación estándar para la estimación).

Answer 4

Esto es intermedio entre una respuesta, y un largo comentario sobre el post de Max Alekseyev.

Como se discute en los comentarios debajo de su respuesta, hay un fallo en su post, por lo que da un límite inferior. Pero hay una forma directa de superar el defecto. Por desgracia, hay un obstáculo más que no veo cómo proceder más allá.

Empiece con una ligera generalización. Comienza con un único nodo de longitud $s$ y construir un árbol aleatorio de la siguiente manera:

• Seleccionar un nodo hoja $n$ uniformemente al azar. Llama a su peso $w$ .
• Seleccione $p\in[0,1]$ uniformemente al azar.
• Adjuntar dos niños a $n$ de peso $pw$ y $(1-p)w$ .

Su problema plantea: si $s=1$ ¿Cuál es el mayor peso de una hoja, cuando hay $n$ ¿nodos? Llama a esta variable aleatoria $X^0_n$ En el caso general, esa longitud se escala a $sX^0_n$ .

Como observó Max Alekseyev, este árbol tiene una estructura de recurrencia natural. Para facilitar la anotación, supongamos que $n+1$ nodos. El nodo raíz tiene dos hijos, ponderados $P$ y $1-P$ que haya $K$ y $n-K$ nodos debajo de cada uno (inclusive); entonces $K$ se elige uniformemente entre $\{0,1,\dots,n\}$ . Tome dos copias iid de $X^0$ , llamado $X^1$ y $X^2$ . Dado que los nodos hoja deben descender de los hijos de la raíz, $$(X_{n+1}^0|K,P)=\max(PX^1_K,(1-P)X^2_{n-K})$$

Para proceder con exactitud, introduzca una función tipo CDF. Dejemos que $F_n(t)=\mathbb{P}\left[{X_n\leq\frac{1}{t}}\right]$ Entonces \begin{align*} (n+1)F_{n+1}(t)&=(n+1)\mathbb{P}\left[{X_n^0\leq\frac{1}{t}}\right] \\ &=\sum_{k=0}^n{\int_0^1{\mathbb{P}\left[{\max(PX^1_K,(1-P)X^2_{n-K})\leq\frac{1}{t}}\middle|{K=k,|P-p|\leq dp}\right]}} \\ &=\sum_{k=0}^n{\int_0^1{\mathbb{P}\left[{pX^1_k\leq\frac{1}{t}}\wedge{(1-p)X^2_{n-k}\leq\frac{1}{t}}\right]\,dp}} \\ &=\sum_{k=0}^n{\int_0^1{F_k(pt)F_{n-k}((1-p)t)\,dp}} \end{align*}

La suma finita es una convolución discreta, y se puede eliminar pasando a funciones generadoras. Dejemos que $\mathcal{F}(t,z)=\sum_{n=0}^{\infty}{F_n(t)z^n}$ . Entonces $$\mathcal{F}(pt,z)\mathcal{F}((1-p)t,z)=\sum_{n=0}^{\infty}{\sum_{k=0}^n{F_k(pt)F_{n-k}((1-p)t)z^n}}$$ Integración en $p$ recupera la recurrencia de arriba, que se simplifica a \begin{gather*} \frac{\mathcal{F}(t,z)}{\partial z}=\int_0^1{\mathcal{F}(pt,z)\mathcal{F}((1-p)t,z)\,dp} \\ \mathcal{F}(t,0)=F_0(t)=\begin{cases}t&0<t\leq1\\0&\text{otherwise}\end{cases} \end{gather*} Tenga en cuenta que $F_n(t)=0$ para $t<0$ para que podamos extender los límites de la integración a $\mathbb{R}$ sin efecto.

La otra integral puede casi se eliminan mediante la transformada de Fourier. Ahora dejemos que $\mathcal{G}(u,z)=\int_\mathbb{R}{\mathcal{F}(t,z)e^{uti}\,dt}$ . Entonces \begin{align*} \frac{\partial\mathcal{G}(u,z)}{\partial z}&=\int_\mathbb{R}{\frac{\mathcal{F}(t,z)}{\partial z}e^{uti}\,dt} \\ &=\iint_{\mathbb{R}^2}{e^{upti}\mathcal{F}(pt,z)\cdot e^{u(1-p)ti}\mathcal{F}((1-p)t,z)\,d^2(p,t)} \\ &=\iint_{\mathbb{R}^2}{e^{\alpha ui}\mathcal{F}(\alpha,z)\cdot e^{\beta ui}\mathcal{F}(\beta,z)\,\frac{d^2(\alpha,\beta)}{\alpha+\beta}} \end{align*} Si el $\alpha+\beta$ en el denominador podría eliminarse (por ejemplo, modificando la definición de $F_n$ y utilizando una transformación integral análoga), entonces la última línea se simplificaría a $\mathcal{G}(u,z)^2$ .

Desgraciadamente, no conozco una transformación integral que evite el extra $\alpha+\beta$ plazo. No obstante, permítanme que me complazca y esboce el argumento después de haber llenado esa laguna, aunque estoy seguro de que la estructura del argumento no sorprenderá a la mayoría de los lectores.

Supongamos que la transformada integral necesaria tiene $L^2$ adjunto dado por el núcleo $\hat{I}$ y definir $$\alpha(u)=\int_1^\infty{\frac{\hat{I}(t)}{t^2}\,dt}$$ (Sí, probablemente hay que tener un poco de cuidado para demostrar que esta integral converge. Pero, en definitiva, se trata de calcular una integral explícita).

En el PO, usted pide \begin{align*} \mathbb{E}[X_n]&=\int_0^1{\mathbb{P}[X_n\leq t]\,dt} \\ &=\int_0^1{F_n\left(\frac{1}{t}\right)\,dt} \\ &=\int_1^\infty{F_n(u)\,\frac{du}{u^2}} \end{align*} que tiene una función generadora $$\mathcal{E}(z)=\int_1^\infty{\mathcal{F}(t,z)\,\frac{dt}{t^2}}=\int_\mathbb{R}{\overline{\alpha(u)}\mathcal{G}(u,z)\,du}$$ Por lo tanto, basta con tener una fórmula explícita para $\mathcal{G}$ .

A partir del valor conocido de $\mathcal{F}(t,0)$ , $$\mathcal{G}(u,0)=\frac{1-e^{ui}(1-ui)}{u^2}$$ La ecuación diferencial anterior es entonces una EDO que determina de forma única $\mathcal{G}$ como algunos locales- $C^{\infty}$ función $$\mathcal{G}(u,z)=\sum_{n=0}^\infty{g_n(u)z^n}$$ Comparando los coeficientes de $z^n$ , $$\mathbb{E}[X_n]=\int_\mathbb{R}{\overline{\alpha(u)}g_n(u)\,du}$$ por lo que el problema se reduce a estimar una integral explícita.