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 .

— 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

To nie jest pełna odpowiedź, ale wykonałem kilka szybkich symulacji i oto, co otrzymałem: Histogram najdłuższego fragmentu

Wygląda to w znacznym stopniu na wersję beta i ma to trochę sensu, ponieważ statystyki porządkowe dla dystrybucji jednolitych iid są w wersji beta wiki .

Może to stanowić punkt wyjścia do uzyskania wynikowego pliku pdf.

Dokonam aktualizacji, jeśli dojdę do ostatecznego zamkniętego rozwiązania.

Twoje zdrowie!

— Lima
źródło

Jeszcze jedna rzecz, kształt histogramu dla zwiększenia k nie zmienia się znacząco, poza tym, że „zgnieciony” jest bliski zeru

— Lima

Dziękujemy za przemyślenia @ Lima (i zapraszamy do Cross Validated). Myślę, że twoją odpowiedź można poprawić. Po pierwsze, powstrzymam się od składania oświadczeń bez dowodu. Jeśli jest to niepoprawne, możesz umieścić osoby, które widzą ten wątek na niewłaściwym torze. Po drugie, udokumentowałbym to, co zrobiłeś. Bez użytej wartości ani kodu liczba nie pomoże nikomu. Na koniec skopiowałbym - edytuj odpowiedź i usuwam wszystko, co nie odpowiada bezpośrednio na pytanie.

k

$k$

— gui11aume

Dziękuję za sugestie. Są ważne poza wymianą stosu i pamiętam, aby ich użyć.

— Lima

Odpowiedziałem na konferencję w Sienie (Włochy) w 2005 r. Artykuł (2006) jest prezentowany na mojej stronie tutaj (pdf) . Dokładne rozkłady wszystkich odstępów (od najmniejszych do największych) znajdują się na stronach 75 i 76.

Mam nadzieję przedstawić prezentację na ten temat na konferencji RSS w Manchesterze (Anglia) we wrześniu 2016 r.

— CJStephens
źródło

Witamy na stronie. Staramy się zbudować stałe repozytorium wysokiej jakości informacji statystycznych w formie pytań i odpowiedzi. Dlatego też obawiamy się odpowiedzi typu „tylko link” z powodu linkrot. Czy możesz zamieścić pełny cytat i streszczenie informacji pod linkiem, na wypadek gdyby nie działał? Nie podpisuj też tutaj swoich postów. Każdy post zawiera link do Twojej strony użytkownika, na której możesz opublikować te informacje.

— gung - Przywróć Monikę