Extensions of Riordan matrices and Applications to Queueing models

다국어 초록 (Multilingual Abstract)

In this dissertation, we study structural properties of Riordan matrices by using the concept of the A-sequence and its generalizations. We propose various extensions of Riordan matrices to the extended Riordan matrix, the 3-dimensional Riordan array and the generalized Riordan array, respectively.

First we observe the basic properties of a Riordan matrix and several well-known extensions of Riordan matrices. These are devoted to the structural property of Riordan matrices and extended Riordan matrices. We consider an infinite lower triangular matrix $L=[\ell_{n,k}]_{n,k\in\mathrm{\mathbf{N_{0}}}}$ and a sequence $\Omega=(\omega_n)_{n\in\mathrm{\mathbf{N_{0}}}}$ called the (a,b)-sequence such that every element $\ell_{n+1,k+1}$ except for column 0 can be expressed as
$$
\ell_{n+1,k+1}=\sum_{i=0}^{\lfloor{(n-k)/m}\rfloor}\omega_{i}\ell_{n-ai,k+bi},\quad \omega_0\ne0
$$
where a and b are integers with a+b=m>0 and $b\ge0$. This concept generalizes the A-sequence of a Riordan matrix. As a result, we explore several structural properties of Riordan matrices by means of (a,b)-sequences. Further, we examine an equivalence relation on the set of formal power series with nonzero constant term. This is done both in terms of functional equations and also by interlacing two concepts from Riordan group theory, the A-sequence and the Bell subgroup. A power series for one member of an equivalence class can be transformed into a power series for the rest of members in the equivalence class, and interpretations in terms of weighted lattice paths can also be given. On the other hand, the concept of an (a,b)-sequence for b<0 provides an extended Riordan matrix defined on the ring of Laurent series over the complex field.

The main concept is a development of 3-dimensional Riordan array. The set of 3-D Riordan arrays forms a group under the 3-D matrix multiplication. We discuss the group extension problem. Specifically we prove that the d-dimensional Riordan group is isomorphic to the group obtained as semidirect product of d-1 $\mathcal{F}_0$s and $\mathcal{F}_1$. We propose some applications of 3-Riordan arrays to the 3-dimensional lattice path counting problems.

Further, we introduce how the Riordan array method can be applied to the transient analysis of an M/M/1 queue starting with zero customers. We then extend this method to the generalized Riordan array with multiple support functions in order to deal with the transient analysis of an M/M/1 queue starting with any number of customers. We also study the transient analysis of an M/M/c queue by means of the column generating functions of the generalized Riordan array. It turns out that the generalized Riordan array, transition probability matrix and the orthogonal polynomials are closely tied to each other in the case of an M/M/c queueing model starting with zero customers. Numerical examples are also given to show how easily the transient probabilities obtained from the generalized Riordan array method can be computed.

목차 (Table of Contents)

• Chapter I : Introduction 1
• Chapter II : Extended Riordan matrices 8
• 1 Structural properties of Riordan matrices 8
• 1.1 The ray sequences and the diagonal sums 8
• 1.2 Equivalence relation on the formal power series 16
• 1.3 Unified combinatorial interpretation for the equivalence class 25
• 2 Extending the Riordan matrices to the ring of Laurent series 29
• 2.1 Extended Riordan matrices 29
• 2.2 Applications to the combinatorial identity 34
• Chapter III : Multi-dimensional Riordan arrays 37
• 1 3-D Riordan arrays and the group structure 37
• 2 Group extension problems 41
• 3 Lattice path counting problem on Z3 45
• Chapter IV : Applications of Riordan arrays to queueing models 48
• 1 Transient analysis of M/M/1 queueing model 48
• 1.1 Transient analysis of M/M/1 queue starting with zero customers 48
• 1.2 Transient analysis of M/M/1 queue starting with h customers 56
• 2 Transient analysis of M/M/c queueing model 60
• 2.1 Transient analysis of M/M/c queue starting with zero customers 61
• 2.2 Transient analysis of M/M/c queue starting with h customers 70
• 3 Numerical examples for several queueing models 78
• Reference 86
• Appendix 90
• 1 PHP codes generating the Riordan matrices, Online Program 90
• 2 Mathematica code for the transient solution of M/M/1 queue 94