Speaker
Description
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. In particular, finding the steady state probability distribution requires computing the minimal nonnegative solution of the quadratic matrix equation $A_1X^2+A_0X+A_{-1}=X$, where the coefficients $A_i$, $i=-1,0,1$, are semi-infinite nonnegative matrices, which are Toeplitz except for a low-rank correction.
We introduce the sets $\mathcal{QT}^d$ and $\mathcal{EQT}$ of semi-infinite matrices with bounded infinity norm [2]. The former is made by matrices representable as a sum of a Toeplitz matrix and a compact correction with columns having entries which decay to zero. The latter is formed by matrices in $\mathcal{QT}^d$ plus a further correction of the kind $ev^T$ for $e^T=(1,1,\ldots)$ and $v=(v_i)_{i\in Z^+}$ such that $\sum_{i=1}^\infty |v_i|<\infty$. We prove that $\mathcal{QT}^d$ and $\mathcal{EQT}$ are Banach algebras, i.e., they are Banach spaces with the infinity norm, closed under matrix multiplication. Moreover, we provide mild conditions under which the minimal nonnegative solution belongs either to $\mathcal{QT}^d$ or to $\mathcal{EQT}$.
These new classes allow to treat random walks with reset, which model queueing systems with breakdowns or restarts. These models cannot be handled by relying on the currently available Banach algebras [1]. Moreover, matrices in both classes can be approximated up to any precision by a finite number of parameters. This allows to introduce a matrix arithmetic and to extend the cqt-toolbox of [3], so that numerical algorithms valid for finite matrices can be applied to solve the quadratic matrix equation. The convergence of various fixed point iterations is analyzed [4].
[1] Bini, D.A., Massei, S., Meini, B.: Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes. Math. Comp. 87(314), 2811-2830 (2018)
[2] Bini, D.A., Massei, S., Meini, B., Robol, L.: A computational framework for two-dimensional random walks with restarts. Submitted for publication. arXiv:1909.11372v1. (2019)
[3] Bini, D.A., Massei, S., Robol, L.: Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox. Numer. Algorithms 81(2), 741-769 (2019)
[4] Bini, D.A., Meini, B., Meng, J.: Solving quadratic matrix equations arising in random walks in the quarter plane. Submitted for publication. arXiv:1907.09796 (2019)
