Rozkład największego fragmentu złamanego patyka (odstępy)

Niech patyk o długości 1 zostanie podzielony losowo na fragmenty równomiernie. Jaki jest rozkład długości najdłuższego fragmentu? $k+1$

Bardziej formalnie, niech będzie IID , i niech będą powiązanymi statystykami zamówień, tzn. Po prostu zamawiamy próbka w taki sposób, że . Niech . $(U_1, \ldots U_k)$ $U(0,1)$ $(U_{(1)}, \ldots, U_{(k)})$ $U_{(1)} \leq U_{(2)} \leq, \ldots , \leq U_{(k)}$ $Z_k = \max \left(U_{(1)}, U_{(2)}-U_{(1)}, \ldots, U_{(k)} - U_{(k-1)}, 1-U_{(k)}\right)$

Interesuje mnie dystrybucja $Z_k$ . $k \uparrow \infty$ są również momenty, wyniki asymptotyczne lub przybliżenia dla .

distributions uniform order-statistics dirichlet-distribution maximum gui11aume
źródło

Jest to dobrze zbadany problem; patrz R. Pyke (1965), „Spacings”, JRSS (B) 27 : 3, s. 395–449. Postaram się wrócić później, aby dodać jakieś informacje, chyba że ktoś mnie do tego pobije. Jest też artykuł tego samego autora z 1972 r. („ Spacings revisited ”), ale myślę, że to, czego szukasz, to właściwie wszystko w pierwszej kolejności. Devroye (1981) , „Laws of Iterated Logarithm for Statistics Statistics of Uniform Spacings”, ma pewne asymptotyki . Ann. Probab , 9 : 5, 860–867.

Glen_b

Powinny one również podać kilka dobrych wyszukiwanych haseł, aby znaleźć później pracę, jeśli jej potrzebujesz.

Glen_b

To jest niesamowite. Trudno znaleźć pierwsze odniesienie. Dla zainteresowanych umieściłem go w Grand Locus .

gui11aume

Popraw błąd:

Y_{(k)}

$Y_{(k)}$ zamiast

U_{(k)}

$U_{(k)}$ .

Viktor,

Dzięki @Viktor! W przypadku takich drobiazgów nie wahaj się samodzielnie edytować (myślę, że zostanie sprawdzony przez innych użytkowników do zatwierdzenia).

gui11aume

Dzięki informacjom podanym przez @Glen_b mogłem znaleźć odpowiedź. Używając tych samych notacji co pytanie

P. (Z_{k} \leq x) = \sum_{jot = 0}^{k + 1} (\binom{k + 1}{jot}) (- 1)^{jot} (1 - jot x)_{+}^{k},

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

gdzie jeśli i przeciwnym razie. Podaję również oczekiwanie i asymptotyczną zbieżność do rozkładu Gumbela ( NB : nie Beta) $a_+ = a$ $a > 0$ $0$

mi (Z_{k}) = \frac{1}{k + 1} \sum_{ja = 1}^{k + 1} \frac{1}{ja} \sim \frac{\log (k + 1)}{k + 1}, P. (Z_{k} \leq x) \sim \exp (- {mi}^{- (k + 1) x + \log (k + 1)}) .

$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).$

Materiał dowodów pochodzi z kilku publikacji połączonych w odnośnikach. Są nieco długie, ale proste.

1. Dowód dokładnego podziału

Niech będą jednolitymi losowymi zmiennymi IID w przedziale . Zamawiając je, otrzymujemy oznaczonych statystyk zamówienia . Jednolite odstępy są zdefiniowane jako , przy czym i . Uporządkowane odstępy to odpowiednie uporządkowane statystyki . Zmienna zainteresowania to . $(U_1, \ldots, U_k)$ $(0,1)$ $k$ $(U_{(1)}, \ldots, U_{(k)})$ $\Delta_i = U_{(i)} - U_{(i-1)}$ $U_{(0)} = 0$ $U_{(k+1)} = 1$ $\Delta_{(1)} \leq \ldots \leq \Delta_{(k+1)}$ $\Delta_{(k+1)}$

Dla stałych definiujemy zmienną wskaźnikową . Przez symetrię losowy wektor jest wymienny, więc łączny rozkład podzbioru rozmiaru jest taki sam jak łączny rozkład pierwszy . W ten sposób uzyskujemy rozszerzenie produktu $x \in (0,1)$ $\mathbb{1}_i = \mathbb{1}_{\{\Delta_i > x\}}$ $(\mathbb{1}_1, \ldots, \mathbb{1}_{k+1})$ $j$ $j$

