Maksymalny odstęp między próbkami pobranymi bez zamiany z dyskretnego jednorodnego rozkładu

16

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 n{ 1 , 2 , , m } {1,2,,m}1 n m1nm

Z tej posortowanej listy liczb wygeneruj różnicę między kolejnymi liczbami a granicami: . Daje to przerwy .{ a ( 1 ) , a ( 2 ) , , a ( n ) } {a(1),a(2),,a(n)}g = { a ( 1 ) , a ( 2 ) - a ( 1 ) , , a ( n ) - a ( n - 1 ) , m + 1 - a ( n ) } g={a(1),a(2)a(1),,a(n)a(n1),m+1a(n)}n +1n+1

Jaki jest rozkład maksymalnej luki?

P ( max ( g ) = k ) = P ( k ; m , n ) = ?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 ) = ?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 ) ]E[g(n+1)] .

Jeśli n = mn=m wszystkie odstępy mają rozmiar 1. Jeśli n + 1 = mn+1=m istnieje jedna przerwa o rozmiarze 2)2 , a n + 1n+1 możliwe lokalizacje. Maksymalny rozmiar odstępu wynosi m - n + 1mn+1 , a odstęp ten można umieścić przed dowolną liczbą n lub po niej nn, w sumie n + 1n+1 możliwych pozycji. Najmniejszy maksymalny rozmiar przerwy to m - nn + 1mnn+1 . Określ prawdopodobieństwo dowolnej kombinacji T = ( mn ) -1T=(mn)1 .

Częściowo rozwiązałem funkcję masy prawdopodobieństwa jako P ( g ( n + 1 ) = k ) = P ( k ; m , n ) = { 0 k < m - nn + 11k=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)nkm-n+1T(n+1)k=m-n+10k>m-n+1P(g(n+1)=k)=P(k;m,n)=011T(n+1)T(n+1)?T(n+1)0k<mnn+1k=mnn+1k=1 (occurs when m=n)k=2 (occurs when m=n+1)k=m(n1)nm(n1)nkmn+1k=mn+1k>mn+1(1)

Bieżąca praca (1): Równanie dla pierwszej przerwy a ( 1 )a(1) jest proste: P ( a ( 1 ) = k ) = P ( k ; m , n ) = 1( mn)mn+1k=1(mk1n1)

P(a(1)=k)=P(k;m,n)=1(mn)k=1mn+1(mk1n1)
Oczekiwana wartość ma prostą wartość: E[P(a(1))]=1(mn)mn+1k=1(mk1n1)k=mn1+nE[P(a(1))]=1(mn)mn+1k=1(mk1n1)k=mn1+n . Symetrii, spodziewam wszystkie nn luki mieć tę dystrybucję. Być może rozwiązanie można znaleźć, wyciągając z tego rozkładu nn razy.

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]
AaronBecker
źródło
1
W tych warunkach musisz mieć n <= m. Myślę, że chcesz g = {a_ (1), a_ (2) -a_ (1), ..., a_ (n) -a_ (n-1)}. Czy losowy wybór oznacza wybranie każdej liczby z prawdopodobieństwem 1 / m przy pierwszym losowaniu? Ponieważ nie zastąpisz, prawdopodobieństwo wynosi 1 / (m-1) na drugim i tak dalej do 1 na m-tym losowaniu, jeśli n = m. Jeśli n <m, zatrzymałoby się to wcześniej przy ostatnim losowaniu z prawdopodobieństwem 1 / (m- (n-1)) na n-tym losowaniu.
Michael R. Chernick
2
Twój oryginalny opis nie miał sensu, ponieważ (sądzę) transponowałeś dwa indeksy dolne. Sprawdź, czy moja edycja jest zgodna z twoją intencją: w szczególności potwierdź, że masz na myśli luk, z których pierwsza . ggnna(1)a(1)
whuber
1
@gung Myślę, że to badania, a nie samokształcenie
Glen_b -Reinstate Monica
1
Myślę, że minimalne i maksymalne rozmiary luki powinny być i . Minimalny rozmiar odstępu występuje po wybraniu kolejnych liczb całkowitych, a maksymalny rozmiar odstępu występuje po wybraniu i pierwszych liczb całkowitych (lub i )11mn+1mn+1mmn1n11,,n11,,n111mn+2,,mmn+2,,m
probabilityislogic
1
Dziękuję Michaelowi Chernickowi i prawdopodobieństwu logiczne, twoje poprawki zostały wprowadzone. Dziękujemy @whuber za dokonanie korekty!
AaronBecker

Odpowiedzi:

9

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)ggggn1n1{g+1,g+2,,m}{g+1,g+2,,m}(mgn1)(mgn1)(mn)(mn)

Pr(a(1)=g=f(g;n,m)=(mgn1)(mn).

Pr(a(1)=g=f(g;n,m)=(mgn1)(mn).

Dodanie dla wszystkich możliwych wartości większych niż daje funkcję przeżyciaf(k;n,m)f(k;n,m)kkgg

Pr(a(1)>g)=Q(g;n,m)=(mg)(mg1n1)n(mn).

Pr(a(1)>g)=Q(g;n,m)=(mg)(mg1n1)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(n1)).

Gn,m=max(a(1),a(2)a(1),,a(n)a(n1)).

(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;n,m)=Pr(Gn,m>g),
Gn,mGn,mn=1n=1

P(g;1,m)=Pr(G1,m>1)=mgm, g=0,1,,m.

P(g;1,m)=Pr(G1,m>1)=mgm, g=0,1,,m.(1)

W przypadku większego należy pamiętać, że zdarzenie jest rozłącznym połączeniem zdarzenian>1n>1Gn,m>gGn,m>g

a1>g,

a1>g,

dla których pierwsza przerwa przekracza , a oddzielne zdarzeniagggg

a1=k and Gn1,mk>g, k=1,2,,g

a1=k and Gn1,mk>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ądkkgg

P(g;n,m)=Q(g;n,m)+gk=1f(k;n,m)P(g;n1,mk).

P(g;n,m)=Q(g;n,m)+k=1gf(k;n,m)P(g;n1,mk).(2)

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 .ggi=1,2,,ni=1,2,,nj=1,2,,mj=1,2,,mP(g;n,m)P(g;n,m)(1)(1)(2)(2)O(gm)O(gm)O(gmn)O(gmn)g=1g=1g=mn+1g=mn+1O(m3n)O(m3n)

Postać

Te wykresy pokazują funkcję przeżycia dla . W miarę wzrostu wykres przesuwa się w lewo, co odpowiada malejącym szansom na duże przerwy.gP(g;n,64)gP(g;n,64)n=1,2,4,8,16,32,64n=1,2,4,8,16,32,64nn

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)nng,n,m

Wreszcie, oczekiwanie uzyskuje się poprzez zsumowanie jego funkcji przeżycia zaczynającej się od :Gn,mg=0

E(Gn,m)=mn+1g=0P(g;n,m).

Rycina 2: Konturowy wykres oczekiwań

Ten wykres konturowy oczekiwań pokazuje kontury w , przechodząc od ciemności do światła.2,4,6,,32

Whuber
źródło
Sugestia: wiersz „Niech będzie zmienną losową podaną przez największą lukę:”, proszę dodać ostatnią lukę . Twoja fabuła oczekiwań odpowiada mojej symulacji Monte Carlo. Gn,mm+1an
AaronBecker