Varasemas loengus oleme näinud, et kaootilise dünaamikaga kaasneb informatsiooni kaotus: Kui algtingimus on antud ainult lõpliku täpsusega, ei ole võimalik, trajektoori käitumist ennustada, ja õigede numbrikohtade arv väheneb igal dünaamika sammul. See tööleht näitab, kuidas me saame informatsiooni kaotust kvantitatiivselt kirjeldada.
Informatsiooni kaotuse kirjeldamiseks kasutame Kolmogorovi entroopiat. Selle definitisioon sõltub sellest, kas me uurime diskreetse või pideva süsteemi kaootilist käitumist. Me alustame diskreetsest süsteemist.
Selleks, et uurida informatsiooni kaotust, jagame faasiruumi $Q$ ühtlaselt plokideks $Q_i$, mille küljepikkus on $\epsilon$. Kui faasiruumi mõõde on $d$, järeldub, et iga ploki ruumala on $\epsilon^d$. Kui me valime juhuslikult algtigimust $x_0 \in Q$, millele vastab trajektoor $(x_n, n \in \mathbb{N})$, siis tähistame sümboliga $P_{i_0 \cdots i_n}$ tõenäosust, et $x_0 \in Q_{i_0}$, $x_1 \in Q_{i_1}$ jne kuni $x_n \in Q_{i_n}$. Informatsiooni, mis meil vaja läheb, et määrata trajektoori osa $x_0, \ldots, x_n$ täpsusega $\epsilon$, kirjeldab Shannoni entroopia
$$K_n = -\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n}.$$Selleks et ennustada järgmist sammu $x_{n + 1}$, on lisainformatsiooni $K_{n + 1} - K_n$ vaja. Vastupidelselt võime õelda, et $K_{n + 1} - K_n$ on lisainformatsioon, mis meil vaja läheb, et rekonstrueerida eelmist sammu $x_n$, kui me teame trajektoori ainult alates punktist $x_{n + 1}$. Seega kirjeldab $K_{n + 1} - K_n$ informatsiooni kaotust sammul $n + 1$. Keskmine informatsiooni kaotus, piirjuhul $n \to \infty$ ja $\epsilon \to 0$, on Kolmogorovi entroopia
$$\begin{split} K &= \lim_{\epsilon \to 0}\lim_{n \to \infty}\frac{1}{n}(K_n - K_0)\\ &= -\lim_{\epsilon \to 0}\lim_{n \to \infty}\frac{1}{n}\left(\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n} - \sum_{i_0}P_{i_0} \ln P_{i_0}\right)\\ &= -\lim_{\epsilon \to 0}\lim_{n \to \infty}\frac{1}{n}\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n}. \end{split}$$Konstantset liiget $K_0$, mis ei sõltu $n$-ist, võib ära jätta, kuna
$$\lim_{n \to \infty}\frac{1}{n}K_0 = 0.$$Kui me uurime diskreetse süsteemi asemel pidevat dünaamilist süsteemi, võime diskreetse ajasammu $\tau > 0$ valida. Sellisel juhul kirjeldab $P_{i_0 \cdots i_n}$ tõenäosust, et $x(0) \in Q_{i_0}$, $x(\tau) \in Q_{i_1}$ jne kuni $x(n\tau) \in Q_{i_n}$. Mida väiksem on ajasamm $\tau$, seda paremini kirjeldab diskreetne süsteem $x(0) \mapsto x(\tau)$ pideva süsteemi käitumist. Kolmogorovi entroopia, mis pideva süsteemi puhul näitab keskmist informatsiooni kaotust ajavahemikus $n\tau$, on seega piirväärtus
$$K = \lim_{\tau \to 0}\lim_{\epsilon \to 0}\lim_{n \to \infty}\frac{1}{n\tau}K_n = -\lim_{\tau \to 0}\lim_{\epsilon \to 0}\lim_{n \to \infty}\frac{1}{n\tau}\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n}.$$Järgmisena uurime informatsiooni kaotust süsteemi puhul, mida me oleme juba varem kohanud: saehambakujutus. Lisaks vaatame, kuidas deterministilise kaootilise süsteemi informatsiooni kaotus erineb juhuslikust liikumisest.
Varasemas loengus vaatasime saehambakujutust $S: [0, 1) \to [0, 1)$, mis on defineeritud valemi
$$S(x) = 2x - \lfloor 2x \rfloor$$abil. Kõige lihtsam on arvutada Kolmogorovi entroopiat, kui me jagame vahemikku $[0, 1)$ ühtlaselt $2^k$ osaks $Q_0, \ldots, Q_{2^k - 1}$, kus
$$Q_i = \left[2^{-k}i, 2^{-k}(i + 1)\right).$$Tõenäosus $P_{i_0}$, et juhuslikult valitud punkt $x \in Q = [0, 1)$ asub vahemikus $Q_{i_0}$, on seega $2^{-k}$. Sellest järeldub, et
$$K_0 = -\sum_{i_0 = 0}^{2^k - 1}2^{-k}\ln 2^{-k} = k\ln 2.$$Kui $x \in Q_i$, siis järeldub, et $S(x) \in Q_{2i \mod 2^k} \cup Q_{(2i + 1) \mod 2^k}$. Järelikult on tõenäosus
$$P_{i_0i_1} = \begin{cases} \frac{1}{2}2^{-k} & \text{kui } i_1 = 2i_0 \mod 2^k \text{ või } i_1 = (2i_0 + 1) \mod 2^k,\\ 0 & \text{vastasel juhul.} \end{cases}$$Sellest järeldub, et
$$K_1 = -\sum_{i_0 = 0}^{2^k - 1}\sum_{i_1 = 2i_0 \mod 2^k}^{(2i_0 + 1) \mod 2^k}2^{-(k + 1)}\ln 2^{-(k + 1)} = (k + 1)\ln 2.$$Samuti leiame, et üldjuhul kehtib
$$P_{i_0 \cdots i_n} = \begin{cases} \frac{1}{2}P_{i_0 \cdots i_{n - 1}} & \text{kui } i_n = 2i_{n - 1} \mod 2^k \text{ või } i_n = (2i_{n - 1} + 1) \mod 2^k,\\ 0 & \text{vastasel juhul.} \end{cases}$$Järelikult kehtib
$$\begin{split} K_n &= -\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n}\\ &= -\sum_{i_0 = 0}^{2^k - 1}\sum_{i_1 = 2i_0 \mod 2^k}^{(2i_0 + 1) \mod 2^k} \cdots \sum_{i_n = 2i_{n - 1} \mod 2^k}^{(2i_{n - 1} + 1) \mod 2^k}\frac{P_{i_0 \cdots i_{n - 1}}}{2}\ln\frac{P_{i_0 \cdots i_{n - 1}}}{2}\\ K_n &= -\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n}\\ &= -\sum_{i_0 = 0}^{2^k - 1}\sum_{i_1 = 2i_0 \mod 2^k}^{(2i_0 + 1) \mod 2^k} \cdots \sum_{i_{n - 1} = 2i_{n - 2} \mod 2^k}^{(2i_{n - 2} + 1) \mod 2^k}P_{i_0 \cdots i_{n - 1}}\left(\ln P_{i_0 \cdots i_{n - 1}} - \ln 2\right)\\ &= K_{n - 1} + \ln 2\\ &= K_0 + n\ln 2\\ &= (k + n)\ln 2. \end{split}$$Lõpuks järeldub, et
$$K = \lim_{k \to \infty}\lim_{n \to \infty}\frac{1}{n}K_n = \lim_{k \to \infty}\ln 2 = \ln 2.$$Igal sammul on entroopia kasv $\ln 2$. Informatsioonikaotus on seega 1 bitt igal sammul. See on kooskõlas vaatlusega, et igal sammul nihkub kahendesitus ühe numbrikohta võrra vasakule, ja üks numbrikoht on kustutatud.
Determineeritud dünaamilise süsteemi asemel võime ka juhusliku liikumise Kolmogorovi entroopiat arvutada. Kui me jagame faasiruumi $Q$ ühtlaselt $m$ osaks $Q_0, \ldots, Q_{m - 1}$, on tõenäosus, et juhuslikult valitud punkt $x \in Q$ asub osas $Q_{i_0}$
$$P_{i_0} = \frac{1}{m}.$$Juhuslik liikumine tähendab, et järgmise punkti asukoht trajektoori peal ei sõltu eelneva punkti asukohast. Sellest järeldub, et trajektoori tõenäosus on
$$P_{i_0 \cdots i_n} = \frac{1}{m^{n + 1}}.$$Järelikult kehtib
$$K_n = -\sum_{i_0, \ldots, i_n}P_{i_0 \cdots i_n} \ln P_{i_0 \cdots i_n} = \sum_{i_0, \ldots, i_n}\frac{(n + 1)\ln m}{m^{n + 1}} = (n + 1)\ln m.$$Lõpuks leiame, et
$$K = \lim_{m \to \infty}\lim_{n \to \infty}\frac{1}{n}K_n = \lim_{m \to \infty}\ln m = \infty.$$Tulemus näitab, et lõpliku osade arvu $m$ korral kaob ära igal sammul kogu informatsioon, mis määrab punkti asukohta. Entroopia kasv igal sammul on seega $\ln m$. Kuna piirjuhul $m \to \infty$ on lõpmatult palju informatsiooni vaja, et punkti asukoha defineerida, on ka entroopia kasv lõpmatu.