Pytania otagowane jako it.information-theory

Pytania w teorii informacji

3
Na entropii sumy
Szukam oprawionego na entropii H(X+Y)H(X+Y)H(X+Y) sumy dwóch niezależnych dyskretnych zmiennych losowych i . Oczywiście, Jednak zastosowane do sumy niezależnych zmiennych losowych Bernoulliego , daje to Innymi słowy, granica rośnie liniowo z przy wielokrotnym stosowaniu. Jednak jest obsługiwany na zestawie rozmiaru , więc jego entropia jest co najwyżejY H ( X …
2
Wyniki kodowania kanałów przy użyciu złożoności Kołmogorowa
Zwykle do udowodnienia wyników kodowania kanału używana jest entropia Shannona. Nawet w przypadku wyników separacji kanałów źródłowych stosowana jest entropia shannon. Biorąc pod uwagę równoważność między Shannonem (globalnym) a Kołmogorowskim (lokalnym) pojęciem informacji, czy przeprowadzono badania nad wykorzystaniem złożoności Kołmogorowa do tych wyników (lub przynajmniej w celu zastąpienia części kodującej …
1
Rozróżnianie
Biorąc pod uwagę stan kwantowy wybrany losowo równomiernie ze zbioru N stanów mieszanych ρ 1 . . . ρ N , jakie jest maksymalne średnie prawdopodobieństwo prawidłowej identyfikacji A ?ρAρA\rho_ANNNρ1.. . ρN.ρ1...ρN.\rho_1 ... \rho_NZAZAA Problem ten można przekształcić w problem odróżnialności dwóch stanów, rozważając problem odróżnienia od ρ B = …
1
Prosty (?) Śmieszny problem kombinatoryczny!
Pozwólmy naprawić 0<E<10<E<100 . dla dowolnego nnn i dla dowolnego wektora c¯∈[0,1]nc¯∈[0,1]n\bar{c} \in [0,1]^n taki, że ∑i∈[n]ci≥E×n∑i∈[n]ci≥E×n\sum_{i\in [n]} c_i \geq E \times n Ac¯:=|{S⊆[n]:∑i∈S ci≥E×t}|≥(E×nt)Ac¯:=|{S⊆[n]:∑i∈S ci≥E×t}|≥(E×nt)A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t } Nie wiem, czy …
4
Związek między złożonością obliczeniową a informacją
Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę ​​linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma wysoką entropię”. Czy ktoś może wskazać mi związek między złożonością obliczeniową …
2
Odwrotność do nierówności Fano?
Nierówność Fano można wyrazić w wielu formach, a jedna szczególnie przydatna wynika (z niewielką modyfikacją) Oded Regev : Niech XXX będzie zmienną losową, a Y=g(X)Y=g(X)Y = g(X) gdzie g(⋅)g(⋅)g(\cdot) jest procesem losowym. Załóżmy, że istnieje procedura fff która dla y=g(x)y=g(x)y = g(x) może zrekonstruować xxx z prawdopodobieństwem ppp . Następnie …
1
Określ minimalną liczbę ważeń monet
W artykule Na temat dwóch problemów teorii informacji Erdõs i Rényi wyznaczają dolne granice minimalnej liczby ważeń, które należy zrobić, aby określić liczbę fałszywych monet w zestawie monet.nnn Bardziej formalnie: Fałszywe monety mają mniejszą wagę niż właściwe monety; znane są wagi i zarówno prawych, jak i fałszywych monet. Podana jest …
1
Funkcja Lovasz theta i wykresy regularne (w szczególności cykle nieparzyste) - związki z teorią spektralną
Wpis dotyczy: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Jak dalece Lovasz jest związany ze zdolnością do zerowego błędu regularnych grafów? Czy istnieją przykłady, w których wiadomo, że ograniczenie Lovasz nie jest równe pojemności zerowego błędu zwykłego wykresu? (Oleksandr Bondarenko odpowiedział poniżej). W szczególności czy znana jest jakakolwiek ścisła nierówność dla nieparzystych cykli boków większych lub …
3
Czy istnieje uogólnienie teorii informacji na wielomianowo poznaną informację?
Przepraszam, to trochę „miękkie” pytanie. Teoria informacji nie ma pojęcia złożoności obliczeniowej. Na przykład instancja SAT lub instancja SAT plus bit wskazujący na satysfakcję niosą tę samą ilość informacji. Czy istnieje sposób sformalizowania pojęcia „wielomianowo poznawalny”? Takie ramy mogą definiować na przykład pojęcie dywergencji wielomianowej KL między zmienną losową X …
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 …
1
Entropia głośnego rozkładu
Powiedzmy, że mamy funkcję f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R}takie, że a jest rozkładem, tzn. .∀x∈Zn2f(x)∈{12n,22n,…,2n2n},∀x∈Z2nf(x)∈{12n,22n,…,2n2n},\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},fff∑x∈Zn2f(x)=1∑x∈Z2nf(x)=1\sum_{x\in \mathbb{Z}_2^n} f(x) = 1 Entropia Shannona dla jest zdefiniowana następująco: fffH(f)=−∑x∈Zn2f(x)log(f(x)).H(f)=−∑x∈Z2nf(x)log⁡(f(x)).H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) . Niech będzie niezmienny. Powiedzmy, że …
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 …
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.