P (Δ_{(k + 1)} \leq x) = E (\prod_{i = 1}^{k + 1} (1 - 1_{i})) = 1 + \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) (- 1)^{j} E (\prod_{i = 1}^{j} 1_{i}) .

$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).$

Udowodnimy teraz, że , co określi rozkład podany powyżej. Udowadniamy to dla , ponieważ ogólny przypadek udowodniono podobnie. $E \left( \prod_{i=1}^j \mathbb{1}_i \right) = (1-jx)_+^k$ $j=2$

mi (\prod_{ja = 1}^{2)} 1_{ja}) = P. (Δ_{1} > x \cap Δ_{2)} > x) = P. (Δ_{1} > x) P. (Δ_{2)} > x | Δ_{1} > x) .

$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).$

Jeśli , punktów przerwania znajduje się w przedziale . Warunkowo w przypadku tego zdarzenia punkty przerwania są nadal wymienne, więc prawdopodobieństwo, że odległość między drugim a pierwszym punktem przerwania jest większa niż jest takie samo, jak prawdopodobieństwo, że odległość między pierwszym punktem przerwania a lewą barierą (w pozycji ) jest większy niż . Więc $\Delta_1 > x$ $k$ $(x,1)$ $x$ $x$ $x$

P (Δ_{2} > x | Δ_{1} > x) = P (all points are in (2 x, 1) | all points are in (x, 1)), so P (Δ_{2} > x \cap Δ_{1} > x) = P (all points are in (2 x, 1)) = (1 - 2 x)_{+}^{k} .

$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. Oczekiwanie

Dla dystrybucji ze skończonym wsparciem mamy

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

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

Łącząc dystrybucję otrzymujemy $\Delta_{(k+1)}$

E (Δ_{(k + 1)}) = \frac{1}{k + 1} \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) \frac{(- 1)^{j + 1}}{j} = \frac{1}{k + 1} \sum_{j = 1}^{k + 1} \frac{1}{j} .

$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}.$

Ostatnia równość to klasyczna reprezentacja liczb harmonicznych , które pokazujemy poniżej. $H_i = 1+ \frac{1}{2}+ \ldots + \frac{1}{i}$

H_{k + 1} = \int_{0}^{1} 1 + x + \dots + x^{k} d x = \int_{0}^{1} \frac{1 - x^{k + 1}}{1 - x} d x .

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

Wraz ze zmianą zmiennej i rozszerzeniem produktu otrzymujemy $u = 1-x$

H_{k + 1} = \int_{0}^{1} \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) (- 1)^{j + 1} u^{j - 1} d u = \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) \frac{(- 1)^{j + 1}}{j} .

$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. Alternatywna konstrukcja równomiernych odstępów

Aby uzyskać asymptotyczny rozkład największego fragmentu, będziemy musieli wykazać klasyczną konstrukcję równomiernych odstępów jako zmiennych wykładniczych podzielonych przez ich sumę. Gęstość prawdopodobieństwa powiązanych statystyk zamówień wynosi $(U_{(1)}, \ldots, U_{(k)})$

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

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

Jeśli oznaczymy jednolite odstępy , przy , otrzymamy $\Delta_i = U_{(i)} - U_{(i-1)}$ $U_{(0)} = 0$

f_{Δ_{1}, \dots Δ_{k}} (δ_{1}, \dots, δ_{k}) = k!, 0 \leq δ_{i} + \dots + δ_{k} \leq 1.

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

Definiując , otrzymujemy w ten sposób $U_{(k+1)} = 1$

f_{Δ_{1}, \dots Δ_{k + 1}} (δ_{1}, \dots, δ_{k + 1}) = k!, δ_{1} + \dots + δ_{k} = 1.

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

Teraz niech będzie wykładniczymi zmiennymi losowymi IID ze średnią 1, i niech . Po prostej zmianie zmiennej możemy to zobaczyć $(X_1, \ldots, X_{k+1})$ $S = X_1 + \ldots + X_{k+1}$

f_{X_{1}, \dots X_{k}, S} (x_{1}, \dots, x_{k}, s) = e^{- s} .

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

Zdefiniuj , tak że poprzez zmianę zmiennej otrzymujemy $Y_i = X_i/S$

f_{Y_{1}, \dots Y_{k}, S} (y_{1}, \dots, y_{k}, s) = s^{k} e^{- s} .

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

Łącząc tę gęstość względem , otrzymujemy w ten sposób $s$

{fa}_{Y_{1}, \dots Y_{k},} (y_{1}, \dots, y_{k}) = \int_{0}^{\infty} s^{k} {mi}^{- s} re s = k!, 0 \leq y_{ja} + \dots + y_{k} \leq 1, a zatem {fa}_{Y_{1}, \dots Y_{k + 1},} (y_{1}, \dots, y_{k + 1}) = k!, y_{1} + \dots + y_{k + 1} = 1.

