Łamigłówka: Jaka jest oczekiwana długość sekwencji iid, która monotonicznie wzrasta, gdy jest pobierana z jednolitego rozkładu [0,1]?

To pytanie do wywiadu dotyczące stanowiska analityka ilościowego, przedstawione tutaj . Załóżmy, że rysujemy z jednolitego rozkładu a losowania są takie same, jaka jest oczekiwana długość monotonicznie rosnącego rozkładu? Oznacza to, że przestajemy rysować, jeśli bieżące losowanie jest mniejsze lub równe poprzedniemu losowaniu. $[0,1]$

Mam kilka pierwszych:

Pr (length = 1) = \int_{0}^{1} \int_{0}^{x_{1}} d x_{2} d x_{1} = 1 / 2

$\Pr(\text{length} = 1) = \int_0^1 \int_0^{x_1} \mathrm{d}x_2\, \mathrm{d}x_1 = 1/2$

Pr (length = 2) = \int_{0}^{1} \int_{x_{1}}^{1} \int_{0}^{x_{2}} d x_{3} d x_{2} d x_{1} = 1 / 3

$\Pr(\text{length} = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} \mathrm{d}x_3 \, \mathrm{d}x_2 \, \mathrm{d}x_1 = 1/3$

Pr (length = 3) = \int_{0}^{1} \int_{x_{1}}^{1} \int_{x_{2}}^{1} \int_{0}^{x_{3}} d x_{4} d x_{3} d x_{2} d x_{1} = 1 / 8

$\Pr(\text{length} = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} \mathrm{d}x_4\, \mathrm{d}x_3\, \mathrm{d}x_2\, \mathrm{d}x_1 = 1/8$

ale coraz trudniej jest mi wyliczyć te zagnieżdżone całki i nie dostaję „sztuczki” do uogólnienia na $\Pr(\text{length} = n)$ . Wiem, że ostateczna odpowiedź jest ułożona

E (length) = \sum_{n = 1}^{\infty} n Pr (length = n)

$\mathbb E(\text{length}) = \sum_{n=1}^{\infty}n\Pr(\text{length} = n)$

Jakieś pomysły na odpowiedź na to pytanie?

— Amazonka
źródło

Odpowiedzi:

Oto kilka ogólnych wskazówek na temat rozwiązania tego pytania:

Masz ciąg ciągłych zmiennych losowych IID, co oznacza, że są one wymienne . Co to oznacza prawdopodobieństwo otrzymania określonego zamówienia dla pierwszych $n$ wartości? Na tej podstawie, jakie jest prawdopodobieństwo uzyskania rosnącego porządku dla pierwszych $n$ wartości? Można to rozwiązać bez integracji w rozkładzie podstawowych zmiennych losowych. Jeśli zrobisz to dobrze, będziesz w stanie uzyskać odpowiedź bez jakiegokolwiek założenia o jednolitym rozkładzie - tzn. Otrzymasz odpowiedź, która dotyczy dowolnych wymienialnych sekwencji ciągłych zmiennych losowych.

Oto pełne rozwiązanie ( nie patrz, czy sam to wymyślisz ):

Niech będzie sekwencją niezależnych ciągłych zmiennych losowych i niech to liczba rosnących elementów na początku sekwencji. Ponieważ są to zmienne losowe wymienialne w sposób ciągły, prawie na pewno nie są sobie równe, a każda kolejność jest równie prawdopodobna, więc mamy: (Zauważ, że ten wynik dotyczy dowolnej sekwencji IID ciągłych zmiennych losowych; nie muszą one mieć jednakowego rozkładu). Zatem zmienna losowa ma funkcję masy prawdopodobieństwa $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 \}$
$P (N ⩾ n) = P (U_{1} < U_{2} < \dots < U_{n}) = \frac{1}{n!} .$ $\mathbb{P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) = \frac{1}{n!}.$ $N$ $p_{N} (n) = P (N = n) = \frac{1}{n!} - \frac{1}{(n + 1)!} = \frac{n}{(n + 1)!} .$ $p_N(n) = \mathbb{P}(N=n) = \frac{1}{n!} - \frac{1}{(n+1)!} = \frac{n}{(n+1)!}.$ Zauważysz, że ten wynik jest zgodny z wartościami obliczonymi przez całkowanie względem wartości leżących u podstaw. (Ta część nie jest potrzebna do rozwiązania; jest uwzględniona dla kompletności.) Korzystając ze znanej reguły oczekiwanej wartości nieujemnej zmiennej losowej , mamy: Zauważ ponownie, że w naszej pracy nie ma nic, co użyłoby leżącego u podstaw rozkładu równomiernego. Jest to zatem ogólny wynik, który stosuje się do dowolnej wymiennej sekwencji ciągłych zmiennych losowych. $E (N) = \sum_{n = 1}^{\infty} P (N ⩾ n) = \sum_{n = 1}^{\infty} \frac{1}{n!} = e - 1 = 1.718282.$ $\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$

