Teoria informacji/TI Wykład 12

Wracamy do szacowania $P{r}_E(\mathrm{\Delta },C)$. Przypomnijmy że (link TODO) obowiązuje dla dowolnego kodu C, o ile n jest wystarczająco duże. Pokażemy teraz że dla wystarczająco dużych n istnieje kod C który spełnia warunki Twierdzenia Shannona. W szczególności taki dla którego drugi składnik (link TODO) można ograniczyć z góry przez $\frac{\delta }{2}$.

Do dowodu użyjemy metody probabilistycznej. Ustalmy $m<2^n$. Niech ${𝒞}$ będzie zbiorem wszystkich możliwych m-elementowych sekwencji $c_1,\dots ,c_m\in \{0,1{\}}^n$ takich że $c_i$ są parami różne. Niech $N=|{𝒞}|$.

$N=(\genfrac{}{}{0ex}{}{2^n}{m})\cdot m!$

Od tego miejsca będziemy używać notacji $\overline{C}$ na oznaczenie sekwencji z ${𝒞}$. Argument probabilistyczny Shannona opiera się na prostej obserwacji. Jeśli

$\frac{1}{N}\sum _{\overline{C}}P{r}_E(\mathrm{\Delta },\overline{C})\le \delta$

to istnieje kod C taki że $P{r}_E(\mathrm{\Delta },\overline{C})\le \delta$.

Zauważmy że jeśli $\overline{C}$ jest sekwencją w ${𝒞}$ o wartościach Parser nie mógł rozpoznać (nieznana funkcja „\c”): {\displaystyle C=\{c_1, \ldots, \c_m \}} to

$\sum _{u\in C}\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\le \rho )=\sum _{i=1}^m\sum _{j\ne i}p(d(c_j,c_i\oplus E)\le \rho )$

A z (link TODO) dostajemy

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \frac{1}{N} \sum_{\bar{C}} \pr_E ( \Delta , \bar{C} ) \leq \frac{1}{N} \sum_{\bar{C}} \left( \frac{\delta }{2} + \frac{1}{m} \sum_{i = 1}^m \sum_{j \neq i} \, p ( d (c_j,c_i \oplus E) \leq \rho ) \right) }

$=\frac{\delta }{2}+\frac{1}{m}\sum _{i=1}^m\sum _{j\ne i}\underset{(*)}{\underbrace{\frac{1}{N}\sum _{\overline{C}}p(d(c_j,c_i\oplus E)\le \rho )}}$

Oszacujemy teraz (*) dla ustalonej pary indeksów $i\ne j$.

Dla $e\in \{0,1{\}}^n$ niech $S_{\rho }(e)$ oznacza kulę w $\{0,1{\}}^n$ o promieniu $\rho$ i środku w punkcie e, tzn.

$S_{\rho }(e)=\{v\in \{0,1{\}}^n:d(v,e)\le \rho \}$

Łatwo zauważyć że

$d(v,u\oplus e)\le \rho ⟺v\oplus u\in S_{\rho }(e)$

Zatem

$\frac{1}{N}\sum _{\overline{C}}p(d(c_j,c_i\oplus E)\le \rho )=\frac{1}{N}\sum _{\overline{C}}p(c_i\oplus c_j\in S_{\rho }(E))$

$=\sum _{e\in \{0,1{\}}^n}p(E=e)\cdot \underset{(**)}{\underbrace{\frac{1}{N}\sum _{\overline{C}}\cdot \chi (c_i\oplus c_j\in S_{\rho }(e))}}$

(gdzie $\chi$ oznacza funkcję charakterystyczną $\chi (\phi )=1⟺\phi holds$).

Możemy oszacować teraz wartość (**) dla ustalonego e. Z pewnością każdy wektor inny niż $0^n$ pojawia się jako $c_i\oplus c_j$ dla pewnej sekwencji $\overline{C}\in {𝒞}$, i łatwo zauważyć że każdy taki wektor pojawia się taką samą liczbę razy

$|\{\overline{C}:u=c_i\oplus c_j\}|=|\{\overline{C}:v=c_i\oplus c_j\}|=\frac{N}{2^n-1}$

dla dowolnych $u,v\in \{0,1{\}}^n-\{0^n\}$. A zatem każde $u\in S_{\rho }(e)-\{0^n\}$ dodaje $\frac{N}{2^n-1}$ do sumy $\sum _{\overline{C}}\cdot \chi (c_i\oplus c_j\in S_{\rho }(e))$, czyli

