24 votos

Distribución del fragmento más grande de un palo roto (espaciados)

Que un palo de longitud 1 se parta en $k+1$ fragmentos uniformemente al azar. ¿Cuál es la distribución de la longitud del fragmento más largo?

Más formalmente, dejemos que $(U_1, \ldots U_k)$ ser IID $U(0,1)$ y que $(U_{(1)}, \ldots, U_{(k)})$ sean las estadísticas de orden asociadas, es decir simplemente ordenamos la muestra de forma que $U_{(1)} \leq U_{(2)} \leq, \ldots , \leq U_{(k)}$ . Sea $Z_k = \max \left(U_{(1)}, U_{(2)}-U_{(1)}, \ldots, U_{(k)} - U_{(k-1)}, 1-U_{(k)}\right)$ .

Me interesa la distribución de $Z_k$ . Momentos, resultados asintóticos o aproximaciones para $k \uparrow \infty$ también son interesantes.

10 votos

Se trata de un problema bien estudiado; véase R. Pyke (1965), "Spacings". JRSS(B) 27 :3, pp. 395-449. Intentaré volver más tarde para añadir algo de información, a menos que alguien se me adelante. También hay un artículo de 1972 del mismo autor (" Espacios revisitados ") pero creo que lo que buscas está más o menos en la primera. Hay algunas asintóticas en Devroye (1981) , "Leyes del logaritmo iterado para estadísticas de orden de espaciamientos uniformes" Ann. Probab. , 9 :5, 860-867.

4 votos

También te proporcionarán buenos términos de búsqueda para encontrar trabajo más adelante si lo necesitas.

4 votos

Esto es impresionante. La primera referencia es difícil de encontrar. Para los interesados, la he puesto en El Gran Locus .

24voto

JMW.APRN Puntos 21

Con la información dada por @Glen_b pude encontrar la respuesta. Utilizando las mismas notaciones que en la pregunta

$$ P(Z_k \leq x) = \sum_{j=0}^{k+1} { k+1 \choose j } (-1)^j (1-jx)_+^k, $$

donde $a_+ = a$ si $a > 0$ y $0$ de lo contrario. También doy la expectativa y la convergencia asintótica a la ecuación de Gumbel ( NB : no Distribución Beta)

$$ E(Z_k)= \frac{1}{k+1}\sum_{i=1}^{k+1}\frac{1}{i} \sim \frac{\log(k+1)}{k+1}, \\ P(Z_k \leq x) \sim \exp\left(- e^{-(k+1)x + \log(k+1)} \right). $$

El material de las pruebas procede de varias publicaciones enlazadas en las referencias. Son algo largas, pero sencillas.

1. Prueba de la distribución exacta

Sea $(U_1, \ldots, U_k)$ sean variables aleatorias uniformes IID en el intervalo $(0,1)$ . Ordenándolos, obtenemos el $k$ estadísticas de orden denotadas $(U_{(1)}, \ldots, U_{(k)})$ . Las distancias uniformes se definen como $\Delta_i = U_{(i)} - U_{(i-1)}$ con $U_{(0)} = 0$ y $U_{(k+1)} = 1$ . Las separaciones ordenadas son las estadísticas ordenadas correspondientes $\Delta_{(1)} \leq \ldots \leq \Delta_{(k+1)}$ . La variable de interés es $\Delta_{(k+1)}$ .

Para fijos $x \in (0,1)$ definimos la variable indicadora $\mathbb{1}_i = \mathbb{1}_{\{\Delta_i > x\}}$ . Por simetría, el vector aleatorio $(\mathbb{1}_1, \ldots, \mathbb{1}_{k+1})$ es intercambiable, por lo que la distribución conjunta de un subconjunto de tamaño $j$ es igual a la distribución conjunta de la primera $j$ . Expandiendo el producto, obtenemos

$$ P(\Delta_{(k+1)} \leq x) = E \left( \prod_{i=1}^{k+1} (1 - \mathbb{1}_i) \right) = 1 + \sum_{j=1}^{k+1} { k+1 \choose j } (-1)^j E \left( \prod_{i=1}^j \mathbb{1}_i \right). $$

Ahora demostraremos que $E \left( \prod_{i=1}^j \mathbb{1}_i \right) = (1-jx)_+^k$ que establecerá la distribución dada anteriormente. Demostramos esto para $j=2$ ya que el caso general se demuestra de forma similar.

