Interesują mnie właściwości losowo ukierunkowanych wykresów o ustalonym out-stopniu . Wyobrażam sobie losowy model wykresu, w którym każdy wierzchołek wybiera u sąsiadów (powiedzmy z zamiennikiem)
Pytanie : Czy coś wiadomo o rozkładzie stacjonarnym i czasach mieszania losowych spacerów na tych losowych grafach (dla różnych wartości )?
Szczególnie interesuje mnie przypadek, w którym , co odpowiada modelowi automatów losowych nad alfabetem boolowskim. (Tak, zdaję sobie sprawę, że te wykresy często nie są połączone, ale co dzieje się w danym składniku?) Cieszę się z częściowych wyników i wyników dotyczących innych właściwości tych wykresów.
Wydaje się, że większość literatury na temat losowych wykresów koncentruje się na modelu Erdősa – Rényi, który ma bardzo inne właściwości niż model, o którym myślę.
Odpowiedzi:
W przypadku nieukierunkowanym losowe wykresy nieregularne są ekspanderami o wysokim prawdopodobieństwie (nie dla d = 2 , ale myślę, że d ≥ 3 wystarcza), co oznacza, że czas mieszania losowych spacerów wynosi O ( log n ) . Nie pamiętam wystarczająco dużo o tych dowodach, aby wiedzieć, czy wszystko przebiega w ukierunkowanym przypadku (z pewnością niektóre właściwości są różne: jednolity rozkład nie jest już stacjonarny), ale warto się temu przyjrzeć. Dobre referencje dla grafów ekspanderów to Grafy ekspanderów i ich zastosowania autorstwa Hoory'ego, Liniala i Wigdersona oraz Pseudorandomnessa autorstwa Vadhana.re re= 2 re≥ 3 O ( logn )
źródło
Czy wiesz o następującej pracy (i jej odnośnikach)? (Jest również dostępny w arXiv.)
Bohman, T. i Frieze, A. (2009), Hamilton jeździ cyklicznie w 3 wyjściach. Struktury losowe i algorytmy, 35: 393–417. doi: 10.1002 / rsa.20272
źródło
Nadal szukasz problemu? Ten artykuł jest właściwie trochę trafny: Alan Frieze, Páll Melsted i Michael Mitzenmacher, „ Analizy losowego chodzenia po kukułce ”, 2009.
źródło