Kilka dalszych spostrzeżeń:

Z powyższego działania wynika, że ten wynik podziału i wynikająca z niego oczekiwana wartość nie zależą od rozkładu leżącego u podstaw, o ile jest to rozkład ciągły. To naprawdę nie jest zaskakujące, gdy weźmiemy pod uwagę fakt, że każdą ciągłą skalarną zmienną losową można uzyskać poprzez monotoniczną transformację jednolitej zmiennej losowej (przy czym transformacja jest funkcją kwantylową). Ponieważ transformacje monotoniczne zachowują porządek rang, analizowanie prawdopodobieństwa uporządkowania dowolnych ciągłych zmiennych losowych IID jest tym samym, co analizowanie prawdopodobieństwa uporządkowania zmiennych losowych jednorodnych IID .

— Przywróć Monikę
źródło

Ładnie wykonane! (+1)

— łucznik

@ Ben Idę za tobą do ostatniego równania ... Myślałem, że oczekiwana wartość powinna wynosić, zamiast ... czy możesz wyjaśnić tę część bardziej?

E (N) = \sum_{n = 1}^{\infty} P (N = n) * n = \sum_{n = 1}^{\infty} n^{2} / (n + 1)!

$E(N)=∑_{n=1}^∞P(N=n)*n=∑_{n=1}^∞ n^2/(n+1)!$

E (N) = \sum_{n = 1}^{\infty} P (N ⩾ n)

$E(N)=∑_{n=1}^∞P(N⩾n)$

— Amazonian

Jest to dobrze znana reguła dotycząca oczekiwanej wartości nieujemnej zmiennej losowej . Korzystając z techniki polegającej na zamianie kolejności sumowań, masz: Powinieneś więc znaleźć, że .

E (N) = \sum_{n = 1}^{\infty} n P (N = n) = \sum_{n = 1}^{\infty} \sum_{k = 1}^{n} P (N = n) = \sum_{n = 1}^{\infty} \sum_{k = n}^{\infty} P (N = k) = \sum_{n = 1}^{\infty} P (N ⩾ n) .

$\mathbb{E}(N) = \sum_{n=1}^\infty n \mathbb{P}(N=n) = \sum_{n=1}^\infty \sum_{k=1}^n \mathbb{P}(N = n) = \sum_{n=1}^\infty \sum_{k=n}^\infty \mathbb{P}(N =k) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n).$

\sum_{n} \frac{1}{n!} = \sum_{n} \frac{n^{2}}{(n + 1)!}

$\sum_n \tfrac{1}{n!} = \sum_n \tfrac{n^2}{(n+1)!}$

— Przywróć Monikę

Czy możesz dlaczego ?

P (N ⩾ n) = P (U_{1} < U_{2} < \dots < U_{n})

${P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n)$

— badmax

@badmax: Zmienna losowa jest liczbą rosnących elementów na początku sekwencji (patrz jej definicja). Zatem, jeśli , oznacza to, że na początku sekwencji jest co najmniej elementów rosnących. Oznacza to, że pierwsze elementów musi być w porządku rosnącym, czyli .

N

$N$

U

$U$

N ⩾ n

$N \geqslant n$

n

$n$

n

$n$

U_{1} < U_{2} < \dots < U_{n}

$U_1 < U_2 < \cdots < U_n$

— Przywróć Monikę

Kolejna metoda rozwiązywania problemów, która zapewnia rozwiązanie bardziej ogólnego przypadku.

Załóżmy, że jest oczekiwaną długością sekwencji monotonicznej , tak że . Wartość, którą chcemy obliczyć, to . I wiemy, że . Uwzględnienie kolejnej wartości, $F(x)$ $\{x_1, x_2, ...\}$ $x\leq x_1\leq x_2\leq\cdots$ $F(0)$ $F(1)=0$

