Первое Неравенство Чебышева

Пусть \(t\) неотрицательная действительная случайная переменная, а \(\alpha\) – положительное действительное число. Тогда, \[P(t\ge \alpha) \le \frac{\overline t}{\alpha}\]

\(\Delta:\) \(P(t\ge\alpha)=\sum_{t\ge\alpha}P(t)\). Умножая каждый член правой части на \(\frac{t}{\alpha}\ge 1\): \(P(t\ge\alpha)\le\sum_{t\ge\alpha}P(t)\frac{t}{\alpha}\). Добавляя недостающие (заведомо положительные) члены в сумму: \(P(t\ge\alpha)\le \frac{1}{\alpha}\sum_{t}P(t)t = \frac{\overline t}{\alpha} \qed\)

Второе Неравенство Чебышева

Пусть \(x\) неотрицательная действительная случайная переменная, а \(\alpha\) – положительное действительное число. Тогда, \[P((x - \overline x)^2 \ge \alpha) \le \frac{\sigma_x^2}{\alpha}\]

\(\Delta:\) Из первого неравенства Чебышева, пусть \(t=(x-\overline x)^2\): \(P((x-\overline x)^2\ge\alpha) \le \frac{\overline{(x - \overline x)^2}}{\alpha} =\frac{\sum_x P(x)(x-\overline x)^2}{\alpha} = \frac{\sigma_x^2}{\alpha}\) \(\qed\)

Слабый закон больших чисел (закон Хинчина)

Пусть \(x\) есть среднее от \(N\) независимых случайных переменных \(h_i\) (\(i\in\{1,\ldots,N\}\)), имеющих одинаковые средние \(\overline h\) и одинаковые дисперсии \(\sigma_h^2\): \(x=\frac{1}{N}\sum_i h_i\). Тогда, \[P((x-\overline h)^2 \ge \alpha)\le \frac{\sigma_h^2}{\alpha N}\]

\(\Delta:\) Применяя 2 неравенство Чебышева к \(x\), \(P((x-\overline x)^2 \ge \alpha) \le \frac{\sigma_x^2}{\alpha},\) но из линейности математического ожидания, \(\overline x = \frac{1}{N}\sum_i \overline h = \overline h,\) а \(\sigma_x^2 = \frac{1}{N^2}\sum_i \sigma_h^2 = \frac{\sigma_h^2}{N}\) в силу независимости \(h_i\) \(\qed\)

• неформально, закон Хинчина утверждает, что среднее \(N\) опытов вероятно произвольно близко к статистическому среднему, для достаточно больших \(N\).

Пропускная способность канала

Пропускная способность \(C\) дискретного канала определяется как \[C = \lim_{T\to\infty}\frac{\log N(T)}{T},\] где \(N(T)\) – число допустимых сигналов продолжительности \(T\).

Теорема (оригинальная формулировка)

Пусть источник имеет энтропию \(H\) (бит на символ), а канал обладает пропускной способностью \(C\) (бит в секунду). Тогда возможно подобрать схему кодирования, такую, что средняя скорость передачи будет составлять \(\frac{C}{H}-\epsilon\) символов в секунду, где \(\epsilon\) произвольно мало. Невозможна передача со средней скоростью выше, чем \(\frac{C}{H}\).

Пропускная способность канала (альтернативная формулировка)

Пропускная способность \(C\) дискретного канала определяется как \[C = \lim_{N\to\infty}\frac{\log \abs{X^N}}{N} = \lim_{N\to\infty}\frac{1}{N}H(X^N)\]

Альтернативная формулировка

Пусть \(X\) – ансамбль с энтропией \(H(X)\). Тогда, для любого данного \(\epsilon>0\), \(\exists\, N_0 \in \mathbb N: \forall N > N_0,\) \[\left|\frac{1}{N}H(X^N)-H(X)\right|<\epsilon,\] где \(X^N\) – последовательность \(N\) значений из ансамбля \(X\).

Доказательство

• Рассмотрим случайную переменную \(\frac{1}{N}\log_2\frac{1}{P(\mathbf{\vec{x}})}\), где \(\mathbf{\vec{x}} \in X^N\).

• Определим множество “типичных” значений из \(X^N\) как

\[T_{N\beta} = \left\{\mathbf{\vec{x}} \in X^N : \left|\frac{1}{N}\log_2\frac{1}{P(\mathbf{\vec{x}})} - H(X)\right| < \beta \right\},\]

• Для \(\mathbf{\vec{x}} \in T_{N\beta}\),
• \[2^{-N(H(X)+\beta)} < P(\mathbf{\vec{x}}) < 2^{-N(H(X)-\beta)}.\]
• По закону больших чисел,
• \[P((x-\overline h)^2 \ge \alpha)\le \frac{\sigma_h^2}{\alpha N}\]
• \[P(\mathbf{\vec{x}}\notin T_{N\beta}) \le \frac{\sigma^2}{\beta^2 N}\]

• \[\sum_{\mathbf{\vec{x}} \in T_{N\beta}} P(\mathbf{\vec{x}}) \le 1\]
• \[|T_{N\beta}| 2^{-N(H(X)+\beta)} < 1,\]
• \[|T_{N\beta}| < 2^{N(H(X)+\beta)}.\]

• Покажем, что \(\frac{1}{N}H(X^N) < H(X)+\epsilon\)
• для кодирования \(\forall \mathbf{\vec{x}} \in T_{N\beta}\) достаточно \(log_2|T_{N\beta}| < N(H(X)+\beta)\) бит.

• Пусть мы кодируем символы из \(T_{N\beta}\) последовательностями длины \(\log_2|T_{N\beta}|+1\) бит
• первый бит всех кодов для \(\mathbf{\vec{x}} \in T_{N\beta}\) равен \(0\)
• Тогда можем закодировать все \(\mathbf{\vec{u}} \in U_{N\beta} = X^N - T_{N\beta}\) кодами, первый бит которых равен \(1\), а число бит в коде не больше \(\log_2|U_{N\beta}|+1\)

• средний информационный объём последовательности, кодирующей \(\mathbf{\vec{x}} \in X^N\)

\(H(X^N) < N(H(X)+\beta+\frac{1}{N}+\frac{\sigma^2}{\beta^2 N}\log_2|X|+\frac{\sigma^2}{\beta^2 N^2})\)

• Пусть \(\beta = N^{-1/4}\)
• \(\frac{1}{N} H(X^N) <\) \(H(X)+\frac{1}{N^{1/4}}+\frac{1}{N}+\frac{\sigma^2}{N^{1/2} }\log_2|X|+\frac{\sigma^2}{N^{3/2}}\)
• \(\forall \epsilon > 0\), \(\exists N_0:\) \(\forall N>N_0,\) \[\frac{1}{N^{1/4}}+\frac{1}{N}+\frac{\sigma^2}{N^{1/2} }\log_2|X|+\frac{\sigma^2}{N^{3/2}} < \epsilon,\] \[\implies \frac{1}{N} H(X^N) < H(X) + \epsilon.\]

• Покажем, что \(\frac{1}{N}H(X^N) > H(X)-\epsilon\)
• От противного. Пусть \(\frac{1}{N}H(X^N) \le H(X)-\epsilon\)
• Тогда, \(\exists S \subset X^N:\)
• \(|S| \le 2^{N(H(X)-\epsilon)}\)
• при этом \(P(\mathbf{\vec{x}} \notin S) \to 0\) при \(N\to\infty\).

\(P(\mathbf{\vec{x}} \in S) =\) \(P(\mathbf{\vec{x}} \in S \cap T_{N\beta}) + P(\mathbf{\vec{x}} \in S \cap (X^N - T_{N\beta}))\)

