The treatment of two-dimensional random walks in the quarter plane leads to Markov processes which involve semi-infinite matrices having Toeplitz or block Toeplitz structure plus a low-rank correction. We propose an extension of the framework introduced in [D. A. Bini, S. Massei, and B. Meini, Math. Comp., 87 (2018), pp. 2811-2830] which allows us to deal with more general situations such as processes involving restart events. This is motivated by the need for modeling processes that can incur in unexpected failures like computer system reboots. We present a theoretical analysis of an enriched Banach algebra that, combined with appropriate algorithms, enables the numerical treatment of these problems. The results are applied to the solution of bidimensional quasi-birth-death processes with infinitely many phases which model random walks in the quarter plane, relying on the matrix analytic approach. The reliability of our approach is confirmed by extensive numerical experimentation on several case studies.

A computational framework for two-dimensional random walks with restarts

Bini D. A.
;
Massei S.;Meini B.;Robol L.
2020

Abstract

The treatment of two-dimensional random walks in the quarter plane leads to Markov processes which involve semi-infinite matrices having Toeplitz or block Toeplitz structure plus a low-rank correction. We propose an extension of the framework introduced in [D. A. Bini, S. Massei, and B. Meini, Math. Comp., 87 (2018), pp. 2811-2830] which allows us to deal with more general situations such as processes involving restart events. This is motivated by the need for modeling processes that can incur in unexpected failures like computer system reboots. We present a theoretical analysis of an enriched Banach algebra that, combined with appropriate algorithms, enables the numerical treatment of these problems. The results are applied to the solution of bidimensional quasi-birth-death processes with infinitely many phases which model random walks in the quarter plane, relying on the matrix analytic approach. The reliability of our approach is confirmed by extensive numerical experimentation on several case studies.
Bini, D. A.; Massei, S.; Meini, B.; Robol, L.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1055668
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact