Maximale Lücke zwischen Proben, die ersatzlos aus einer diskreten Gleichverteilung gezogen wurden

16

Dieses Problem hängt mit der Erforschung der Roboterabdeckung in meinem Labor zusammen:

Zeichne zufällig Zahlen aus der Menge ohne Ersetzung und sortiere die Zahlen in aufsteigender Reihenfolge. .n{1,2,,m}1nm

Aus dieser sortierten Liste von Zahlen wird die Differenz zwischen aufeinanderfolgenden Zahlen und den Grenzen erzeugt: . Dies ergibt Lücken.g = { a ( 1 ) , a ( 2 ) - a ( 1 ) , ... , a ( n ) - a ( n - 1 ) , m + 1 - a ( n ) } n +{a(1),a(2),,a(n)}g={a(1),a(2)a(1),,a(n)a(n1),m+1a(n)}n+1

Wie ist die maximale Lücke verteilt?

P(max(g)=k)=P(k;m,n)=?

Dies kann mit Hilfe der Auftragsstatistik umrahmt werden : P(g(n+1)=k)=P(k;m,n)=?

Siehe Link für die Verteilung der Lücken , aber diese Frage fragt nach der Verteilung der maximalen Lücke.

Ich wäre mit dem Durchschnittswert zufrieden, E[g(n+1)] .

Wenn n=m alle Lücken die Größe 1. Wenn n+1=m gibt es eine Lücke der Größe 2 und n+1 mögliche Stellen. Die maximale Lückengröße ist mn+1 , und diese Lücke kann vor oder nach einer der n Zahlen für insgesamt n+1 mögliche Positionen platziert werden. Die kleinste maximale Lückengröße ist \ lceil \ frac {mn} {n + 1} \ rceilmnn+1 . Definieren Sie die Wahrscheinlichkeit einer beliebigen Kombination T=(mn)1 .