• БОО, положим \(\epsilon = 2\beta\).
• \(P(\mathbf{\vec{x}} \in S \cap T_{N\beta}) = \sum_{\mathbf{\vec{x}} \in S \cap T_{N\beta}} P(\mathbf{\vec{x}})\)
• \(\abs{S \cap T_{N\beta}} \le \abs S \le 2^{N(H(X)-2\beta)}\)
• \(P(\mathbf{\vec{x}} \in T_{N\beta}) < 2^{-N(H(X)-\beta)}\)
• \(P(\mathbf{\vec{x}} \in S \cap (X^N - T_{N\beta})) \le P(\mathbf{\vec{x}} \notin T_{N\beta}) \le \frac{\sigma^2}{\beta^2 N}\)

• при \(N\to\infty,\) \(P(\mathbf{\vec{x}} \notin S) \to 1\).

Пропускная способность канала с шумом

теоретически максимально возможное количество взаимной информации между приёмником и источником

количество информации, переданной через канал, для некого “оптимального” источника.

Теорема (оригинальная формулировка)

Пусть дискретный канал имеет пропускную способность \(C\) и дискретный источник с энтропией \(H=H(M)\). Если \(H\le C\), то существует схема кодирования, такая, что сигнал источника может быть передан через канал с произвольно малой частотой ошибок (произвольно малой \(H(M|R)\)). Если \(H > C\), то \(H(M|R) = H - C + \epsilon\), где \(\epsilon\) произвольно мало. Не существует метода кодирования, такого, чтобы \(H(M|R) < H-C\).

Некоторые определения

\((N, K)\) блочный код

Множество \(2^K\) кодовых слов длины \(N\), кодирующих некий источник с алфавитом мощности \(2^K\).

Плотность кодирования \((N, K)\) блочного кода

\(ρ = K/N\).

Декодер \((N, K)\)-блочного кода

Отображение множества всех последовательностей длины \(N\) сигналов на выходе из канала на множество \(2^K+1\) меток кодовых слов, где “лишняя” метка означает неудачу.

Вероятность ошибки блочного кода

\[p_B = \sum_{m\in M}P(m)P(r\neq m|m),\] где \(M\) множество сообщений на входе канала, \(R\) множество сигналов на выходе канала, \(r \in R\)

Максимальная вероятность ошибки блочного кода

\[p_{BM} = \max_{m\in M}{P(r\neq m|m)}\]

Оптимальный декодер

декодер, минимизирующий вероятность ошибки блочного кода.

Вероятность битовой ошибки

Пусть номер кодового слова \(s\) в \((N, K)\)-блочном коде представлен двоичным числом \(\mathbf{\vec{s}}\) длиной \(K\) бит. Вероятность битовой ошибки \(p_b\) составляет среднюю вероятность того, что один бит в представлении \(\mathbf{\vec{s}}\) изменился после передачи соответствующего кода через канал.

Используем альтернативную формулировку теоремы.

Теорема (альтернативная формулировка)

1. \(\forall\) ДКБП с пропускной способностью \(C\), \(\forall \epsilon > 0, \forall ρ < C\), \(\exists N > 0:\) для кода длины \(N\), плотности кодирования \(\ge ρ < C\) и данного алгоритма декодирования, \(p_{BM} \le \epsilon\)
2. \(\forall\) наперёд заданной \(p_b\) достижима плотность кодирования до \(ρ(p_b) = \frac{C}{1-H_2(p_b)}\)
3. Плотность кодирования выше \(ρ(p_b)\) недостижима.

Пара случайных последовательностей \(\mathbf{\vec{x}}\), \(\mathbf{\vec{y}}\), элементы которых принадлежат ансамблям, соответственно, \(X\) и \(Y\), называются совместно-типичными (с точностью \(\beta\)), если:

