Verteilung des größten Fragmentes eines gebrochenen Stockes (Abstände)

Lassen Sie einen Stab der Länge 1 gleichmäßig zufällig in Fragmente zerbrechen . Wie ist die Verteilung der Länge des längsten Fragments? $k+1$

Genauer gesagt, sei IID , und sei die zugehörige Ordnungsstatistik, dh wir ordnen einfach die Probe so, dass . Sei . $(U_1, \ldots U_k)$ $U(0,1)$ $(U_{(1)}, \ldots, U_{(k)})$ $U_{(1)} \leq U_{(2)} \leq, \ldots , \leq U_{(k)}$ $Z_k = \max \left(U_{(1)}, U_{(2)}-U_{(1)}, \ldots, U_{(k)} - U_{(k-1)}, 1-U_{(k)}\right)$

Ich interessiere mich für die Distribution von $Z_k$ . Momente, asymptotische Ergebnisse oder Näherungen für $k \uparrow \infty$ sind ebenfalls interessant.

distributions uniform order-statistics dirichlet-distribution maximum gui11aume
quelle

Dies ist ein gut untersuchtes Problem. siehe R. Pyke (1965), "Spacings", JRSS (B) 27 : 3, S. 395-449. Ich werde versuchen, später noch einmal Informationen hinzuzufügen, es sei denn, jemand schlägt mich. Es gibt auch einen Artikel von 1972 desselben Autors (" Spacings revisited "), aber ich denke, was Sie suchen, ist so ziemlich alles im Ersten. In Devroye (1981) , "Gesetze des iterierten Logarithmus für die Ordnungsstatistik einheitlicher Abstände" Ann. Probab. , 9 : 5, 860 & ndash; 867.

Glen_b -Reinstate Monica

Diese sollten auch einige gute Suchbegriffe enthalten, um später Arbeit zu finden, wenn Sie es brauchen.

Glen_b

Das ist fantastisch. Die erste Referenz ist schwer zu finden. Für Interessierte habe ich es auf The Grand Locus gestellt .

gui11aume

Bitte korrigieren Sie den Druckfehler:

Y_{(k)}

$Y_{(k)}$ anstelle von

U_{(k)}

$U_{(k)}$ .

Viktor

Vielen Dank @Viktor! Zögern Sie nicht, die Bearbeitung für solche kleinen Dinge selbst vorzunehmen (ich denke, dass sie von anderen Benutzern zur Genehmigung überprüft wird).

gui11aume

Mit den Informationen von @Glen_b konnte ich die Antwort finden. Verwenden Sie die gleichen Notationen wie die Frage

P (Z_{k} \leq x) = \sum_{j = 0}^{k + 1} (\binom{k + 1}{j}) (- 1)^{j} (1 - j x)_{+}^{k},

$P(Z_k \leq x) = \sum_{j=0}^{k+1} { k+1 \choose j } (-1)^j (1-jx)_+^k,$

Dabei ist $a_+ = a$ wenn $a > 0$ und sonst $0$ . Ich gebe auch die Erwartung und die asymptotische Konvergenz für die Gumbel- Distribution ( NB : nicht Beta) an

E (Z_{k}) = \frac{1}{k + 1} \sum_{i = 1}^{k + 1} \frac{1}{i} \sim \frac{\log (k + 1)}{k + 1}, P (Z_{k} \leq x) \sim \exp (- e^{- (k + 1) x + \log (k + 1)}) .

$E(Z_k)= \frac{1}{k+1}\sum_{i=1}^{k+1}\frac{1}{i} \sim \frac{\log(k+1)}{k+1}, \\ P(Z_k \leq x) \sim \exp\left(- e^{-(k+1)x + \log(k+1)} \right).$

Das Material der Proofs stammt aus mehreren Veröffentlichungen, die in den Referenzen verlinkt sind. Sie sind etwas langwierig, aber unkompliziert.

1. Nachweis der genauen Verteilung

Sei IID gleichförmige Zufallsvariablen im Intervall . Indem wir sie bestellen, erhalten wir die mit bezeichneten Ordnungsstatistiken . Die einheitlichen Abstände sind definiert als , mit und . Die geordneten Abstände sind die entsprechenden geordneten Statistiken . Die interessierende Variable ist . $(U_1, \ldots, U_k)$ $(0,1)$ $k$ $(U_{(1)}, \ldots, U_{(k)})$ $\Delta_i = U_{(i)} - U_{(i-1)}$ $U_{(0)} = 0$ $U_{(k+1)} = 1$ $\Delta_{(1)} \leq \ldots \leq \Delta_{(k+1)}$ $\Delta_{(k+1)}$

