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

21

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 .(U1,Uk)U(0,1)(U(1),,U(k))U(1)U(2),,U(k)Zk=max(U(1),U(2)U(1),,U(k)U(k1),1U(k))

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

gui11aume
źródło
9
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
4
Powinny one również podać kilka dobrych wyszukiwanych haseł, aby znaleźć później pracę, jeśli jej potrzebujesz.
Glen_b
3
To jest niesamowite. Trudno znaleźć pierwsze odniesienie. Dla zainteresowanych umieściłem go w Grand Locus .
gui11aume
Popraw błąd: Y(k) zamiast 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

Odpowiedzi:

18

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

P.(Zkx)=jot=0k+1(k+1jot)(-1)jot(1-jotx)+k,

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

mi(Zk)=1k+1ja=1k+11jalog(k+1)k+1,P.(Zkx)exp(-mi-(k+1)x+log(k+1)).

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 .( 0 , 1 ) k ( U ( 1 ) , ... , u ( k ) ) Δ I = U ( i ) - u ( i - 1 ) u ( 0 ) = 0 U ( k + 1 ) = 1 Δ ( 1 )(U1,,Uk)(0,1)k(U(1),,U(k))Δi=U(i)U(i1)U(0)=0U(k+1)=1 Δ ( k + 1 )Δ(1)Δ(k+1)Δ(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 produktu1 i = 1 { Δ i > x } ( 1 1 , , 1 k + 1 ) j jx(0,1)1i=1{Δi>x}(11,,1k+1)jj

P(Δ(k+1)x)=E(i=1k+1(11i))=1+j=1k+1(k+1j)(1)jE(i=1j1i).

Udowodnimy teraz, że , co określi rozkład podany powyżej. Udowadniamy to dla , ponieważ ogólny przypadek udowodniono podobnie. j = 2mi(ja=1jot1ja)=(1-jotx)+kjot=2)

mi(ja=12)1ja)=P.(Δ1>xΔ2)>x)=P.(Δ1>x)P.(Δ2)>x|Δ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ęck ( x , 1 ) x x xΔ1>xk(x,1)xxx

P(Δ2>x|Δ1>x)=P(all points are in (2x,1)|all points are in (x,1)),soP(Δ2>xΔ1>x)=P(all points are in (2x,1))=(12x)+k.

2. Oczekiwanie

Dla dystrybucji ze skończonym wsparciem mamy

E(X)=P(X>x)dx=1P(Xx)dx.

Łącząc dystrybucję otrzymujemyΔ(k+1)

E(Δ(k+1))=1k+1j=1k+1(k+1j)(1)j+1j=1k+1j=1k+11j.

Ostatnia równość to klasyczna reprezentacja liczb harmonicznych , które pokazujemy poniżej.Hi=1+12++1i

Hk+1=011+x++xkdx=011xk+11xdx.

Wraz ze zmianą zmiennej i rozszerzeniem produktu otrzymujemyu=1x

Hk+1=01j=1k+1(k+1j)(1)j+1uj1du=j=1k+1(k+1j)(1)j+1j.

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),,U(k))

fU(1),U(k)(u(1),,u(k))=k!,0u(1)u(k+1).

Jeśli oznaczymy jednolite odstępy , przy , otrzymamyΔi=U(i)U(i1)U(0)=0

fΔ1,Δk(δ1,,δk)=k!,0δi++δk1.

Definiując , otrzymujemy w ten sposóbU(k+1)=1

fΔ1,Δk+1(δ1,,δk+1)=k!,δ1++δk=1.

Teraz niech będzie wykładniczymi zmiennymi losowymi IID ze średnią 1, i niech . Po prostej zmianie zmiennej możemy to zobaczyć(X1,,Xk+1)S=X1++Xk+1

fX1,Xk,S(x1,,xk,s)=es.

Zdefiniuj , tak że poprzez zmianę zmiennej otrzymujemyYi=Xi/S

fY1,Yk,S(y1,,yk,s)=skes.

Łącząc tę ​​gęstość względem , otrzymujemy w ten sposóbs

faY1,Yk,(y1,,yk)=0skmi-sres=k!,0yja++yk1,a zatemfaY1,Yk+1,(y1,,yk+1)=k!,y1++yk+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 dystrybucjik+1(0,1)k+1

Δ(k+1)X(k+1)X1++Xk+1.

4. Dystrybucja asymptotyczna

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

P((k+1)Δ(k+1)log(k+1)x)=P(X(k+1)(x+log(k+1))X1++Xk+1k+1)=P(X(k+1)log(k+1)x+(x+log(k+1))Tk+1),

gdzie . Ta zmienna znika z prawdopodobieństwem, ponieważ i . Asymptotycznie rozkład jest taki sam jak w przypadku . Ponieważ to IID, mamyTk+1=X1++Xk+1k+11E(Tk+1)=0V.zar(log(k+1)T.k+1)=(log(k+1))2)k+10X(k+1)-log(k+1)Xja

P.(X(k+1)-log(k+1)x)=P.(X1x+log(k+1))k+1=(1-mi-x-log(k+1))k+1=(1-mi-xk+1)k+1exp{-mi-x}.

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 .kk=10,20,50kk50

Dystrybucja największego fragmentu złamanego patyka

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.

  1. Bairamov i in. (2010) Ogranicz wyniki dla zamówionych jednolitych odstępów , dokumenty statystyczne, 51: 1, s. 227–240
  2. Holst (1980) O długości kawałków patyka przypadkowo złamanych , J. Appl. Prob., 17, str. 623-634
  3. Pyke (1965) Spacings , JRSS (B) 27: 3, ss. 395–449
  4. 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 ? mi(Zk2))
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
1
$ gui11aume Zajrzyj tutaj: mathoverflow.net/a/293381/42864
Amir Sagiv
1
@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. Zk2)
gui11aume
3

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
1
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
gui11aume
1
Dziękuję za sugestie. Są ważne poza wymianą stosu i pamiętam, aby ich użyć.
Lima
1

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
2
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ę