Ich habe die Wahrscheinlichkeitsmassenfunktion teilweise gelöst als (1)P(g(n+1)=k)=P(k;m,n)={0k<mnn+11k=mnn+11k=1 (occurs when m=n)T(n+1)k=2 (occurs when m=n+1)T(n+1)k=m(n1)n?m(n1)nkmn+1T(n+1)k=mn+10k>mn+1

Aktuelle Arbeit (1): Die Gleichung für die erste Lücke a(1) ist einfach:

P(a(1)=k)=P(k;m,n)=1(mn)k=1mn+1(mk1n1)
Der erwartete Wert hat einen einfachen Wert: E[P(a(1))]=1(mn)k=1mn+1(mk1n1)k=mn1+n . Aufgrund der Symmetrie erwarte ich, dass alle n Lücken diese Verteilung haben. Vielleicht könnte die Lösung gefunden werden, indem n mal aus dieser Verteilung gezogen wird.

Aktuelle Arbeit (2): Es ist einfach, Monte-Carlo-Simulationen auszuführen.

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
quelle
1
Unter diesen Bedingungen muss n <= m sein. Ich denke, Sie wollen g = {a_ (1), a_ (2) -a_ (1), ..., a_ (n) -a_ (n-1)}. Bedeutet Zufallsauswahl, dass bei der ersten Ziehung jede Zahl mit einer Wahrscheinlichkeit von 1 / m ausgewählt wird? Da Sie nicht ersetzen, wäre die Wahrscheinlichkeit 1 / (m-1) in der Sekunde und so weiter bis zu 1 in der m-ten Ziehung, wenn n = m ist. Wenn n <m, würde dies früher aufhören, wobei die letzte Ziehung die Wahrscheinlichkeit 1 / (m- (n-1)) bei der n-ten Ziehung hat.
Michael R. Chernick
2
Ihre ursprüngliche Beschreibung von ergab keinen Sinn, da Sie (glaube ich) zwei der Indizes transponiert haben. Vergewissern Sie sich, dass meine Bearbeitung Ihrer Absicht entspricht. Bestätigen Sie insbesondere, dass es Lücken gibt, von denen die erste ist. gna(1)
whuber
1
@gung Ich denke, dies ist Forschung, anstatt Selbststudium
Glen_b -Reinstate Monica
1
Ich denke, Ihre minimalen und maximalen Spaltgrößen sollten und . Die minimale Lückengröße wird festgelegt, wenn aufeinanderfolgende ganze Zahlen ausgewählt werden, und die maximale Lückengröße wird festgelegt, wenn Sie und erste ganze Zahlen (oder und ) auswählen1mn+1mn11,,n11mn+2,,m
Wahrscheinlichkeitsrechnung
1
Vielen Dank Michael Chernick und Wahrscheinlichkeitslogik, Ihre Korrekturen wurden vorgenommen. Vielen Dank an @whuber für die Korrektur!
AaronBecker

Antworten:

9

Sei die Chance, dass das Minimum gleich ; Das heißt, die Stichprobe besteht aus und einer Teilmenge von . Es gibt solche Teilmengen aus den gleich wahrscheinlich Teilmengen, aus denenf(g;n,m)a(1)ggn1{g+1,g+2,,m}(mgn1)(mn)

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

Addiert man für alle möglichen Werte von größer als ergibt sich die Überlebensfunktionf(k;n,m)kg

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

Sei die Zufallsvariable, die durch die größte Lücke gegeben ist:Gn,m

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

(Dies beantwortet die Frage in ihrer ursprünglichen Fassung, bevor sie so geändert wurde, dass sie eine Lücke zwischen und .)a(n)m Wir berechnen ihre Überlebensfunktion woraus sich die gesamte Verteilung von ohne weiteres ableitet. Die Methode ist ein dynamisches Programm, das mit beginnt , für das dies offensichtlich ist

P(g;n,m)=Pr(Gn,m>g),
Gn,mn=1

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

Für ein größeres ist zu beachten, dass das Ereignis die disjunkte Vereinigung des Ereignisses istn>1Gn,m>g

a1>g,

für die die allererste Lücke überschreitet , und die getrennten Ereignissegg

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

für die die erste Lücke gleich und eine Lücke größer als später in der Probe auftritt. Das Gesetz der Gesamtwahrscheinlichkeit setzt die Wahrscheinlichkeiten dieser Ereignisse hinzukg

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

Wenn wir korrigieren und ein durch und indiziertes Zweiwege-Array auslegen , können wir unter Verwendung von berechnen die erste Zeile ausfüllen und jede nachfolgende Zeile mit pro Zeile ausfüllen . Folglich kann die Tabelle in werden und alle Tabellen für bis können in konstruiert werden.gi=1,2,,nj=1,2,,mP(g;n,m)(1)(2)O(gm)O(gmn)g=1g=mn+1O(m3n)

Zahl

Diese Diagramme zeigen die Überlebensfunktion für . Wenn zunimmt, bewegt sich der Graph nach links, entsprechend der abnehmenden Wahrscheinlichkeit großer Lücken.gP(g;n,64)n=1,2,4,8,16,32,64n

Geschlossene Formeln für können in vielen speziellen Fällen erhalten werden, insbesondere für große , aber ich konnte keine geschlossene Formel erhalten, die für alle . Gute Näherungen sind leicht verfügbar, wenn dieses Problem durch das analoge Problem für kontinuierliche gleichförmige Variablen ersetzt wird.P(g;n,m)ng,n,m

Schließlich erhält man die Erwartung von , indem man seine Überlebensfunktion ab summiert :Gn,mg=0

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

Abbildung 2: Konturdiagramm der Erwartung

Dieses Konturdiagramm der Erwartung zeigt Konturen bei , die von dunkel nach hell übergehen.2,4,6,,32

whuber
quelle
Vorschlag: Zeile "Sei die durch die größte Lücke gegebene Zufallsvariable:", addieren Sie bitte die letzte Lücke von . Ihr Erwartungsdiagramm entspricht meiner Monte-Carlo-Simulation. Gn,mm+1an
AaronBecker