Exact FCFS matching rates for two infinite multitype sequences (Q2917639)

The paper under review studies two infinite sequences of items. The first of them is characterized by the types \(\{c_1, c_2, \dots, c_I\}\), and the second one by the types \(\{s_1, s_2, \dots, s_J\}\). In addition to these types, there is a bivariate graph \(G\) of allowance matches between the types. The types of items in the two sequences are assumed to be independently and identically distributed with given probability vectors \(\alpha\) and \(\beta\). Matchings of two sequences are on the first-come, first-served basis, and they define a unique infinite matching between two sequences. For each pair \((c_i,s_j)\in G\) the authors define the matching rate \(r_{c_i,s_j}\) as the long-term fraction of \((c_i,s_j)\) matches in the infinite matching, if it exists. They describe a multi-dimensional Markov chain for this system, obtain conditions for ergodicity, and derive its stationary distribution. The last stationary distribution is expressed in product form. It is proved that if the chain is ergodic, then the matching rates exist almost surely. The paper gives a closed form formula for its calculation. The connection of this model to some queueing systems is shown.