$$ E \left( \prod_{i=1}^2 \mathbb{1}_i \right) = P(\Delta_1 > x \cap \Delta_2 > x) = P(\Delta_1 > x) P(\Delta_2 > x | \Delta_1 > x). $$

Si $\Delta_1 > x$ El $k$ los puntos de ruptura están en el intervalo $(x,1)$ . Condicionado a este evento, los puntos de ruptura siguen siendo intercambiables, por lo que la probabilidad de que la distancia entre el segundo y el primer punto de ruptura sea mayor que $x$ es igual a la probabilidad de que la distancia entre el primer punto de ruptura y la barrera izquierda (en la posición $x$ ) es mayor que $x$ . Así que

$$ P(\Delta_2 > x | \Delta_1 > x) = P\big(\text{all points are in } (2x,1) \big| \text{all points are in } (x,1)\big), \; \text{so} \\ P(\Delta_2 > x \cap \Delta_1 > x) = P\big(\text{all points are in } (2x,1)\big) = (1-2x)_+^k. $$

2. Expectativas

Para distribuciones con soporte finito, tenemos

$$ E(X) = \int P(X > x)dx = 1 - \int P(X \leq x)dx. $$

Integración de la distribución de $\Delta_{(k+1)}$ obtenemos

$$ E\left(\Delta_{(k+1)}\right) = \frac{1}{k+1}\sum_{j=1}^{k+1}{k+1 \choose j}\frac{(-1)^{j+1}}{j} = \frac{1}{k+1}\sum_{j=1}^{k+1}\frac{1}{j}. $$

La última igualdad es una representación clásica de los números armónicos $H_i = 1+ \frac{1}{2}+ \ldots + \frac{1}{i}$ que demostramos a continuación.

$$ H_{k+1} = \int_0^1 1 + x + \ldots + x^k dx = \int_0^1 \frac{1-x^{k+1}}{1-x}dx. $$

Con el cambio de variable $u = 1-x$ y expandiendo el producto, obtenemos

$$ H_{k+1} = \int_0^1\sum_{j=1}^{k+1}{ k+1 \choose j }(-1)^{j+1}u^{j-1}du = \sum_{j=1}^{k+1}{k+1 \choose j}\frac{(-1)^{j+1}}{j}. $$

3. Construcción alternativa de distancias uniformes

Para obtener la distribución asintótica del fragmento mayor, necesitaremos exponer una construcción clásica de espaciamientos uniformes como variables exponenciales divididas por su suma. La densidad de probabilidad de la estadística de orden asociada $(U_{(1)}, \ldots, U_{(k)})$ es

$$ f_{U_{(1)}, \ldots U_{(k)}}(u_{(1)}, \ldots, u_{(k)}) = k!, \; 0 \leq u_{(1)} \leq \ldots \leq u_{(k+1)}. $$

Si denotamos las distancias uniformes $\Delta_i = U_{(i)} - U_{(i-1)}$ con $U_{(0)} = 0$ obtenemos

$$ f_{\Delta_1, \ldots \Delta_k}(\delta_1, \ldots, \delta_k) = k!, \; 0 \leq \delta_i + \ldots + \delta_k \leq 1. $$

Definiendo $U_{(k+1)} = 1$ obtenemos

$$ f_{\Delta_1, \ldots \Delta_{k+1}}(\delta_1, \ldots, \delta_{k+1}) = k!, \; \delta_1 + \ldots + \delta_k = 1. $$

Ahora, dejemos que $(X_1, \ldots, X_{k+1})$ sean variables aleatorias exponenciales IID con media 1, y sea $S = X_1 + \ldots + X_{k+1}$ . Con un simple cambio de variable, podemos ver que

$$f_{X_1, \ldots X_k, S}(x_1, \ldots, x_k, s) = e^{-s}.$$

Defina $Y_i = X_i/S$ tal que por cambio de variable obtenemos

$$f_{Y_1, \ldots Y_k, S}(y_1, \ldots, y_k, s) = s^k e^{-s}.$$

Integrando esta densidad con respecto a $s$ obtenemos

