Ten problem jest związany z badaniami mojego laboratorium w zakresie robotów:
Narysuj losowo liczb ze zbioru bez zamiany i posortuj liczby w porządku rosnącym. .n
Z tej posortowanej listy liczb wygeneruj różnicę między kolejnymi liczbami a granicami: . Daje to przerwy .{ a ( 1 ) , a ( 2 ) , … , a ( n ) }
Jaki jest rozkład maksymalnej luki?
P ( max ( g ) = k ) = P ( k ; m , n ) = ?
Można to sformułować za pomocą statystyk zamówienia :
P ( g ( n + 1 ) = k ) = P ( k ; m , n ) = ?
Zobacz link do podziału luk , ale pytanie to dotyczy rozkładu maksymalnej luki.
Byłbym zadowolony ze średniej wartości, E [ g ( n + 1 ) ]
Jeśli n = m
Częściowo rozwiązałem funkcję masy prawdopodobieństwa jako
P ( g ( n + 1 ) = k ) = P ( k ; m , n ) = { 0 k < ⌈ m - nn + 1 ⌉1k=m-nn + 1 1k=1 (występuje, gdy m=n)T(n+1)k=2 (występuje, gdy m=n+1)T(n+1)k=m-(n-1)n ? m-(n-1)n ≤k≤m-n+1T(n+1)k=m-n+10k>m-n+1
Bieżąca praca (1):
Równanie dla pierwszej przerwy a ( 1 )
Bieżąca praca (2): łatwo jest uruchomić symulacje Monte Carlo.
simMaxGap[m_, n_] := Max[Differences[Sort[Join[RandomSample[Range[m], n], {0, m+1}]]]];
m = 1000; n = 1; trials = 100000;
SmoothHistogram[Table[simMaxGap[m, n], {trials}], Filling -> Axis,
Frame -> {True, True, False, False},
FrameLabel -> {"k (Max gap)", "Probability"},
PlotLabel -> StringForm["m=``,n=``,smooth histogram of maximum map for `` trials", m, n, trials]][![enter image description here][1]][1]
Odpowiedzi:
Niech będzie szansą, że minimum, , równa się ; to znaczy, że próbka składa się z a -subset o . Istnieje takich podzbiorów z równie prawdopodobnych podzbiorówf(g;n,m)f(g;n,m) a(1)a(1) gg gg n−1n−1 {g+1,g+2,…,m}{g+1,g+2,…,m} (m−gn−1)(m−gn−1) (mn)(mn)
Pr(a(1)=g=f(g;n,m)=(m−gn−1)(mn).
Dodanie dla wszystkich możliwych wartości większych niż daje funkcję przeżyciaf(k;n,m)f(k;n,m) kk gg
Pr(a(1)>g)=Q(g;n,m)=(m−g)(m−g−1n−1)n(mn).
Niech będzie zmienną losową podaną przez największą lukę:Gn,mGn,m
Gn,m=max(a(1),a(2)−a(1),…,a(n)−a(n−1)).
(To odpowiada na pytanie w pierwotnym kształcie, zanim zostało zmodyfikowane w celu uwzględnienia luki między i .)a(n)a(n) mm
Obliczymy jego funkcję przeżycia z którego łatwo wywodzi się cały rozkład . Metoda jest programem dynamicznym rozpoczynającym się od , dla którego jest oczywiste, żeP(g;n,m)=Pr(Gn,m>g),
P(g;1,m)=Pr(G1,m>1)=m−gm, g=0,1,…,m.
W przypadku większego należy pamiętać, że zdarzenie jest rozłącznym połączeniem zdarzenian>1n>1 Gn,m>gGn,m>g
a1>g,
dla których pierwsza przerwa przekracza , a oddzielne zdarzeniagg gg
a1=k and Gn−1,m−k>g, k=1,2,…,g
dla których pierwsza przerwa wynosi a przerwa większa niż występuje później w próbce. Prawo całkowitego prawdopodobieństwa zakłada, że prawdopodobieństwa tych zdarzeń dodają, skądkk gg
P(g;n,m)=Q(g;n,m)+g∑k=1f(k;n,m)P(g;n−1,m−k).
Naprawiając i układając tablicę dwukierunkową indeksowaną przez i , możemy obliczyć za pomocą wypełnić pierwszy wiersz i wypełnić każdy kolejny wiersz, używając operacji na wiersz. W związku z tym tabelę można uzupełnić w operacjach , a wszystkie tabele dla do można konstruować w operacjach .gg i=1,2,…,ni=1,2,…,n j=1,2,…,mj=1,2,…,m P(g;n,m)P(g;n,m) (1)(1) (2)(2) O(gm)O(gm) O(gmn)O(gmn) g=1g=1 g=m−n+1g=m−n+1 O(m3n)O(m3n)
Te wykresy pokazują funkcję przeżycia dla . W miarę wzrostu wykres przesuwa się w lewo, co odpowiada malejącym szansom na duże przerwy.g→P(g;n,64)g→P(g;n,64) n=1,2,4,8,16,32,64n=1,2,4,8,16,32,64 nn
Wzory zamknięte dla można uzyskać w wielu szczególnych przypadkach, szczególnie dla dużych , ale nie byłem w stanie uzyskać zamkniętego wzoru, który dotyczy wszystkich . Dobre przybliżenia są łatwo dostępne poprzez zastąpienie tego problemu analogicznym problemem dla ciągłych zmiennych jednorodnych.P(g;n,m)P(g;n,m) nn g,n,m
Wreszcie, oczekiwanie uzyskuje się poprzez zsumowanie jego funkcji przeżycia zaczynającej się od :Gn,mg=0
E(Gn,m)=m−n+1∑g=0P(g;n,m).
Ten wykres konturowy oczekiwań pokazuje kontury w , przechodząc od ciemności do światła.2,4,6,…,32
źródło