Oprócz Części 4', warto przejrzeć przed czytaniem poniższego tekstu, lub w trakcie, także Część 4. Będę zakładał ich znajomość. Zresztą warto porównać Część 4' i 4", widzieć jak są pokrewne.
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n>2;] będzie liczbą naturalną (według intencji raczej sporą, choć formalnie tego nie wymagam). [;A;]-strunę [;S := (a_0\ \dots\ a_{n-1});] nazywam [;(\mathbf{A}\ n^+);]-struną lub minimalnie przesyconą lub dla krótkości po prostu przesyconą [;\Leftarrow:\Rightarrow;] spełnione są dwie nierówności:
- [;\iota(S) \ge n;]
- [;\iota(S') < n;] dla [;S' := (a_0\ \dots\ a_{n-2});]
Zbiór wszystkich takich strun przesyconych oznaczamy symbolicznie [;\Delta(\mathbf{A}\ n);].
UWAGA 0 Zbiory [;\Delta(\mathbf{A}\ n);] oraz [;\nabla(\mathbf{A}\ n);] można słowo w słowo tak samo zdefiniować dla dowolnej liczby dodatniej [;n;] (zamiast wyłącznie dla naturalnych). Zachodzi wtedy równość:
[;\Delta(\mathbf{A}\ n) = \nabla\left(\mathbf{A}\ \,n\!+\!\mu\left(\mathbf{A}\right)\right);]
TWIERDZENIE 0 Żadna z dowolnych dwóch różnych [;(\mathbf{A}\ n^+);]-strun nie jest prefiksem drugiej.
DOWÓD Gdy prefiks właściwy pewnej struny ma informację [;n;] lub większą, to sama struna nie może być minimalnie przesycona. KONIEC DOWODU
TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun przesyconych. 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ą przesycone.
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, przesyconych 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 struny nieskończonej [;(a_0\ a_1\ \cdots)\in A^{\mathbb{Z}_+};] istnieje dokładnie jedno [;m;] takie, że [;(a_0\ \cdots\ a_{m-1})\in\Delta(\mathbf{A}\ n);]. Innymi słowy:
[;\bigcup_{S\in\Delta(\mathbf{A}\ n)}B_S = A^{\mathbb{Z}_+};]
DOWÓD Ponieważ [;A;] jest skończone, to
[;\min_{a\in A}\iota(a) > 0;]
więc
[;\lim_{m\rightarrow \infty} \iota\left((a_0\ \dots\ a_{m-1})\right) = \infty;]
przy czym ciąg informacji prefiksów [;\iota\left((a_0\ \dots\ a_{m-1})\right));] jest rosnący. Zatem istnieje dokładnie jedno naturalne [;m;] takie, że prefiks jest przesycony. KONIEC DOWODU
Przypominam (patrz Część 4', Tw.3), że dla dowolnej A-struny skończonej [;S;] zachodzi nierówność
[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]
Wynika z niej, że
[;\pi''(B_S) \le \frac{1}{2^n};]
Stąd
TWIERDZENIE 4
[;|\Delta(\mathbf{A}\ n)| \ge 2^n;]
KONIEC DOWODU
Przypominam (patrz Część 4'), że marginesem [;\mu(\mathbf{A});] alfabetu probabilistycznego [;\mathbf{A};] nazywam maksimum informacji jego symboli. Natychmiast otrzymujemy wynik główny
TWIERDZENIE 5 Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Rozpatrzmy dowolne wierne kodowanie binarne skończonych [;A;]-strun. Wtedy dla dowolnej liczby naturalnej [;n;] istnieje przesycona A-struna [;S;] (więc spełnia warunek [;\iota(S) < n+\mu(\mathbf{A});] ), której kod ma conajmniej [;n;] bitów dwójkowych.
DOWÓD Wszystkich niepustych ciągów zer i jedynek, o długości mniejszej od [;n;], jest tylko [;2^{n}-2;]. Natomiast strun przesyconych jest co najmniej [;2^n;]. KONIEC DOWODU
No comments:
Post a Comment