Niniejszy post jest kontynuacją Części 4, w której wprowadziłem klasyczną terminologię:
- alfabet probabilistyczny [;(A\ \pi);] - zawsze zakładamy, że [;|A| > 1;], czyli że istnieją co najmniej 2 różne symbole;
- [;A;]-struna (i [;A;]-blok) ;
- informacja
[;\iota(a) := \log_2\left(\frac{1}{\pi(a)}\right);]
symbolu [;a;] alfabetu [;A;] ; - entropia
[;\epsilon(A\ \pi) := \sum_{a\in A} \pi(a)\cdot\log_2\left(\frac{1}{\pi(a)}\right);]
alfabetu probabilistycznego [;(A\ \pi);] ; - informacja
[;\iota(S) := \sum_{k < n} \log_2\left(\frac{1}{\pi(a_k)}\right);]
[;A;]-struny [;S := (a_0 \dots\ a_{n-1});] ; - przestrzenie skończenie i nieskończenie wymiarowe [;A;]-strun:
[;A^n;] oraz [;A^{\mathbb{Z_+}};]
wraz z funkcją prawdopodobieństwa [;\pi'';] (patrz następne trzy punkty tej listy); - prawdopodobieństwo [;\pi''(B);] dowolnego zbioru [;B\subseteq A^n;], jako suma prawdopodobieństw [;\pi(S);] jego [;A;]-strun:
[;\pi''(B) := \sum_{S\in B} \pi(S);]
dla dowolnego [;n = 1\ 2\ \dots;] - S-kub [;B_S;]:
[;B_S := \left\{(x_0\ x_1\ \dots) : \displaystyle\forall_{k < n}\ x_k = a_k \right\} ;]
dla dowolnej skończonej [;A;]-struny [;S := (a_0 \dots\ a_{n-1});] ; - Prawdopodobieństwo [;\pi'';] w przestrzeni [;A^{\mathbb{Z_+}};]:
[;\pi''(B_S) := \pi(S);]
oraz prawdopodobieństwo [;\pi'';] dowolnego zbioru, będącego unią skóńczonej lub przeliczalnej rodziny parami rozłącznych S-kubów jest sumą prawdopodobieństw [;pi'';] S-kubów, będących składnikami unii.
Prawdopodobieństwo [;\pi''(B);], zbioru [;B;] w przestrzeni [;A^n;] lub [;A^{\mathbb{Z_+}};], można traktować jako objętość tego zbioru; przy czym objętość całej przestrzeni jest równa 1. Myślenie w terminach objętości powinno ułatwić zrozumienie i zapamiętanie wielu rozważań (chyba, że jesteś strasznym oryginałem :-).
Alfabety probabilistyczne rozważamy w kontekście strun losowych, w których symbole na każdym miejscu występują z prawdopodobieństwem danym przez alfabet probabilistyczny, przy czym symbole w różnych miejscach struny występują niezależnie od pozostałych (jak wyniki rzutów kostką lub monetą).
Powszechnym w algebrze nieprzemiennej i w logice matematycznej, a potem podstawowym dla całej informatyki, jest pojęcie złożenia dwóch strun (skończonych):
[;W := S.T;]
Dla strun [;S := (a_0\ \dots\ a_{m-1});] oraz [;T := (b_0\ \dots\ b_{n-1});], ich złożenie [;W;] definiujemy jako strunę o długości [;m+n;]:
- [;W(i) := S(i);] dla [;i=0\ \dots\ m-1;]. oraz
- [;W(i) := T(i-m);] dla [;i=m\ \dots\ n-1;].
Złożenie strun jest działaniem łącznym, dzięki czemu w wyrażeniach [;S.T.U;] [;Q.S.T.U;] itp. nie musimy stosować nawiasów.
Złożenie strun skończonych i skończonej z nieskończoną (w tej kolejności) rozpatruje się także w przestrzeni [;A^{\mathbb{Z}_+};]. W szczególności, dla A-struny skończonej [;S;], S-kub [;B_S;] może być równoważnie i elegancko określony jak następuje:
[;B_S := \left\{ S.T : T\in A^{\mathbb{Z}_+}\right\};]
Dla ustalonego alfabetu [;A;], skończone struny niepuste (o skończonej, dodatniej długości - innych strun dotąd w tej serii not nie rozpatrywałem, z wyjątkiem elementów przestrzeni [;A^{\mathbb{Z}_+};]) tworzą półgrupę (i to półgrupę wolną). Gdy dołączymy strunę pustą [;\emptyset;], to uzyskamy monoid (a nawet monoid wolny), w którym rolę jedności gra właśnie struna pusta.
Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Jego marginesem [;\mu(A\ \pi);] nazywam maksymalną informację jego symbolu:
[;\mu(A\ \pi) := \max_a\ \iota(a);]
Margines jest więc informacja symbolu o najmniejszym prawdopodobieństwie, więc zawsze jest równy nie mniej niż 1 (nawet jest większy niż 1, poza jedynym wyjątkiem, gdy mamy dokładnie 2 symbole, i każdy ma prawdopodobieństwo równe 1/2).
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n > \mu(\mathbf{A});] będzie dowolną liczbą naturalną (tak naprawdę, to obchodzą nas przede wszystkim liczby [;n;] sporo większe od marginesu). [;A;]-strunę [;S := (a_0 \dots\ a_{m-1});] nazywam [;(\mathbf{A}\ n);]-struną lub struną nasyconą (względem [;\mathbf{A};] oraz [;n;]) [;\Leftarrow:\Rightarrow;] [;S;] spełnia dwa warunki:
- [;n - \mu(\mathbf{A}) < \iota(S) \le n;]
- [;\iota(S') \le n-\mu(\mathbf{A});], gdzie [;S' := (a_0\ \dots\ a_{m-2});]
(Prawa nierówność w pierwszym warunku wynika z pozostałych dwóch nierówności). W kontekście jednego twierdzenia, gdy mówimy o strunach nasyconych, to cały czas mamy na myśli ustaloną liczbę naturalną [;n;], oraz ustalony alfabet propbabilistyczny. Udowodnię teraz ciąg łatwych własności strun nasyconych, prowadzący do wyniku głównego.
TWIERDZENIE 0 Żadna [;(\mathbf{A}\ n);]-struna nie jest prefiksem żadnej innej, różnej od niej [;(\mathbf{A}\ n);]-struny.
DOWÓD Prefiks właściwy struny nasyconej nie jest nasycony, gdyż ma informację nieprzekraczającą [;n-\mu(\mathbf{A});]. KONIEC DOWODU
TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun nasyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są nasycone.
DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU
TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, nasyconych A-strun są rozłączne.
DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU
TWIERDZENIE 3 Dla dowolnej A-struny skończonej [;S;] zachodzi równość
[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]
DOWÓD Niech [;S := (a_0\ \dots\ a_{n-1});] Należy skorzystać z definicji informacji, i z własności logarytmu:
[;\frac{1}{2^{\iota(S)}} =
\frac{1}{2^{\sum_{k < n}\iota(a_k)}} =
\frac{1}{2^{\sum_{k < n}\log_2\left(\frac{1}{\pi(a_k)}\right)}} ;]
[;= \frac{1}{2^{\log_2\left(
\prod_{k < n}\frac{1}{\pi(a_k)}
\right)}} = \frac{1}{\prod_{k < n}\frac{1}{\pi(a_k)}} = \pi(S);]
KONIEC DOWODU
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;\nabla(\mathbf{A}\ n);] będzie zbiorem wszystkich [;(\mathbf{A}\ n);]-strun (czyli strun nasyconych). Jest ich nie więcej niż [;2^n;], co - w połączeniu z Twierdzeniem 1 jest głównym wynikiem tej noty:
TWIERDZENIE 4
[;|\nabla(\mathbf{A}\ n)| \le 2^n;]
dla każdego naturalnego [;n \ge \mu(\mathbf{A});].
DOWÓD Wiemy z poprzedniego twierdzenia (Tw. 3), że [;\pi''(B_S) \ge 2^{-n};] dla dowolnej struny nasyconej [;S;]. Ponieważ S-kuby są rozłączne, oraz [;\pi''(A^{\mathbb{Z}_+}) = 1;], to takich S-kubów jest nie więcej niż [;2^n;]. KONIEC DOWODU
Widzimy, że struny nasycone [;S;] możemy kodować za pomocą bloków zero-jedynkowych, długości [;n;], czyli - przy [;n;] sporo większym od marginesu [;\mu(\mathbf{A});] - co najwyżej nieznacznie dłuższych od informacji [;\iota(S);]. Niech [;\delta > 0;] będzie dowolną, dodatnią liczbą rzeczywistą (chodzi o dowolnie małe). Gdy ustalimy
[;n > \delta + \mu\cdot(1+\delta);]
to liczba bitów dwójkowych kodu będzie tylko nieznacznie przekraczać liczbę bitów informacji zawartej w źródłowej strunie nasyconej:
[;\frac{n}{\iota(S)} < 1 +\delta;]
Niech [;\delta\ n;] będą jak powyżej. Gdy ustalimy dostatecznie wielką liczbę naturalną [;M;], to A-struny [;T;] długości co najmniej [;M;] będą złożeniem długiego ciągu strun nasyconych, zakończonych ewentualnie struną nienasyconą (a te są relatywnie krótkie, bo marginesowe). Struny nasycone zakodują się za pomocą nie więcej niż [;(1+\delta');] dwójkowego bitu per bit informacji, gdzie [\delta';] jest stałą spełniającą:
[;0 < \delta' < \delta;]
Gdyby nie było nienasyconej końcówki, to cała struna [;T;] zakodowałaby się za pomocą średnio [;1+\delta';] dwójkowego bitu per bit informacji. Ewentualna nienasycona końcówka może to nieco zepsuć, ale dla dostatecznie dużego [;M;] wciąż będzie prawdziwe nieco gorsze oszacowanie [;1+\delta;] dwójkowego bitu per bit informacji.
UWAGA Istnienie [;\delta';] wynika ze skończoności zbioru \nabla(\mathbf{A}\ n) wszystkich strun nasyconych [;S;]. Możemy przyjąć
[;\delta' =
\max_{S\in\nabla(\mathbf{A}\ n)}\ \left(\frac{n}{\iota(S)}\ -\ 1\right);]
Nieco już praktyczniejszą kwestią jest takie dobranie [;\delta';] by [;M;] mogło być jak najmniejsze.
W tym odcinku nie chciałem Was nużyć zbyt pedantycznymi, rutynowymi, epsilon-delta ścisłymi dowodami.
W całej nocie moglibyśmy zastąpić [;2;], w roli podstawy logarytmu i potęgowania, przez dowolną liczbę naturalną [;b > 1;] - Hugo Steinhaus powiedziałby, że 2 jest zmienna :-). Chociaż takie uogólnienie jest automatyczne, to i tak jest bardzo wartościowe. Wynika z niego na przykład to, że przy ustalonej liczbie [;\alpha := |A|;] symboli alfabetu, maksuymalną entropię alfabetu probabilistycznego otrzymuje się przy jednorodnym rozkładzie prawdopodobieństw symboli, gdy
[;\pi(a) = \frac{1}{\alpha};]
dla każdego [;a\in A;]. Pomyślcie o tym :-)
No comments:
Post a Comment