Przystanek autobusowy

Jako pierwsze w tym roku proponuję zadanie o marznięciu na przystanku w oczekiwaniu na autobus. Interesuje nas policzenie wartości oczekiwanej minimum z n niezależnych zmiennych losowych, z których każda ma rozkład jednostajny ciągły.

Zadanie pochodzi z AIM Fund Cup 2015. Treść nie jest niestety dostępna internecie, ale nie ma w niej wiele ponad to co wyżej. Może warto tylko dopowiedzieć, że każda zmienna odpowiada jednej linii, której autobusy przyjeżdżają na przystanek co określoną liczbę minut (bez żadnych opóźnień!). Czyli dokładnie co t_i minut na przystanek podjeżdża autobus linii i. Nie wiemy jednak jakie jest „przesunięcie”, w związku z tym zakładamy, że jest ono liczbą rzeczywistą wybraną z przedziału [0,t_i]. Przesunięcia autobusów różnych linii są od siebie całkowicie niezależne. Chcielibyśmy wyznaczyć oczekiwany czas oczekiwania na autobus dowolnej linii. Jeśli więc oznaczymy przez X_i zmienną losową oznaczającą przesunięcie i-tej linii, interesuje nas policzenie E[\min_i X_i]. Dodajmy jeszcze, że n\leq 10^5.

Dla n=1 odpowiedź to oczywiście po prostu \frac{t_1}{2}. Może więc podobnie prosty wzór istnieje także dla większych n? Spróbujmy go wyprowadzić.

Oznaczmy m = \min_i t_i oraz X=\min_i X_i. Z defincji wartości oczekiwanej E[X] = \int_{-\infty}^{\infty}xf(x)dx, gdzie f(x) jest funkcją gęstości zmiennej X. Ta funkcja gęstości to po prostu pochodna funkcji F(x) = \Pr[X \leq x]. Przyjrzyjmy się więc bliżej F(x).

Skoro X = \min_i X_i to (o ile x\in [0,m]) F(x) = 1 - \Pr[X_1 \geq x] \cdot \ldots \cdot \Pr[X_n \geq x]. Każda zmienna X_i ma bardzo prosty rozkład, jesteśmy więc w stanie wyliczyć, że F(x) = 1 - \prod_i \frac{t_i-x}{t_i}. No i fajnie, mamy wzór na F(x)!

F(x) jest wielomianem zmiennej x, oznaczmy więc F(x) = \sum_i a_i x^i. Teraz licząc pochodną i całkując dostajemy, że E[X] = \sum_{i\geq 1} a_i\cdot\frac{i}{i+1}\cdot x^{i+1}. Czyli jeśli tylko znamy współczynniki wielomianu F(x), bez problemu wyliczymy szukaną wartość oczekiwaną. Ale jak wyznaczyć te współczynniki?

Musimy dość szybko przejść z reprezentacji wielomianu przez podanie zer (bo F(x) = 1 - \prod_i \frac{t_i-x}{t_i} to z grubsza właśnie podanie zer) do reprezentacji przez podanie współczynników.

Lemat 1. Można wyznaczyć wszystkie współczynniki wielomianu g(x) = \prod_{i=1}^{n} (x-b_i) w sumarycznym czasie \mathcal{O}(n\log^2 n).

Dowód. Zastosujmy dziel-i-zwyciężaj. Podzielmy iloczyn na dwie części g(x) = \prod_{i=1}^{n/2} (x-b_i) \cdot \prod_{i=n/2+1}^{n} (x-b_i). Wywołując się rekurencyjnie możemy wyznaczyć współczynniki wielomianu g_1(x) = \prod_{i=1}^{n/2} (x-b_i) oraz g_2(x) = \prod_{i=n/2+1}^{n} (x-b_i). Następnie trzeba tylko wymnożyć te dwa wielomiany przy użyciu FFT. Sumaryczny czas działania to T(n) = 2T(n/2)+\mathcal{O}(n\log n), czyli właśnie \mathcal{O}(n\log^2n).

Wydaje się więc, że dostaliśmy rozwiązanie zadania: po wyliczeniu współczynników F(x) wyznaczenie E[X] wymaga tylko czasu liniowego, jeśli użyjemy schematu Hornera (czyli przejrzymy i=n,n-1,\ldots,0 utrzymując aktualny wynik; w kolejnym kroku należy przemnożyć go przez m oraz dodać a_i\cdot\frac{i}{i+1}). Niestety takie rozwiązanie jest obarczone koszmarnie dużymi błędami obliczeń. Błędy zaokrągleń pojawiające się przy wyznaczaniu współczynników F(x) są tak duże, że raczej nie ma co liczyć na uzyskanie żądanej dokładności 10^{-8} (głównie dlatego, że mnożone jednomiany mogą mieć ujemne współczynniki). Trzeba więc jakoś inaczej.

