Wiem, że wyraźnie poprosiłeś o intuicyjne wyjaśnienie i pominięcie formalnej definicji, ale myślę, że są one raczej powiązane, więc pozwól mi przypomnieć definicję typowego zestawu:
X1,X2,... są to zmienne losowe a następnie typowy zestaw w odniesieniu do jest zbiorem sekwencji z właściwością
oznacza to, że dla stałego , typowy zestaw składa się ze wszystkich sekwencji w którym prawdopodobieństwa Close do . Aby sekwencja należała do typowego zestawu, jej prawdopodobieństwo musi być zbliżone do~ P ( x ) ( n ) ε P ( x ) ( x 1 , x 2 , . . . , X n ) ∈ Ď n 2 - N ( H ( X ) + ε ) ≤ P ( x 1 , x 2 , .∼ p(x)A(n)ϵp(x)(x1,x2,...,xn)∈χn2−n(H(X)+ϵ)≤p(x1,x2,...,xn)≤2−n(H(X)−ϵ)(1)
ϵ2-nH(X)2-nH(X)log22−nH(X)2−nH(X), zwykle tak nie jest. Aby zrozumieć dlaczego, pozwól mi przepisać równanie 1, stosując na nim .log2
H(X)−ϵ≤1nlog2(1p(x1,x2,...,xn))≤H(X)+ϵ(2)
Teraz typowa definicja zbioru jest bardziej bezpośrednio związana z pojęciem entropii lub inaczej mówiąc, średnią informacją zmiennej losowej. Bliski termin może być traktowane jako próbki entropii sekwencji, więc typowy zestaw jest wykonany przez wszystkich sekwencji, które dają nam pewną ilość informacji zbliżona do średniej informacji o zmiennej losowej . Najbardziej prawdopodobna sekwencja zwykle daje nam mniej informacji niż średnia. Pamiętaj, że im niższe jest prawdopodobieństwo wyniku, tym wyższa będzie informacja, jaką nam przedstawi. Aby zrozumieć, dlaczego podam przykład:X
Załóżmy, że mieszkasz w mieście, którego pogoda jest prawdopodobnie słoneczna i ciepła, między 24 ° C a 26 ° C. Możesz oglądać prognozę pogody każdego ranka, ale nie przejmowałbyś się tym, to znaczy, zawsze jest słonecznie i ciepło. Ale co, jeśli któregoś dnia pogoda / mężczyzna / kobieta powie ci, że dziś będzie deszczowo i zimno, to zmieniarka gier. Będziesz musiał użyć różnych ubrań, wziąć parasol i robić inne rzeczy, których zwykle nie robisz, więc człowiek od pogody udzielił ci naprawdę ważnych informacji.
Podsumowując, intuicyjna definicja typowego zestawu polega na tym, że składa się on z sekwencji, które dają nam informacje zbliżone do oczekiwanego źródła (zmienna losowa).
$$H(X)-\epsilon\le \frac{1}{n}log_2(\frac{1}{p(x_1,x_2,...,x_n)}) \le H(X)+\epsilon \tag{2}$$...Odpowiedź Diegobatta dobrze wyjaśnia intuicyjnie, jaki jest typowy zestaw. Ta odpowiedź odniesie się do drugiego pytania OP, powtórzonego przez @tomwesolowski: dlaczego zdefiniowałbyś typowy zestaw w sposób, który mógłby wykluczyć najbardziej prawdopodobne elementy?
Krótka odpowiedź jest taka, że typowy zestaw jest przede wszystkim narzędziem matematycznym. Został zdefiniowany, aby pomóc coś udowodnić, a ta definicja jest najwygodniejsza dla dowodu. Jest to dobry przykład tego, jak potrzeby teoretyczne mogą czasem przebijać intuicyjne preferencje matematyczne.
Typowy zestaw został zdefiniowany przez ojca teorii informacji , Claude'a Shannona . Chciał, aby ustalić, jak skutecznie można by ewentualnie kodować strumień symboli z ustalonym alfabetem, przy założeniu każdy symbol jest iid losowa próbka z jakiejś dystrybucji. Jego kluczowe spostrzeżenia były następujące:
Typowy zestaw, który odkryła Shannon, składa się właśnie z sekwencji, których samoinformacja , czyli „zaskakująca”, jest mniej więcej taka sama, jak oczekiwana średnio informacja o dystrybucji źródła w strumieniu. Takie sekwencje są „typowe” w tym sensie, że ich informacje dotyczą średniej, ale ta definicja domyślnie wyklucza te sekwencje, które mają znacznie mniej informacji niż średnia. Te mniej pouczające sekwencje są również najbardziej prawdopodobne.
Jak zauważa OP, nie jest to intuicyjnie atrakcyjne! Na jego twarzy typowy zestaw brzmi, jakby zawierał wszystkie najbardziej prawdopodobne sekwencje do pewnego progu. To lepiej reprezentuje to, co zwykle widać w strumieniu.
Ale Shannon nie chciał najbardziej „typowego” możliwego zestawu; chciał takiego, który ułatwi udowodnienie wyniku, który chciał udowodnić. Typowy zestaw zdefiniowany przez Shannona gwarantuje, że istnieje, gwarantuje, że jest mały i gwarantuje, że będzie mniej więcej tak mały, jak każdy inny zestaw, który możesz zaproponować, jak wskazuje ta odpowiedź . Dodanie najbardziej prawdopodobnych elementów sprawia, że zestaw jest bardziej prawdopodobny, co jest dobre, ale także zwiększa zestaw, co jest złe. Jeśli zależy Ci tylko na wykonaniu dowodu, po co naprawiać to, co nie jest zepsute?
Jeśli masz inne cele niż Shannon, twoja preferowana koncepcja typowości może być również inna. Na przykład w kodowaniu Huffmana najbardziej prawdopodobne symbole (lub sekwencje symboli) otrzymują najkrótsze kody. W pewnym sensie technicznym kodowanie Huffmana jest optymalnym rozwiązaniem pierwotnego problemu Shannona i lepiej oddaje naszą intuicję dotyczącą typowości. Z drugiej strony definicja typowości Shannona jest wygodniejsza do udowodnienia.
źródło
Idea typowego zestawu domyślnie traktuje sekwencje wynikowe jako multisets, tzn. Zakłada, że zależy ci na histogramie każdej sekwencji, np. Bierzesz pod uwagę wszystkie 10 sekwencji rzutu monetą z 7 główkami i 3 ogonami jako równoważne.
Ważnym rezultatem jest to, że w przypadku wystarczająco długich sekwencji prawie wszystkie próbkowane sekwencje będą arbitralnie zbliżone do oczekiwanych częstotliwości, tj. Rozkład staje się wyjątkowo szczytowy wraz ze wzrostem długości rozważanych sekwencji.
Typowy zestaw to bardziej ogólna, teoretycznie zdefiniowana wersja tego pomysłu.
źródło
źródło