Für festes definieren wir die Indikatorvariable . Aufgrund der Symmetrie ist der Zufallsvektor austauschbar, sodass die gemeinsame Verteilung einer Teilmenge der Größe der gemeinsamen Verteilung von entspricht der erste . Durch die Erweiterung des Produktes erhalten wir somit $x \in (0,1)$ $\mathbb{1}_i = \mathbb{1}_{\{\Delta_i > x\}}$ $(\mathbb{1}_1, \ldots, \mathbb{1}_{k+1})$ $j$ $j$

P (Δ_{(k + 1)} \leq x) = E (\prod_{i = 1}^{k + 1} (1 - 1_{i})) = 1 + \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) (- 1)^{j} E (\prod_{i = 1}^{j} 1_{i}) .

$P(\Delta_{(k+1)} \leq x) = E \left( \prod_{i=1}^{k+1} (1 - \mathbb{1}_i) \right) = 1 + \sum_{j=1}^{k+1} { k+1 \choose j } (-1)^j E \left( \prod_{i=1}^j \mathbb{1}_i \right).$

Wir werden nun beweisen, dass , wodurch die oben angegebene Verteilung erstellt wird. Wir beweisen dies für , da der allgemeine Fall ähnlich bewiesen ist. $E \left( \prod_{i=1}^j \mathbb{1}_i \right) = (1-jx)_+^k$ $j=2$

E (\prod_{i = 1}^{2} 1_{i}) = P (Δ_{1} > x \cap Δ_{2} > x) = P (Δ_{1} > x) P (Δ_{2} > x | Δ_{1} > x) .

$E \left( \prod_{i=1}^2 \mathbb{1}_i \right) = P(\Delta_1 > x \cap \Delta_2 > x) = P(\Delta_1 > x) P(\Delta_2 > x | \Delta_1 > x).$

Wenn , liegen die Haltepunkte im Intervall . In diesem Fall sind die Haltepunkte noch austauschbar, sodass die Wahrscheinlichkeit, dass der Abstand zwischen dem zweiten und dem ersten Haltepunkt größer als ist, mit der Wahrscheinlichkeit identisch ist, dass der Abstand zwischen dem ersten Haltepunkt und der linken Barriere (an Position ) ist größer als . So $\Delta_1 > x$ $k$ $(x,1)$ $x$ $x$ $x$

P (Δ_{2} > x | Δ_{1} > x) = P (all points are in (2 x, 1) | all points are in (x, 1)), so P (Δ_{2} > x \cap Δ_{1} > x) = P (all points are in (2 x, 1)) = (1 - 2 x)_{+}^{k} .

$P(\Delta_2 > x | \Delta_1 > x) = P\big(\text{all points are in } (2x,1) \big| \text{all points are in } (x,1)\big), \; \text{so} \\ P(\Delta_2 > x \cap \Delta_1 > x) = P\big(\text{all points are in } (2x,1)\big) = (1-2x)_+^k.$

2. Erwartung

Für Distributionen mit endlicher Unterstützung haben wir

E (X) = \int P (X > x) d x = 1 - \int P (X \leq x) d x .

$E(X) = \int P(X > x)dx = 1 - \int P(X \leq x)dx.$

Durch Integration der Verteilung von erhalten wir $\Delta_{(k+1)}$

E (Δ_{(k + 1)}) = \frac{1}{k + 1} \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) \frac{(- 1)^{j + 1}}{j} = \frac{1}{k + 1} \sum_{j = 1}^{k + 1} \frac{1}{j} .

$E\left(\Delta_{(k+1)}\right) = \frac{1}{k+1}\sum_{j=1}^{k+1}{k+1 \choose j}\frac{(-1)^{j+1}}{j} = \frac{1}{k+1}\sum_{j=1}^{k+1}\frac{1}{j}.$

Die letzte Gleichheit ist eine klassische Darstellung der harmonischen Zahlen , die wir unten demonstrieren. $H_i = 1+ \frac{1}{2}+ \ldots + \frac{1}{i}$

H_{k + 1} = \int_{0}^{1} 1 + x + \dots + x^{k} d x = \int_{0}^{1} \frac{1 - x^{k + 1}}{1 - x} d x .

$H_{k+1} = \int_0^1 1 + x + \ldots + x^k dx = \int_0^1 \frac{1-x^{k+1}}{1-x}dx.$

Mit der Änderung der Variablen und der Erweiterung des Produkts erhalten wir $u = 1-x$

H_{k + 1} = \int_{0}^{1} \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) (- 1)^{j + 1} u^{j - 1} d u = \sum_{j = 1}^{k + 1} (\binom{k + 1}{j}) \frac{(- 1)^{j + 1}}{j} .

