Brain-Teaser: Was ist die erwartete Länge einer iid-Sequenz, die bei einer gleichmäßigen [0,1] -Verteilung monoton ansteigt?

Dies ist eine Interviewfrage für eine quantitative Analystenposition, über die hier berichtet wird . Angenommen, wir zeichnen aus einer gleichmäßigen $[0,1]$ -Verteilung und die Ziehungen lauten: Wie lang ist die erwartete monoton ansteigende Verteilung? Das heißt, wir hören auf zu zeichnen, wenn die aktuelle Auslosung kleiner oder gleich der vorherigen Auslosung ist.

Aber ich finde es immer schwieriger, diese verschachtelten Integrale zu berechnen, und ich habe nicht den "Trick", zu zu verallgemeinern . Ich weiß, die endgültige Antwort ist strukturiert. $\Pr(\text{length} = n)$

Irgendwelche Ideen zur Beantwortung dieser Frage?

Hier einige allgemeine Hinweise zur Lösung dieser Frage:

Sie haben eine Folge von kontinuierlichen IID-Zufallsvariablen, was bedeutet, dass sie austauschbar sind . Was bedeutet dies für die Wahrscheinlichkeit, eine bestimmte Reihenfolge für die ersten Werte zu erhalten? Wie groß ist die Wahrscheinlichkeit, dass die Reihenfolge für die ersten Werte steigt ? Es ist möglich, dies herauszufinden, ohne die Verteilung der zugrunde liegenden Zufallsvariablen zu integrieren. Wenn Sie dies gut machen, können Sie eine Antwort ableiten, ohne von einer gleichmäßigen Verteilung ausgehen zu müssen, dh Sie erhalten eine Antwort, die für austauschbare Folgen kontinuierlicher Zufallsvariablen gilt.$n$$n$

Hier ist die vollständige Lösung ( schauen Sie nicht, ob Sie das selbst herausfinden sollen ):

Sei Ihre Folge von unabhängigen kontinuierlichen Zufallsvariablen, und sei ist die Anzahl ansteigender Elemente am Anfang der Sequenz. Da es sich um fortlaufend austauschbare Zufallsvariablen handelt, sind sie mit ziemlicher Sicherheit ungleich und jede Reihenfolge ist gleich wahrscheinlich. Wir haben also: (Beachten Sie, dass dieses Ergebnis für jede IID-Sequenz kontinuierlicher Zufallsvariablen gilt; sie müssen nicht gleichmäßig verteilt sein.) Die Zufallsvariable hat also eine Wahrscheinlichkeitsmassenfunktion$U_1, U_2, U_3, \cdots \sim \text{IID Continuous Dist}$$N \equiv \max \{ n \in \mathbb{N} | U_1 < U_2 < \cdots < U_n \}$

$$\mathbb{P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) = \frac{1}{n!}.$$ $N$ $$p_N(n) = \mathbb{P}(N=n) = \frac{1}{n!} - \frac{1}{(n+1)!} = \frac{n}{(n+1)!}.$$ Sie werden feststellen, dass dieses Ergebnis mit den Werten übereinstimmt, die Sie mithilfe der Integration über die zugrunde liegenden Werte berechnet haben. (Dieser Teil wird für die Lösung nicht benötigt; er ist der Vollständigkeit halber enthalten.) Unter Verwendung einer bekannten Regel für den erwarteten Wert einer nicht negativen Zufallsvariablen haben wir: Beachten Sie erneut, dass in unserer Arbeit nichts die zugrunde liegende gleichmäßige Verteilung verwendet hat. Daher ist dies ein allgemeines Ergebnis, das für jede austauschbare Folge kontinuierlicher Zufallsvariablen gilt. $$\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$$

Einige weitere Einblicke:

Aus der obigen Arbeit sehen wir, dass dieses Verteilungsergebnis und der daraus resultierende erwartete Wert nicht von der zugrunde liegenden Verteilung abhängen, solange es sich um eine kontinuierliche Verteilung handelt. Dies ist wirklich nicht überraschend, wenn man bedenkt, dass jede kontinuierliche skalare Zufallsvariable durch eine monotone Transformation einer einheitlichen Zufallsvariablen erhalten werden kann (wobei die Transformation ihre Quantilfunktion ist). Da monotone Transformationen die Rangordnung beibehalten, ist das Betrachten der Ordnungswahrscheinlichkeiten beliebiger kontinuierlicher IID-Zufallsvariablen dasselbe wie das Betrachten der Ordnungswahrscheinlichkeiten einheitlicher IID- Zufallsvariablen.

Eine weitere Lösungsmethode, mit der Sie die Lösung für einen allgemeineren Fall finden.

Angenommen, ist die erwartete Länge einer monotonen Sequenz , sodass . Der zu berechnende Wert ist . Und wir wissen, dass . Konditionierung auf den nächsten Wert,$F(x)$$\{x_1, x_2, ...\}$$x\leq x_1\leq x_2\leq\cdots$$F(0)$$F(1)=0$

Dabei ist die U [0,1] -Dichte. So$\pi(y)=1$

Wenn wir mit der Randbedingung lösen , erhalten wir . Daher ist .$F(1)=0$$F(x) = e^{(1-x)}-1$$F(0)=e-1$

Eine andere Lösungsmethode besteht darin, das Integral direkt zu berechnen.

Die Wahrscheinlichkeit, eine Sequenz zu erzeugen, deren zunehmender Teil die Länge von ist , wobei .$\geq n$$f^n(0)$$f^n(x) = \int_{x}^{1}\int_{x_1}^{1}\int_{x_2}^{1}...\int_{x_{n-2}}^{1}\int_{x_{n-1}}^{1}dx_ndx_{n-1}...dx_2dx_1$

Wir müssen berechnen .$f^n(0)$

Wenn Sie versuchen, die ersten mehreren zu berechnen , werden Sie vielleicht feststellen, dass$f^n(x)$$f^n(x) = \sum_{t=0}^n \dfrac{(-x)^t}{t!(n-t)!}$

Basisfall: Wenn , ist$n=1$$f^1(x) = \sum_{t=0}^1 \dfrac{(-x)^t}{t!(n-t)!}=1-x=\int_{x}^{1}dx_1$

Induktive Hypothese: Wenn , ist$n=k$$f^n(x) = \sum_{t=0}^k \dfrac{(-x)^t}{t!(k-t)!}\text{ , for }k \geq 1$

Induktive Stufe: wenn ,$n = k+1$

$\ \ \ \ \ f^{n}(x) = f^{k+1}(x) = \int_{x}^{1}f^{k}(x^*)dx^*$

$=\int_{x}^{1}\sum_{t=0}^{k} \dfrac{(-x^*)^t}{t!(k-t)!}dx^*$

$=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{t!(k-t)!\times(t+1)}\Biggr|_{x}^{1}\\=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{(t+1)!(k-t)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{-(-x^*)^{t}}{t!(k-t+1)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}}{t!(k-t+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}+\sum_{t=0}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}-\dfrac{(1-1)^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=0}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

Durch die mathematische Induktion gilt die Annahme.

Wir erhalten also$f^n(0)=\dfrac{1}{n!}$

Also ist$E(length)=\sum_{n=1}^{\infty} Pr(length\geq n)=\sum_{n=1}^{\infty} \dfrac{1}{n!}=e-1$