Praktika 2 resene priklady

pr0

Máme daný Markovův řetězec s diskrétním časem {Xn | n ∈ N0}. Stavový prostor tohoto řetězce je {1, 2}, s počátečním rozdělením X0 daným vektorem p(0) = (1/2, 1/2).

graph LR
    A[1]
    B[2]
    A --1--> A
    B --1/2--> B
    B --1/2--> A

Úkoly jsou následující:

1. Výpočet entropie náhodné veličiny X1
2. Vypočítejte podmíněnou entropii H(X_1|X_0) a H(X_0|X_1).
3. Najděte vzájemnou informaci náhodných veličin X0 a X1.

Máme daný Markovův řetězec s diskrétním časem {Xn | n ∈ N0}.

Stavový prostor tohoto řetězce je {1, 2}, s počátečním rozdělením X0 daným vektorem p(0) = (1/2, 1/2).

Matice pravděpodobností přechodů je následující:

	1	2
1	1	0
2	1/2	1/2

Entropie náhodné veličiny X1

Entropii náhodné veličiny $X_1$ můžeme vypočítat následovně:

Entropie je definována jako

$$H(X) = -\sum_{i \in I} p(x_i) \log_2 p(x_i)$$

kde $I$ je množina všech možných hodnot náhodné veličiny a $p(x_i)$ je pravděpodobnost, že náhodná veličina nabývá hodnoty $x_i$. Počáteční stavový vektor: $p(0) = \begin{bmatrix}1/2\\1/2\end{bmatrix}$

Přechodová matice: $P = \begin{bmatrix}1 & 0\\1/2 & 1/2\end{bmatrix}$

Můžeme vypočítat vektor stavů $X_1$ násobením počátečního stavového vektoru přechodovou maticí:

$p(1) = p(0) \times P = \begin{bmatrix}1/2\\1/2\end{bmatrix} \times \begin{bmatrix}1 & 0\\1/2 & 1/2\end{bmatrix} = \begin{bmatrix}3/4\\1/4\end{bmatrix}$

Takže pravděpodobnosti stavů $X_1$ jsou $P(X_1 = 1) = 3/4$ a $P(X_1 = 2) = 1/4$.

Nyní můžeme pokračovat výpočtem entropie $X_1$ tedy $H(X_1)$ $$H(X_1) = - P(X_1 = 1) \log_2 P(X_1 = 1) - P(X_1 = 2) \log_2 P(X_1 = 2) = -3/4*\log_2(3/4) - 1/4*\log_2(1/4)$$

Podmíněná entropie $H(X_1|X_0)$ a $H(X_0|X_1)$

Podmíněnou entropii můžeme vypočítat pomocí vzorce

$$H(X | Y) = - \sum_{y \in Y} p(y) \sum_{x \in X} p(x | y) \log_2 p(x | y)$$

Opět můžeme vložit naše hodnoty do tohoto vzorce a vypočítat výsledky.

Vzájemná informace náhodných veličin X0 a X1

Vzájemná informace je definována jako

$$I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log_2 \left(\

\frac{p(x,y)}{p(x)p(y)}\right)$$

Toto je také rovno rozdílu entropií $H(X) - H(X|Y)$.

Výpočet vzájemné informace vyžaduje znalost společné distribuce $p(x, y)$, kterou lze vypočítat z podmínek Markovova řetězce.

Entropie náhodné veličiny X1

Nejprve vypočítejme pravděpodobnosti stavů v čase $X_1$ podle přechodové matice a počátečního rozdělení.

$$P(X_1 = 1) = P(X_0 = 1)*P(X_1 = 1 | X_0 = 1) + P(X_0 = 2)*P(X_1 = 1 | X_0 = 2) = 1/2*1 + 1/2*1/2 = 3/4$$

a

$$P(X_1 = 2) = P(X_0 = 1)*P(X_1 = 2 | X_0 = 1) + P(X_0 = 2)*P(X_1 = 2 | X_0 = 2) = 1/2*0 + 1/2*1/2 = 1/4$$

Nyní vypočteme entropii $X_1$:

$$H(X_1) = - P(X_1 = 1) \log_2 P(X_1 = 1) - P(X_1 = 2) \log_2 P(X_1 = 2) = -3/4*\log_2(3/4) - 1/4*\log_2(1/4)$$

Podmíněná entropie $H(X_1|X_0)$ a $H(X_0|X_1)$

Podmíněnou entropii můžeme vypočítat pomocí vzorce.

V případě $H(X_1|X_0)$ to je:

$$H(X_1 | X_0) = - \sum_{x \in \{1,2\}} P(X_0 = x) \sum_{y \in \{1,2\}} P(X_1 = y | X_0 = x) \log_2 P(X_1 = y | X_0 = x)$$

Dosazením hodnot dostáváme:

$$H(X_1 | X_0) = -1/2*\{1*\log_2(1) + 0*\log_2(0)\} - 1/2*\{1/2*\log_2(1/2) + 1/2*\log_2(1/2)\}$$

Podobně můžeme vypočítat $H(X_0|X_1)$.

Vzájemná informace náhodných veličin X0 a X1

Vzájemná informace je rovna rozdílu entropií $H(X_1) - H(X_1|X_0)$.

Dosazením našich výsledků dostáváme:

$$I(X_0;X_1) = H(X_1) - H(X_1|X_0)$$

Pro nalezení vzájemné informace náhodných veličin $X_0$ a $X_1$ pro daný Markovův řetězec, můžeme použít vzorec pro vzájemnou informaci, který je definován jako:

$$I(X_0;X_1) = \sum_{x_0} \sum_{x_1} p(x_0, x_1) \log \left(\frac{p(x_0, x_1)}{p(x_0)p(x_1)}\right),$$

kde $p(x_0, x_1)$ je sdružené rozdělení pravděpodobnosti $X_0$ a $X_1$, a $p(x_0)$ a $p(x_1)$ jsou marginální rozdělení pravděpodobnosti $X_0$ a $X_1$.

Chcete-li vytvořit tabulku sdruženého rozdělení pravděpodobnosti z matice přechodových pravděpodobností a vektoru počátečních pravděpodobností, postupujte následovně:

Mějme matici přechodových pravděpodobností $P$ a počáteční vektor pravděpodobnosti $p(0)$. Sdruženou pravděpodobnost, že systém začíná ve stavu $i$ v čase 0 a přechází do stavu $j$ v čase 1, můžeme vypočítat jako

$$p(X_0=i, X_1=j) = p(X_0=i) \cdot P_{ij},$$

kde $P_{ij}$ je prvek matice $P$ na pozici $(i, j)$.

Příklad: Mějme matici přechodových pravděpodobností $$P = \begin{bmatrix} 1 & 0 \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix},$$

a počáteční vektor pravděpodobnosti $p(0) = \left(\frac{1}{2}, \frac{1}{2}\right)^T$.

Tabulku sdruženého rozdělení pravděpodobnosti můžeme vytvořit následovně:

	X1 = 1	X1 = 2
X0 = 1	1/2 * 1	1/2 * 0
X0 = 2	1/2 * 1/2	1/2 * 1/2

Dosazením hodnot dostaneme:

	X1 = 1	X1 = 2
X0 = 1	1/2	0
X0 = 2	1/4	1/4

Tabulka reprezentuje sdružené rozdělení pravděpodobnosti $X_0$ a $X_1$.