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 -