Pytania w teorii prawdopodobieństwa
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...
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...
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...
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...
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...
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...
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 ( α -...
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,...
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...
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ć...
(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ą...
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...
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...
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...
Dawno temu myślałem o tym problemie, ale nie mam o nim pojęcia. Algorytm generujący jest następujący. Zakładamy, że istnieje dyskretnych węzłów ponumerowanych od do . Następnie dla każdego w , nadrzędny ty węzeł w drzewie będzie losowym węzłem w . Iteruj po każdym , aby wynik był losowym drzewem z...
Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1±1\pm 1 Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli...
Powszechnie wiadomo, że jeśli wrzucisz n piłek do n pojemników, najprawdopodobniej w najbardziej załadowanym pojemniku będą znajdować się kulki O(logn)O(logn)O(\log n) . Ogólnie można zapytać o m>nm>nm > n piłek w nnn pojemnikach. Artykuł z RANDOM 1998 autorstwa Raaba i Stegera analizuje to...
Rozważ następujący proces: Istnieje nnn pojemników ułożonych od góry do dołu. Początkowo każdy pojemnik zawiera jedną kulkę. Na każdym kroku my wybierz losowo piłkę równomiernie ibbb przenieś wszystkie kule z pojemnika zawierającego bbb do pojemnika poniżej. Jeśli był to już najniższy...
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do...
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b -> b seq ⊥ b =...