Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T17:29:52.307Z Has data issue: false hasContentIssue false
  • English
  • Français

On spatial matchings: The first-in-first-match case

Part of: Geometric probability and stochastic geometry

Published online by Cambridge University Press:  08 October 2021

Mayank Manjrekar
Mayank Manjrekar*
Affiliation:
University of Texas at Austin
*
*Postal address: University of Texas at Austin, Austin, TX 78712. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe a process where two types of particles, marked red and blue, arrive in a domain at a constant rate. When a new particle arrives into the domain, if there are particles of the opposite color present within a distance of 1 from the new particle, then, among these particles, it matches to the one with the earliest arrival time, and both particles are removed. Otherwise, the particle is simply added to the system. Additionally, particles may lose patience and depart at a constant rate. We study the existence of a stationary regime for this process, when the domain is either a compact space or a Euclidean space. In the compact setting, we give a product-form characterization of the stationary distribution, and then prove an FKG-type inequality that establishes certain clustering properties of the particles in the steady state.

Keywords

Stochastic processesFCFS matchingFKG inequalityspatial clustering

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Type
Original Article
Information
Advances in Applied Probability , Volume 53 , Issue 3 , September 2021 , pp. 757 - 800
Check for updates
Copyright
© The Author(s) 2021. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adan, I., Bušić, A., Mairesse, J. and Weiss, G. (2018). Reversibility and further properties of FCFS infinite bipartite matching. Math. Operat. Res. 43, 598–621.10.1287/moor.2017.0874CrossRefGoogle Scholar
Adan, I. and Weiss, G. (2012). Exact FCFS matching rates for two infinite multitype sequences. Operat. Res. 60, 475–489.CrossRefGoogle Scholar
Asmussen, S. (2003). Applied Probability and Queues. Springer, New York.Google Scholar
Baccelli, F., Mathieu, F. and Norros, I. (2017). Mutual service processes in Euclidean spaces: existence and ergodicity. Queueing Systems 86, 95–140.CrossRefGoogle Scholar
Błaszczyszyn, B. and Yogeshwaran, D. (2014). On comparison of clustering properties of point processes. Adv. Appl. Prob. 46, 1–20.CrossRefGoogle Scholar
Büke, B. and Chen, H. (2017). Fluid and diffusion approximations of probabilistic matching systems. Queueing Systems 86, 1–33.10.1007/s11134-017-9516-3CrossRefGoogle Scholar
Bušić, A., Gupta, V. and Mairesse, J. (2013). Stability of the bipartite matching model. Adv. Appl. Prob. 45, 351–378.CrossRefGoogle Scholar
Caldentey, R., Kaplan, E. H. and Weiss, G. (2009). FCFS infinite bipartite matching of servers and customers. Adv. Appl. Prob. 41, 695–730.CrossRefGoogle Scholar
Chayes, J., Chayes, L. and Kotecky, R. (1995). The analysis of the Widom–Rowlinson model by stochastic geometric methods. Commun. Math. Phys. 172, 551–569.CrossRefGoogle Scholar
Daley, D. J. and Vere-Jones, D. (2007). An Introduction to the Theory of Point Processes, Volume II: General Theory and Structure. Springer, New York.Google Scholar
Engel, K.-J. and Nagel, R. (1999). One-Parameter Semigroups for Linear Evolution Equations. Springer, New York.Google Scholar
Georgii, H.-O. and Küneth, T. (1997). Stochastic comparison of point random fields. J. Appl. Prob. 34, 868–881.10.2307/3215003CrossRefGoogle Scholar
Giacomin, G., Lebowitz, J. and Maes, C. (1995). Agreement percolation and phase coexistence in some Gibbs systems. J. Statist. Phys. 80, 1379–1403.CrossRefGoogle Scholar
Holley, R. (1974). Remarks on the FKG inequalities. Commun. Math. Phys. 36, 227–231.CrossRefGoogle Scholar
Kashyap, B. R. (1966). The double-ended queue with bulk service and limited waiting space. Operat. Res. 14, 822–834.CrossRefGoogle Scholar
Kelly, F. P. (2011). Reversibility and Stochastic Networks. Cambridge University Press.Google Scholar
Kurtz, T. G. (1980). Representations of Markov processes as multiparameter time changes. Ann. Prob. 8, 682–715.CrossRefGoogle Scholar
Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge University Press.CrossRefGoogle Scholar
Ruelle, D. (1971). Existence of a phase transition in a continuous classical system. Phys. Rev. Lett. 27, 1040.CrossRefGoogle Scholar
Thorisson, H. (2000). Coupling, Stationarity, and Regeneration. Springer, New York.CrossRefGoogle Scholar
Widom, B. and Rowlinson, J. S. (1970). New model for the study of liquid–vapor phase transitions. J. Chem. Phys. 52, 1670–1684.CrossRefGoogle Scholar