Martingalne tehnike i vremena miješanja Markovljevih lanaca

Na početku ovog rada dajemo kratak uvod u teoriju Markovljevih lanaca na konačnom prostoru stanja. Glavni rezultat je da ireducibilan Markovljev lanac na konačnom prostoru stanja ima jedinstvenu stacionarnu distribuciju, te da uz dodatni zahtjev aperiodičnosti, distribucija lanca konvergira prema stacionarnoj distribuciji. Zanima nas brzina te konvergencije. Ključni pojmovi za njeno kvantificiranje su udaljenost potpune varijacije i vrijeme miješanja Markovljevog lanca. Središnji pojam ovog rada je proces evoluirajućih skupova koji pridružujemo svakom Markovljevom lancu. To je Markovljev lanac na podskupovima stanja originalnog lanca, sa jednostavnim prijelaznim pravilom koje povećava ili smanjuje trenutno stanje (skup). Pokazujemo osnovna svojstva tog procesa, vezu sa vremenima miješanja originalnog lanca, te definiramo Doobovu transformaciju evoluirajućih skupova. U ostatku radu koristimo evoluirajuće skupove i martingalne tehnike u rješavanju problema vezanih uz miješanje Markovljevih lanaca. Najprije se upoznajemo sa standardnom tehnikom ograničavanja vremena miješanja Markovljevih lanaca koja koristi jako stacionarna vremena. Sparivanjem Markovljevog lanca i pripadne Doobove transformacije evoluirajućih skupova, konstruiramo jako stacionarno vrijeme za originalni lanac. Nadalje, koristeći evoluirajuće skupove, poboljšavamo dosada poznate ograde na vremena miješanja Markovljevog lanca u terminima radijusa toka (engl. conductance) podskupova pripadnog prostora stanja. Ključan pojam tog dijela je funkcija radijusa toka, koja je direktna generalizacija omjera uskog grla. Na kraju, definiramo jednostavnu slučajnu šetnju na grafu, te uz pomoć evoluirajućih skupova dajemo ogradu na povratne vjerojatnosti slučajne šetnje u terminima maksimalnog stupnja pripadnog grafa.In the beginning of this paper, we give a short introduction into theory of finite Markov chains. The key result is that every irreducible and finite Markov chain has a unique stationary distribution, and in the case when the chain is aperiodic, the distribution of the chain converges to its stationary distribution. The goal is to determine the rate of that convergence. We define total variation distance and mixing time of a Markov chain, the key tools for quantifying that convergence. Given a Markov chain, we define the evolving set process, a Markov chain whose states are subsets of the state space of the original chain. The transition rule of that process is a simple procedure which grows or shrinks the current state. We show the basic properties of the evolving set process, the connection with mixing time of the original chain, and define the Doob transform of the evolving sets. In the rest of the paper, we present some applications of the evolving set process using martingale techniques. At first, we introduce a standard technique for bounding mixing time of a Markov chain which uses strong stationary times. Then we construct one such time by coupling a Markov chain and the Doob transform of the evolving set process. Next, we use the evolving set process to give sharp bounds on mixing time of Markov chains in terms of conductance. An extension of the bottleneck ratio, the conductance function of a Markov chain, is key to this part. In the end, we define a simple random walk on a graph, and use evolving sets to bound the return probabilities of the random walk in terms of maximum degree of the underlying grap