Pytania oznaczone «pr.probability»

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 =...

Można mówić o treewidth z logicznego obwodu, określające go jako treewidth o „o zabarwieniu moralnym” wykresu na przewodach (wierzchołków) otrzymany w następujący sposób: przewody CONNECT aaa i bbb , gdy bbb jest wyjście z bramki mające jako wejście (lub nawzajem); Podłączyć przewody a i b , gdy są...

f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f\colon\{-1,1\}^n \to \{-1,1\}iiiInfi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]Infi⁡[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)] \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})] x⊕ix⊕ix^{\oplus...

ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Gdy piszę losowy wielomian o stopniu ≤d≤d\le d a n zmiennych, można myśleć o każdy...

Szukam odwołania (a nie dowodu, że mogę to zrobić) do następującego rozszerzenia Chernoff. Niech bądź logiczne zmienne losowe, niekoniecznie niezależne . Zamiast tego jest zagwarantowane, że P r ( X i = 1 | C ) < p dla każdego i i każdego zdarzenia C, które zależy tylko od { X j | j ≠ i }...

Nierówności typu Chernoffa służą do wykazania, że ​​prawdopodobieństwo, że suma niezależnych zmiennych losowych znacznie odbiega od wartości oczekiwanej, jest wykładniczo małe w wartości oczekiwanej i odchyleniu. Czy istnieje jakakolwiek nierówność typu Chernoffa dla dowolnej sumy niezależnych...

Czy możemy udowodnić ostry wynik koncentracji na sumie niezależnych wykładniczych zmiennych losowych, tj. Niech będą niezależnymi zmiennymi losowymi takimi, że . Niech . Czy możemy udowodnić granice postaci . Wynika to bezpośrednio, jeśli użyjemy formy wariancji granic chernoffa i dlatego uważam,...

W Załączniku B do Zwiększania i różnicowej prywatności autorstwa Dwork i wsp. Autorzy podają następujący wynik bez dowodu i nazywają go nierównością Azumy: Niech być rzeczywista zmiennymi losowymi takimi, że dla każdego ,C1,…,CkC1,…,CkC_1, \dots, C_ki∈[k]i∈[k]i \in [k]...

Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie...

Biorąc pod uwagę filtr Blooma o rozmiarze N-bitów i funkcjach skrótu K, w których ustawionych jest M-bitów (gdzie M <= N) filtra. Czy jest możliwe przybliżenie liczby elementów wstawionych do filtra Bloom? Prosty przykład Zastanawiam się nad poniższym przykładem, zakładając BF 100 bitów i 5...

Biorąc pod uwagę X1,…,XkX1,…,XkX_1,\ldots,X_k (iid gaussians ze średnią 000 i wariancją 111 ), czy możliwe jest (jak?) Próbkowanie (dla m=k2m=k2m=k^2 ) Y1,…,YmY1,…,YmY_1, \ldots, Y_m takie, że YiYiY_i są parami niezależni gaussowie ze średnią 000 i wariancją 111...

Czytałem artykuł zatytułowany Losowe wyrocznie z (poza) programowalnością . Ostatni akapit sekcji 2.3 brzmi: [Stosując nasze nowatorskie podejście] nie ma potrzeby stosowania dobrze znanych klasycznych asymptotycznych (i jednolitych) technik derandomizacji opartych na lemacie Borela-Cantellego...

Odpowiednio, czy istnieje znana semantyka denotacyjna dla probabilistycznych funkcjonalnych języków programowania wyższego rzędu? Konkretnie, czy istnieje model domenowy czystego nietypowego -kalkultu rozszerzony o symetryczną operację losowego wyboru binarnego.λλ\lambda Motywacja Kartezjańskie...

Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe. Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe. Można łatwo skonstruować takie...

Załóżmy, że Alice ma rozkład μμ\mu w skończonej (ale być może bardzo dużej) domenie, takiej jak entropia (Shannon) μμ\mu jest górny ograniczony dowolnie małą stałą εε\varepsilon. Alice rysuje wartośćxxx od μμ\mu, a następnie pyta Boba (kto wie μμ\mu) zgadywać xxx. Jakie jest prawdopodobieństwo...

Pozwolić XXX być zmienną losową przyjmującą wartości w ΣnΣn\Sigma^n (dla jakiegoś dużego alfabetu ΣΣ\Sigma), który ma bardzo wysoką entropię - powiedzmy, H(X)≥(n−δ)⋅log|Σ|H(X)≥(n−δ)⋅log⁡|Σ|H(X) \ge (n- \delta)\cdot\log|\Sigma| dla arbitralnie małej stałej δδ\delta. PozwolićE⊆Supp(X)E⊆Supp(X)E...

Szukam twierdzenia, które mówi coś takiego: jeśli czas pokrycia odwracalnego łańcucha Markowa jest mały, to szczelina widmowa jest duża. Tutaj oznacza lukę widmową1 - |λ2)|1-|λ2)|1-|\lambda_2|oznacza to, że ignorujemy najmniejszą wartość własną łańcucha. Jedyny wynik, jaki udało mi się znaleźć 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,...

Pozwolić UUU być równomiernym rozkładem nnn bitów i pozwól DDD być dystrybucją nnn bity, w których bity są niezależne, a każdy bit jest 111 z prawdopodobieństwem 1/2−ϵ1/2−ϵ1/2-\epsilon. Czy to prawda, że ​​statystyczna odległość międzyDDD i UUU jest Ω(ϵn−−√)Ω(ϵn)\Omega(\epsilon \sqrt{n}), kiedy...

Załóżmy, że mamy zmienną losową, która przyjmuje wartości nienumeryczne a, b, c i chce określić ilościowo, w jaki sposób rozkład empiryczny nnnpróbki tej zmiennej odbiegają od rozkładu rzeczywistego. W tym przypadku obowiązuje następująca nierówność (z Cover & Thomas ). Twierdzenie 12.4.1...