Exact FCFS matching rates for two infinite multi-type sequences

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

Onderzoeksoutput: Boek/rapportRapportAcademic

174 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.
Originele taal-2Engels
Plaats van productieEindhoven
Aantal pagina's18
StatusGepubliceerd - 2010

Publicatie series

NaamReport Eurandom
ISSN van geprinte versie1389-2355

Vingerafdruk Duik in de onderzoeksthema's van 'Exact FCFS matching rates for two infinite multi-type sequences'. Samen vormen ze een unieke vingerafdruk.

Citeer dit