• \(\mathbf{\vec{x}}\) типичный относительно \(P(\mathbf{\vec{x}})\), т.е. \(\left|-\frac{1}{N}\log P(\mathbf{\vec{x}}) - H(X)\right| < \beta\)
• \(\mathbf{\vec{y}}\) типичный относительно \(P(\mathbf{\vec{y}})\), т.е. \(\left|-\frac{1}{N}\log P(\mathbf{\vec{y}}) - H(Y)\right|< \beta\)
• \(\mathbf{\vec{x}}\), \(\mathbf{\vec{y}}\) типичны относительно \(P(\mathbf{\vec{x}},\mathbf{\vec{y}})\), т.е. \(\left|-\frac{1}{N}\log P(\mathbf{\vec{x}},\mathbf{\vec{y}}) - H(XY)\right|< \beta\)

Рассмотрим следующую систему кодирования-декодирования с плотностью \(ρ'\):

1. Пусть \(K = N ρ'\), тогда случайным образом составим блочный код \((N, Nρ')\), в соответствии с \(P(\mathbf{\vec{x}}) = \prod_{n=1}^N P(x_n),\) где \(\mathbf{\vec{x}}\) – кодовые слова. Обозначим этот код \(\mathcal{C}\).
2. Код известен отправителю и получателю.
3. Сообщение \(s \in \{1, 2, \ldots, 2^{Nρ'}\},\) соответствует коду \(\mathbf{\vec{x}}^{(s)}\). Кодированный сигнал \(\mathbf{\vec{y}}\) имеет вероятность \(P(\mathbf{\vec{y}} | \mathbf{\vec{x}}^{(s)}) = \prod_{n=1}^N P(y_n|x_n^{(s)})\)

4. \(\mathbf{\vec{y}}\) декодируется как \(\hat s\), если \((\mathbf{\vec{x}}^{(\hat s)}, \mathbf{\vec{y}})\) взаимно типичные, и \(\nexists s': (\mathbf{\vec{x}}^{(s')}, \mathbf{\vec{y}})\) взаимно типичные. В противном случае, сообщить об ошибке, \(\hat s = 0\).
5. Ошибка декодирования соответствует ситуации \(\hat s \neq s\).

Мы можем выделить следующие вероятности ошибки декодирования:

