University of Twente Student Theses
Need for convergence speed : how do graph metrics influence the convergence speed of Markov chains?
Doychev, K. (2023) Need for convergence speed : how do graph metrics influence the convergence speed of Markov chains?
|
PDF
392kB |
| Abstract: | Markov chains are systems that can describe the probabilities of going from one state to another. Usually, they are drawn using graphs or transition matrices. Markov chains have realworld applications that can help us predict the future based on recent data. Forecast predictions [6] and Google search results [3] are a few examples of where Markov chains are being used. It has been researched how to converge Markov chains [1, 2] but there has not been any research on how graph metrics influence the convergence speed of Markov chains. DiscreteTime Markov Chains (DTMC) models are probabilistic systems, that eventually converge to an equilibrium state. The convergence speed measures how long it takes to reach this equilibrium. This is an important parameter because it also plays a role in the robustness of a system: if the convergence is fast, then the system will return to equilibrium quickly. To conduct this research I will try to find and analyse realworld examples of DTMC. I will look at these matrices to try and generate matrices that are similar enough to real-world data. I need to generate some data because I was not able to find a lot of publicly available Markov chains and I needed a larger dataset to work with. For all of these matrices, I need to identify and extract important metrics that could influence the convergence speed. Finally, I will use Pearson Correlation Coefficient (PCC) analysis to identify the correlation between the convergence time and the different metrics. I will first explain some definitions and ground truths about the Markov chains. Then, I will go through the data collection/generation for the experiment. Finally, I will explain what conclusions I was able to make based on my experiments. I found out that the graph metrics with the largest correlation were the diameter, the radius, and the Second-Largest Eigenvalue (SLE). Surprisingly, graph size turned out to play no role in the convergence speed. Overall, this study suggests that the number of states of a Markov chain is not important for its convergence speed, a more important metric to take into account is the longest hop count between any two states and the SLE. As we will see, this study suggests that some graph-theoretic metrics can have a strong influence on the convergence speed and some do not. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 30 exact sciences in general, 31 mathematics, 54 computer science |
| Programme: | Computer Science BSc (56964) |
| Link to this item: | https://purl.utwente.nl/essays/94341 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page