Stacionární rozdělení a limitní vlastnosti
Stacionární rozdělení je jedním z nejdůležitějších konceptů v teorii Markovových řetězců. Je to takové rozdělení pravděpodobnosti stavů, které se nemění v čase. Jinými slovy, je to vektor pravděpodobností, který zůstává konstantní po aplikaci přechodové matice.
Představte si, že máte Markovův řetězec s konečným počtem stavů a s přechodovou maticí P. Stacionární rozdělení je takové rozdělení pravděpodobnosti (označme ho π), které splňuje následující rovnici:
πP = π
To znamená, že když vynásobíme přechodovou matici P vektorem stacionárního rozdělení π zleva, dostaneme zpět π.
Například vezměme Markovův řetězec se dvěma stavy a přechodovou maticí:
Připomeňme, že hledáme vektor pravděpodobností π, který splňuje rovnici πP = π, kde P je přechodová matice. Pro naši matici
P = [[0.9, 0.1], [0.5, 0.5]]
hledáme takový vektor π = [π1, π2], že platí
π1 0,9 + π2 0,5 = π1,
π1 0,1 + π2 0,5 = π2.
To jsou dvě rovnice pro dvě neznámé π1 a π2. Všimněte si, že se vlastně jedná o systém lineárních rovnic. K tomu je třeba připočíst ještě jednu rovnici, která vychází z podmínky, že součet prvků vektoru π musí být roven 1 (protože π je pravděpodobnostní rozdělení), tedy π1 + π2 = 1.
Takže máme systém tří rovnic o dvou neznámých. Ale při bližším pohledu zjistíme, že první a druhá rovnice jsou ve skutečnosti identické, takže ve skutečnosti máme jen dvě nezávislé rovnice:
π10.9 + π20.5 = π1, π1 + π2 = 1.
Z první rovnice vyplyne, že π1 = π2 0,5/0,1 = 5π2.
Dosazením tohoto vztahu do druhé rovnice dostáváme 5π2 + π2 = 1, odkud π2 = 1/6 ≈ 0,167. A potom π1 = 5π2 = 5/6 ≈ 0,833.
Takže výsledné stacionární rozdělení je π = [0,833, 0,167]. Nic hrozného.
Stacionární rozdělení má mnoho důležitých vlastností. Jednou z nich je, že pokud je Markovův řetězec ergodický (což znamená, že je aperiodický a pozitivně rekurentní), pak má jednoznačné stacionární rozdělení a pravděpodobnostní rozdělení stavů řetězce konverguje k tomuto stacionárnímu rozdělení, pokud řetězec běží dostatečně dlouho (toto je rozebráno zde).
Tato vlastnost je často užitečná v aplikacích, protože umožňuje odhadovat dlouhodobé chování systému bez nutnosti znát jeho počáteční stav. Například v oblasti počítačových sítí může stacionární rozdělení poskytnout informace o tom, jaký procentuální podíl času stráví systém v určitých stavech v dlouhodobém horizontu. Zkusme si na tohle jednoduchý příklad.
Příklad 1.
Představme si jednoduchý systém, který reprezentuje server obsluhující požadavky od uživatelů. Tento systém může být v jednom ze tří stavů:
- Nečinný - server momentálně neobsluhuje žádný požadavek.
- Částečně zaneprázdněný - server obsluhuje jeden požadavek.
- Plně zaneprázdněný - server obsluhuje dva požadavky najednou.
Předpokládejme, že přechodová matice tohoto systému je:
Přechodovou matici můžeme získat na základě historických dat nebo pomocí expertního odhadu. Pokud jde o praktické aplikace, často používáme kombinaci obou přístupů.
Pokud máme k dispozici historická data, můžeme analyzovat, jak se systém choval v minulosti, a na základě toho odhadnout pravděpodobnosti přechodu mezi jednotlivými stavy. Například, pokud pravidelně a dlouho sledujeme server, můžeme zaznamenávat, jak často se server pohybuje mezi různými stavy (nečinný, částečně zaneprázdněný, plně zaneprázdněný) a na základě těchto dat vytvořit přechodovou matici. Pokud nemáme k dispozici dostatek historických dat, můžete také použít expertní odhad - prostě se zeptat někoho, kdo tomu rozumí :D. To teď ale neřešme. Ještě se budeme zabývat přechodovou maticí v praxi.
Tato matice ukazuje pravděpodobnosti přechodu mezi jednotlivými stavy. Například, pokud je systém nečinný, s pravděpodobností 0,5 zůstane v nečinném stavu, s pravděpodobností 0,4 přejde do stavu částečně zaneprázdněný a s pravděpodobností 0,1 se stane plně zaneprázdněným.
Podobně, pokud je systém částečně zaneprázdněný, s pravděpodobností 0,3 přejde do stavu nečinný, s pravděpodobností 0,3 zůstane v částečně zaneprázdněném stavu a s pravděpodobností 0,4 se stane plně zaneprázdněným. Nakonec, pokud je systém plně zaneprázdněný, s pravděpodobností 0,1 přejde do stavu nečinný, s pravděpodobností 0,3 se stane částečně zaneprázdněným a s pravděpodobností 0,6 zůstane plně zaneprázdněným.
Předpokládejme, že tento systém je ergodický ( je možné se dostat z jakéhokoli stavu do jakéhokoli jiného stavu) a že máme stacionární rozdělení, například π = [0,2, 0,3, 0,5].
To znamená, že v dlouhodobém horizontu stráví systém přibližně 20% času v nečinném stavu, 30% času v částečně zaneprázdněném stavu a 50% času v plně zaneprázdněném stavu.
Tato informace může být velmi užitečná například při rozhodování o tom, zda je třeba přidat další server pro zvládnutí zátěže, nebo při plánování údržby serveru. Pokud víme, že server je plně využitý 50% času, můžeme například usoudit, že přidání dalšího serveru by mohlo zlepšit výkon naší sítě.
Příklad 2.
Zkusme teď něco více reálného, co můžeme použít třeba v bakalářce. Zatím ale pořád uvažujeme jednodušší příklady. K těm složitějším se dostaneme.
Uvažme tedy téma vliv počasí na návštěvnost parku. Cílem je předpovědět návštěvnost parku v závislosti na počasí, a proto může být užitečné použít Markovovy řetězce.
Nejprve bychom měli identifikovat stavy, které budeme sledovat. V tomto případě by to mohly být tři stavy počasí: slunečno, oblačno a déšť. Tyto stavy můžeme získat z historických meteorologických dat.
Dále potřebujeme určit pravděpodobnosti přechodu mezi těmito stavy, které vytvoří naši přechodovou matici. Tyto pravděpodobnosti můžeme odhadnout na základě historických dat. Například, můžeme zjistit, jak často se po slunečném dni objevil déšť, kolikrát se po oblačném dni objevilo slunce atd. Toto by nám dalo představu o pravděpodobnostech přechodu.
Poté bychom měli sledovat návštěvnost parku v závislosti na počasí a zaznamenat tyto data. Například, pokud je slunečno, kolik lidí obvykle navštíví park? Co když je oblačno? A co když prší?
S touto sadou dat můžeme nyní použít Markovovy řetězce k modelování chování návštěvníků parku v závislosti na počasí. Můžeme například zjistit, jaké je stacionární rozdělení pro naše stavy počasí. To by nám dalo představu o tom, jaké počasí je nejčastější, a tedy očekávanou návštěvnost parku v dlouhodobém horizontu.
Navíc můžeme použít limitní vlastnosti Markovových řetězců k předpovědi návštěvnosti parku. Například, pokud víme, že dnes je slunečno, můžeme vypočítat pravděpodobnost, že bude zítra slunečno, oblačno nebo déšť a podle toho předpovědět návštěvnost parku.
Tento příklad je poměrně jednoduchý a nebere v úvahu mnoho dalších faktorů, které by mohly ovlivnit návštěvnost parku (jako například roční období, den v týdnu, apod.), ale poskytuje základní představu o tom, jak by mohly být Markovovy řetězce použity v reálném kontextu.
Co budeme potřebovat? Potřebujeme nějaký soubor/dataset dat o chování počasí. Ten samozřejmě musíme zjistit manuálně třeba na ČSÚ nebo na různých stránkách počasí. Tohle je ta nudná část práce. Ale potřebujeme to. Mohli bychom vytvořit nějakou tabulku nebo soubor za těch 100 dní.
[1] "Sunny" "Rainy" "Cloudy" "Rainy" "Rainy" "Sunny" "Sunny" "Cloudy" "Sunny" "Sunny" ...
Takhle by to mohlo být uvedeno třeba v proměné v jazyce R, když zobrazíme prvních 10 hodnot.
"R" je super jazyk. Dokáže na základě těchto dat vytvořit přechodovou matici, a to následovně.
Naše data jsou uložena v proměnné "weather". Přechodová matice může vypadat následovně.
Toto je naše přechodová matice, která říká, jaká je pravděpodobnost přechodu mezi jednotlivými stavy počasí. Poté můžeme získat stacionární rozdělení následně. Napíšeme
steadyStates(mcWeather$estimate).
Výsledek je celkem "trapný", protože vyšel moc ideálně. Ale to nevadí.
Sunny Cloudy Rainy
[1,] 0.3333 0.3333 0.3333.
Říká nám, že v dlouhodobém horizontu, každý ze stavů počasí zaujímá přibližně třetinu času. Podobně můžeme analyzovat data o návštěvnosti parku v závislosti na počasí a předpovědět budoucí návštěvnost.
Příklad 3.
Nyní koukneme na něco více praktického. To může být třeba dobrá myšlenka do bakalářské či diplomové práce.
Můžeme se podívat na modelování chování zákazníků v maloobchodě pomocí Markovových řetězců, což je průmyslově relevantní příklad, který může být předmětem bakalářské práce.
Představte si, že provozujete maloobchod a chcete pochopit, jak se vaši zákazníci pohybují po obchodě, abyste mohli lépe uspořádat své zboží a zlepšit prodeje. Chcete zjistit, jaký je pravděpodobný přechod zákazníka mezi různými odděleními obchodu.
V tomto příkladu budou stavy markovského řetězce oddělení v obchůdku, například ovoce a zelenina, pekárna, mléčné výrobky, maso, ryby, nápoje, drogerie. Zákazník se může pohybovat z jednoho oddělení do druhého a my chceme určit pravděpodobnosti těchto přechodů.
Přechodová matice tedy bude obsahovat následující položky: Ovoce a zelenina (O), Pekárna (P), Mléčné výrobky (M), Maso (Ma), Drogerie (D) a Nápoje (N).
Teď se podíváme na to, jak průzkum realizovat tak, aby byl co nejrelevantnější. Potřebujeme zjistit, jak se zákazníci chovají. Měli byste tedy sledovat jednotlivé zákazníky, abyste získali přesný průběh jejich cesty obchodem. Ale to může být náročné a potenciálně problematické z hlediska soukromí.
Alternativou je využít technologie pro sledování pohybu zákazníků. Existují systémy, které mohou sledovat pohyb zákazníků v obchodě pomocí video sledování nebo Wi-Fi sledování. Tyto systémy mohou poskytnout data o pohybu zákazníků mezi jednotlivými odděleními, aniž by bylo nutné individuálně sledovat každého zákazníka.
Pokud však tyto technologie pro vás nejsou dostupné, jednou možností je provést malé pilotní studie, kde skutečně sledujete několik zákazníků (s jejich souhlasem) a zaznamenáváte jejich pohyb mezi odděleními. I když to nebude tak přesné jako plnohodnotná data, může to poskytnout dostatečný odhad přechodových pravděpodobností pro vaše účely. Co se týče doby sledování, záleží na tom, kolik dat potřebujete pro robustní analýzu. Mohli byste začít s tím, že budete sledovat zákazníky po dobu jednoho týdne, a pokud zjistíte, že potřebujete více dat, můžete to rozšířit na další týden nebo měsíc. Velikost vzorku bude také záležet na velikosti obchodu a počtu zákazníků.
Ideální by bylo sledovat zákazníka od začátku až do konce jeho nákupu. Důvodem je, že chcete získat úplný přehled o tom, jak se zákazník pohybuje po obchodě. Pokud sledujete jen část nákupu, mohli byste zmeškat některé přechody mezi odděleními.
Nicméně, v závislosti na tom, jak je to prakticky proveditelné, můžete také sledovat jen část nákupu a poté přejít na sledování dalšího zákazníka. To by mohlo být užitečné, pokud máte omezené zdroje pro sledování (například pokud máte jen jeden člověk, který může sledovat zákazníky, a v obchodě je mnoho zákazníků najednou).
Pokud máte data, bude vhodné je převést do nějaké formy, která bude vhodná pro výpočet přechodové matice. Jak ale tato data mají vypadat? Máme Sadu údajů o tom, jak různí zákazníci přecházeli mezi odděleními. Pro každého zákazníka vytvoříme sadu přechodů, jak prochází obchodem. Pokud se např. zdrží v nějakém oddělení, vytvoříme přechod z tohoto oddělení do toho samého. Takže pokud setrvá zákazník déle třeba v oddělení nápoje, pak to klasifikujeme jako přechod z N do N. Pak bychom moli mít pro 50 zákazníků následující zaznamenaná data, např. ve Wordu, v Excelu apod. Je to strašně malým, já vím, ale chtěl jsem Vám zde dát všechny položky.
Co vidíme? Číslo zákazníka a pod ním jeho přechody mezi odděleními. Nejpracnější bude to dostat do nějaké formy pro program, ve kterém potřebujete počítat. Já bych to sice od začátku dělal jinak, ale uvádím to pro studenty, kteří nemají zkušenosti se software pro analýzu dat. Když to chcete dát do R, měli byste si to vypsat následovně.
Uvedl jsem 5 zákazníků, pokračovali byste dále stejným způsobem. Kód, který Vám z pohybu zákazníků vytvoří přechodovou matici je v R následující.
Přikládám i soubor, kdybyste si jej chtěli stáhnout a použít v R. Jen si ho zkopírujete a vložíte do prostředí s jazykem R.
Musíte si ale před ten kód vložit dataset s těmi zákazníky. Jak jsem výše psal: data_zakaznici <- list(c("N" "M" "Ma" ...
Když to spustíte, vypadne vám nějaká krásná přechodová matice. Něco jako mám já.
Vyšlo nám následující stacionární rozdělení.
O P M Ma Sp N
[1,] 0.1667292 0.1705055 0.1672577 0.1418028 0.1688511 0.1848537
Tyto pravděpodobnosti se neliší o moc, což znamená, že zákazníci se poměrně rovnoměrně rozdělují mezi různá oddělení. Avšak oddělení "Nápoje" má největší pravděpodobnost, což by mohlo naznačovat, že toto oddělení je nejoblíbenější nebo nejnavštěvovanější. Na základě těchto informací můžeme učinit několik strategických rozhodnutí pro obchod, např. optimalizaci uspořádání, plánování zásob, marketing a prodej, personální řízení či design obchodu.
Příklad 4:
Tento příklad se bude týkat využitelnosti míst v parku. Máme následující sekce či objekty, které se v něm nacházejí:
"Hřiště", "Květinová zahrada", "Jezero", "Altán", "Lavičky", "Průlezková atrakce", "Posezení v trávě", "Zmrzlinový stánek".
Budeme zkoumat návštěvníky v parku a zaznamenávat u nich sekvence mobility v rámci těchto objektů/sekcí. Máme např. 60 lidí s jejich sekvencemi, které jsme zaznamenali třeba během dvou dní. Příklad sekvencí by mohl pro 4 lidí vypadat následovně. Nevypisoval jsem tu všech 60, to by bylo zbytečné.
Už jsem je tedy vygeneroval v jazyce R, ale je to ukázka, ať vidíte, jak to zhruba bude vypadat. Nyní použiji kódy z příkladu 3, akorát proměnné samozřejmě nazvu jinak. Zde je kód, který jsem použil. Máte to i v souboru, který si můžete stáhnout. Musíte mít ale opět uvedenu proměnnosu s daty. Tu tady nazývam "sequences". V ní jsou uloženi návštěvníci.
Po puštění kódu dostaneme následující přechodovou matici.
Z výstupu lze vyčísl spousta zajímavých informací. Například od jezera nikdo nešel k altánu nebo na lavičku apod. Ještě si vygenerujeme stacionární rozdělení.
Vidíme následující:
- Hřiště: 0,12607034
- Květinová zahrada: 0,11257994
- Jezero: 0,08527117
- Altán: 0,04247727
- Lavičky: 0,04524784
- Průlezková atrakce: 0,19978162
- Posezení v trávě: 0,08470303
- Zmrzlinový stánek: 0,30386878
Tyto hodnoty představují pravděpodobnost, že náhodně vybraný člověk v parku bude v daný čas na daném místě. Takže například zmrzlinový stánek je nejpopulárnější s pravděpodobností 30 %, zatímco altán a lavičky jsou nejméně populární s pravděpodobností okolo 4-5 %.
Taková informace může být velmi užitečná pro plánování služeb v parku. Například pokud je zmrzlinový stánek velmi oblíbený, je užitečné zvýšit jeho kapacitu nebo zlepšit nabídku. Na druhou stranu, pokud jsou lavičky méně oblíbené, mohlo by to naznačovat jejich nevhodné umístění apod.
Taková informace nám může klidně sloužit pro další akce. Co kdybychom se rozhodli, že budeme chtít někam umístit záchod. Stacionární distribuce nám k tomu poskytuje skvělé informace. Jedním ze způsobů, jak bychom to mohli udělat, je vytvořit matici vzdáleností mezi jednotlivými místy v parku. Tato matice by nám ukázala, jak daleko jsou od sebe jednotlivá místa v parku.
Předpokládejme, že máme takovou matici vzdáleností (v metrech):
Poté bychom mohli pro každé možné místo, kde bychom mohli umístit záchody, vypočítat vážený průměr vzdáleností od všech ostatních míst v parku, přičemž váhy by odpovídaly podílu času, který návštěvníci tráví na těchto místech (naše stacionární distribuce). Místo s nejnižším váženým průměrem by bylo nejlepší pro umístění záchodů.
Tento přístup by se dal upravit i tak, aby zohledňoval další faktory, jako je například skutečnost, že nechceme umístit záchody příliš blízko k místům, kde se konzumuje jídlo. Mohli bychom například přidat velkou penalizaci ke vzdálenostem od těchto míst apod. To teď ale nebudeme řešit. Tento text není úplně o teorii centrálních míst, jen o tom, k čemu nám data ze stacionární distribuce mohou sloužit.
1. Hřiště: 0.12607034 * 0 + 0.11257994 * 100 + 0.08527117 * 200 + 0.04247727 * 150 + 0.04524784 * 50 + 0.19978162 * 80 + 0.08470303 * 100 + 0.30386878 * 120 = 88.234 m
2. Květinová zahrada: 0.12607034 * 100 + 0.11257994 * 0 + 0.08527117 * 50 + 0.04247727 * 70 + 0.04524784 * 80 + 0.19978162 * 110 + 0.08470303 * 90 + 0.30386878 * 30 = 62.526 m
3. Jezero: 0.12607034 * 200 + 0.11257994 * 50 + 0.08527117 * 0 + 0.04247727 * 60 + 0.04524784 * 150 + 0.19978162 * 180 + 0.08470303 * 40 + 0.30386878 * 20 = 72.680 m
Průlezková atrakce: (0.12680 + 0.112110 + 0.085180 + 0.042130 + 0.04530 + 0.1990 + 0.084110 + 0.303130) = 84.10 m
Posezení v trávě (0.126100 + 0.11290 + 0.08540 + 0.04220 + 0.04580 + 0.199110 + 0.0840 + 0.30330) = 53.49 m
Zmrzlinový stánek: (0.126120 + 0.11230 + 0.08520 + 0.04250 + 0.045100 + 0.199130 + 0.08430 + 0.3030) = 55.13 m
4. Lavičky: 229.11 m (už se mi to nechtělo vypisovat, tak uvádím jen výsledky)
5. Altán: 336.79 m
Pro umístění záchodů by tak mohlo být ideální místo "posezení v trávě", což nám teda moc nepomůže :D. V rámci prostoru je to dost vágní. Zase bychom museli analyzovat, kde všude se sedí apod. Ale to je spíš tím, že jsem ty kategorie v parku zvolil vymyšlené - co mě náhodně napadlo. Kdybychom uvažovali třeba druhou nejmenší hodnotu - zmrzlinový stánek - to už je lepší. Mohli bychom umístit záchody poblíž. Ale z estetických důvodů by to zase nebylo úplně ok. To už si musíte ale ve své práci sami rozmyslet. Pouze jsem ukázal, jak je možné na markovovské řetězce navázat. Snad Vám to trochu pomohlo.