$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.$

Zatem łączny rozkład równomiernych odstępów w przedziale jest taki sam, jak wspólny rozkład losowych zmiennych podzielonych przez ich sumę. Dochodzimy do następującej równoważności dystrybucji $k+1$ $(0,1)$ $k+1$

Δ_{(k + 1)} \equiv \frac{X_{(k + 1)}}{X_{1} + \dots + X_{k + 1}} .

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

4. Dystrybucja asymptotyczna

Korzystając z powyższej równoważności, otrzymujemy

\begin{aligned} P ((k + 1) Δ_{(k + 1)} - \log (k + 1) \leq x) & = P (X_{(k + 1)} \leq (x + \log (k + 1)) \frac{X_{1} + \dots + X_{k + 1}}{k + 1}) \\ = P (X_{(k + 1)} - \log (k + 1) \leq x + (x + \log (k + 1)) T_{k + 1}), \end{aligned}

$\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}$

gdzie . Ta zmienna znika z prawdopodobieństwem, ponieważ i . Asymptotycznie rozkład jest taki sam jak w przypadku . Ponieważ to IID, mamy $T_{k+1} = \frac{X_1+\ldots+X_{k+1}}{k+1} -1$ $E\left(T_{k+1}\right) = 0$ $Var\big(\log(k+1)T_{k+1}\big) = \frac{(\log(k+1))^2}{k+1} \downarrow 0$ $X_{(k+1)} - \log(k+1)$ $X_i$

\begin{aligned} P. (X_{(k + 1)} - \log (k + 1) \leq x) & = P. {(X_{1} \leq x + \log (k + 1))}^{k + 1} \\ = {(1 - {mi}^{- x - \log (k + 1)})}^{k + 1} = {(1 - \frac{{mi}^{- x}}{k + 1})}^{k + 1} \sim \exp {- {mi}^{- x}} . \end{aligned}

$\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. Przegląd graficzny

Poniższy wykres pokazuje rozkład największego fragmentu dla różnych wartości . Dla nałożyłem również asymptotyczny rozkład Gumbela (cienka linia). Gumbel jest bardzo złym przybliżeniem małych wartości więc pomijam je, aby nie przeciążały obrazu. Przybliżenie Gumbela jest dobre od . $k$ $k=10, 20, 50$ $k$ $k \approx 50$

6. Referencje

Powyższe dowody pochodzą z odniesień 2 i 3. Cytowana literatura zawiera wiele innych wyników, takich jak rozkład uporządkowanych odstępów dowolnej rangi, ich rozkład graniczny i niektóre alternatywne konstrukcje uporządkowanych jednolitych odstępów. Najważniejsze odniesienia nie są łatwo dostępne, dlatego udostępniam również linki do pełnego tekstu.

Bairamov i in. (2010) Ogranicz wyniki dla zamówionych jednolitych odstępów , dokumenty statystyczne, 51: 1, s. 227–240
Holst (1980) O długości kawałków patyka przypadkowo złamanych , J. Appl. Prob., 17, str. 623-634
Pyke (1965) Spacings , JRSS (B) 27: 3, ss. 395–449
Renyi (1953) Na temat teorii statystyki zamówień Acta math Hung, 4, s. 191–231

gui11aume
źródło

Znakomity. Nawiasem mówiąc, czy jest znana asymptotyka ?

E (Z_{k}^{2})

$E(Z_k ^2)$

Amir Sagiv

@AmirSagiv to dobre pytanie. Rzuciłem okiem na referencje i nie mogłem ich znaleźć. Nie mogłem również dostosować powyższego dowodu. To uświadomiło mi, że nie wiem, jaki jest rozkład kwadratu Gumbela. Być może dobre miejsce na start?

gui11aume

$ gui11aume Zajrzyj tutaj: mathoverflow.net/a/293381/42864

Amir Sagiv

@AmirSagiv To jest bardzo dobry post. Z jakiegoś powodu źle zrozumiałem twoje pytanie i pomyślałem, że jesteś zainteresowany asymptotycznym rozkładem (nawet jeśli twój komentarz był bardzo jasny), więc mój komentarz powyżej nie jest tak trafny.

Z_{k}^{2}

$Z_k^2$

gui11aume

Rozkład największego fragmentu złamanego patyka (odstępy)

Odpowiedzi:

1. Dowód dokładnego podziału

2. Oczekiwanie

3. Alternatywna konstrukcja równomiernych odstępów

4. Dystrybucja asymptotyczna

5. Przegląd graficzny

6. Referencje