$H_{k+1} = \int_0^1\sum_{j=1}^{k+1}{ k+1 \choose j }(-1)^{j+1}u^{j-1}du = \sum_{j=1}^{k+1}{k+1 \choose j}\frac{(-1)^{j+1}}{j}.$

3. Alternative Konstruktion gleichmäßiger Abstände

Um die asymptotische Verteilung des größten Fragments zu erhalten, müssen wir eine klassische Konstruktion einheitlicher Abstände als Exponentialvariablen dividiert durch ihre Summe zeigen. Die Wahrscheinlichkeitsdichte der zugehörigen Ordnungsstatistik beträgt $(U_{(1)}, \ldots, U_{(k)})$

f_{U_{(1)}, \dots U_{(k)}} (u_{(1)}, \dots, u_{(k)}) = k!, 0 \leq u_{(1)} \leq \dots \leq u_{(k + 1)} .

$f_{U_{(1)}, \ldots U_{(k)}}(u_{(1)}, \ldots, u_{(k)}) = k!, \; 0 \leq u_{(1)} \leq \ldots \leq u_{(k+1)}.$

Wenn wir die gleichmäßigen Abstände , erhalten wir mit $\Delta_i = U_{(i)} - U_{(i-1)}$ $U_{(0)} = 0$

f_{Δ_{1}, \dots Δ_{k}} (δ_{1}, \dots, δ_{k}) = k!, 0 \leq δ_{i} + \dots + δ_{k} \leq 1.

$f_{\Delta_1, \ldots \Delta_k}(\delta_1, \ldots, \delta_k) = k!, \; 0 \leq \delta_i + \ldots + \delta_k \leq 1.$

Durch die Definition von wir also $U_{(k+1)} = 1$

f_{Δ_{1}, \dots Δ_{k + 1}} (δ_{1}, \dots, δ_{k + 1}) = k!, δ_{1} + \dots + δ_{k} = 1.

$f_{\Delta_1, \ldots \Delta_{k+1}}(\delta_1, \ldots, \delta_{k+1}) = k!, \; \delta_1 + \ldots + \delta_k = 1.$

Nun sei eine exponentielle IID-Zufallsvariable mit dem Mittelwert 1 und sei . Mit einer einfachen Änderung der Variablen können wir das sehen $(X_1, \ldots, X_{k+1})$ $S = X_1 + \ldots + X_{k+1}$

f_{X_{1}, \dots X_{k}, S} (x_{1}, \dots, x_{k}, s) = e^{- s} .

$f_{X_1, \ldots X_k, S}(x_1, \ldots, x_k, s) = e^{-s}.$

Definiere , so dass wir durch eine Änderung der Variablen erhalten $Y_i = X_i/S$

f_{Y_{1}, \dots Y_{k}, S} (y_{1}, \dots, y_{k}, s) = s^{k} e^{- s} .

$f_{Y_1, \ldots Y_k, S}(y_1, \ldots, y_k, s) = s^k e^{-s}.$

Durch Integration dieser Dichte in Bezug auf wir also $s$

f_{Y_{1}, \dots Y_{k},} (y_{1}, \dots, y_{k}) = \int_{0}^{\infty} s^{k} e^{- s} d s = k!, 0 \leq y_{i} + \dots + y_{k} \leq 1, and thus f_{Y_{1}, \dots Y_{k + 1},} (y_{1}, \dots, y_{k + 1}) = k!, y_{1} + \dots + y_{k + 1} = 1.

$f_{Y_1, \ldots Y_k,}(y_1, \ldots, y_k) = \int_0^{\infty}s^k e^{-s}ds = k!, \; 0 \leq y_i + \ldots + y_k \leq 1, \; \text{and thus} \\ f_{Y_1, \ldots Y_{k+1},}(y_1, \ldots, y_{k+1}) = k!, \; y_1 + \ldots + y_{k+1} = 1.$

Die gemeinsame Verteilung von gleichmäßigen Abständen im Intervall ist also die gleiche wie die gemeinsame Verteilung von exponentiellen Zufallsvariablen geteilt durch ihre Summe. Wir kommen zur folgenden Äquivalenz der Verteilung $k+1$ $(0,1)$ $k+1$

Δ_{(k + 1)} \equiv \frac{X_{(k + 1)}}{X_{1} + \dots + X_{k + 1}} .

$\Delta_{(k+1)} \equiv \frac{X_{(k+1)}}{X_1 + \ldots + X_{k+1}}.$

4. Asymptotische Verteilung

Unter Verwendung der obigen Äquivalenz erhalten wir

