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

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,\ldots,m\}$$1\le n\le m$

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)},\ldots,a_{(n)}−a_{(n-1)},m+1-a_{(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, $\mathbb{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 $m-n+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} \ rceil$\lceil\frac{m-n}{n+1}\rceil$ . Definieren Sie die Wahrscheinlichkeit einer beliebigen Kombination $T= {m \choose n}^{-1}$ .

Ich habe die Wahrscheinlichkeitsmassenfunktion teilweise gelöst als $P(g_{(n+1)} = k) = P(k;m,n) = \begin{cases} 0 & k < \lceil\frac{m-n}{n+1}\rceil\\ 1 & k = \frac{m-n}{n+1} \\ 1 & k = 1 \text{ (occurs when $m=n$)} \\ T(n+1)& k = 2 \text{ (occurs when $m=n+1$)} \\ T(n+1)& k = \frac{m-(n-1)}{n} \\ ? & \frac{m-(n-1)}{n} \le k \le m-n+1 \\ T(n+1)& k = m-n+1\\ 0 & k > m-n+1 \end{cases} \tag{1}$

Aktuelle Arbeit (1): Die Gleichung für die erste Lücke $a_{(1)}$ ist einfach:

$$P(a_{(1)} = k) = P(k;m,n) = \frac{1}{{m \choose n}} \sum_{k=1}^{m-n+1} {m-k-1 \choose n-1}$$ Der erwartete Wert hat einen einfachen Wert: $\mathbb{E}[P(a_{(1)})] = \frac{1}{ {m \choose n}} \sum_{k=1}^{m-n+1} {m-k-1 \choose n-1} k = \frac{m-n}{1+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]

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 denen$f(g;n,m)$$a_{(1)}$$g$$g$$n-1$$\{g+1,g+2,\ldots,m\}$$\binom{m-g}{n-1}$$\binom{m}{n}$

$$\Pr(a_{(1)}=g = f(g;n,m) = \frac{\binom{m-g}{n-1}}{\binom{m}{n}}.$$

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

$$\Pr(a_{(1)} \gt g) = Q(g;n,m)= \frac{(m-g)\binom{m-g-1}{n-1}}{n \binom{m}{n}}.$$

Sei die Zufallsvariable, die durch die größte Lücke gegeben ist:$G_{n,m}$

$$G_{n,m} = \max\left(a_{(1)}, a_{(2)}-a_{(1)}, \ldots, a_{(n)}-a_{(n-1)}\right).$$

(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(G_{n,m}\gt g),$$ $G_{n,m}$$n=1$

$$P(g;1,m) = \Pr(G_{1,m} \gt 1) = \frac{m-g}{m},\ g=0, 1, \ldots, m.\tag{1}$$

Für ein größeres ist zu beachten, dass das Ereignis die disjunkte Vereinigung des Ereignisses ist$n\gt 1$$G_{n,m}\gt g$

$$a_{1} \gt g,$$

für die die allererste Lücke überschreitet , und die getrennten Ereignisse$g$$g$

$$a_{1}=k\text{ and } G_{n-1,m-k} \gt g, \ k=1, 2, \ldots, 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 hinzu$k$$g$

$$P(g;n,m) = Q(g;n,m) + \sum_{k=1}^g f(k;n,m) P(g;n-1,m-k).\tag{2}$$

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.$g$$i=1,2,\ldots,n$$j=1,2,\ldots,m$$P(g;n,m)$$(1)$$(2)$$O(gm)$$O(gmn)$$g=1$$g=m-n+1$$O(m^3n)$

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

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

Schließlich erhält man die Erwartung von , indem man seine Überlebensfunktion ab summiert :$G_{n,m}$$g=0$

$$\mathbb{E}(G_{n,m}) = \sum_{g=0}^{m-n+1} P(g;n,m).$$

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