Teoria informacji/TI Wykład 12

Wracamy do szacowania $Pr_{E}(\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 ${\mathcal {C}}$ będzie zbiorem wszystkich możliwych m-elementowych sekwencji $c_{1},\ldots ,c_{m}\in \{0,1\}^{n}$ takich że $c_{i}$ są parami różne. Niech $N=|{\mathcal {C}}|$.

$N={2^{n} \choose m}\cdot m!$

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

${\frac {1}{N}}\sum _{\bar {C}}Pr_{E}(\Delta ,{\bar {C}})\leq \delta$

to istnieje kod C taki że $Pr_{E}(\Delta ,{\bar {C}})\leq \delta$.

Zauważmy że jeśli ${\bar {C}}$ jest sekwencją w ${\mathcal {C}}$ 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)\leq \rho )=\sum _{i=1}^{m}\sum _{j\neq i}\,p(d(c_{j},c_{i}\oplus E)\leq \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\neq i}\underbrace {{\frac {1}{N}}\sum _{\bar {C}}p(d(c_{j},c_{i}\oplus E)\leq \rho )} _{(*)}$

Oszacujemy teraz (*) dla ustalonej pary indeksów $i\neq 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)\leq \rho \}$

Łatwo zauważyć że

$d(v,u\oplus e)\leq \rho \Longleftrightarrow v\oplus u\in S_{\rho }(e)$

Zatem

${\frac {1}{N}}\sum _{\bar {C}}p(d(c_{j},c_{i}\oplus E)\leq \rho )={\frac {1}{N}}\sum _{\bar {C}}p\left(c_{i}\oplus c_{j}\in S_{\rho }(E)\right)$

$=\sum _{e\in \{0,1\}^{n}}p(E=e)\cdot \underbrace {{\frac {1}{N}}\sum _{\bar {C}}\cdot \chi (c_{i}\oplus c_{j}\in S_{\rho }(e))} _{(**)}$

(gdzie $\chi$ oznacza funkcję charakterystyczną $\chi (\varphi )=1\Longleftrightarrow \varphi 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 ${\bar {C}}\in {\mathcal {C}}$, i łatwo zauważyć że każdy taki wektor pojawia się taką samą liczbę razy

$|\{{\bar {C}}:u=c_{i}\oplus c_{j}\}|=|\{{\bar {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 _{\bar {C}}\cdot \chi (c_{i}\oplus c_{j}\in S_{\rho }(e))$, czyli

$\sum _{\bar {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 _{\bar {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}\}|\leq 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 \underbrace {(m-1)\cdot {\frac {1}{2^{n}-1}}} _{\leq {\frac {m}{2^{n}}}}\cdot 2^{n\cdot H(Q+\eta )}$

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

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

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

Konkretniej, do tej pory wiemy że powyższe równanie jest spełnione dla wystarczająco dużych n, np. $n\geq n_{1}$, i dla $2\leq m\leq 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}\geq n_{1}$ m i </math>\eta</math> w ten sposób że dla dowolnego $n\geq 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\leq -{\frac {\varepsilon }{3}}$

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

$2^{n\cdot \left({\frac {\log _{2}m}{n}}+H(Q+\eta )-1\right)}\leq {\frac {1}{2^{n\cdot {\frac {\varepsilon }{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 $Pr_{E}(\Delta ,C)\leq \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_{\Gamma }-{\frac {1}{3}}\cdot \varepsilon \leq 1-H(Q+\eta )\leq C_{\Gamma }$. Jeśli n jest wystarczająco duże, to potem możemy znaleźć k takie że $C_{\Gamma }-\varepsilon \leq {\frac {k}{n}}\leq C_{\Gamma }-{\frac {2}{3}}\cdot \varepsilon$. Tym samym oba warunki są spełnione, co kończy dowód.