\begin{aligned} P ((k + 1) Δ_{(k + 1)} - \log (k + 1) \leq x) & = P (X_{(k + 1)} \leq (x + \log (k + 1)) \frac{X_{1} + \dots + X_{k + 1}}{k + 1}) \\ = P (X_{(k + 1)} - \log (k + 1) \leq x + (x + \log (k + 1)) T_{k + 1}), \end{aligned}

$\begin{align} P\big((k+1)\Delta_{(k+1)} - \log(k+1) \leq x\big) &= P\left(X_{(k+1)} \leq (x + \log(k+1))\frac{X_1 + \ldots + X_{k+1}}{k+1}\right) \\ &= P\left(X_{(k+1)} - \log(k+1) \leq x + (x + \log(k+1))T_{k+1}\right), \end{align}$

Dabei ist . Diese Variable verschwindet wahrscheinlich, weil und . Asymptotisch ist die Verteilung dieselbe wie die von . Weil die IID sind, haben wir $T_{k+1} = \frac{X_1+\ldots+X_{k+1}}{k+1} -1$ $E\left(T_{k+1}\right) = 0$ $Var\big(\log(k+1)T_{k+1}\big) = \frac{(\log(k+1))^2}{k+1} \downarrow 0$ $X_{(k+1)} - \log(k+1)$ $X_i$

\begin{aligned} P (X_{(k + 1)} - \log (k + 1) \leq x) & = P {(X_{1} \leq x + \log (k + 1))}^{k + 1} \\ = {(1 - e^{- x - \log (k + 1)})}^{k + 1} = {(1 - \frac{e^{- x}}{k + 1})}^{k + 1} \sim \exp {- e^{- x}} . \end{aligned}

$\begin{align} P\left(X_{(k+1)} - \log(k+1) \leq x \right) &= P\left(X_1 \leq x + \log(k+1)\right)^{k+1} \\ &= \left(1-e^{-x - \log(k+1)}\right)^{k+1} = \left(1-\frac{e^{-x}}{k+1}\right)^{k+1} \sim \exp\left\{-e^{-x}\right\}. \end{align}$

5. Grafische Übersicht

Das folgende Diagramm zeigt die Verteilung des größten Fragments für verschiedene Werte von . Für ich auch die asymptotische Gumbelverteilung (dünne Linie) überlagert. Das Gumbel ist eine sehr schlechte Näherung für kleine Werte von so dass ich sie weglasse, um das Bild nicht zu überladen. Die Gumbel-Näherung ist gut von . $k$ $k=10, 20, 50$ $k$ $k \approx 50$

6. Referenzen

Die obigen Beweise sind den Referenzen 2 und 3 entnommen. Die zitierte Literatur enthält viel mehr Ergebnisse, wie die Verteilung der geordneten Abstände eines beliebigen Ranges, ihre Grenzverteilung und einige alternative Konstruktionen der geordneten gleichmäßigen Abstände. Die wichtigsten Verweise sind nicht leicht zugänglich, daher biete ich auch Links zum Volltext an.

Bairamov et al. (2010) Grenzergebnisse für geordnete gleichmäßige Abstände , Stat. Papers, 51: 1, S. 227-240
Holst (1980) Auf den Längen der zufällig gebrochenen Stockstücke beschreibt J. Appl. Prob., 17, S. 623–634
Pyke (1965) Spacings , JRSS (B) 27: 3, S. 395-449
Renyi (1953) Zur Theorie der Ordnungsstatistik , Acta math Hung, 4, S. 191-231

gui11aume
quelle

Brillant. übrigens eine bekannte Asymptotik für ?

E (Z_{k}^{2})

$E(Z_k ^2)$

Amir Sagiv

@AmirSagiv das ist eine gute Frage. Ich habe mir die Referenzen angesehen und konnte sie nicht finden. Ich konnte den obigen Beweis auch nicht anpassen. Dadurch wurde mir klar, dass ich nicht weiß, wie die Verteilung eines Quadrats eines Gumbel ist. Vielleicht ein guter Anfang?

gui11aume

$ gui11aume Schau mal hier: mathoverflow.net/a/293381/42864

Amir Sagiv

@AmirSagiv Dies ist ein sehr guter Beitrag. Aus irgendeinem Grund habe ich Ihre Frage falsch verstanden und dachte, Sie an der asymptotischen Verteilung von interessiert (obwohl Ihr Kommentar sehr klar war), daher ist mein Kommentar oben nicht so relevant.

Z_{k}^{2}

$Z_k^2$

gui11aume

Verteilung des größten Fragmentes eines gebrochenen Stockes (Abstände)

Antworten:

1. Nachweis der genauen Verteilung

2. Erwartung

3. Alternative Konstruktion gleichmäßiger Abstände

4. Asymptotische Verteilung

5. Grafische Übersicht

6. Referenzen