Prueba de que la entropía de la Fuente de Markov es $H(S) = \sum_s P(s) H(s)$

Question

Dejemos que $S$ sea una fuente de Markov en la que la distribución $P$ no depende de $P_0$ y que genera números del conjunto finito $\Omega$ . Prueba de que $$H(S) = \sum_{s \in \text{process states}} P(s)H(s) $$ donde $$H(s) = \sum_{x\in\Omega} P(x| s) \log P(x | s)$$

Mi intento

Según la definición de la entropía, para una variable aleatoria discreta $X$ con posibles ocurrencias $x_1, ..., x_n$ es $H(X) = \sum_{i=1}^{n} P(x_i)\log P(x_i)$ . Así que en mi caso, $X$ sería $S$ y $x_i, ... x_n$ sería $s_1, ..., s_n$ . Entonces: $$H(X) =H(S)= -\sum_{i=1}^n P(s_i) \log P(s_i) $$

Así que quiero que $ - \log P(s_i) = H(s_i)$ Pero no sé cómo seguir adelante con eso. También busqué eso en algunos libros pero no encontré ninguna prueba.

Answer 1

Un proceso aleatorio $X_1,X_2,\cdots$ se asocia a un tasa de entropía definido como \begin{eqnarray*} \mathcal{H} &=& \lim_{n \rightarrow \infty} \frac{1}{n}H(X_n, X_{n-1}, \cdots, X_1) \end{eqnarray*} (cuando existe el límite). Si el proceso es estacionario, como parece ser en tu ejemplo, entonces puedes utilizar una definición equivalente para la tasa de entropía: \begin{eqnarray*} \mathcal{H} &=& \lim_{n \rightarrow \infty} H(X_n | X_{n-1}, \cdots, X_1) \\ \end{eqnarray*}

La definición que tiene sentido utilizar en el caso de un proceso de Markov estacionario es la segunda. En tu ejemplo, parece que estás asumiendo una fuente de Markov de orden 1 (el símbolo actual depende de un solo símbolo pasado). En ese caso \begin{eqnarray*} H(X_n | X_{n-1}, \cdots, X_1) = H(X_n | X_{n-1}) = H(X_1|X_0) \end{eqnarray*} donde la última igualdad se deriva de la estacionariedad del proceso. Entonces la ecuación para la tasa de entropía que mencionaste se deduce trivialmente, como \begin{eqnarray*} H(X_1|X_0) &=& \sum_{x_0} p(x_0) \sum_{x_1} p(x_1|x_0) \log \frac{1}{p(x_1|x_0)} \\ &=&\sum_{x_0} p(x_0) H(X_1 | X_0 = x_0) \end{eqnarray*}

Ahora, usted tiene una condición adicional en su problema que es que " $P$ " no depende de " $P_0$ ". No está claro a qué te refieres exactamente, pero con mucha probabilidad, estás intentando afirmar que la distribución estacionaria de la cadena de Markov no depende de la distribución del estado inicial. Esta condición no es estrictamente necesaria para obtener la fórmula de la entropía anterior, sin embargo esa condición suele ser muy útil cuando se quiere estudiar cómo se asocia la probabilidad de las secuencias largas con la entropía.

Si la distribución estacionaria no depende de las condiciones iniciales, la cadena de Markov es "ergódica". Una de las consecuencias de la ergodicidad es que los promedios empíricos convergen a la expectativa con probabilidad 1, a medida que el número de muestras que se promedian llega al infinito; concretamente si $E[X_0] < \infty$ para un proceso aleatorio estacionario y ergódico,

\begin{eqnarray*} \lim_{n \rightarrow \infty} \frac{1}{n} \sum_i f(X_i) = E[X_0] \end{eqnarray*}

con probabilidad 1. Si se introduce $f = \log P_{X_1|X_0}$ , entonces se obtiene que

\begin{eqnarray*} \lim_{n \rightarrow \infty} \frac{1}{n} \sum_i -\log P_{X_1|X_0}(X_i | X_{i-1}) = E[-\log P(X_1|X_{0})] = H(X_1|X_0) \end{eqnarray*} con probabilidad 1. Así pues, la ergodicidad hace que la entropía tenga sentido: puede utilizarse para estimar la probabilidad de secuencias largas de símbolos, independientemente de cómo empiece la secuencia.

Para más referencias, consulte el libro clásico Elements of Information Theory de Cover y Thomas.