University of Twente Student Theses
Red-Light-Green-Light algorithm with MaxC heuristic for solving Markov chains
Ottens, Iris (2022) Red-Light-Green-Light algorithm with MaxC heuristic for solving Markov chains.
|
PDF
1MB |
| Abstract: | Markov chains are versatile mathematical models which can represent stochastic processes from many different fields. A common task when using Markov chains is the computation of the stationary distribution. A new and fast algorithm that can be used to calculate this stationary distribution is the Red-Light-Green- Light(RLGL) algorithm. To give a brief summary of the algorithm: first each state receives a certain amount of cash, which can be positive or negative, and at each iteration a subset of all states receive 'green light' after which these states distribute all their cash proportional to the transition probabilities of the Markov chain. The stationary distribution can then be found to be proportional to the total cash distributed by each state. Green light can be given in many different ways and choosing the correct way can lead to faster convergence. Finding the optimal green light sequence can, however, be very challenging. It is therefore better to look at heuristics for giving green light. The MaxC heuristic and the MaxCMinC heuristics are such heuristics. The MaxC heuristic gives green light to the states that have the absolute maximum amount of cash and the MaxCMinC heuristic gives green light to both the states with the maximal positive and those with the maximum negative amount of cash. For both of these heuristics we have proven exponential convergence for certain types of Markov chains and estimated their convergence rate. It is shown that, in practice, the heuristics often outperform their theoretical bounds, as well as methods of how these bounds can be made more precise. |
| Item Type: | Essay (Master) |
| Clients: | Unknown organization, En |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/89541 |
| 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