Pytania otagowane jako pr.probability

Pytania w teorii prawdopodobieństwa

2
Suma niezależnych wykładniczych zmiennych losowych
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, że jest to prawda, ale granice, które czytam, wymagają …
1
Próbkowanie z wielowymiarowego Gaussa z grafem kowariancji Laplaciana (odwrotna)
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 jednej z tych grafów macierzy Laplaciana jako kowariancji lub …
1
Lemma i derandomizacja Borela-Cantellego
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 . Zgodnie z naszą najlepszą wiedzą, podejście to jest nowością w tym dokumencie. Rzuciłem okiem na …
3
Czy jakieś znane CCC są zamknięte w ramach probabilistycznej operacji powerdomain?
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 zamknięte kategorie zapewniają semantykę wyższego rzędu -calculi. Probabilistyczne powerdomains zapewniają semantykę programom stochastycznym. CCC zamknięty w ramach probabilistycznej operacji powerdomain …
4
Konstrukcje lepsze niż losowe.
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 sztuczne przykłady. Interesują mnie przykłady takie jak algebraiczne kody geometrii, w których …
2
Statystyczna odległość między monetą jednolitą a stronniczą
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 n≤1/ϵ2n≤1/ϵ2n \le 1/\epsilon^2?
2
Odgadywanie niskiej wartości entropii przy wielu próbach
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 sukcesu dla Boba? Jeśli można mu tylko …
2
Zdarzenia o wysokim prawdopodobieństwie bez współrzędnych o niskim prawdopodobieństwie
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 \subseteq \rm{Supp}(X) być wydarzeniem wspierającym XXX takie, że Pr[X∈E]≥1−εPr[X∈E]≥1−ε\Pr[X \in E] \ge 1 - \varepsilon, gdzie εε\varepsilon jest dowolnie …
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}, …
2
Nierówność typu Chernoffa dla zmiennej losowej z 3 wynikami
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 (twierdzenie Sanowa): Niech X1,X2,…,XnX1,X2,…,XnX_1, X_2, \ldots, X_n bądź tam …
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.