Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider exploration algorithms of the random sequential adsorption type both for homogeneous random graphs and random geometric graphs based on spatial Poisson processes. At each step, a vertex of the graph becomes active and its neighboring nodes become blocked. Given an initial number of vertices N growing to infinity, we study statistical properties of the proportion of explored (active or blocked) nodes in time using scaling limits. We obtain exact limits for homogeneous graphs and prove an explicit central limit theorem for the final proportion of active nodes, known as the jamming constant, through a diffusion approximation for the exploration process which can be described as a unidimensional process. We then focus on bounding the trajectories of such exploration processes on random geometric graphs, i.e., random sequential adsorption. As opposed to exploration processes on homogeneous random graphs, these do not allow for such a dimensional reduction. Instead we derive a fundamental relationship between the number of explored nodes and the discovered volume in the spatial process, and we obtain generic bounds for the fluid limit and jamming constant: bounds that are independent of the dimension of space and the detailed shape of the volume associated to the discovered node. Lastly, using coupling techinques, we give trajectorial interpretations of the generic bounds. © 2017, Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:Scaling Limits and Generic Bounds for Exploration Processes
Autor:Bermolen, P.; Jonckheere, M.; Sanders, J.
Filiación:IMERL, Facultad de Ingeniería, Universidad de la República, Montevideo, Uruguay
Instituto de Cálculo, Universidad de Buenos Aires and Conicet, Buenos Aires, Argentina
KTH Royal Institute of Technology, Stockholm, Sweden
Palabras clave:Random graphs; Random sequential adsorption; Scaling limits
Año:2017
Volumen:169
Número:5
Página de inicio:989
Página de fin:1018
DOI: http://dx.doi.org/10.1007/s10955-017-1902-z
Título revista:Journal of Statistical Physics
Título revista abreviado:J. Stat. Phys.
ISSN:00224715
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224715_v169_n5_p989_Bermolen

Referencias:

  • Sanders, J., Jonckheere, M., Kokkelmans, S., Sub-Poissonian statistics of jamming limits in ultracold Rydberg gases (2015) Phys. Rev. Lett., 115, p. 043002
  • Bermolen, P., Jonckheere, M., Moyal, P., The jamming constant of uniform random graphs (2016) Stoch. Proces. Appl., 127, pp. 2138-2178
  • Evans, J.W., Random and cooperative sequential adsorption (1993) Rev. Mod. Phys., 65, pp. 1281-1329
  • Bermolen, P., Jonckheere, M., Larroca, F., Moyal, P., Estimating the transmission probability in wireless networks with configuration models (2016) ACM Trans. Model. Perform. Eval. Comput. Syst., 1 (2), pp. 9:1-9:23
  • Gallagher, T.F., (1994) Rydberg Atoms (Cambridge Monographs on Atomic, Molecular and Chemical Physics), , Cambridge University Press, Cambridge
  • Darling, R., Norris, J., Differential equation approximations for Markov chains (2008) Probab. Surv., 5, pp. 37-79
  • Berkes, I., Liu, W., Wu, W.B., Komlós-Major-Tusnády approximation under dependence (2014) Ann. Probab., 42 (2), pp. 794-817
  • Sanders, J., (2016) Stochastic optimization of large-scale complex systems, , Ph.D. thesis, Technische Universiteit Eindhoven
  • Bermolen, P., Jonckheere, M., Sanders, J., Scaling limits for exploration algorithms (2015) Technical Report
  • Erdös, P., Rényi, A., On random graphs, I (1959) Publ. Math. (Debrecen), 6, pp. 290-297
  • Grimmett, G., Stirzaker, D., (2001) Probability and Random Processes, , Oxford University Press, Oxford
  • Steele, J.M., (2001) Stochastic Calculus and Financial Applications, , Springer, New York
  • Aiello, W., Graham, F.C., Lu, L., A random graph model for power law graphs (2001) Exp. Math., 10, pp. 53-66
  • Chung, F., Lu, L., Connected components in random graphs with given expected degree sequences (2002) Ann. Comb., 6 (2), pp. 125-145
  • Chung, F., Lu, L., The average distance in a random graph with given expected degrees (2004) Internet Math., 1 (1), pp. 91-113
  • Dhara, S., van Leeuwaarden, J.S.H., Mukherjee, D., Generalized random sequential adsorption on Erdös–Rényi random graphs (2016) J. Stat. Phys., 164 (5), pp. 1217-1232
  • Dhara, S., van Leeuwaarden, J., Mukherjee, D., (2016) Solvable random network model for disordered sphere packing. arXiv, 1611, p. 05019
  • Kurtz, T.G., Strong approximation theorems for density dependent Markov chains (1978) Stoch. Proces. Appl., 6 (3), pp. 223-240
  • Komlós, J., Major, P., Tusnády, G., An approximation of partial sums of independent rv’-s, and the sample df. i (1975) Z. Wahrscheinlichkeitstheor. Verw. Geb., 32 (1-2), pp. 111-131
  • Komlós, J., Major, P., Tusnády, G., An approximation of partial sums of independent rv’s, and the sample df. ii (1976) Z. Wahrscheinlichkeitstheor. Verw. Geb., 34 (1), pp. 33-58
  • McDiarmid, C., Colouring random graphs (1984) Ann. Oper. Res., 1 (3), pp. 183-200
  • Teerapabolaan, K., A bound on the binomial-Poisson relative error (2013) Int. J. Pure Appl. Math., 87 (4), pp. 535-540
  • Penrose, M.D., Yukich, J., Limit theory for random sequential packing and deposition (2002) Ann. Appl. Probab., 12 (1), pp. 272-301
  • Penrose, M.D., Random parking, sequential adsorption, and the jamming limit (2001) Commun. Math. Phys., 218 (1), pp. 153-176
  • Penrose, M.D., (2003) Random geometric graphs, , 5, Oxford University Press, Oxford
  • Rudin, W., (1987) Real and Complex Analysis, , Tata McGraw-Hill, New York

Citas:

---------- APA ----------
Bermolen, P., Jonckheere, M. & Sanders, J. (2017) . Scaling Limits and Generic Bounds for Exploration Processes. Journal of Statistical Physics, 169(5), 989-1018.
http://dx.doi.org/10.1007/s10955-017-1902-z
---------- CHICAGO ----------
Bermolen, P., Jonckheere, M., Sanders, J. "Scaling Limits and Generic Bounds for Exploration Processes" . Journal of Statistical Physics 169, no. 5 (2017) : 989-1018.
http://dx.doi.org/10.1007/s10955-017-1902-z
---------- MLA ----------
Bermolen, P., Jonckheere, M., Sanders, J. "Scaling Limits and Generic Bounds for Exploration Processes" . Journal of Statistical Physics, vol. 169, no. 5, 2017, pp. 989-1018.
http://dx.doi.org/10.1007/s10955-017-1902-z
---------- VANCOUVER ----------
Bermolen, P., Jonckheere, M., Sanders, J. Scaling Limits and Generic Bounds for Exploration Processes. J. Stat. Phys. 2017;169(5):989-1018.
http://dx.doi.org/10.1007/s10955-017-1902-z