TY - BOOK
T1 - Exact FCFS matching rates for two infinite multi-type sequences
AU - Adan, I.J.B.F.
AU - Weiss, G.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
M3 - Report
T3 - Report Eurandom
BT - Exact FCFS matching rates for two infinite multi-type sequences
PB - Eurandom
CY - Eindhoven
ER -