Maximal effect of aggregation on the KL-divergences of short-time Markov chains

Abstract

Aggregation is a fundamental tool for reducing the complexity and storage require- ments of large datasets. It is commonly applied to stochastic models such as Markov chains. One common aggregation method for Markov chains is occupancy time, which records the total time a chain spends in a given state, thus disregarding the chronological order of the visited states. This thesis studies the maximal loss of information caused by occupancy time aggregation in discrete-time two-state Markov chains, measured by Kullback-Leibler (KL) divergence. The information loss from this aggregation is measured by calcu- lating the ratio between the KL-divergences of two stationary Markov chains and the KL-divergence of their aggregated occupancy time distributions. The research question addresses how much the distinguishability between two Markov chains P and Q can suffer under such aggregation. The goal is to determine whether the ratio of the divergences is bounded from above, or whether it can diverge to infinity. The analysis focuses on sequences of two and three time steps taken in the Markov chain. For two time steps it was proven that aggregation does not lose any information, and the KL-divergence remains identical for any two stationary Markov chains and their aggregated counterparts. This guarantees that the aggregated distribution preserves all of the information from the original path distribution of the Markov chain. For three time steps, specific Markov chains were constructed via an ansatz, for which the ratio of the divergences grows without bound as ϵ goes to zero, behaving asymptotically like 1/ϵ. This proves that the ratio of the KL-divergences can be made arbitrarily large, and thus the distinguishability of two Markov chains P and Q can be almost completely lost through aggregation. The results are consistent with previous literature such as the data processing inequality. They show that although computationally convenient, occupancy time can lead to significant loss of information, and should therefore not be applied to all situations.

Aggregointi on keskeinen menetelmä, jolla vähennetään suurten aineistojen monimut- kaisuutta ja tallennustilan tarvetta. Sitä sovelletaan yleisesti stokastisiin malleihin, kuten Markovin ketjuihin. Eräs yleinen aggregointitapa Markovin ketjuille on ti- lassaoloaika (engl. occupancy time), joka mittaa kokonaisajan, jonka ketju viettää annetussa tilassa, ja sivuuttaa vierailtujen tilojen kronologisen aikajärjestyksen. Vaik- ka menetelmä on laskennallisesti kätevä, aggregointi ei voi lisätä informaation määrää, ja yleisesti se väistämättä hävittää informaatiota. Tässä työssä tutkitaan suurinta mahdollista informaatiohävikkiä, joka syntyy dis- kreettiaikaisten kahden tilan Markovin ketjujen aggregoinnista, mitattuna Kullback- Leibler (KL) divergenssin avulla. Informaatiohävikkiä mitataan vertaamalla kahden stationaarisen kaksitilaisen Markovin ketjun polkujakauman divergenssiä aggregoi- tujen tilassaoloaikajakaumien väliseen KL-divergenssiin. Tutkimuskysymyksenä on, kuinka paljon kahden Markovin ketjun P ja Q erotettavuus voi heikentyä tämän aggregaation alaisena. Tavoitteena on selvittää, onko divergenssien suhde rajoitettu ylhäältä, vai voiko jakaumien suhde kasvaa äärettömän suureksi. Tarkastelu rajataan kahteen ja kolmeen aika-askeleeseen. Kahden aika-askeleen tapauksessa todistetaan, että aggregointi ei vaikuta ket- jujen väliseen KL-divergenssiin, sillä divergenssin arvo pysyy samana aggregoinnin jälkeen. Tämä takaa, että aggregoitu jakauma säilyttää kaiken informaation alku- peräisestä Markovin ketjun polkujakaumasta. Kolmen aika-askeleen tapauksessa muodostetaan yrite kahdesta Markovin ketjusta, joille polkudivergenssin ja tilassao- lojakaumien divergenssin suhde kasvaa ilman rajaa parametrin ϵ lähestyessä arvoa 0. Divergenssien suhde kasvaa nopeudella 1/ϵ, mikä tarkoittaa, että aggregoinnin vuoksi kadotetun informaation määrä voi olla mielivaltaisen suuri. Tämän takia kaksi Markovin ketjua voivat muuttua lähes erottamattomiksi aggregoinnin jälkeen. Tulokset ovat yhdenmukaisia aiemman kirjallisuuden, kuten datankäsittelyepäyhtä- lön kanssa. Ne osoittavat, että vaikka tilassaoloaika on laskennallisesti kätevä, se voi johtaa merkittävään informaatiohävikkiin, mikä tarkoittaa, että sitä ei tulisi soveltaa kaikkiin tilanteisiin.