|
|
Coupling and speed of convergence of discrete MCMC algorithms.
Kalaš, Martin ; Prokešová, Michaela (advisor) ; Dvořák, Jiří (referee)
Convergence of the marginal distribution of a Markov chain to its stationary distribution is an essential property of this model with many applications in different fields of modern mathematics. Such typical applications are for example the Markov Chain Monte Carlo algorithms, which are useful for sampling from complicated probability distributions. A crucial point for usefulness of such algorithms is the so called mixing time of corresponding Markov chain, i.e. the number of steps the chain has to make for the difference between its current marginal distribution and stationary distribution to be sufficiently small. The main goal of this thesis is to describe a method for estimation of the mixing time based on a probability technique called coupling. In the first part we collect some definitions and propositions to show how the method works. Later the method is demonstrated on several traditional examples of Markov chains including e.g. random walk on a graph. In the end we study Metropolis chain on the set of proper colorings of a graph as a specific example of MCMC algorithm and show how to estimate its mixing time.
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Usage of Markov chains in banking
Klímová, Hana ; Marada, Tomáš (advisor) ; Prášková, Zuzana (referee)
The aim of the thesis is to get acquainted with the theory of Markov chains and to show how it is used in banking for estimation of credit rating transitions. In the first part, an introduction to the theory of discrete-time and continuous-time Markov chain with discrete state space is provided. In the next part three estimating methods that are used to calculate credit rating transitions - namely cohort method, durability method and Aalen-Johansen estimator are described theoreticaly. In the last part these methods are applied to calculate the matrices of transition probabilities on the basis of real rating migrations. Next an empirical transition matrix is used to simulate set of rating progressions, which are then used for estimating the original matrix by all the above mentioned methods. Finally the distance between the original and estimated matrices is evaluated to show the differences between the methods.
|
|
|
Mixing processes with finite alphabet
Vostal, Ondřej ; Kupsa, Michal (advisor) ; Dostál, Petr (referee)
An introduction to the theory of mixing of random processes is presented. The aim of this introduction is to be eventually able to separate general random processes, markov chains and markov chains with finite alphabet into groups which mix differently. The introduction is made complete by examples. We show, that for general processes those groups are separate, for markov chains some coincide, and for markov chains with finite alphabet all coincide. Powered by TCPDF (www.tcpdf.org)
|
|
|
Scenario structures in multistage stochastic programs
Harcek, Milan ; Kopa, Miloš (advisor) ; Branda, Martin (referee)
This thesis deals with multi-stage stochastic programming in the context of random process representation. Basic structure for random process is a scenario tree. The thesis introduces general and stage-independent scenario tree and their properties. Scenario trees can be also combined with Markov chains which describe the state of the system and determine which scenario tree should be used. Another structure which enables reduce the complexity of the problem is a scenario lattice. Scenario generation is performed using moment method. Scenario trees are used for representation of random returns as the input to the investment problem.
|
|
|
Mixing of Markov chains - lower bounds for mixing
Ditrich, Jakub ; Prokešová, Michaela (advisor) ; Swart, Jan (referee)
The focus of the thesis is the convergence of irreducible aperiodic homoge- neous Markov chains with a finite and discrete set of states. Specifically, lower bounds on the time needed for the chain's marginal probability distribution to be sufficiently close to the stationary distribution, so called mixing time. Multiple methods are introdu- ced, properly motivated and proven. Finally, each method is demonstrated on a suitable example. The result is an overview of three methods that can be used to derive lower bounds for mixing time. 1
|
|
| |
|
|
Runs and Randomness
Zdeněk, Pavel ; Čoupek, Petr (advisor) ; Antoch, Jaromír (referee)
In this thesis probability distribution of five random variables related to success runs in a sequence of Bernoulli trials was found. The techinque of imbedding random sequences into Markov chains is used and improved compared to existing results. For every run a Markov chain was constructed, the definiton of imbedding was verified, a method for computation of its distribution was stated and examples of distribution were computed. 1
|
|
|
Scenario structures in multistage stochastic programs
Harcek, Milan ; Kopa, Miloš (advisor) ; Branda, Martin (referee)
This thesis deals with multi-stage stochastic programming in the context of random process representation. Basic structure for random process is a scenario tree. The thesis introduces general and stage-independent scenario tree and their properties. Scenario trees combined with Markov chains are also introduced. Markov chains states determine if there is a crisis period or not. Information about historical number of crises helps us to construct a scenario lattice. Scenario generation is performed using moment method. Scenario trees are used as an input to the investment problem.
|
|
|
The Stigler-Luckock model for a limit order book
Fornůsková, Monika ; Swart, Jan (advisor) ; Večeř, Jan (referee)
THE STIGLER-LUCKOCK MODEL FOR A LIMIT ORDER BOOK Abstract One of the types of modern-day markets are so-called order-driven markets whose core component is a database of all incoming buy and sell orders (order book). The main goal of this thesis is to extend the Stigler-Luckock model for order books to give a better insight into the price forming process and behaviour of the market participants themselves. The model introduced in this thesis focuses on a comparison of behaviour and various strategies of market makers who are sophisticated market participants profiting from extensive trading. The market is described using Markov chains, and the strategies are compared using Monte Carlo simulations and game theory. The results showed that market makers' orders should have small spread and large volumes. The final model compares two strategies in which market makers monitor their portfolio. In case of having more cash than asset (or vice versa), they shift prices of their orders to equalise the portfolio. The model recommends checking the market quite often, but acting conservatively, which means not changing prices that frequently and not jumping to conclusions just from a small imbalance in the portfolio.
|
guest ::
