×

MATRIX-MFO tandem workshop: Stochastic reinforcement processes and graphs. Abstracts from the MATRIX-MFO tandem workshop held March 5–10, 2023. (English) Zbl 1525.00021

Summary: Stochastic processes with reinforcement are the central theme of the present tandem workshop. We assembled a diverse group of international experts that worked on reinforcement dynamics from several different perspectives. We discussed progress and future strategies around a number of key open problems in the area of interacting urns with graph based interaction, preferential attachment, and reinforced random walks.

MSC:

00B05 Collections of abstracts of lectures
00B25 Proceedings of conferences of miscellaneous specific interest
60-06 Proceedings, conferences, collections, etc. pertaining to probability theory
05-06 Proceedings, conferences, collections, etc. pertaining to combinatorics
05Cxx Graph theory
60Gxx Stochastic processes
60Jxx Markov processes
Full Text: DOI

References:

[1] D. Kious, C. Mailler, B. Schapira. Finding geodesics on graphs using reinforcement learning, Ann. Appl. Probab. 32, (2022), 3889-3929. · Zbl 1501.05029
[2] D. Kious, C. Mailler, B. Schapira. The trace-reinforced ants process does not find shortest paths, J.Éc. polytech. Math 9, (2022), 505-536. · Zbl 1485.60036
[3] D. Aldous and J.M. Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on discrete structures, volume 110 of Ency-clopaedia Math. Sci., pages 1-72. Springer, Berlin, 2004. · Zbl 1037.60008
[4] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. · Zbl 1226.05223
[5] I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13 pp. (electronic), 2001. · Zbl 1010.82021
[6] N. Berger, C. Borgs, J. Chayes, and A. Saberi. Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab., 42(1):1-40, 2014. · Zbl 1296.60010
[7] B. Bollobás and O. Riordan. Coupling scale-free and classical random graphs. Internet Math., 1(2):215-225, 2004. · Zbl 1061.05084
[8] B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The degree sequence of a scale-free random graph process. Random Structures Algorithms, 18(3):279-290, 2001. · Zbl 0985.05047
[9] A. C. Cooper, Frieze and J. Vera. Random deletion in a scale-free random graph process. Int. Math., 1:463-483, 2004. · Zbl 1080.60006
[10] F. Caravenna, A. Garavaglia, and R. van der Hofstad. Diameter in ultra-small scale-free random graphs. Random Structures Algorithms, 54(3):444-498, 2019. · Zbl 1414.05098
[11] F. Chung and L. Lu. Coupling online and offline analyses for random power law graphs. Internet Math., 1(4):409-461, 2004. · Zbl 1089.05021
[12] M. Deijfen. Random networks with preferential growth and vertex death. J. Appl. Probab., 47:1150-1163, 2010. · Zbl 1210.60096
[13] M. Deijfen, H. van den Esker, R. van der Hofstad, and G. Hooghiemstra. A preferential attachment model with random initial degrees. Ark. Mat., 47(1):41-72, 2009. · Zbl 1182.05107
[14] S. Dereich, C. Mönch, and P. Mörters. Typical distances in ultrasmall random networks. Adv. in Appl. Probab., 44(2):583-601, 2012. · Zbl 1244.05199
[15] S. Dereich and P. Mörters. Random networks with sublinear preferential attachment: Degree evolutions. Electronic Journal of Probability, 14:122-1267, 2009. · Zbl 1185.05127
[16] S. Dereich and P. Mörters. Random networks with concave preferential attachment rule. Jahresber. Dtsch. Math.-Ver., 113(1):21-40, 2011. · Zbl 1217.05206
[17] S. Dereich and P. Mörters. Random networks with sublinear preferential attachment: the giant component. Ann. Probab., 41(1):329-384, 2013. · Zbl 1260.05143
[18] S. Dommers, R. van der Hofstad, and G. Hooghiemstra. Diameters in preferential attachment graphs. Journ. Stat. Phys., 139:72-107, 2010. · Zbl 1191.82020
[19] Alessandro Garavaglia, Rajat Subhra Hazra, Remco van der Hofstad, and Rounak Ray. Universality of the local limit of preferential attachment models. arXiv preprint arXiv:2212.05551, 2022.
[20] R. van der Hofstad. Random graphs and complex networks. Volume 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2017. · Zbl 1361.05002
[21] R. van der Hofstad. Random graphs and complex networks. Vol. 2. In preparation, see http://www.win.tue.nl/∼rhofstad/NotesRGCNII.pdf, 2023.
[22] P. Jagers and O. Nerman. The growth and composition of branching populations. Adv. in Appl. Probab., 16(2):221-259, 1984. · Zbl 0535.60075
[23] T.Y.Y. Lo. Weak local limit of preferential attachment random trees with additive fitness. arXiv:2103.00900 [math.PR], 2021.
[24] T. F. Móri. The maximum degree of the Barabási-Albert random tree. Combin. Probab. Comput., 14(3):339-348, 2005. · Zbl 1078.05077
[25] A. Rudas, B. Tóth, and B. Valkó. Random trees and general branching processes. Random Structures Algorithms, 31(2):186-202, 2007. · Zbl 1144.60051
[26] S. Chatterjee and M. Harel, Localization in random geometric graphs with too many edges, Ann. Probab. 48(2) (2020), 574-621. · Zbl 1446.60024
[27] S. Dereich, Preferential attachment with fitness: unfolding the condensate, Electron. J. Probab. 21 (2016), 1-38. https://doi.org/10.1214/16-EJP3801 · Zbl 1338.05245 · doi:10.1214/16-EJP3801
[28] S. Dereich, C. Mailler, and P. Mörters. Nonextensive condensation in reinforced branching processes, Ann. Appl. Probab. 27(4) (2017), 2539-2568. · Zbl 1373.60146
[29] S. Großkinsky, G. M. Schütz, and H. Spohn , Condensation in the zero range process: stationary and dynamical properties, J. Stat. Phys. 113(3/4) (2003), 389-410. · Zbl 1081.82010
[30] R. van der Hofstad, P. van der Hoorn, C. Kerriou, N. Maitra, and P. Mörters, Condensation in scale-free geometric graphs with excess edges, forthcoming.
[31] C. Kerriou and P. Mörters, The fewest-big-jumps principle and an application to random graphs, arXiv:2206.14627.
[32] M. Benaïm, I. Benjamini, J. Chen, and Y. Lima. A generalized Pólya’s urn with graph based interactions. Random Struct. Alg., 46(4):614-634, (2015). · Zbl 1317.05103
[33] Y. Couzinié, and C. Hirsch. Weakly reinforced Polya urns on countable networks. Electron. Commun. Probab. 26: 1-10 (2021). · Zbl 1490.60266
[34] C. Hirsch, M. Holmes and V. Kleptsyn. Absence of WARM percolation in the very strong reinforcement regime. Ann. Appl. Probab. 31 (1), 199-217, (2021). · Zbl 1479.60196
[35] C. Hirsch, M. Holmes, and V. Kleptsyn. Infinite WARM graphs III: strong reinforcement regime. Nonlinearity (to appear). · Zbl 1523.60167
[36] C. Hirsch, M. Holmes, and V. Kleptsyn. WARM percolation on a regular tree in the strong reinforcement regime. preprint, arXiv:2009.07682
[37] R.v.d. Hofstad, M. Holmes, A. Kuznetsov, and W. Ruszel. Strongly reinforced Pólya urns with graph-based competition. Ann. Appl. Probab., 26(4):2494-2539 (2016). · Zbl 1352.60132
[38] M. Holmes and V. Kleptsyn. Proof of the WARM whisker conjecture for neuronal connec-tions. Chaos: an interdisciplinary journal of nonlinear science. 27, (2017). · Zbl 1387.60143
[39] M. Holmes and V. Kleptsyn. Infinite WARM graphs II: Critical regime. in preparation (2020).
[40] G. Aletti, I. Crimaldi, A. Ghiglietti, Synchronization of reinforced stochastic processes with a network-based interaction, Annals of Applied Probability, 27(6) (2017) 3787-3844. · Zbl 1382.60046
[41] G. Aletti, I. Crimaldi, A. Ghiglietti, Networks of reinforced stochastic processes: asymptotics for the empirical means, Bernoulli, 25(4B) (2019) 3339-3378. · Zbl 1430.60078
[42] G. Aletti, I. Crimaldi, A. Ghiglietti, Interacting reinforced stochastic processes: statistical inference based on the weighted empirical means, Bernoulli, 26(2) (2020) 1098-1138. · Zbl 1466.60192
[43] G. Aletti, I. Crimaldi, A. Ghiglietti, Networks of reinforced stochastic processes: a complete description of the first-order asymptotics, (2022) arXiv: 2206.07514. References
[44] O. Angel, N. Crawford, and G. Kozma, Localization for linearly edge reinforced random walks, Duke Math. J. 163(5) (2014), 889-921. · Zbl 1302.60129
[45] R. Bauerschmidt, N. Crawford, T. Helmuth, and A. Swan, Random spanning forests and hyperbolic symmetry, Comm. Math. Phys. 381(3) (2021), 1223-1261. · Zbl 1470.60270
[46] R. Bauerschmidt, T. Helmuth, and A. Swan, Dynkin isomorphism and Mermin-Wagner the-orems for hyperbolic sigma models and recurrence of the two-dimensional vertex-reinforced jump process, Ann. Probab. 47(5) (2019), 3375-3396. · Zbl 1448.60109
[47] R. Bauerschmidt, T. Helmuth, and A. Swan, The geometry of random walk isomorphism theorems, Ann. Inst. Henri Poincaré Probab. Stat. 57(1) (2021), 408-454. · Zbl 1484.60105
[48] D. Coppersmith and P. Diaconis, Random walk with reinforcement, Unpublished manuscript (1986).
[49] M. Disertori, V. Rapenne, C. Rojas-Molina, and X. Zeng, Phase transition in the inte-grated density of states of the Anderson model arising from a supersymmetric sigma model, arXiv:2211.10268 (2022).
[50] M. Disertori, C. Sabot, and P. Tarrès, Transience of edge-reinforced random walk, Comm. Math. Phys. 339(1) (2015), 121-148. · Zbl 1329.60116
[51] M. Disertori and T. Spencer, Anderson localization for a supersymmetric sigma model, Comm. Math. Phys. 300(3) (2010), 659-671. · Zbl 1203.82017
[52] M. Disertori, T. Spencer, and M.R. Zirnbauer, Quasi-diffusion in a 3D supersymmetric hyperbolic sigma model, Comm. Math. Phys. 300(2) (2010), 435-486. · Zbl 1203.82018
[53] M.S. Keane and S.W.W. Rolles, Edge-reinforced random walk on finite graphs, In Infinite dimensional stochastic analysis (Amsterdam, 1999), R. Neth. Acad. Arts Sci., Amsterdam (2000), pages 217-234. · Zbl 0986.05092
[54] G. Kozma and R. Peled, Power-law decay of weights and recurrence of the two-dimensional VRJP, Electron. J. Probab. 26 (2021), Paper No. 82 , 1-19. · Zbl 1478.60265
[55] T. Lupu, C. Sabot, and P. Tarrès, Fine mesh limit of the VRJP in dimension one and Bass-Burdzy flow, Probab. Theory Related Fields 177(1-2) (2020), 55-90. · Zbl 1434.60215
[56] T. Lupu, C. Sabot, and P. Tarrès, Inverting the Ray-Knight identity on the line, Electron. J. Probab. 26 (2021), Paper No. 96, 1-25. · Zbl 1480.60094
[57] F. Merkl and S.W.W. Rolles, Edge-reinforced random walk on a ladder, Ann. Probab. 33(6) (2005), 2051-2093. · Zbl 1102.82010
[58] F. Merkl and S.W.W. Rolles, Bounding a random environment for two-dimensional edge-reinforced random walk, Electron. J. Probab. 13 no. 19 (2008), 530-565. · Zbl 1187.82051
[59] F. Merkl and S.W.W. Rolles, Recurrence of edge-reinforced random walk on a two-dimensional graph, Ann. Probab. 37(5) (2009), 1679-1714. · Zbl 1180.82085
[60] F. Merkl, S.W.W. Rolles, and P. Tarrès, Random interlacements for vertex-reinforced jump processes, Ann. Inst. Henri Poincaré Probab. Stat. 57(2) (2021), 1058-1080. · Zbl 1491.60181
[61] R. Pemantle, Phase transition in reinforced random walk and RWRE on trees, Ann. Probab. 16(3) (1988), 1229-1241. · Zbl 0648.60077
[62] R. Poudevigne-Auboiron, Monotonicity and phase transition for the VRJP and the ERRW, JEMS (2022)
[63] C. Sabot. Polynomial localization of the 2D-vertex reinforced jump process, Electron. Com-mun. Probab. 26 (2021), Paper No. 1, 1-9. · Zbl 1489.60157
[64] C. Sabot and P. Tarrès, Edge-reinforced random walk, vertex-reinforced jump process and the supersymmetric hyperbolic sigma model, JEMS 17(9) (2015), 2353-2378. · Zbl 1331.60185
[65] C. Sabot and P. Tarrès. Inverting Ray-Knight identity, Probab. Theory Related Fields 165(3-4) (2016), 559-580. · Zbl 1345.60097
[66] C. Sabot, P. Tarrès, and X. Zeng, The vertex reinforced jump process and a random Schrödinger operator on finite graphs, Ann. Probab. 45(6A) (2017), 3967-3986. · Zbl 06838112
[67] W.B. Arthur, Y. Ermoliev, and Y. Kaniovski, Strong laws for a class of path-dependent stochastic processes with applications, In Stochastic optimization (1986), 287-300 · Zbl 0617.60027
[68] A. Barbour, The asymptotic behaviour of birth and death and some related processes, Ad-vances in Applied Probability 7(1) (1975), 28-43 · Zbl 0306.60054
[69] T. Gottfried, S. Grosskinsky, Asymptotics of generalized Pólya urns with non-linear feed-back, arXiv preprint arXiv:2303.01210 (2023)
[70] B. Hill, D. Lane, W. Sudderth, A strong law for some generalized urn processes, The Annals of Probability 8(2) (1980), 214-226 · Zbl 0429.60021
[71] R. Oliveira, The onset of dominance in balls-in-bins processes with feedback, Random Struc-tures & Algorithms 34(4) (2009), 454-477 · Zbl 1203.60104
[72] R. Pemantle, A survey of random processes with reinforcement, Probability surveys 4 (2007), 1-79 · Zbl 1189.60138
[73] W. Ruszel, D. Thacker, Positive reinforced generalized time-dependent Pólya urns via sto-chastic approximation, arXiv preprint arXiv:2201.12603 (2022) References
[74] G. Bianconi and A.-L. Barabási. Bose-einstein condensation in complex networks. Physical review letters, 86(24):5632, 2001.
[75] S. Dereich, C. Mailler, and P. Mörters. Nonextensive condensation in reinforced branching processes. The Annals of Applied Probability, 27(4):2539-2568, 2017. · Zbl 1373.60146
[76] E. Drinea, M. Enachescu, and M. D. Mitzenmacher. Variations on random graph models for the web. Harvard Computer Science Technical Report TR-06-01, 2001.
[77] G. Ergün and G. J. Rodgers. Growing random networks with fitness. Physica A: Statistical Mechanics and its Applications, 303(1-2):261-272, 2002. · Zbl 0978.90012
[78] T. Iyer. Degree distributions in recursive trees with fitnesses. arXiv preprint arXiv:2005.02197, 2020. · Zbl 1512.90060
[79] T. Iyer. On explosion in crump-mode-jagers branching processes, with applications to the limiting structure of recursive trees with fitness. 2023.
[80] P. L. Krapivsky and S. Redner. Organization of growing random networks. Physical Review E, 63(6):066123, 2001.
[81] B. Lodewijks and M. Ortgiese. A phase transition for preferential attachment models with additive fitness. Electronic Journal of Probability, 25:1 -54, 2020. · Zbl 1468.05280
[82] R. Oliveira and J. Spencer. Connectivity transitions in networks with super-linear preferen-tial attachment. Internet Mathematics, 2(2):121-163, 2005. References · Zbl 1097.68016
[83] W. Anderson, Continuous time Markov chains: an application oriented approach (1991), Springer Verlag. · Zbl 0731.60067
[84] E. Crane, N. Georgiou, S. Volkov, A.R. Wade, R. Waters, The simple harmonic urn, Ann. Probab. 39 (2011), 2119-2177. · Zbl 1262.60070
[85] D. Iglehart, Multivariate competition processes, Ann. Math. Statist. 35 (1964), 350-361. · Zbl 0143.19902
[86] J.F.C. Kingman, S. Volkov, Solution to the OK Corral model via decoupling of Friedman’s urn, J. Theoret. Probab. 16 (2003), 267-276. · Zbl 1022.60007
[87] S. Janson, Functional limit theorems for muti-type branching processes and generalised Polya urns, Stoch. Proc. Appl. 110 (2004) 177-245. · Zbl 1075.60109
[88] E. Renshaw, Modelling biological populations in space and time (1991), Cambridge Univer-sity Press. · Zbl 0754.92018
[89] G. Reuter, Competition processes. In: Neyman J. (Ed.) Proceedings of The Fourth Berkeley Symposium on Mathematical Statistics and Probability, v.II: Contributions to Probability Theory (1961), University of California Press, Berkeley. References · Zbl 0114.09001
[90] Bandyopadhyay, A., Janson, S., and Thacker, D. Strong convergence of infinite color balanced urns under uniform ergodicity. J. Appl. Probab. 57, 3 (2020), 853-865. · Zbl 1452.60019
[91] Bandyopadhyay, A., and Thacker, D. Pólya urn schemes with infinitely many colors. Bernoulli 23, 4B (2017), 3243-3267. · Zbl 1407.60099
[92] Bandyopadhyay, A., and Thacker, D. A new approach to Pólya urn schemes and its infinite color generalization. Ann. Appl. Probab. 32, 1 (2022), 46-79. · Zbl 07493816
[93] Janson, S. Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110, 2 (2004), 177-245. · Zbl 1075.60109
[94] Janson, S. Random replacements in Pólya urns with infinitely many colours. Electron. Commun. Probab. 24 (2019), Paper No. 23, 11. · Zbl 1412.60021
[95] Janson, S., Mailler, C., and Villemonais, D. Fluctuations of balanced urns with infin-itely many colours. arXiv:2111.13571. · Zbl 1520.60014
[96] Mahmoud, H. M. Pólya urn models. Texts in Statistical Science Series. CRC Press, Boca Raton, FL, [2009] ©2009. · Zbl 1149.60005
[97] Mailler, C., and Marckert, J.-F. Measure-valued Pólya urn processes. Electron. J. Probab. 22 (2017), Paper No. 26, 33. · Zbl 1358.60091
[98] Mailler, C., and Villemonais, D. Stochastic approximation on noncompact measure spaces and application to measure-valued Pólya processes. Ann. Appl. Probab. 30, 5 (2020), 2393-2438. · Zbl 1461.62147
[99] Baur, E., and Bertoin, J. Elephant random walks and their connection to pólya-type urns. Physical review. E 94, 052134 (2016).
[100] Bercu, B. A martingale approach for the elephant random walk. J. Phys. A 51, 1 (2018), 015201, 16. · Zbl 1392.60038
[101] Chauvin, B., Mailler, C., and Pouyanne, N. Smoothing equations for large Pólya urns. J. Theoret. Probab. 28, 3 (2015), 923-957. · Zbl 1358.60010
[102] Janson, S. Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110, 2 (2004), 177-245. · Zbl 1075.60109
[103] Kubota, N., and Takei, M. Gaussian fluctuation for superdiffusive elephant random walks. J. Stat. Phys. 177, 6 (2019), 1157-1171. · Zbl 1439.60043
[104] Schütz, G. M., and Trimper, S. Elephants can always remember: Exact long-range mem-ory effects in a non-markovian random walk. Physical review. E 70, 045101 (2004).
[105] Y. Couzinié and C. Hirsch. Weakly reinforced Pólya urns on countable networks. Electron. Commun. Probab., 26:1-10, 2021. · Zbl 1490.60266
[106] M. Heydenreich and C. Hirsch. A spatial small-world graph arising from activity-based reinforcement. In K. Avrachenkov, P. Pra lat, and N. Ye, editors, Algorithms and Models for the Web Graph, volume 8305 of Lecture Notes in Comput. Sci., pages 102-114. Springer, Cham, 2019. · Zbl 1534.68170
[107] M. Heydenreich and C. Hirsch. Extremal linkage networks. Extremes, 25:229-255, 2022. · Zbl 1502.60083
[108] C. Hirsch, M. Holmes, and V. Kleptsyn. Absence of WARM percolation in the very strong reinforcement regime. Ann. Appl. Probab., 31(1):199-217, 2021. · Zbl 1479.60196
[109] C. Hirsch, M. Holmes, and V. Kleptsyn. Infinite WARM graphs III: strong reinforcement regime. Preprint, 2023+. · Zbl 1523.60167
[110] R. v. d. Hofstad, M. Holmes, A. Kuznetsov, and W. Ruszel. Strongly reinforced Pólya urns with graph-based competition. Ann. Appl. Probab., 26(4):2494-2539, 2016. · Zbl 1352.60132
[111] Kalisman, N., Silberberg, G., Markram, H.: The neocortical microcircuit as a tabula rasa. Proc. Natl. Acad. Sci. U.S.A. 102(3), 880-885 (2005)
[112] ⋆-Reinforced Random Walks, Bayesian Statistics and Statistical Physics Pierre Tarrès (joint work with S. Bacallado, C. Sabot) · Zbl 1124.60043
[113] Consider a directed graph G = (V, E) endowed with an involution on the vertices denoted by * , and such that (1) (i, j) ∈ E ⇐⇒ (j * , i * ) ∈ E.
[114] A discrete Markov Chain on G with transition probability p(i, j) from i to j, and endowed with that involution * , is called Yaglom reversible if and only if there exists a probability measure π on V such that, for all i, j ∈ V, i ∼ j, π(i, j) := π(i)p(i, j) = π(j * )p(j * , i * ) = π(j * , i * ), π(i) = π(i * ).
[115] S. Bacallado, C. Sabot and P. Tarrès The ⋆-Edge-Reinforced Random Walk. Available on ArXiv:2102.08984 (2021).
[116] D. Coppersmith and P. Diaconis Random walks with reinforcements. Stanford Univ. Preprint (1987).
[117] P. Diaconis and D. Freedman De Finetti’s Theorem for Markov Chains. The Annals of Probability 8 No. 1 (1980), 115-130. · Zbl 0426.60064
[118] C. Sabot and P. Tarrès Edge-reinforced random walk, Vertex-reinforced jump process and the sigma supersymmetric hyperbolic sigma model. Journal of the European Mathematical Society 17 (2015), 2353-2378. · Zbl 1331.60185
[119] C. Sabot and P. Tarrès The *-Vertex-Reinforced Jump Process. Available on ArXiv:2102.08988 (2021).
[120] C. Sabot, P. Tarrès and X. Zeng The vertex-reinforced jump process and a random Schrödinger operator on finite graphs. The Annals of Probability 45 No. 6A (2017), 3967-3986. · Zbl 06838112
[121] C. Sabot and X. Zeng A random Schrödinger operator associated with the vertex-reinforced jump process on infinite graphs. Journal of the American Mathematical Society 32 No. 2 (2019), 311-349. Reporter: Bas Lodewijks · Zbl 1450.60062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.