Exact FCFS matching rates for two infinite multi-type sequences

I.J.B.F. Adan, G. Weiss

Research output: Book/ReportReportAcademic

290 Downloads (Pure)


We consider an infinite sequence of items of types C = {c_1, ..., c_I}, and another infinite sequence of items of types S = {s_1, ... , s_J}, and a bipartite graph G of allowable matches between the types. Matching the two sequences on a first come first served basis defines a unique infinite matching between the sequences. For (c_i, s_j) in G we 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. We assume that the types of items in the two sequences are i.i.d. with given probability vectors a, ß. We describe this system by a Markov chain, obtain conditions for ergodicity, and derive its stationary distribution which is of product form. We show that if the chain is ergodic, then the matching rates exist almost surely, and give a closed form formula to calculate them.
Original languageEnglish
Place of PublicationEindhoven
Number of pages18
Publication statusPublished - 2010

Publication series

NameReport Eurandom
ISSN (Print)1389-2355


Dive into the research topics of 'Exact FCFS matching rates for two infinite multi-type sequences'. Together they form a unique fingerprint.

Cite this