Pytania otagowane jako random-walks

2
Pijane ptaki kontra pijane mrówki: losowe spacery między dwoma a trzema wymiarami
Powszechnie wiadomo, że losowy spacer w dwuwymiarowej siatce powróci do początku z prawdopodobieństwem 1. Wiadomo również, że ten sam losowy spacer w TRZY wymiarach ma prawdopodobieństwo mniej niż 1 powrotu do początku . Moje pytanie brzmi: Czy jest coś pomiędzy? Załóżmy na przykład, że moja przestrzeń była w rzeczywistości ograniczonym …
1
Losowa złożoność zapytań problemu drzew połączonych
Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej, który składa się z dwóch kompletnych dwójkowych drzewek głębokości n, których …
2
Czas pokrycia kierowanych wykresów
Biorąc pod uwagę losowy spacer na wykresie, czas pokrycia jest pierwszym (oczekiwana liczba kroków), że każdy wierzchołek został trafiony (pokryty) przez spacer. W przypadku podłączonych niekierowanych wykresów czas pokrycia jest znany z górnej granicy . Istnieją silnie połączone digrafy z wykładniczym czasem pokrycia w n . Przykładem tego jest dwuznakiem …
3
Właściwości losowo ukierunkowanych wykresów z ustalonym kątem końcowym
Interesują mnie właściwości losowo ukierunkowanych wykresów o ustalonym out-stopniu ddd . 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 )? ddd Szczególnie interesuje …
2
Jednorazowe kwantowe uderzenia
W artykule Kwantowe losowe spacery uderzają wykładniczo szybciej ( arXiv: quant-ph / 0205083 ) Kempe podaje pojęcie czasu uderzenia w spacery kwantowe (w hipersześcianie), które nie jest zbyt popularne w literaturze dotyczącej spacerów kwantowych. Jest on zdefiniowany w następujący sposób: One-Shot Quantum Uderzanie Czas: Dyskretny czasie spaceru ma kwantowy (T,p)(T,p)(T,p) …
1
Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań
Rozważ następujący problem. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj …
2
Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm 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:O ( τ ) τGsolGO(τ)O(τ)O(\tau)ττ\tauτ=∑v∈Vπ(v)⋅H(u,v),τ=∑v∈V.π(v)⋅H.(u,v),\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), ππ\pi to rozkład …
2
Tasowanie tokenów na wykresie za pomocą lokalnych zamian
Niech będzie nieregularnym połączonym wykresem, którego stopień jest ograniczony. Załóżmy, że każdy węzeł zawiera unikalny token.G = ( V, E)G=(V,E)G= (V, E) Chcę równomiernie tasować tokeny między wykresami, używając tylko lokalnych zamian (tj. Wymiany tokenów między dwoma sąsiadującymi węzłami)? Czy znana jest dolna granica tego problemu? Jedyny pomysł, jaki miałem, …
3
Pytanie techniczne dotyczące losowych spacerów
(Na moje pierwotne pytanie wciąż nie ma odpowiedzi. Dodałem dalsze wyjaśnienia.) Analizując losowe spacery (na niekierowanych grafach), widząc losowy spacer jako łańcuch Markowa, wymagamy, aby wykres nie był dwustronny, aby obowiązywało podstawowe twierdzenie o łańcuchach Markowa. Co się stanie, jeśli wykres GGGjest zamiast tego dwustronny? Jestem szczególnie zainteresowany czasem uderzeniahi,jhi,jh_{i,j}, …
3
Jak mogę losowo wygenerować drzewa o ograniczonej wysokości?
W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości. Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją. 1) Zaczynając od minimalnego drzewa opinającego (Prim'a lub Kruskala), dodaję nieistniejącą krawędź i to tworzy cykl, wykrywam ten cykl …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.