F (x) = \int_{0}^{x} π (y) \cdot 0 d y + \int_{x}^{1} π (y) (1 + F (y)) d y = \int_{x}^{1} 1 + F (y) d y

$F(x) = \int_0^x \pi(y)\cdot 0 dy + \int_x^1\pi(y)(1+F(y))dy= \int_x^1 1+F(y) dy$

gdzie to gęstość U [0,1]. Więc $\pi(y)=1$

F^{'} (x) = - (1 + F (x))

$F'(x)=-(1+F(x))$

Rozwiązując warunek brzegowy , otrzymujemy . Stąd . $F(1)=0$ $F(x) = e^{(1-x)}-1$ $F(0)=e-1$

— jf328
źródło

To jest bardzo sprytne. Wystarczy przeliterować: twoje obserwacje są takie: 1) jeśli jest długością najdłuższej początkowej sekwencji rosnącej minus jeden, wystarczy określić i ustawić i 2) wynosi zero, jeśli i przeciwnym razie. Ponieważ otrzymujemy , które w jednolitym przypadku można rozwiązać bezpośrednio.

L

$L$

E (L | X_{0} = x) =: F (x)

$E(L|X_0=x)=:F(x)$

x = 0

$x=0$

E (L | X_{0} = x, X_{1} = y)

$E(L|X_0=x,X_1=y)$

y < x

$y<x$

1 + E (L | X_{0} = y)

$1+E(L|X_0=y)$

E (L | X_{0} = x) = E (E (L | X_{0} = x, X_{1})) = \int_{R} f_{X} (y) E (L | X_{0} = x, X_{1} = y) d y = \int_{x}^{1} f_{X} (y) (1 + E (L | X_{0} = y)) d y = \int_{x}^{1} f_{X} (y) (1 + F (y)) d y

$E(L|X_0=x)=E(E(L|X_0=x,X_1)) = \int_\mathbb{R} f_X(y) E(L|X_0=x, X_1=y) dy = \int_x^1 f_X(y)(1+E(L|X_0=y))dy= \int_x^1 f_X(y)(1+F(y))dy$

F^{'} (x) = - f_{X} (x) (1 + F (x))

$F'(x)=-f_X(x)(1+F(x))$

— Matthew Towers

+1 Naprawdę bardzo sprytny. Ale ponieważ ostateczna odpowiedź nie zależy od dystrybucji (jak omawia druga odpowiedź), to obliczenie również nie powinno zależeć od . Czy jest jakiś sposób, aby to zobaczyć? CC do @m_t_.

π (y)

$\pi(y)$

— ameba mówi Przywróć Monikę

@amoeba Zgadzam się, że nie powinno zależeć od rozkładu , ale inne wartości powinny: ogólne rozwiązanie tego DE to

F (0)

$F(0)$

X

$X$

F

$F$

F = C e^{- \int π} - 1

$F=Ce^{-\int \pi}-1$

— Matthew Towers

@MartijnWeterings Myślę, że , a nie 1, np. W mundurze dostajemy

C = e

$C=e$

e e^{- x} - 1

$e e^{-x} -1$

— Matthew Towers

Tak masz rację. Użyłem jednolitego przypadku, aby wydedukować moje stwierdzenie, ale fałszywie użyłem zamiast

c e^{1 - x} - 1

$ce^{1-x}-1$

c e^{- x} - 1

$ce^{-x}-1$

— Sextus Empiricus

Inną metodą rozwiązywania jest bezpośrednie obliczenie całki.

Prawdopodobieństwo wygenerowania sekwencji, której rosnąca część ma długość wynosi , gdzie . $\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$

Musimy obliczyć . $f^n(0)$

Jeśli spróbujesz obliczyć kilka pierwszych , być może okaże się, że $f^n(x)$ $f^n(x) = \sum_{t=0}^n \dfrac{(-x)^t}{t!(n-t)!}$

Przypadek podstawowy: gdy , $n=1$ $f^1(x) = \sum_{t=0}^1 \dfrac{(-x)^t}{t!(n-t)!}=1-x=\int_{x}^{1}dx_1$

Hipoteza indukcyjna: gdy , $n=k$ $f^n(x) = \sum_{t=0}^k \dfrac{(-x)^t}{t!(k-t)!}\text{ , for }k \geq 1$

Krok indukcyjny: gdy , $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)!}$

Według indukcji matematycznej założenie to obowiązuje.

Tak więc otrzymujemy to $f^n(0)=\dfrac{1}{n!}$

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

— 劉家維
źródło