| |
|
Cumulative Optimality in Risk-Sensitive and Risk-Neutral Markov Reward Chains
Sladký, Karel
This contribution is devoted to risk-sensitive and risk-neutral optimality in Markov decision chains. Since the traditional optimality criteria (e.g. discounted or average rewards) cannot reflect the variability-risk features of the problem, and using the mean variance selection rules that stem from the classical work of Markowitz present some technical difficulties, we are interested in expectation of the stream of rewards generated by the Markov chain that is evaluated by an exponential utility function with a given risk sensitivity coefficient. Recall that for the risk sensitivity coefficient equal zero we arrive at¨traditional optimality criteria. In this note we present necessary and sufficient risk-sensitivity and risk-neutral optimality conditions; in detail for unichain models and indicate their generalization to multichain Markov reward chains.
|
|
Recursive Estimation of High-Order Markov Chains: Approximation by Finite Mixtures
Kárný, Miroslav
A high-order Markov chain is a universal model of stochastic relations between discrete-valued variables. The exact estimation of its transition probabilities suers from the curse of dimensionality. It requires an excessive amount of informative observations as well as an extreme memory for storing the corresponding su cient statistic. The paper bypasses this problem by considering a rich subset of Markov-chain models, namely, mixtures of low dimensional Markov chains, possibly with external variables. It uses Bayesian approximate estimation suitable for a subsequent decision making under uncertainty. The proposed recursive (sequential, one-pass) estimator updates a product of Dirichlet probability densities (pds) used as an approximate posterior pd, projects the result back to this class of pds and applies an improved data-dependent stabilised forgetting, which counteracts the dangerous accumulation of approximation errors.
|
|
Coupling a rychlost konvergence Markovských řetězců
Macháček, Adam ; Prokešová, Michaela (vedoucí práce) ; Honzl, Ondřej (oponent)
V předložené práci studujeme dvě metody pro odvození od- hadu rychlosti konvergence marginálního rozdělení diskrétního, aperio- dického a nerozložitélného Markovského řetězce s konečným stavovým prostorem k jeho stacionárnímu rozdělení. Nejprve se zabýváme odhado- váním rychlosti konvergence pomocí couplingové metody. K této metodě potřebujeme vzdálenost v totální variaci, kterou definujeme a vysvětlíme úlohu, kterou má tato vzdálenost v teorii odhadování rychlosti konver- gence. V druhé části studujeme odhad rychlosti konvergence metodou silně rovnoměrných časů. Obě metody popíšeme a dokážeme o nich ně- která základní tvrzení. Poté ukážeme použití obou postupů na několika příkladech, především na příkladu procházky po hyperkrychli a na mo- delu míchání karet. 1
|
|
Optimalizace volby alternativ v markovských řetězcích pomocí metod lineárního programování
Krátká, Jitka ; Kořenář, Václav (vedoucí práce) ; Šindelářová, Irena (oponent)
Cílem této práce bylo vypracování postupu a popisu při řešení úloh markovských rozhodovacích procesů s alternativami pomocí metod lineárního programovaní. Teoretická část se zabývá popisem markovských rozhodovacích řetězců s alternativami. Praktická část práce je věnovaná konstrukci matematického modelu úloh a jeho popisu. Dále je zde vysvětleno a popsáno následné užití v programech pro lineární modelování jako je LINGO a MPL. Práce obsahuje také vysvětlení výstupů z programů, a kde v nich lze výsledky hledat. V příloze jsou přiloženy výstupy bez zkrácené podoby a také obrázky, které ukazují pracovní prostředí obou programů.
|
| |
|
Algoritmické aplikace konečných Markovských řetězců
Pavlačková, Petra ; Prokešová, Michaela (vedoucí práce) ; Staňková Helisová, Kateřina (oponent)
Název práce: Algoritmické aplikace konečných Markovských řetězců Autor: Petra Pavlačková Katedra/Ústav: Katedra pravděpodobnosti a matematické statistiky Vedoucí bakalářské práce: RNDr. Michaela Prokešová, Ph.D. e-mail vedoucího: prokesov@karlin.mff.cuni.cz V předložené práci studujeme MCMC algoritmy, které používáme k simulaci z rozdělení na konečné stavové množině. Algoritmy aplikujeme pro dva modely: hard-core model a q-obarvení grafu. Využíváme zde znalosti z teorie náhodných procesů, hlavně Markovských řetězců a jejich vlastnosti. Také se seznámíme s problémy, které mohou při simulaci těchto algoritmů nastat, zejména tedy s problémem odhadu rychlosti konvergence marginálního rozdělení Markovského řetězce k požadovanému stacionárnímu rozdělení. Součástí práce je numerická ilustrace použití Gibbsova algoritmu pro odhad středního počtu jedniček zobecněného hard-core modelu. Klíčová slova: Markovský řetězec, MCMC algoritmus, hard-core model, rychlost konvergence
|
|
Silně stacionární časy a konvergence Markovských řetězců
Suk, Luboš ; Prokešová, Michaela (vedoucí práce) ; Kříž, Pavel (oponent)
V této práci si ukážeme, jak se dá odhadovat rychlost konvergence markovských řetězců k jejich stacionárnímu rozdělení. Budeme k tomu používat metodu využívající silně stacionárních časů. Zaměříme se pouze na nerozložitelné a aperiodické řetězce, u kterých máme zaručenou existenci právě jednoho sta- cionárního rozdělení. Zavedeme si čas mixingu markovského řetězce neboli čas potřebný k tomu, aby marginální rozdělení řetězce bylo dostatečně blízko stacionárnímu. K měření vzdálenosti mezi rozděleními budeme v této práci používat vzdálenost v totální variaci. Hlavním cílem práce bude pro vybrané řetězce zkonstruovat vhodný silně stacionární čas a ten pak použít k nalezení horního odhadu času mixingu.
|
|
Coupling a rychlost konvergence diskrétních MCMC algoritmů.
Kalaš, Martin ; Prokešová, Michaela (vedoucí práce) ; Dvořák, Jiří (oponent)
Konvergence marginálního rozdělení Markovova řetězce ke stacionárnímu rozdělení je důležitá vlastnost, která má v moderní matematice mnoho aplikací. Jednou z nich jsou např. Markov Chain Monte Carlo algoritmy, které slouží ke generování realizací ze složitých pravděpodobnostních rozdělení. Pro takové aplikace je klíčové správně odhadnout tzv. mixing time Markovova řetězce, tj. počet kroků nutný k tomu, aby se marginální rozdělení řetězce lišilo od stacionárního rozdělení jen s povolenou nepřesností. Cílem této práce je popsat metodu odhadu mixing time, která využívá obecnou pravděpodobnostní techniku zvanou coupling. V první části textu bude vybudován teoretický aparát, na jehož základě tuto metodu odvodíme. Ve druhé části předvedeme její použití na klasických příkladech Markovových řetězců, kterým je například náhodná procházka po grafu. V závěru ukážeme odhad rychlosti konvergence Metropolisova řetězce pro přípustná obarvení grafu, jakožto typického příkladu MCMC algoritmu.
|
| |
host ::
