Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie

10

Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach. $G=(V,E)$ $n$ $m$

Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie: $G$ $O(\tau)$ $\tau$

τ = \sum_{v \in V.} π (v) \cdot H. (u, v),

$\tau = \sum_{v \in V} \pi(v) \cdot H(u, v),$

$\pi$ to rozkład stacjonarny , $\pi(v)=\frac{d(v)}{2m}$
$u$ jest dowolnym wierzchołkiem i
$H(u,v)$ to czas uderzenia ( czas dostępu AKA ), tj. Oczekiwana liczba kroków przed odwiedzeniem wierzchołka , zaczynając od wierzchołka . $v$ $u$

Jaka jest ogólna górna granica średniego czasu uderzenia? A jaki jest najgorszy przypadek który maksymalizuje średni czas uderzenia? $G$

Aby wyjaśnić moje pytanie, nie wymagam obliczeń ani szczegółowego dowodu (chociaż mogą być przydatne dla innych osób, które napotkają to pytanie w przyszłości). Dla mnie osobiście wystarczyłoby cytowanie.

Artykuł wspomina o innym algorytmie Brodera, który działa w oczekiwanym czasie pokrycia (pierwszy raz, gdy wszystkie wierzchołki zostały odwiedzone). Mówi się wtedy, że średni czas uderzenia jest zawsze krótszy niż czas ochrony. Daje jednak tylko asymptotyczne ograniczenie dla większości grafów (tj. Grafów ekspanderów ) w celu porównania go z Brodera dla większości grafów (z nieco bardziej włączającą definicją większości ). $\Theta(n)$ $\Theta(n \log n)$

Daje przykład wykresu, na którym średni czas uderzenia wynosi a czas przykrycia to . Chociaż wiadomo, że jest to najgorszy przypadek tego drugiego, nie mówi on konkretnie o najgorszym przypadku tego drugiego. Oznaczałoby to, że najgorszy przypadek algorytmu Wilsona może przypadać gdziekolwiek między a . $\Theta(n^2)$ $\Theta(n^3)$ $O(n^2)$ $O(n^3)$

Istnieją dwie publicznie dostępne implementacje algorytmu Wilsona, o których wiem. Jeden znajduje się w bibliotece grafów pomocniczych , a drugi w narzędziu graficznym . Dokumentacja tego pierwszego nie wspomina o czasie wykonywania, podczas gdy drugi stwierdza:

Typowy czas działania losowych wykresów to . $O(n \log n)$

Co nie odpowiada na pytanie i wydaje się być niezgodne z pismem Wilsona. Ale zgłaszam to na wszelki wypadek, aby zaoszczędzić czas każdemu, kto ma ten sam pomysł na sprawdzenie dokumentacji wdrożeniowej.

Początkowo miałem nadzieję, że najgorszy przypadek może zostać osiągnięty za pomocą wykresu skonstruowanego przez dołączenie ścieżki do kliki, dzięki Lovászowi , gdzie czas uderzenia może wynosić nawet . Jednak prawdopodobieństwo tego zdarzenia wynosi około $\Omega(n^3)$ podczas wybierania wierzchołków z rozkładu stacjonarnego. W rezultacie uzyskuje sięzwiązany dla średniego czasu uderzenia na tym wykresie. $\frac{1}{n}$ $O(n^2)$

Papier według Brightwell i Winkler pokazuje, że podzbiór lizak wykresów zwiększa czas planowanej uderzenie, osiągając . Wykres Lovásza jest również wykresem Lollipopa, ale w tym przypadku rozmiar kliki wynosi $4n^3/27$ , a nie połowa. Należy jednak uważać, aby nie pomylić oczekiwanego czasu uderzenia ze średnim czasem uderzenia. Ten wynik, podobnie jak poprzedni, odnosi się do oczekiwanego czasu uderzenia dla dwóch określonych wcześniej wybranych wierzchołków. $\frac{2}{3} n$

— arekolek
źródło

2

Dziękujemy za wykrycie tego błędu w dokumentacji narzędzia graficznego! Rzeczywiście dla typowych losowych wykresów średni czas uderzenia wynosi

