Detecting Markov chain instability: a Monte Carlo approach

DOI10.1287/STSY.2017.0003zbMATH Open1390.60332arXiv1608.03257OpenAlexW2493949634MaRDI QIDQ1704952FDOQ1704952

Authors: M. R. H. Mandjes, Neil Walton, Brendan Patch 

Publication date: 14 March 2018

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: We devise a Monte Carlo based method for detecting whether a non-negative Markov chain is stable for a given set of parameter values. More precisely, for a given subset of the parameter space, we develop an algorithm that is capable of deciding whether the set has a subset of positive Lebesgue measure for which the Markov chain is unstable. The approach is based on a variant of simulated annealing, and consequently only mild assumptions are needed to obtain performance guarantees. The theoretical underpinnings of our algorithm are based on a result stating that the stability of a set of parameters can be phrased in terms of the stability of a single Markov chain that searches the set for unstable parameters. Our framework leads to a procedure that is capable of performing statistically rigorous tests for instability, which has been extensively tested using several examples of standard and non-standard queueing networks.

Full work available at URL: https://arxiv.org/abs/1608.03257

Recommendations

• Stopping tests for Markov chain Monte-Carlo methods
• Tests for the Nonergodicity of Multidimensional Markov Chains
• scientific article; zbMATH DE number 3886848
• Monte Carlo and Markov Chain techniques for network reliability and sampling
• Stability of adversarial Markov chains, with an application to adaptive MCMC algorithms

zbMATH Keywords

stabilityMarkov chainsstochastic networksqueueing networksMonte Carlo algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Optimization by simulated annealing
• Markov chains and stochastic stability
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Title not available (Why is that?)
• Probability with Martingales
• Open, Closed, and Mixed Networks of Queues with Different Classes of Customers
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Dynamic server allocation to parallel queues with randomly varying connectivity
• Instability of FIFO queueing networks
• Stability of queueing networks
• Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems
• Networks of queues with customers of different types
• Queue-based random-access algorithms: fluid limits and stability issues
• A Numerical Approach to Stability of Multiclass Queueing Networks
• A Markov chain model of a polling system with parameter regeneration
• Window flow control in FIFO networks with cross traffic
• Asymptotic Stability Region of Slotted Aloha

Cited In (1)

• A survey of parameter and state estimation in queues

This page was built for publication: Detecting Markov chain instability: a Monte Carlo approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704952)