$$ f_{Y_1, \ldots Y_k,}(y_1, \ldots, y_k) = \int_0^{\infty}s^k e^{-s}ds = k!, \; 0 \leq y_i + \ldots + y_k \leq 1, \; \text{and thus} \\ f_{Y_1, \ldots Y_{k+1},}(y_1, \ldots, y_{k+1}) = k!, \; y_1 + \ldots + y_{k+1} = 1. $$

Por tanto, la distribución conjunta de $k+1$ distancias uniformes en el intervalo $(0,1)$ es igual a la distribución conjunta de $k+1$ variables aleatorias exponenciales divididas por su suma. Llegamos a la siguiente equivalencia de distribución

$$ \Delta_{(k+1)} \equiv \frac{X_{(k+1)}}{X_1 + \ldots + X_{k+1}}. $$

4. Distribución asintótica

Utilizando la equivalencia anterior, obtenemos

$$ \begin{align} P\big((k+1)\Delta_{(k+1)} - \log(k+1) \leq x\big) &= P\left(X_{(k+1)} \leq (x + \log(k+1))\frac{X_1 + \ldots + X_{k+1}}{k+1}\right) \\ &= P\left(X_{(k+1)} - \log(k+1) \leq x + (x + \log(k+1))T_{k+1}\right), \end{align} $$

donde $T_{k+1} = \frac{X_1+\ldots+X_{k+1}}{k+1} -1$ . Esta variable desaparece en probabilidad porque $E\left(T_{k+1}\right) = 0$ y $Var\big(\log(k+1)T_{k+1}\big) = \frac{(\log(k+1))^2}{k+1} \downarrow 0$ . Asintóticamente, la distribución es la misma que la de $X_{(k+1)} - \log(k+1)$ . Porque el $X_i$ son IID, tenemos

$$ \begin{align} P\left(X_{(k+1)} - \log(k+1) \leq x \right) &= P\left(X_1 \leq x + \log(k+1)\right)^{k+1} \\ &= \left(1-e^{-x - \log(k+1)}\right)^{k+1} = \left(1-\frac{e^{-x}}{k+1}\right)^{k+1} \sim \exp\left\{-e^{-x}\right\}. \end{align} $$

5. Resumen gráfico

El gráfico siguiente muestra la distribución del fragmento mayor para distintos valores de $k$ . Para $k=10, 20, 50$ También he superpuesto la distribución asintótica de Gumbel (línea fina). La distribución de Gumbel es una muy mala aproximación para valores pequeños de $k$ así que los omito para no sobrecargar la imagen. La aproximación de Gumbel es buena a partir de $k \approx 50$ .

Distribution of the largest fragment of a broken stick

6. Referencias

Las pruebas anteriores se han tomado de las referencias 2 y 3. La bibliografía citada contiene muchos más resultados, como la distribución de los espaciamientos ordenados de cualquier rango, su distribución límite y algunas construcciones alternativas de los espaciamientos uniformes ordenados. Las referencias principales no son fácilmente accesibles, por lo que también proporciono enlaces al texto completo.

  1. Bairamov et al. (2010) Resultados límite para distancias uniformes ordenadas Stat papers, 51:1, pp 227-240
  2. Holst (1980) Sobre las longitudes de los trozos de un palo roto al azar J. Appl. Prob., 17, pp 623-634
  3. Pyke (1965) Espacios , JRSS(B) 27:3, pp. 395-449
  4. Renyi (1953) Sobre la teoría de la estadística de órdenes Acta math Hung, 4, pp 191-231

3voto

cms Puntos 2500

Esta no es una respuesta completa, pero hice algunas simulaciones rápidas y esto es lo que obtuve: Histogram of the longest fragment

Esto parece notablemente beta, y tiene un poco de sentido, ya que las estadísticas de orden de las distribuciones uniformes i.i.d. son beta wiki .

Esto podría dar algún punto de partida para derivar la f.d.p. resultante.

Actualizaré si llego a una solución final cerrada.

¡Salud!

1voto

ben Puntos 124

Produje la respuesta para una conferencia en Siena (Italia) en 2005. La ponencia (2006) se presenta en mi sitio web aquí (pdf) . Las distribuciones exactas de todas las distancias (de menor a mayor) se encuentran en las páginas 75 y 76.

Espero hacer una presentación sobre este tema en la Conferencia RSS de Manchester (Inglaterra) en septiembre de 2016.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X