Chcieliśmy wzorek. Co prawda nie jest jasne czy taki wzorek istnieje, ale wydaje się dość prawdopodobne, że dla t_1=t_2=\ldots=t_n=t rozwiązanie powinno mieć dość prostą postać. Spróbujmy. Skoro F(x) = 1 - (1-\frac{x}{t})^{n} to f(x) = \frac{n}{t}(1-\frac{x}{t})^{n-1}. Następnie E[X]=\int_{0}^{t} xf(x)dx = n\int_{0}^{t} \frac{x}{t}(1-\frac{x}{t})^{n-1}dx. Zamieniając \frac{x}{t} na 1-\frac{x}{t} otrzymujemy n\cdot t \int_{0}^{1} (1-x)x^{n-1}dx, czyli ostatecznie E[x] = \frac{t}{n+1}. Mamy prosty wzorek! Fajnie, ale przecież t_i nie muszą być wszystkie takie same. Ale może mogą?

Zredukujemy ogólny przypadek do takiego, w którym wszystkie t_i są takie same. W tym celu wystarczy policzyć p_i, które oznacza prawdopodobieństwo, że dokładnie i zmiennych X_i nie przekracza m. Wtedy E[X] = \sum_{i\geq 1} p_i \frac{t}{i+1} (zauważmy, że p_0=0). Ale jak wyznaczyć te p_i?

Zdefiniujmy kolejny wielomian h(x) = \prod_i (1-\frac{t}{t_i} + \frac{t}{t_i}x). Zauważmy, że współczynnik przy x^i w tym wielomianie to dokładnie prawdopodobieństwo, że pewne i zmiennych wpadło w przedział [0,t], a pozostałe n-i są poza nim. Czyli h(x) = \sum_i p_i x^i. Wystarczy więc wyznaczyć współczynniki h(x). Jak? Korzystając z udowodnionego przed chwilą lematu. Co prawda poprzednia próba jego użycia skończyła się dramatyczną porażką, jednak teraz sytuacja jest znacznie prostsza: wszystkie współczynniki są nieujemne i sumują się do 1. Dzięki temu błędy obliczeń nie zaburzają istotnie otrzymanego wyniku i otrzymujemy rozwiązanie całego zadania w czasie \mathcal{O}(n\log^2n).

Odrobinę smutna w powyższym rozumowaniu była konieczność ręcznego wyliczenia całki. Spróbujmy inaczej. Niech X_1,X_2,\ldots,X_n będą niezależnymi zmiennymi losowymi przyjmującymi wartości z [0,1] (wciąż interesuje nas rozkład jednostajny ciągły). Chcemy policzyć E[\min_i X_i]. Dorzućmy nową niezależną zmienną X_{n+1}, która także przyjmuje wartości z [0,1]. Ze względu na symetrię prawdopodobieństwo, że X_{n+1}<\min_{i=1}^{n} X_i jest równe \frac{1}{n+1}, każda zmienna ma bowiem taką samą szansę na bycie minimum. Jednak to prawdopodobieństwo jest dokładnie równe E[\min_{i=1}^{n} X_i], gdyż dla ustalonych X_1,X_2,\ldots,X_n zlicza długość przedziału [0,\min_{i=1}^{n}X_i]. Więc nie trzeba całkować. Uff.

Advertisements

4 myśli nt. „Przystanek autobusowy

  1. Wydaje mi się, (zwłaszcza, że potem sam siebie „cytujesz” nieco inaczej), że w tym pierwszym wzorze też powinno być t_i – x w liczniku, a nie t_i * x . Z resztą, chyba w przeciwnym razie skróciłbyś ten ułamek 🙂
    Wydaje mi się też, że jedyny sposób w jaki umiem sobie uzasadnić zdanie „zauważmy, że p_0=0” to taki, że chciałbyś aby „t=m” (albo może od razu chciałeś tak zdefiniować „t”, ale przez pomyłkę nazwałeś to „m”?).

  2. Cwany pomysł, aby spojrzeć na te p_i :). Jednak przejście z iloczynu wyrazów (x-b_i) do (1-t/t_i + xt/t_i) można wykonać bez wprowadzania nowego spojrzenia na problem, po prostu wystarczy scałkować od prawej do lewej zamiast od lewej do prawej i dostajemy dokładnie to, co chcemy :). Konkretniej, jeżeli F(x) = prod (x-b_i) oraz G(x) = F(m – mx), to całkujemy G (które chyba jest tym samym co h).

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s