(patrz np. Arxiv.org/abs/1003.1266 ), a nie

. Zostanie to poprawione w następnej wersji. (Zauważ też, że narzędzie grafów korzysta z biblioteki grafów Boost poniżej, więc nie są to tak naprawdę odrębne implementacje.)

O (n)

$O(n)$

O (n \log n)

$O(n \log n)$

— Tiago Peixoto,

1

@Tiago Cieszę się, że mogę pomóc! Dziękuję za Twój komentarz. W najgorszym przypadku możesz również chcieć wspomnieć o spodziewanym czasie (choć jest to mało prawdopodobne), ponieważ zaktualizowałem odpowiedź o odpowiedź Davida Wilsona.

— arekolek

11

Postanowiłem zapytać samego Davida Wilsona, wkrótce potem otrzymałem odpowiedź:

W przypadku niekierowanych wykresów na wierzchołkach najgorszym przypadkiem jest średni czas trafienia . Przykładem jest wykres sztangowy , który składa się z dwóch klik o rozmiarze połączonych ścieżką o długości . Nie wiem, jaka jest najgorsza stała. Artykuł [Brightwella-Winklera] analizuje (oczekiwane) czasy uderzeń rozpoczynające się od i kończące się na . Średni czas uderzenia to średnia $n$ $\Theta(n^3)$ $n/3$ $n/3$ $H(x,y)$ $x$ $y$ $H(x,y)$ dla ustalonego i losowych wyborów ze stacjonarnego rozkładu losowego marszu. Miło jest, że to nie zależy od . O czasach trafień dowiedziałem się z książki Aldous-Fill , która jest niedokończona, ale w Internecie. $x$ $y$ $x$

Istnieje nawet dowód na ten fakt we wspomnianej książce, która wygląda następująco:

Aby zbudować wykres na wierzchołkach, zacznij od dwóch pełnych wykresów na wierzchołkach. Rozróżnij wierzchołki na jednym wykresie („lewy dzwon”) i wierzchołki na drugim wykresie („prawy dzwon”). Następnie połączyć wykresy poprzez drogę . $n=2n_1+n_2$ $n_1$ $v_l \neq v_L$ $v_R \neq v_r$ $v_L - w_1 - \cdots w_{n_2} - v_R$

Następnie jest nieformalnie argumentowane, że trafienie zajmuje średni czas około , a stamtąd jest szansa $n_1$ $v_L$ uderzy, tak, że trwa średni czas o uderzy. Odjest szansa na $\frac{1}{n_1}$ $w_1$ $n_1^2$ $w_1$ $w_1$ aby uderzyć w prawy dzwon przed powrotem do lewego dzwonu, więc potrzeba czasu okołoaby wejść do prawego dzwonu. $\frac{1}{n_2}$ $n_1^2 n_2$

Ustawienie daje nam średni czas . $n_1 = n_2 = n/3$ $O(n^3)$

Wprawdzie jestem zagubiony w punkcie, w którym stwierdzają:

Od jest szansa na $w_1$ aby trafić w prawy dzwon przed powrotem do lewego dzwonka. $\frac{1}{n_2}$

Aby jednak uspokoić umysł, przeprowadziłem symulację przypadkowych spacerów na tak skonstruowanych grafach sztang, między wierzchołkami wybranymi z rozkładu stacjonarnego. Rzeczywiście, średni czas uderzenia bardzo ładnie dopasował się do krzywej . $\frac{(n+1)^3}{54}$

Komentarze do nieformalnego dowodu są jednak mile widziane.

— arekolek
źródło

3

W niedawnym artykule znaleźliśmy mn górną granicę (bez dużego O) oczekiwanej liczby „cykli wystrzelonych” przez algorytm Wilsona i jest on ściśle związany ze stałymi. Nie odpowiada bezpośrednio na pytanie o czas działania algorytmów Wilsona, ponieważ średni rozmiar wyskakujących cykli nie wydaje się oczywisty. Z drugiej strony nie mam wystarczającej „reputacji”, aby zostawić komentarz ...

— Heng Guo
źródło