Pytania otagowane jako pr.probability

Chociaż zdałem kilka kursów z teorii prawdopodobieństwa, zarówno w szkole średniej, jak i na uniwersytecie, trudno mi czytać artykuły TCS, jeśli chodzi o prawdopodobieństwo. Wydaje się, że autorzy artykułów TCS są bardzo dobrze zaznajomieni z prawdopodobieństwem. Magicznie działają ze wzorami prawdopodobieństwa i bardzo łatwo dowodzą twierdzeń; podczas gdy muszę spędzić …

32 reference-request  big-list  pr.probability  books 

Czy istnieje odwrotna granica Chernoffa, która ogranicza, że ​​prawdopodobieństwo ogona jest co najmniej tak duże. tj. jeśli X 1 , X 2 , … , X nX1,X2,…,XnX_1,X_2,\ldots,X_n są niezależnymi dwumianowymi zmiennymi losowymi, a μ = E [ ∑ n i = 1 X i ]μ=E[∑ni=1Xi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Czy możemy zatem …

31 pr.probability  chernoff-bound 

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 …

30 pr.probability  random-walks  markov-chains 

Cytując Wikipedię , „[Gra życia Conwaya] ma moc uniwersalnej maszyny Turinga: to znaczy wszystko, co można obliczyć algorytmicznie, można obliczyć w ramach Gry życia Conwaya”. Czy takie wyniki obejmują hałaśliwe wersje Gry życia Conwaya? Najprostsza wersja jest taka, że ​​po każdej rundzie każda żywa komórka umiera z małym prawdopodobieństwem a …

30 cc.complexity-theory  pr.probability  cellular-automata  fault-tolerance 

Podczas badań pojawił się następujący problem, który jest zaskakująco czysty: Masz źródło monet. Każda moneta ma stronniczość, a mianowicie prawdopodobieństwo upadku na „głowę”. Dla każdej monety niezależnie istnieje prawdopodobieństwo 2/3, że ma ona stronniczość co najmniej 0,9, a przy pozostałym prawdopodobieństwie jej stronniczość może wynosić dowolną liczbę w [0,1]. Nie …

29 ds.algorithms  pr.probability 

Słyszałem, że w fizyce statystycznej istnieją heurystyczne argumenty, które dają wyniki w teorii prawdopodobieństwa, dla których rygorystyczne dowody są albo nieznane, albo bardzo trudne do uzyskania. Jaki jest prosty zabawkowy przykład takiego zjawiska? Byłoby dobrze, gdyby odpowiedź obejmowała niewielkie podstawy fizyki statystycznej i mogła wyjaśnić, czym są te tajemnicze heurystyki …

29 sat  pr.probability  physics  statistical-physics 

Interesuje mnie krytyczna gęstość 3-satysfakcji (3-SAT) . Przypuszcza się, że takie α istnieje: jeśli liczba losowo wygenerowanych klauzul 3-SAT wynosi ( α + ϵ ) n lub więcej, są prawie na pewno niezadowalające. (Tutaj ϵ jest dowolną małą stałą, a n jest liczbą zmiennych.) Jeśli liczba wynosi ( α - …

26 pr.probability  random-k-sat 

Dobrze wiadomo, że wiele ważnych parametrów wykresu pokazuje (silne) stężenie na losowych wykresach, przynajmniej w pewnym zakresie prawdopodobieństwa krawędzi. Niektóre typowe przykłady to liczba chromatyczna, maksymalna klika, maksymalna niezależny zestaw maksymalne dopasowanie, numer dominacja, liczba kopii stałe podgrafu, średnicy, maksymalny stopień, numer Choice (lista kolorowania numer), Lovász θθ\theta -liczba, szerokość …

23 graph-theory  pr.probability  random-graphs 

mmmnnnm≫nm≫nm \gg nXiXiX_iiiiXmaxXmaxX_\maxXminXminX_\minXsec−maxXsec−maxX_{\mathrm{sec-max}}Xi−Xj∼N(0,2m/n)Xi−Xj∼N(0,2m/n)X_i - X_j \sim N(0,2m/n)|Xi−Xj|=Θ(m/n−−−−√)|Xi−Xj|=Θ(m/n)|X_i - X_j| = \Theta(\sqrt{m/n}) i,ji,ji,jXmax−Xmin=O(mlogn/n−−−−−−−−√)Xmax−Xmin=O(mlog⁡n/n)X_{\max} - X_{\min} = O(\sqrt{m\log n/n})n/2n/2n/2 pary rozłącznych pojemników. Ten (nie do końca formalny) argument prowadzi nas do oczekiwania, że ​​różnica między XmaxXmaxX_{\max} aXminXminX_{\min} to Θ(mlogn/n−−−−−−−−√)Θ(mlog⁡n/n)\Theta(\sqrt{m\log n/n}) z dużym prawdopodobieństwem. Interesuje mnie różnica między XmaxXmaxX_\max a Xsec−maxXsec−maxX_{\mathrm{sec-max}} . Przedstawiony …

23 reference-request  pr.probability 

Czas dojazdu na połączonym wykresie definiuje się jako oczekiwaną liczbę kroków w losowym marszu rozpoczynającym się od , przed odwiedzeniem węzła a następnie ponownie osiągnięciem węzła . Jest to w zasadzie suma dwóch czasów uderzenia i .i j i H ( i , j ) H ( j , i …

22 graph-theory  co.combinatorics  random-walks  pr.probability 

Podczas moich badań spotkałem następujący wynik. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 gdzie m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) i a1,⋯,ama1,⋯,ama_1,\cdots,a_m są wybierane losowo z [n][n][n] . Szukam referencji / bezpośredniego dowodu. Skrzyżowane na MO

21 reference-request  co.combinatorics  pr.probability 

Kiedy uczę ograniczeń ogona, używam zwykłego postępu: Jeśli twoje Rv jest dodatnie, możesz zastosować nierówność Markowa Jeśli masz niezależność, a także ograniczoną wariancję, możesz zastosować nierówność Czebyszewa Jeśli każdy niezależny rv ma również ograniczone wszystkie chwile, możesz użyć ograniczenia Chernoffa. Po tym wszystko staje się trochę mniej czyste. Na przykład …

21 reference-request  pr.probability  randomized-algorithms 

Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy istnieje jakieś standardowe ograniczenie, które określa …

21 randomness  pr.probability  randomized-algorithms 

(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą jest zobowiązany.) Załóżmy, że mamy nnn identycznych monet o nastawieniu δ=P[Head]−P[Tail]δ=P[Head]−P[Tail]\delta=P[Head]-P[Tail] . …

21 cc.complexity-theory  circuit-complexity  pr.probability 

Klasycznym problemem w teorii prawdopodobieństwa jest wyrażenie prawdopodobieństwa zdarzenia w kategoriach bardziej specyficznych zdarzeń. W najprostszym przypadku można powiedzieć . Write LET'S za zdarzenie .A B A ∩ BP[A∪B]=P[A]+P[B]−P[A∩B]P[A∪B]=P[A]+P[B]−P[A∩B]P[A \cup B] = P[A] + P[B] - P[A \cap B]ABABABA∩BA∩BA \cap B Istnieją zatem pewne sposoby na powiązanie , bez zakładania …

20 reference-request  pr.probability