Analysis of Randomized Algorithms: Markov Chain Approach

本研究的目的是建立理论计算机科学的一个重要领域的理论研究方法，即随机算法的分析。主要关注的是可以用马尔可夫链建模或可以用马尔可夫链方法分析的问题。该项目集中在三个主要主题：(1)离散时间马尔可夫链和蒙特卡洛马尔可夫链方法的一般分析，(2)马尔可夫链生成随机排列的分析，以及(3)分布式系统中的资源分配问题。在马尔可夫链的一般分析领域，研究的目标是开发新的分析马尔可夫链混合次数的工具。本研究的一个重要部分是探讨各种已知的马尔可夫链混合时间分析方法之间的关系。在马尔可夫链产生随机排列的研究中，主要关注的是所谓的随机交换网络。这些网络模拟了许多在密码学应用中所寻求的马尔可夫链的行为。在分布式系统中的资源分配问题方面，研究主要集中在网络中的资源分配问题，其中资源分配的代价取决于输入网络的路由属性以及系统所采用的冲突解决协议。

The objective of this research is to establish methods for theoretical study in an important area of theoretical computer science, which isthe analysis of randomized algorithms. The main focus is on problemsthat either can be modeled by Markov chains or can be analyzed usingthe Markov chain approach.This project concentrates on three main topics: (1) general analysisof discrete-time Markov chains and the Monte Carlo Markov Chainmethod, (2) analysis of Markov chains for generating randompermutations, and (3) resource allocation problems in distributedsystems.In the area of general analysis of Markov chains the goal of theresearch is to develop new tools for the analysis of mixing times ofMarkov chains. An important part of this study is to investigaterelationships between various known methods of the analysis of mixingtimes of Markov chains.In the investigations of Markov chains for generating randompermutations the main focus is on so called random switchingnetworks. These networks model behavior of many Markov chains thatare sought in applications in cryptography.In the area of resource allocation problems in distributed systems,the research focuses mostly on resource allocation problems innetworks, in which the cost of the allocation depend on the routingproperties of the input network as well as on the contentionresolution protocols applied to the system.