Teoria informacji/TI Ćwiczenia 12

From Studia Informatyczne

Druga zasada termodynamiki

Druga zasada termodynamiki w fizyce brzmi następująco:

W układzie zamkniętym w dowolnym procesie entropia nigdy nie maleje.

Pokażemy tutaj, jak prawo to wiąże się z pojęciami z teorii informacji.

W mechanice statystycznej, entropia układu jest definiowana przy pomocy identycznego wzoru jak entropia Shannona, gdzie konkretnym wartościom zmiennej losowej odpowiadają pojedyncze mikrostany układu. Każdy mikrostan opisuje wszystkie parametry układu mające wpływ na jego dalszą ewolucję. Oznacza to, że stan układu w przyszłości zależy wyłącznie od stanu aktualnego, niezależnie od tego, w jaki sposób stan aktualny został uzyskany. Dzięki temu zachowanie układu izolowanego w czasie możemy modelować za pomocą łańcucha Markowa X_0, X_1, \ldots. Okazuje się, że entropia w takim modelu nie zawsze rośnie, ale można wskazać warunki dla których tak się dzieje.


Ćwiczenie 1 [Jednostajny rozkład stacjonarny]

Załóżmy, że rozkład stacjonarny procesu Markowa jest jednostajny (prawdopodobieństwa wszystkich mikrostanów są równe).

W takim przypadku cały układ dąży do stanu jednostajnego i jego entropia dąży do maksymalnej. Udowodnij, że w takiej sytuacji dla dowolnego stanu początkowego X_0 i dowolnej ilości kroków n zachodzi H(X_{n+1}) \ge H(X_n).


Ćwiczenie 2 [Entropia przyszłości]

Załóżmy, że układ znajduje się w stanie stacjonarnym, a więc H(X_n) nie zmienia się w czasie. Udowodnij, że H(X_n|X_1) rośnie razem z n (a więc przewidywanie przyszłości jest tym trudniejsze, im dalszą

przyszłość chcemy przewidzieć).


Ćwiczenie 3 [Entropia przyszłości - c.d.]

Znajdź przykład dla którego w H(X_n|X_1=x_1) nie zawsze rośnie razem z n.


Ćwiczenie 4 [Strzałka czasu]

Niech \{X_i\}_{i=-\infty}^{\infty} będzie stacjonarnym procesem Markowa. Pokaż, że

H(X_0|X_{-1},X_{-2}, \ldots, X_{-n})=H(X_0|X_1,X_2,\ldots,X_n)

(Czyli że mając dany stan układu w kolejnych krokach, równie trudno jest obliczyć stan układu w przyszłości, jak

jego stan w przeszłości.


Ćwiczenie 5 [Tasowanie kart]

Niech T oznacza tasowanie (permutację) talii kart, X oznacza początkowe ich ułożenie, a TX oznacza ułożenie kart po zaaplikowaniu tasowania T do X. Pokaż, że jeśli wybór T i X jest niezależny, to

H(TX) \ge H(X)