×

Infinite WARM graphs III: strong reinforcement regime. (English) Zbl 1523.60167

Summary: We study a reinforcement process on graphs \(G\) of bounded degree. The model involves a parameter \(\alpha>0\) governing the strength of reinforcement, and Poisson clock rates \(\lambda_v\) at the vertices \(v\) of the graph. When the Poisson clock at a vertex \(v\) rings, one of the edges incident to it is reinforced, with edge \(e\) being chosen with probability proportional to its current count (counts start from 1) raised to the power \(\alpha\). The main problem in such models is to describe the (random) subgraph \(\mathcal{E}_\infty\), consisting of edges that are reinforced infinitely often. In this paper, we focus on the finite connected components of \(\mathcal{E}_\infty\) in the strong reinforcement regime \((\alpha>1)\) with clock rates that are uniformly bounded above. We show here that when \(\alpha\) is sufficiently large, all connected components of \(\mathcal{E}_\infty\) are trees. When the firing rates \(\lambda_v\) are constant, we show that all components are trees of diameter at most 3 when \(\alpha\) is sufficiently large, and that there are infinitely many phase transitions as \(\alpha\downarrow 1\). For example, on the triangular lattice, increasingly large (odd) cycles appear as \(\alpha\downarrow 1\) (while on the square lattice no finite component of \(\mathcal{E}_\infty\) contains a cycle for any \(\alpha>1)\). Increasingly long paths and other structures appear in both lattices when taking \(\alpha\downarrow 1\). In the special case where \(G=\mathbb{Z}\) and \(\alpha>1\), all connected components of \(\mathcal{E}_\infty\) are finite and we show that the possible cluster sizes are non-monotone in \(\alpha\). We also present several open problems.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J25 Continuous-time Markov processes on general state spaces
37C10 Dynamics induced by flows and semiflows
05C90 Applications of graph theory

References:

[1] Arthur, W.; Ermoliev, Y.; Kaniovskii, Y., Path dependent processes and the emergence of macro-structure, Eur. J. Oper. Res., 30, 294-303 (1987) · doi:10.1016/0377-2217(87)90074-9
[2] Benaïm, M.; Benjamini, I.; Chen, J.; Lima, Y., A generalized Pólya’s urn with graph based interactions, Random Struct. Algorithms, 46, 614-34 (2015) · Zbl 1317.05103 · doi:10.1002/rsa.20523
[3] Benaïm, M., On strict convergence of stochastic gradients (2018)
[4] Davis, B., Reinforced random walk, Prob. Theory Relat. Fields, 84, 203-29 (1990) · Zbl 0665.60077 · doi:10.1007/BF01197845
[5] Couzinié, Y.; Hirsch, C., Weakly reinforced Pólya urns on countable networks, Electron. Commun. Probab., 26, 1-10 (2021) · Zbl 1490.60266 · doi:10.1214/21-ECP404
[6] Hirsch, C.; Holmes, M.; Kleptsyn, V., Absence of WARM percolation in the very strong reinforcement regime, Ann. Appl. Probab., 31, 199-217 (2021) · Zbl 1479.60196 · doi:10.1214/20-AAP1587
[7] Hofbauer, J.; Sigmund, K., Evolutionary Games and Population Dynamics (1998), Cambridge: Cambridge University Press, Cambridge · Zbl 0914.90287
[8] Hofstad, R.; Holmes, M.; Kuznetsov, A.; Ruszel, W., Strongly reinforced Pólya urns with graph-based competition, Ann. Appl. Probab., 26, 2494-539 (2016) · Zbl 1352.60132 · doi:10.1214/16-AAP1153
[9] Hirsch, C.; Holmes, M.; Kleptsyn, V., WARM percolation on a regular tree in the strong reinforcement regime
[10] Holmes, M.; Kleptsyn, V., Proof of the WARM whisker conjecture for neuronal connections, Chaos, 27 (2017) · Zbl 1387.60143 · doi:10.1063/1.4978683
[11] Holmes, M.; Kleptsyn, V., Infinite WARM graphs II: Critical regime (2020)
[12] Khanin, K.; Khanin, R., A probabilistic model for establishment of neuron polarity, J. Math. Biol., 42, 26-40 (2001) · Zbl 0980.92005 · doi:10.1007/PL00000071
[13] Launay, M.; Limic, V., Generalized interacting Urn models (2012)
[14] Pemantle, R., A survey of random processes with reinforcement, Probab. Surv., 4, 1-79 (2007) · Zbl 1189.60138 · doi:10.1214/07-PS094
[15] Pólya, G., Sur quelques points de la théorie des probabilités, Ann. Inst. Henri Poincaré, 1, 117-61 (1930)
[16] Tadić, V. B., Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema, Stoch. Proc. Appl., 125, 1715-55 (2015) · Zbl 1357.62274 · doi:10.1016/j.spa.2014.11.001
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.