1. Средняя вероятность ошибки для конкретного кода \(\mathcal C:\) \(p_B(\mathcal C) \equiv 2^{-N\rho'}\sum_s P(\hat s \neq s | s, \mathcal C).\)
2. Средняя вероятность ошибки по всем (случайно составленным) кодам: \(\langle p_B \rangle = \sum_\mathcal{C} p_B(\mathcal C) P(\mathcal C)\)
3. Максимальная условная вероятность ошибки: \(p_{BM}(\mathcal C) = \max_s P(\hat s \ne s|s,\mathcal C).\)

• Обозначим множество взаимно-типичных \(\mathbf{\vec{x}}, \mathbf{\vec{y}}\) (с точностью \(\beta\)) как \(J_{N\beta}\).

• Оценим среднюю вероятность ошибки. Существует два потенциальных источника ошибки:

1. \((\mathbf{\vec{x}}^{(s)},\mathbf{\vec{y}}) \notin J_{N\beta}\)
2. \(\exists s' \neq s, \mathbf{\vec{x}}^{(s')} \in \mathcal C: (\mathbf{\vec{x}}^{(s')},\mathbf{\vec{y}}) \in J_{N\beta}\)

• В силу симметрии построения кодов, \(\langle p_B\rangle\) не зависит от конкретного \(s\), поэтому БОО можем рассмотреть \(s=1\): \(\angle{p_B} = \sum_{\mathcal C} P(\mathcal C) P(\hat s \ne 1|s = 1,\mathcal C)\)

• вероятность, что \(\mathbf{\vec{x}}, \mathbf{\vec{y}}\) не взаимно типичны \[p_{NJT} \le \frac{\sigma_X^2+\sigma_Y^2+\sigma_{XY}^2}{\beta^2N} = \delta.\]
• вероятность ошибки из-за (a) не превшывает \(\delta\).

• \(\sum_{(\mathbf{\vec{x}}, \mathbf{\vec{y}}) \in J_{N\beta}} P(\mathbf{\vec{x}} \mathbf{\vec{y}}) \le 1\)
• \(2^{-N(H(XY) + \beta)} < P(\mathbf{\vec{x}}\mathbf{\vec{y}}) < 2^{-N(H(XY) - \beta)}\)
• Тогда
• \(|J_{N\beta}| 2^{-N(H(XY) + \beta)} \le 1,\)
• \(|J_{N\beta}| \le 2^{N(H(XY) + \beta)}.\)

Для двух независимых \(\mathbf{\vec{x}}' \in X^N\) и \(\mathbf{\vec{y}}' \in Y^N\), вероятность того, что они совместно типичны

• \(P((\mathbf{\vec{x}}', \mathbf{\vec{y}}') \in J_{N\beta}) =\)
• \(\sum_{(\mathbf{\vec{x}}, \mathbf{\vec{y}}) \in J_{N\beta}} P(\mathbf{\vec{x}})P(\mathbf{\vec{y}})\)
• \(\le |J_{N\beta}|2^{-N(H(X)-\beta)}2^{-N(H(Y)-\beta)}\)
• \(\le 2^{N(H(XY) + \beta)}2^{-N(H(X)-\beta)}2^{-N(H(Y)-\beta)}\)
• \(= 2^{N(H(XY)-H(X)-H(Y)+3\beta)}\)
• \(= 2^{-N(I(XY)-3\beta)}\)

• Всего имеем \(2^{N\rho'}\) возможных значений \(x'\neq x^{(1)}\).
• Тогда вероятность ошибки из-за (b) не превышает \[2^{Nρ'}2^{-N(I(XY)-3\beta)} = 2^{-N(I(XY)-ρ'-3\beta)}.\]

• средняя вероятность ошибки \[\langle p_B\rangle \le \delta + 2^{-N(I(XY)-ρ'-3\beta)},\]
• равенство достигается только если (a) и (b) никогда не происходят одновременно.
• если \(ρ' < I(XY)-3 \beta\), \((I(XY)-ρ'-3\beta) > 0\)
• можно выбрать достаточно большой \(N\), такой, что \(\langle p_B \rangle < 2\delta\) (т.к. \(\delta \sim \frac{1}{N}\), а экспонента убывает быстрее гиперболы)

• Пусть теперь источник – оптимальный для данного канала,
• тогда \(I(XY)=C\)
• тогда \(ρ' < C-3 \beta\)
• средняя вероятность ошибки по всем случайно составленным кодам \(<2\delta\)
• значит существует хотя бы один код \(\mathcal C\), такой, что \(p_B(\mathcal C) < 2\delta\).

• Составим на основе \(\mathcal C\) новый код
• исключим в нём половину кодовых слов, имеющих наиболее высокие вероятности ошибки
• Вероятность ошибки у каждого из оставшихся кодовых слов менее \(4 \delta\).
• получили новый код \(\mathcal C'\) с плотностью \(\rho'' = \rho'-\frac{1}{N}\) и \(p_{BM}(\mathcal C') < 4 \delta\).
• Положив \(ρ' = (ρ+C)/2\), \(\delta = \epsilon/4\), \(\beta < (C-ρ')/3\), получим формулировку первой части теоремы.

• Рассмотрим канал без шума с пропускной способностью \(C\)
• попытаемся передать количество информации \(H>C\)
• Простая стратегия – передавать только количество информации, равное \(C\), и отбрасывать остальное
• Приёмник тогда должен угадать \(H-C\) бит сообщения
• Потери информации в канале очевидно \(H(M|R) = H-C\) (при \(N\to\infty\))
• Доля сообщения, которое приёмник должен угадать \(\frac{H-C}{H} = 1-\frac{C}{H}\)
• вероятность битовой ошибки \(p_b = \frac{1}{2}(1-\frac{C}{H}).\)

• если распределить вероятность битовой ошибки равномерно по всем битам, результат будет немного лучше

Доказательство

• Пусть \(E=1\), если возникла ошибка “угадывания”, 0 в противном случае.
• \(P(E=1) = p_e\), \(H(E) = H_2(p_e).\)
• \(H(EXY) = H(E|XY) + H(XY) =\) \(H(E|XY) + H(X|Y) + H(Y)\)
• \(H(EXY) = H(X|EY)+H(EY) =\) \(H(X|EY) + H(E|Y) + H(Y)\)
• Тогда

• \(H(X|EY)\)

• Для двоичного алфавита, \(N=2\) и \[H(X|Y) \le H_2(p_e)\]

Доказательство

• Для \(n=2\) прямо следует из определения выпуклой функции
• Далее индукция по n.

• Пусть \(R^N\) – кодовое слово на выходе из канала
• используется \((N, K)\)-блочный код
• вероятность битовой ошибки \(p_b\)
• \(S\) – отправленное сообщение
• \(M^N\) – кодовое слово на входе в канал.
• \(H(M^N R^N S) =\)

\(H(M^N R^N S) = H(S) + \sum_{i=1}^N H(R_i|M_i)\)

• С другой стороны, \(H(M^N R^N S) =\)

• \(I(S R^N)\)

\[I(S R^N) \le C \frac{K}{ρ}\]

Теорема Шеннона-Хартли

Определяет пропускную способность канала с аддитивным гауссовским шумом.

\[C = B \log_2(1+\frac{S}{N}),\]

где C – пропускная способность канала, бит/с, \(B\) – полоса пропускания (частотная ширина канала), Гц, \(S\) – средняя мощность сигнала над полосой пропускания, Вт, \(N\) – средняя мощность шума над полосой пропускания, Вт.

Аксиомы Хинчина

1. \(H(p_1,\ldots,p_n)\) – непрерывная относительно аргументов функция в области определения \(0\le p_i \le 1\), \(\sum_i p_i = 1\)
2. \(H(p_1, \ldots, p_n)\) не меняется от перестановок аргументов.
3. \(H(p_1, \ldots, p_n, 0) = H(p_1,\ldots,p_n)\)
4. \(H(XY)=H(X)+H(Y|X)\), где \(H(Y|X) = \sum_{x\in X} P(x) H(\frac{P(x_i y_1)}{P(x_i)},\ldots,\frac{P(x_i y_m)}{P(x_i)}).\)
5. \(H(p_1, \ldots, p_n)\leq H(\frac{1}{n},\ldots,\frac{1}{n})\)

• однозначно приводит к энтропии Шеннона
• (4) кажется несколько неестественной

Если взять более интуитивную аксиому,

4. Энтропия двух независимых систем аддитивна, \(H(XY) = H(X)+H(Y)\).

Аксиомы Фаддеева

Эквивалентная системе Хинчина аксиоматика.

1. \(H(p, 1-p)\) непрерывна при \(p\in[0,1]\) и положительна хотя бы в одной точке.
2. \(H(p_1, \ldots, p_n)\) не меняется от перестановок аргументов
3. При \(n\ge 2\), \[H(p_1,\ldots, p_{n-1}; q_1, q_2) = \\H(p_1, \ldots, p_n) + p_n H\left(\frac{q_1}{p_n}, \frac{q_2}{p_n}\right),\] где \(p_n=q_1+q_2\).

• аксиома 5 Хинчина заменяется на требование положительности \(H\) хотя бы в одной точке,
• аксиомы Хинчина 3, 4 заменяются аксиомой 3.

• Аксиома Фаддеева 3 оказывается более интуитивной, если интерпретировать энтропию как меру неопределённости.
• Тогда неопределённость, возникающая от деления события с вероятностью \(p_n\) на два события с условными вероятностями \(\frac{q_1}{p_n}\), \(\frac{q_2}{p_n}\), должна возникать только если собственно происходит событие с вероятностью \(p_n\)
• этому соответствует член \(p_n H\left(\frac{q_1}{p_n}, \frac{q_2}{p_n}\right)\).