Lawina jak proces stochastyczny

Rozważ następujący proces:

Istnieje $n$ pojemników ułożonych od góry do dołu. Początkowo każdy pojemnik zawiera jedną kulkę. Na każdym kroku my

1. wybierz losowo piłkę równomiernie i$b$
2. przenieś wszystkie kule z pojemnika zawierającego $b$ do pojemnika poniżej. Jeśli był to już najniższy kosz, usuwamy kulki z procesu.

Ile kroków wymaga oczekiwania do zakończenia procesu, tj. Do momentu, gdy wszystkie $n$ kulek zostaną usunięte z procesu? Czy zostało to wcześniej zbadane? Czy odpowiedź wynika łatwo ze znanych technik?

W najlepszym przypadku proces może zakończyć się po $n$ krokach. W najgorszym przypadku może to zająć $\Theta(n^2)$ kroków. Oba przypadki powinny być jednak bardzo mało prawdopodobne. Moje przypuszczenie jest takie, że wymaga $\Theta(n\log n)$ kroków i przeprowadziłem kilka eksperymentów, które wydają się to potwierdzać.

(Zauważ, że wybranie pojemnika równomiernie losowo jest zupełnie innym procesem, który oczywiście zajmie kroki do końca.)$\Theta(n^2)$

Nie do końca odpowiedź, ale obszerny komentarz do odpowiedzi Andrása.

Odpowiedź Andrása zawiera niezłą intuicję, choć nie sądzę, aby była to dokładna kalkulacja oczekiwanej liczby kroków. Myślę, że jest to dobre przybliżenie do odpowiedzi, ale wydaje się, że nie radzi sobie właściwie z przypadkami, w których pojemnik poniżej najwyższego zajętego pojemnika staje się pusty, zanim górny pojemnik zostanie opróżniony w dół. Mimo to może to być rozsądne przybliżenie (nie jestem pewien).

Jego obliczenia zawierają błąd, który wpływa na skalowanie. Wezmę dokładnie ten sam punkt początkowy, powtórzę i rozszerzę obliczenia.

Pomija współczynnik p wewnątrz sumy, ponieważ prawdopodobieństwo losowego wyboru prawidłowego bin wynosi zamiast$\frac{p}{n}$ . W rezultacie mamy$\frac{1}{n}$

$\begin{eqnarray*} n + \sum_{p=1}^n \sum_{k=0}^{\infty} (k+1) \frac{p}{n} \left(\frac{n-p}{n}\right)^k & = & n + \sum_{p=1}^{n} \frac{p}{n} \sum_{k=0}^{\infty} (k+1) \left(\frac{n-p}{n}\right)^k \\\\& = & n + \sum_{p=1}^{n} \frac{p}{n} \cdot \frac{n^2}{p^2} \\\\& = & n + n\sum_{p=1}^{n} 1/p \\\\& = & n (1+H_n) \end{eqnarray*}$

gdzie jest n-tą liczbą harmonicznych . Aby zbliżyć H n , możemy po prostu zastąpić sumę całką: H n ≈ ∫ n + 1 1$H_n = \sum_{p=1}^{n} 1/p$$H_n$. Zatem skalowanie wynosin(1+log(n+1))lub okołonlog(n+1). Chociaż to skalowanie nie pasuje dokładnie do skalowania problemu (patrz symulacja poniżej), jest ono prawie dokładnie o współczynniklog(2).$H_n \approx \int_{1}^{n+1} \frac{1}{x} dx = \log(n+1)$$n (1+\log(n+1))$$n \log(n+1)$$\log(2)$

Czerwone kółka: Punkty danych z symulacji procesu uśrednione dla 10 000 przebiegów. Zielony: . Niebieski: n log ( n + 1 ) .$n \log_2(n+1)$$n \log(n+1)$

Edycja: Pozostawiam tę odpowiedź taką, jaka jest (na razie), aby zilustrować niechlujny proces dowodzenia twierdzeń, coś, co zostało pominięte w opublikowanych artykułach. Podstawową intuicją jest to, że wystarczy skupić się na górnej piłce, która zamiata wszystko pod nią. Zobacz komentarze (w szczególności @Michael wskazujący, że mogą wystąpić luki) i późniejszą odpowiedź @ Joe na to, w jaki sposób błędy zostały zidentyfikowane i poprawione. Szczególnie podoba mi się użycie eksperymentów przez Joe, aby dwukrotnie sprawdzić, czy formuły są rozsądne.

$n$$(1 + \pi^2/6)n$

$b_1b_2\cdots b_n$$b_1 = n$$b_2 \ge n-1$$\dots$$b_i \ge n-i+1$$b_1$$b_2$$b_n$$1,2,\ldots,n$). Można je postrzegać jako osobne zdarzenia, jedno po drugim. Oczekiwana liczba kroków to wtedy

$\begin{eqnarray*}n + \sum_{p=1}^n \sum_{k=0}^{\infty} \frac{k+1}{n} \left(\frac{n-p}{n}\right)^k & = & n + \sum_{p=1}^{n-1} \frac{1}{n-p} \sum_{k=1}^{\infty} k\left(\frac{n-p}{n}\right)^k \\& = & n + \sum_{p=1}^{n-1} \frac{1}{n-p} n(n-p)/p^2 \\& = & n + n\sum_{p=1}^{n-1} 1/p^2 \\& \le & (1 + \pi^2/6)n. \end{eqnarray*}$