Hide metadata

dc.contributor.authorYang, Yang Kjeldsen
dc.date.accessioned2015-09-01T22:01:40Z
dc.date.available2015-09-01T22:01:40Z
dc.date.issued2015
dc.identifier.citationYang, Yang Kjeldsen. Numerical Methods for Solving the Fastest Mixing Markov Chain Problem. Master thesis, University of Oslo, 2015
dc.identifier.urihttp://hdl.handle.net/10852/45372
dc.description.abstractConsider a random walk on an undirected, connected graph. On each edge we can set a transition probability to connect two adjacent vertices. The mixing rate of the associated Markov chain to the uniform equilib- rium distribution is determined by the second largest eigenvalue in modulus (SLEM) of the transition probability matrix. This problem is called the fastest mixing Markov chain problem (FMMC). This thesis will cover numerical methods for solving the FMMC problem. We will compare different methods for solving the problem, including the subgradient method and primal-dual interior-point methods. We will pro- vide a complexity analysis of implentation of the methods, and make a com- parison with the convex optimization solver CVXOPT written by Andersen, Dahl, and Vandenberghe. Finally, we will also look at small applications of the problem in shuffling.eng
dc.language.isoeng
dc.subjectfast
dc.subjectmixing
dc.subjectmarkov
dc.subjectchain
dc.subjectconvergence
dc.subjectgraph
dc.titleNumerical Methods for Solving the Fastest Mixing Markov Chain Problemeng
dc.typeMaster thesis
dc.date.updated2015-09-01T22:01:40Z
dc.creator.authorYang, Yang Kjeldsen
dc.identifier.urnURN:NBN:no-49587
dc.type.documentMasteroppgave
dc.identifier.fulltextFulltext https://www.duo.uio.no/bitstream/handle/10852/45372/7/yangthesis2.pdf


Files in this item

Appears in the following Collection

Hide metadata