$\sum _{\overline{C}}\cdot \chi (c_i\oplus c_j\in S_{\rho }(e))=\frac{N}{2^n-1}|S_{\rho }(e)-\{0^n\}|$

Możemy to teraz zsumować po możliwych wartościach e:

$\sum _{e\in \{0,1{\}}^n}p(E=e)\cdot \frac{1}{N}\sum _{\overline{C}}\cdot \chi (c_i\oplus c_j\in S_{\rho }(e))=\sum _{e\in \{0,1{\}}^n}p(E=e)\cdot \frac{1}{2^n-1}|S_{\rho }(e)-\{0^n\}|$

$=\frac{1}{2^n-1}|S_{\rho }(e)-\{0^n\}|$

Znamy ponadto objętość $S_{\rho }(e)$, więc

$|S_{\rho }(e)-\{0^n\}|\le 2^{n\cdot H(\rho )}=2^{n\cdot H(Q+\eta )}$

Wracając do równania (link TODO) daje to

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \frac{1}{N} \sum_{\bar{C}} \, \pr_E ( \Delta , \bar{C} ) \leq \frac{\delta }{2} + \frac{1}{m} \sum_{i = 1}^m \sum_{j \neq i} \frac{1}{2^n - 1} \cdot 2^{n \cdot H(Q + \eta )}}

$=\frac{\delta }{2}+\frac{1}{m}\cdot m\cdot \underset{\le \frac{m}{2^n}}{\underbrace{(m-1)\cdot \frac{1}{2^n-1}}}\cdot 2^{n\cdot H(Q+\eta )}$

$\le \frac{\delta }{2}+\frac{m}{2^n}\cdot 2^{n\cdot H(Q+\eta )}$

$=\frac{\delta }{2}+2^{n\cdot (\frac{{\log }_{2}m}{n}+H(Q+\eta )-1)}$

Jesteśmy tu już blisko celu, gdyż $(\frac{{\log }_{2}m}{n}+H(Q+\eta )-1)$ odpowiada „prawie” $R(C)-C_{\mathrm{\Gamma }}$.

Konkretniej, do tej pory wiemy że powyższe równanie jest spełnione dla wystarczająco dużych n, np. $n\ge n_1$, i dla $2\le m\le 2^n$, Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 < \eta < \frac{1}{2} – Q} . Twierdzimy że można dobrać $n_0\ge n_1$ m i </math>\eta</math> w ten sposób że dla dowolnego $n\ge n_0$ spełnione jest

Parser nie mógł rozpoznać (nieznana funkcja „\label”): {\displaystyle C_{\Gamma } - \varepsilon \leq \frac{\log_2 m}{n} \leq C_{\Gamma } \label{(i)} }

$\frac{{\log }_{2}m}{n}+H(Q+\eta )-1\le -\frac{\epsilon }{3}$

W szczególności druga nierówność implikuje

$2^{n\cdot (\frac{{\log }_{2}m}{n}+H(Q+\eta )-1)}\le \frac{1}{2^{n\cdot \frac{\epsilon }{3}}}$

A więc jeśli n jest wystarczająco duże, to dostajemy

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \frac{1}{N} \sum_{\bar{C}} \, \pr_E ( \Delta , \bar{C} ) \leq \frac{\delta }{2} + \frac{\delta }{2} = \delta }

Używając argumentu probabilistycznego wnioskujemy że musi istnieć kod C rozmiaru m, spełniający $P{r}_E(\mathrm{\Delta },C)\le \delta$. Ponieważ $R(C)=\frac{{\log }_{2}m}{n}$, ten kod spełnia warunki Shannona.

Wybór spełniający warunki (link TODO) najłatwiej przedstawić na diagramie

(Rysunek TODO)

Używając ciągłości H, wybieramy $\eta$ takie że $C_{\mathrm{\Gamma }}-\frac{1}{3}\cdot \epsilon \le 1-H(Q+\eta )\le C_{\mathrm{\Gamma }}$. Jeśli n jest wystarczająco duże, to potem możemy znaleźć k takie że $C_{\mathrm{\Gamma }}-\epsilon \le \frac{k}{n}\le C_{\mathrm{\Gamma }}-\frac{2}{3}\cdot \epsilon$. Tym samym oba warunki są spełnione, co kończy dowód.