1.1. Overview of our learning model

For any positive integer m with $m \geqslant 2$ , let $\mathbb{T}_{m}$ indicate the infinite rooted tree, with root $\phi$ , in which each vertex has precisely m children. Let $V(\mathbb{T}_{m})$ denote the set of all vertices of $\mathbb{T}_{m}$ , and imagine an agent occupying each vertex of $V(\mathbb{T}_{m})$ . We consider a learning model in which each agent, at each time step (where time is indexed by the set $\mathbb{N}_{0}$ of non-negative integers), has to adopt one of two possible technologies that we henceforth refer to as colours or states and denote by the letters B and R. The state of the agent at a vertex $v \in V(\mathbb{T}_{m})$ at time step t, for each $t \in \mathbb{N}_{0}$ , is denoted by $C_{t}(v)$ . Conditioned on the states of the agents at all the vertices of $V(\mathbb{T}_{m})$ at time step t, the (random) state $C_{t+1}(v)$ to which the agent at v updates itself at time step $t+1$ has a probability distribution that is a function of $C_{t}(v_{1}), C_{t}(v_{2}), \ldots, C_{t}(v_{m})$ , where $v_{1}, v_{2}, \ldots, v_{m}$ are the children of v.

Such a model can be viewed from a number of different perspectives, such as

1. (i) as a discrete-time interacting system of particles on $\mathbb{T}_{m}$ with infinitely many changes allowed to happen at each time step,

2. (ii) as a model for social learning, for understanding the diffusion of technologies throughout an infinite population of agents, and

3. (iii) as a probabilistic finite state tree automaton on $\mathbb{T}_{m}$ .

We delve deeper into each of the above motivating reasons for the study of such models in Subsection 1.4.

Each model studied in this paper admits a crucial component known as a policy function: it governs how the agent at v, for each $v \in V(\mathbb{T}_{m})$ , learns from the states $C_{t}(v_{i})$ , $i \in \{1,2,\ldots,m\}$ , of the agents situated at the children $v_{1}, v_{2}, \ldots, v_{m}$ of v at time step t, and subsequently updates its own state to $C_{t+1}(v)$ at time step $t+1$ . When such a model is viewed as a probabilistic tree automaton (PTA), as explained in Subsection 1.4, the policy function is referred to as the stochastic update rule associated with that PTA. We are concerned with studying the absolute majority policy function, which we describe in detail in Subsection 1.2.

1.2. Absolute majority policy

In this model, the agent occupying vertex v, for each $v \in V(\mathbb{T}_{m})$ , is endowed with two random variables, $X_{t}(v)$ and $Y_{t}(v)$ , for each time step $t \in \mathbb{N}_{0}$ . For each $v \in V(\mathbb{T}_{m})$ and each $t \in \mathbb{N}_{0}$ , the random variable $X_{t}(v)$ captures the outcome of the (random) experiment performed by the agent located at v, during the time step or epoch t, using the technology $C_{t}(v)$ that this agent is currently equipped with. This experiment has two possible outcomes—success and failure—so $X_{t}(v)$ is a Bernoulli random variable that acts as an indicator for the event of success. We let $X_{t}(v)$ follow Bernoulli $(\, p_{B})$ conditioned on $C_{t}(v)=B$ , and we let $X_{t}(v)$ follow Bernoulli $(\, p_{R})$ conditioned on $C_{t}(v)=R$ , where $p_{B}, p_{R} \in [0, 1]$ are preassigned parameters in our model. The random variable $Y_{t}(v)$ follows Bernoulli $\left(\frac{1}{2}\right)$ for each $v \in V(\mathbb{T}_{m})$ and each $t \in \mathbb{N}_{0}$ . It is assumed that the entire collection $\left\{X_{t}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}\cup\left\{Y_{t}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}$ of random variables is independent for each time step $t \in \mathbb{N}_{0}$ , and the collection $\left\{Y_{t}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}$ is independent of $\left\{C_{s}(u)\,:\, u \in V(\mathbb{T}_{m}), s \in \{0,1,\ldots,t\}\right\}$ for each $t \in \mathbb{N}_{0}$ .

Conditioned on $\left\{C_{t}(u)\,:\, u \in V(\mathbb{T}_{m})\right\}$ , the agent at v updates its state to $C_{t+1}(v)$ according to the following rule, where $v_{1}, v_{2}, \ldots, v_{m}$ denote the children of v:

(1) \begin{equation} C_{t+1}(v) = \begin{cases} B & \text{if } \sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=B} > \sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=R}, \\[3pt] B & \text{if } \sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=B} = \sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=R} \text{ and } Y_{t}(v)=1, \\[3pt] R & \text{otherwise.} \end{cases}\end{equation}

In words, this can be described as follows: the agent at the vertex v counts the number $\sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=B}$ of successful experiments performed, during epoch t, by all those agents that occupy the children of v and that are in state B at time step t, and likewise, it also counts the number $\sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=R}$ of successful experiments performed, during epoch t, by all those agents that occupy the children of v and that are in state R at time step t. If the former count strictly exceeds the latter then the agent at v updates its state to B at time step $t+1$ , while if the latter strictly exceeds the former then the agent at v updates its state to R at time step $t+1$ . If the two counts are equal then the agent at v tosses a fair coin in order to break the tie. If the coin lands as a head, indicated by $Y_{t}(v)=1$ , then the agent at v updates its state to B at time step $t+1$ , and if the coin lands as a tail, it updates its state to R at time step $t+1$ .

We begin the process at time step $t=0$ with an independent and identically distributed (i.i.d.) assignment of states to the vertices of $\mathbb{T}_{m}$ , i.e. the collection $\left\{C_{0}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}$ is i.i.d. with

(2) \begin{equation}C_{0}(v)=B \text{ with probability } \pi_{0} \text{ and } C_{0}(v)=R \text{ with probability } 1-\pi_{0}\end{equation}

for each $v \in V(\mathbb{T}_{m})$ . Letting $\nu_{t}$ denote the joint law of $\left\{C_{t}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}$ for each $t \in \mathbb{N}_{0}$ , we are concerned in this paper with answering the following question: does $\left\{\nu_{t}\right\}_{t \in \mathbb{N}_{0}}$ converge as $t \rightarrow \infty$ , and if it does, what is its distributional limit? We investigate this question for all values of $(\, p_{B},p_{R}) \in [0, 1]^{2}$ when $m=2$ , whereas when $m \geqslant 3$ , we consider two regimes of values of the parameter pair $(\, p_{B},p_{R})$ . The first of these regimes is where $p_{B}=p_{R}=p$ for some $p \in [0, 1]$ , i.e. an agent, located at any vertex of $\mathbb{T}_{m}$ , stands the same chance of achieving a successful outcome in the experiment performed during epoch t irrespective of whether its state at time step t is B or R. We present a full description of what happens in such a scenario as the common value p of the two parameters is allowed to vary over [0, 1]. The complement of this regime is where $p_{B} \neq p_{R}$ , but when $m \geqslant 3$ , the analysis for $p_{B} \neq p_{R}$ , without additional assumptions, quickly becomes intractable, and it becomes difficult to conclude anything about the distributional limit(s) of $\left\{\nu_{t}\right\}_{t \in \mathbb{N}_{0}}$ (depending on the initial distribution $\nu_{0}$ given by (2), and on the values of $p_{B}$ and $p_{R}$ ). We, therefore, focus on the special case of $p_{B}=1$ and $p_{R} \in [0,1)$ , and we demonstrate, via the relatively less unwieldy examples of $m=2$ and $m=3$ , that the conclusion is rather non-intuitive and further investigations are warranted. This special case can be considered ‘extremal’ in the sense that a vertex that is in state B is sure to achieve success when it performs its experiment (using technology B), since $p_{B}=1$ , whereas the experiment performed (with technology R) by a vertex in state R has a positive probability of resulting in a failure. Intuition seems to suggest that in such a scenario, eventually, every vertex of $\mathbb{T}_{m}$ would opt for the (evidently superior) technology B, but it turns out (see Section 5) that this is not necessarily the case, and the distributional limit depends heavily on the value of $p_{R}$ .

1.3. Main results

We begin with a result that is applicable to all values of the parameter pair $(\, p_{B},p_{R})$ .

From the last assertion made in the statement of Theorem 1, it becomes apparent that we need to answer the following questions.

1. (i) Does the function $g_{m}$ have a unique fixed point in [0, 1]?

2. (ii) If $g_{m}$ has multiple fixed points in [0, 1], which of these are attractive and which are repulsive?

Let us now make the following simple observation.

Before moving on to higher values of m, we state the following result concerning $m=2$ and all possible values of $p_{B}$ and $p_{R}$ .

From Remark 1, it is evident that for $m=2$ and when $(\, p_{B},p_{R}) \neq (1,1)$ , the sequence $\{\nu_{t}\}_{t \in \mathbb{N}_{0}}$ converges to $\nu$ , as $t \rightarrow \infty$ , where $\nu$ is as defined by (4), with $\pi$ being the unique fixed point of $g_{2}$ . For $m=2$ and $p_{B}=p_{R}=1$ , for each $\pi_{0} \in [0, 1]$ (where $\pi_{0}$ is as defined in (2)), the law $\nu_{t}$ is the same as $\nu_{0}$ for every $t \in \mathbb{N}$ , so the limit equals $\nu_{0}$ itself.

We now come to the two specific regimes of values of the parameter pair $(\, p_{B},p_{R})$ that, as mentioned towards the end of Subsection 1.2, are considered in this paper. When $p_{B}=p_{R}=p$ for some $p \in [0, 1]$ , the learning model with the absolute majority policy described in Subsection 1.2 admits the following phase transition phenomenon.

In particular, we show, via analytical methods in Subsection 4.1, that for $m=3$ , the threshold $p(m) \approx 0.557507$ , whereas for $m=4$ , the threshold $p(m) \approx 0.42842$ .

When $p_{B}=1$ and $p_{R} \in [0,1)$ , our learning model is devoid of any phase transition for $m=2$ (which follows as a special case of Theorem 2), whereas a striking and rather non-intuitive phenomenon of phase transition is observed when $m=3$ , as stated below.

The reason we describe this result as non-intuitive is as follows. The value $p_{B}=1$ ensures that every experiment performed with the technology labelled B is bound to result in a success. Evidently, the technology labelled B is superior to the technology labelled R, unless $p_{R}=1$ . This would seem to suggest that eventually the state of each vertex of $\mathbb{T}_{m}$ would be updated to B and would remain that way, but this is not the case when $p_{R}$ is sufficiently large (i.e. for $p_{R} \geqslant \sqrt{3}-1$ ). The phase transition exhibited by our model in Theorem 4, therefore, seems unusual.

1.4. Motivation and a brief discussion of relevant literature

As alluded to in Subsection 1.1, there is a myriad of perspectives from which the study of our model can be motivated. For any two vertices $u, v \in V(\mathbb{T}_{m})$ , with u the parent of v, let us refer to the agent located at v as an influencing neighbour to the agent located at u. Our model can then be viewed as an interacting particle system in which each agent, at each time step, is allowed to update its policy or protocol on some matter by taking note of the policies or protocols adopted, and the outcomes (such as rewards or penalties) obtained as a consequence, by its influencing neighbours at the previous time step. Each agent can adopt one of two available policies (such as a liberal stance and a conservative stance) at the beginning of time step t, following which it executes a plan of action (as decreed by the adopted policy) during the epoch t. Such a plan of action (which is a random experiment) has two possible outcomes: a desirable one and an undesirable one. At the end of time step t, each agent counts the number of its influencing neighbours who adopted the liberal stance at the beginning of time step t and who were then rewarded with the desirable outcome, and the number of its influencing neighbours who adopted the conservative stance at the beginning of time step t and who were then rewarded with the desirable outcome. If the former exceeds the latter, the agent adopts the liberal stance at the beginning of time step $t+1$ , whereas if the latter exceeds the former, the agent adopts the conservative stance at the beginning of time step $t+1$ . If the two counts are equal, the agent decides which stance to adopt by tossing a fair coin and thereby breaking the tie.

The interpretation presented above is reminiscent of the well-known and well-studied voter model. In the classical linear voter model (see, for instance, [Reference Holley and Liggett57], which introduced the voter model as a continuous-time proximity process, as well as [Reference Liggett68], [Reference Liggett67], and [Reference Liggett66] for a detailed review of old and new developments in this topic of research), individuals or agents occupy the elements (referred to as sites) of an arbitrary countable set S, and each agent, at any given point in time, can have one of two possible opinions on an issue. For each site $x \in S$ , at exponential times with a specified rate, the agent located at x chooses a site $y \in S \setminus \{x\}$ with probability p(x, y) (where $p(x,y) \geqslant 0$ for each $y \in S\setminus\{x\}$ and $\sum_{y \in S \setminus \{x\}}p(x,y)=1$ ) and adopts the opinion being currently held by the agent at y.

Yet another interpretation of the voter model is that of two species, fairly matched, competing for territory, and the invasion by one species of the territory belonging to the other. In our model, each vertex v of $\mathbb{T}_{m}$ can be viewed as a city, and B and R can be thought of as two belligerent armies contesting the city. At any time step t, the event $C_{t}(v)=B$ indicates that army B retains dominion over the city v at the beginning of time step t, but that there are ongoing clashes between B and R during the epoch t. Conditioned on $C_{t}(v)=B$ , the event $X_{t}(v)=1$ indicates that the defenders, i.e. the armed forces of B, are able to defeat the invaders, i.e. the armed forces of R, in the battle that takes place in v during the epoch t. It is not only reasonable, but is even practical, to assume that, in the event of $X_{t}(v)=0$ , even though the invaders clinch a victory over the defenders, they incur heavy losses, and those among them that remain alive are not able to travel from v to anywhere else for further attempts at conquests. A similar interpretation is true if $C_{t}(v)=R$ . Letting $v_{1}, v_{2}, \ldots, v_{m}$ denote the children of v, we may imagine them to be, in some sense, ‘border cities’ or ‘outposts’ of the ‘main city’ v, with routes leading to v (along which armies can travel). From each outpost $v_{i}$ where the defenders B defeat the invaders R in the battle that takes place during the epoch t, a battalion of soldiers loyal to B is dispatched to v by the end of the epoch t. Likewise, from each $v_{i}$ where the defenders R defeat the invaders B in the battle that takes place during the epoch t, a battalion of soldiers loyal to R is dispatched to v by the end of the epoch t. The inequality $\sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=B} > \sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=R}$ then indicates that the soldiers who are loyal to B and who travel to v from its outposts outnumber the soldiers who are loyal to R and who travel to v from its outposts, resulting in v becoming occupied by B by the beginning of the epoch $t+1$ . On the other hand, when $\sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=B} = \sum_{i=1}^{m}X_{t}(v_{i})\mathbf{1}_{C_{t}(v_{i})=R}$ , the number of soldiers loyal to B who travel to v from its outposts equals the number of soldiers loyal to R who travel to v from its outposts, and in this case, v is equally likely to be conquered by either of the armies by the beginning of the epoch $t+1$ . In this regard, we mention [Reference Clifford and Sudbury26], in which a simple stochastic model is devised for two fairly matched species competing for territory along the boundary or frontier of their respective regions of dominion, wherein the result of the conflict is the invasion by one of the species of territory previously held by the other. Asymptotic results for the pattern of territories held by a single species are presented in [Reference Clifford and Sudbury26], along with the exhibition of markedly distinct behaviour between one-dimensional and two-dimensional competitions on one hand, and three-dimensional competition on the other.

Interacting particle systems are indispensable for modelling complex phenomena, in natural and social sciences, that involve a very large number of interrelated components (such as the flow of traffic on highways, interaction among the constituents of a cell, opinion dynamics, the spread of epidemics or fires, reaction diffusion systems, crystal surface growth, and chemotaxis). For instance, the biased voter model, a generalization of the voter model described above, has been studied in [Reference Williams and Bjerknes101], [Reference Bramson and Griffeath19], [Reference Bramson and Griffeath20], and [Reference Komarova61], in the context of how cancerous cells spread and metastasize throughout the body of an organism. In [Reference Mukhopadhyay, Mazumdar and Roy80], binary opinion dynamics in a fully connected network of interacting agents is studied, with agents being biased towards one of the two opinions and allowed to interact according to (i) the voter rule, where an updating agent simply copies the opinion of a different, randomly sampled, agent, and (ii) the majority rule, where an updating agent samples multiple other agents and adopts the opinion that is in majority among the members of this selected sample. The diverse applications of the voter model and its variants in the field of social sciences, especially in the analysis of discrete and continuous opinion dynamics, can be seen, for example, in [Reference Granovsky and Madras49], [Reference Mobilia75], [Reference Mobilia and Georgiev76], [Reference Mobilia, Petersen and Redner77], [Reference Congleton29], [Reference Sood and Redner91], [Reference Sood, Antal and Redner90], [Reference Masuda, Gibert and Redner72], and [Reference Castellano, Muñoz and Pastor-Satorras23].

We mention here that the two other extensively studied models of interacting particle systems are the contact processes (see, for instance, [Reference Griffeath50], [Reference Durrett and Liu36], [Reference Bezuidenhout and Grimmett16], [Reference Stacey92, Reference Stacey93] and [Reference Liggett67]) and the exclusion processes (see, for instance, [Reference Liggett65], [Reference De Masi, Presutti and Scacciatelli30], [Reference Quastel85], [Reference Sandow87], [Reference Schütz88], [Reference Rajewsky, Santen, Schadschneider and Schreckenberg86], [Reference Tracy and Widom94], [Reference Mallick71], and [Reference Liggett67]). Of these, the contact process finds applications in the study of the susceptible-infected-susceptible (SIS) model of compartmental epidemiology (see, for instance, [Reference Berger, Borgs, Chayes and Saberi14]), wherein every vertex of the network under consideration, at any point in time, is either infected or healthy but susceptible, and whereas each infected vertex becomes healthy, independent of all else, at a given constant rate, a healthy vertex becomes infected at a rate that equals the product of the propagation ratio of the disease and the number of infected neighbours of that vertex (at that time). Much like the model considered in this paper, this, too, is a model involving agents stationed at the vertices of a given (or random) graph or network (in particular, Berger et al. [Reference Berger, Borgs, Chayes and Saberi14] studied the contact process, emulating the spread of a virus throughout a network of computers in the presence of a particular class of antivirus software, on scale-free graphs in preferential attachment models), wherein each agent can be in one of two possible states at any given point in time, and if an agent is currently healthy, the rate at which it transitions into the infected state is influenced by the number of infected neighbours it currently possesses. In [Reference Durrett and Jung37], the contact process/SIS model is studied on small-world networks proposed by Newman and Watts [Reference Newman and Watts83], wherein all pairs of vertices that are a distance m or less apart are connected (referred to as short-range connections), and in addition, there is a density p of edges (called long-range connections) that connect vertices to neighbours that are farther away and are chosen at random from the graph.

The model studied in this paper also seems to be redolent of models for competing first passage percolation, such as that studied in [Reference Antunović, Dekel, Mossel and Peres4]. Here, at any time $t\geqslant 0$ of the stochastic process, the set of vertices V of a given graph $G=(V,E)$ can be partitioned into three subsets, namely (i) $\mathcal{B}_{t}$ , consisting of all the vertices painted blue so far, (ii) $\mathcal{R}_{t}$ , consisting of all the vertices painted red so far, and (iii) $V\setminus\left(\mathcal{B}_{t}\cup\mathcal{R}_{t}\right)$ , consisting of the yet-uncoloured vertices, and the Markov process evolves by having each yet-uncoloured vertex v of V assigned (i) the colour blue with rate equal to $\beta\left|N(v)\cap\mathcal{B}_{t}\right|$ and (ii) the colour red with rate equal to $\rho\left|N(v)\cap\mathcal{R}_{t}\right|$ , where N(v) indicates the set of all neighbours of v in G, and $\rho$ and $\beta$ are positive rates that remain fixed throughout the process. Here, however, once a vertex has been coloured, it retains that colour forever in the future. Continuing with this line of thought, we are ushered into the world of two-type Richardson models, introduced in [Reference Häggström and Pemantle52], wherein two infections, type 1 and type 2, starting from two distinct sources, $s_{1}$ and $s_{2}$ , respectively, in the cubic grid $\mathbb{Z}^{d}$ , compete to invade the sites of $\mathbb{Z}^{d}$ , each progressing like a first-passage percolation process on $\mathbb{Z}^{d}$ governed by the same family of i.i.d. exponential random variables, but with the assumption that once a site is captured by the type i infection, it remains of type i forever and cannot transmit the other infection. In [Reference Häggström and Pemantle53], the two-type Richardson model on $\mathbb{Z}^{d}$ , with $d\geqslant 2$ , is studied in the asymmetric case with different infection rates: a site $\mathbf{x}$ in $\mathbb{Z}^{d}$ that is yet uninfected may either become type 1 infected at a rate that is equal to $\lambda_{1}$ times the number of type-1-infected neighbours of $\mathbf{x}$ or else become type 2 infected at a rate that is equal to $\lambda_{2}$ times the number of type-2-infected neighbours of $\mathbf{x}$ , with $\lambda_{1}\neq \lambda_{2}$ . The main question of interest in both [Reference Häggström and Pemantle52] and [Reference Häggström and Pemantle53] is whether it is possible, with positive probability, for both the set of sites that are type 1 infected and the set of sites that are type 2 infected to keep growing indefinitely as time approaches $\infty$ (in other words, whether coexistence is possible). In [Reference Garet and Marchand43], it is shown that coexistence occurs with strictly positive probability when stationary ergodic first-passage percolation is considered (on $\mathbb{Z}^{d}$ for $d\geqslant 2$ , and also on an infinite cluster of Bernoulli percolation) and some additional assumptions (such as integrability conditions on the passage times, finite energy properties, and positivity conditions on the functional giving the directional asymptotic speeds) are imposed.

In [Reference Hoffman56], results from the study of stationary first-passage percolation are applied to the analysis of limiting configurations in a large family of competing spatial growth models that may be interpreted as variants of the two-type Richardson model, on $\mathbb{Z}^{d}$ . In [Reference Deijfen and Häggström31], a generalized version of the two-type Richardson model (with infection rates of the type 1 and type 2 infections being $\lambda_{1}$ and $\lambda_{2}$ , respectively) is considered, in which it is assumed that at the start of the process, all sites in the set $\xi_{i}$ are infected with type i, where $\xi_{1}$ and $\xi_{2}$ are two finite, disjoint subsets of $\mathbb{Z}^{d}$ , and all sites in $\mathbb{Z}^{d}\setminus\left(\xi_{1}\cup\xi_{2}\right)$ are uninfected. The set $\xi_{i}$ is said to strangle the set $\xi_{j}$ , for $\{i,j\}=\{1,2\}$ , if there exists no infinite self-avoiding path in $\mathbb{Z}^{d}$ that starts at a vertex in $\xi_{j}$ and does not intersect $\xi_{i}$ , and the pair $(\xi_{1},\xi_{2})$ is said to be fertile if neither of them strangles the other. In [Reference Deijfen and Häggström31], it is shown that as long as $(\xi_{1},\xi_{2})$ is fertile, the actual choice of $\xi_{1}$ and $\xi_{2}$ has no impact on whether the probability of coexistence is strictly positive or not. In [Reference Deijfen and Häggström32], the two-type Richardson model is studied on graphs other than the cubic lattice $\mathbb{Z}^{d}$ , and the existence of graphs that (i) exhibit coexistence at some value of the parameter pair $(\lambda_{1},\lambda_{2})$ such that $\lambda_{1}\neq \lambda_{2}$ and (ii) exhibit non-coexistence when the ratio $\lambda_{1}/\lambda_{2}$ is brought closer to 1 is proved. In [Reference Deijfen and Häggström33], unbounded sets of initially infected sites are considered, and it is shown that (i) if, initially, all sites of $\mathcal{H}\setminus (0,0,\ldots,0)$ , where $\mathcal{H}=\left\{(x_{1},x_{2},\ldots,x_{d})\in\mathbb{Z}^{d}\,:\,x_{1}=0\right\}$ , are type 1 infected and the site $(0,0,\ldots,0)$ is type 2 infected, then there is a positive probability for the type 2 infection to grow unboundedly if and only if its intensity strictly exceeds that of the type 1 infection (i.e. $\lambda_{2}>\lambda_{1}$ ), whereas (ii) if, initially, all sites of $\mathcal{L}\setminus(0,0,\ldots,0)$ , where $\mathcal{L}=\left\{(x_{1},x_{2},\ldots,x_{d})\,:\,x_{1}\leqslant 0, x_{i}=0 \text{ for each }i\in\{2,\ldots,d\}\right\}$ , are type 1 infected and the site $(0,0,\ldots,0)$ is type 2 infected, then there is a positive probability for the type 2 infection to grow unboundedly even if $\lambda_{1}=\lambda_{2}$ . In [Reference Garet and Marchand44], a weakened version of non-coexistence for the two-type Richardson model with distinct infection rates for the two infection types is proved, i.e. assuming that the two types of infection propagate according to passage times that are distinct and stochastically comparable, [Reference Garet and Marchand44] shows that when the weaker infection type survives, the space occupied by the stronger infection is almost impossible to detect, and in particular, in dimension 2, one of the two infection types occupies a set of sites with full density, while the other occupies a set of sites with null density.

In [Reference Deijfen and van der Hofstad34], the two-type Richardson model is studied on random graphs generated by the configuration model, and it is shown that, as the number of vertices tends to infinity, (i) if the degree distribution is a power law with exponent in (2, 3), one of the infection types will occupy all but finitely many vertices, and (2) which infection type wins is random, and either infection type has a positive probability of winning, irrespective of the values of $\lambda_{1}$ and $\lambda_{2}$ . In the same thread, we mention [Reference Baroni, van der Hofstad and Komjáthy11], [Reference van der Hofstad and Komjáthy98], and [Reference van der Hofstad97], which study the two-type Richardson model on scale-free random graphs with degree distributions satisfying asymptotic power laws with infinite variance, where the spread of each of the two types of infection is governed by i.i.d. passage times (whose distributions may depend on the type of infection considered). In [Reference Ahlberg, Griffiths, Janson and Morris3], the two-type Richardson model is studied in two settings, namely a planar growth model related to two-neighbour bootstrap percolation, and a system of urns with graph-based interactions. In [Reference Ahlberg, Deijfen and Janson2], the two-type Richardson model is studied on configuration models with given degree sequences, and as the total number of vertices approaches infinity, it is shown that (i) when $\lambda_{1}=\lambda_{2}$ and the degree of a randomly chosen vertex has a finite second moment, the proportion of vertices infected by type 1 converges to a continuous random variable $V\in(0,1)$ , and (ii) when $\lambda_{1}>\lambda_{2}$ , the type 1 infection occupies all but a vanishing fraction of vertices. In [Reference Lodewijks and Maitra69], competition between two growth models with long-range interactions on a torus of size n in dimension d is studied.

We mention here [Reference Asavathiratham, Roy, Lesieutre and Verghese6], which admits, as a special case of the influence model studied therein, the binary influence model. Here, at any given point in time, each site of the network under consideration can be in one of two statuses, and transitions between these statuses at any given site can occur under the influence only of the neighbours (of that site) that have the opposite status (i.e. opposite the current status of that site). The binary influence model evolves in discrete time, and the structure of the underlying network plays a crucial role in determining whether all sites, eventually, reach a consensus status.

Some discussion is now in order as to the apparent connection that our work bears with [Reference Antunović, Mossel and Rácz5], which studies a model that couples the growth of a random network with the nodal dynamics taking place on that network. To elucidate, [Reference Antunović, Mossel and Rácz5] studies a dynamically evolving network, $\{G_{n}\}_{n}$ , consisting of vertices coloured either blue or red. This begins with an initial graph $G_{0}$ , with an assignment $\left\{C(u)\,:\,u \in G_{0}\right\}$ of colours to the vertices of $G_{0}$ . At time stamp $(n+1)$ , a new vertex, say $v_{n+1}$ , with m edges attached to it, is introduced. Each of these m edges, independent of all else, attaches to vertex u in $G_{n}$ with probability proportional to $\deg_{n}(u)$ , which is the degree of u in $G_{n}$ . Once this step has been completed, the probability with which $v_{n+1}$ is assigned the colour blue is equal to $p_{k}$ , where k is the number of edges that connect $v_{n+1}$ with blue vertices in $G_{n}$ . The goal of [Reference Antunović, Mossel and Rácz5] is to investigate the limiting behaviour of $a_{n}=(A_{n}+B_{n})^{-1}A_{n}$ , where $A_{n}$ is the number of blue vertices in $G_{n}$ , and $B_{n}$ is the number of red vertices in $G_{n}$ . This is accomplished by studying the Markov process $\{(A_{n},X_{n})\}_{n}$ , where $X_{n}$ equals the sum of the degrees of all blue vertices in $G_{n}$ , and the analysis is done by expressing $\{(A_{n},X_{n})\}_{n}$ as a stochastic approximation process. The conditional expectation of the increment $A_{n+1}-A_{n}$ , conditioned on $\mathcal{F}_{n}$ (the $\sigma$ -field containing all information regarding the stochastic process up to and including time stamp n) is computed, yielding a drift function (which takes as the argument the proportion $x_{n}=(X_{n}+Y_{n})^{-1}X_{n}$ , where $X_{n}$ is as defined above, and $Y_{n}$ is the sum of the degrees of all red vertices in $G_{n}$ ) that is closely connected with the function $g_{m}$ defined in (5) (when $p_{k}=f_{m}(k)+k/m$ for each k). This similarity arises from the interpretation that each new vertex being introduced in the model studied in [Reference Antunović, Mossel and Rácz5] has, as its ‘children’, the existing vertices to which it becomes connected via its m edges—of course, there may not, in this case, be m distinct ‘children’ of $v_{n+1}$ , but the decision as to which colour $v_{n+1}$ will adopt is made via m distinct edges. This is reminiscent of how, in our model, at the beginning of each epoch, the agent located at any vertex v of $\mathbb{T}_{m}$ relies on the feedback it receives from the agents located at the m children of v (over the previous epoch) in order to update its selection of technology. It should be noted, however, that the model presented in [Reference Antunović, Mossel and Rácz5] differs from the model studied in this paper in two crucial aspects.

1. (i) The underlying network in [Reference Antunović, Mossel and Rácz5] evolves with time, whereas the underlying network (i.e. $\mathbb{T}_{m}$ ) in our model remains fixed throughout.

2. (ii) In [Reference Antunović, Mossel and Rácz5], the colour of each vertex, once chosen, remains fixed throughout, whereas in our model, every vertex gets the opportunity of updating its choice of which technology to adopt during every epoch.

Our analysis relies on the deduction and resolution of recursive distributional equations (see (10)), and since we are, ultimately, interested in the limiting joint distribution of the technologies adopted by all the agents on $\mathbb{T}_{m}$ , i.e. the limit of the joint distribution of $\left(C_{t}(v)\,:\,v \in V\left(\mathbb{T}_{m}\right)\right)$ as $t\rightarrow\infty$ , recursive distributional equations seem to be the most direct and effective approach to our problem. On the other hand, recurrence relations of the forms given by equations (2) and (3) in [Reference Antunović, Mossel and Rácz5] seem to be the most obvious approach to analysing the dynamics of the set-up studied in [Reference Antunović, Mossel and Rácz5], following which it is natural to study these recurrence relations as a stochastic approximation process. While (1) does relate $C_{t+1}(v)$ , for each v and each $t\in\mathbb{N}_{0}$ , with $C_{t}(v_{i})$ and $X_{t}(v_{i})$ for $i\in\{1,2,\ldots,m\}$ , where $v_{1},\ldots,v_{m}$ are the children of v, it does not take the same form as a stochastic approximation process, since we cannot get a recurrence relation directly connecting the random variables $C_{t+1}(v)$ and $C_{t}(v)$ . Having said this, we speculate that when studying similar models of social learning involving (possibly) more complicated update policies, it may be the case that the sequence of random variables $\left\{C_{t}(v)\,:\,t\in\mathbb{N}_{0}\right\}$ for each $v\in V\left(\mathbb{T}_{m}\right)$ (or perhaps some other, more suitable, statistic, as a function of time) can be expressed as a stochastic approximation process, and from there onward, the techniques used in [Reference Antunović, Mossel and Rácz5] may prove to be very helpful.

As a sequel to [Reference Antunović, Mossel and Rácz5], we mention here [Reference Haslegrave and Jordan54], wherein a conjecture, postulating that an extension of the model studied in [Reference Antunović, Mossel and Rácz5] to more than two opinions exhibits the same behaviour as its two-opinion counterpart (in that there is almost sure convergence to a limit which is a stationary point of a multidimensional vector field), is shown to be false. In the counterexample proposed in [Reference Haslegrave and Jordan54], each agent/vertex may adopt one of three available opinions, and the opinion-assignment mechanism (for the incoming vertex) is inspired by the game of ‘rock-paper-scissors’. Another work closely related to [Reference Antunović, Mossel and Rácz5] is [Reference Jordan59], wherein the class of attachment models studied in [Reference Antunović, Mossel and Rácz5] is extended in order to take into account the possibility that the two types (or colours, i.e. red and blue, as mentioned in the previous paragraph) have different fitnesses (for instance, one of the types may be favoured, or seen as having higher fitness than the other), inspired by the multiplicative fitness model (see [Reference Bianconi and Barabási18]) as well as the additive fitness model (see [Reference Ergün and Rodgers1]). Finally, in [Reference Haslegrave, Jordan and Yarrow55], the work accomplished in [Reference Antunović, Mossel and Rácz5] is extended to take into account a community structure in the network, and whether the proportions of vertices of each type synchronize between communities has been investigated.

Our learning model is also relevant in the context of social learning, a term that was first coined in [Reference Ellison and Fudenberg39]. In [Reference Ellison and Fudenberg39], each economic agent decides between two technologies, whose relative profitability is unknown, by taking into account the experiences of its neighbours and via exogenously specified rules of thumb that ignore historical data. Two learning environments are considered in [Reference Ellison and Fudenberg39], in one of which the same technology is considered optimal for all agents, whereas in the other, each technology is better for some of the agents. In [Reference Ellison and Fudenberg40], economic agents rely on information obtained via word-of-mouth communication in order to make decisions, without knowing the costs and benefits of the available choices. Two scenarios are considered in [Reference Ellison and Fudenberg40], the first of which allows a choice between two competing products with unequal qualities or pay-offs, while the second allows a choice between two products that are equally good. In [Reference Bala and Goyal7], when the pay-offs from the various possible actions are unknown, agents use their own past experience as well as the experiences of agents belonging to their neighbourhoods to guide them in their decision-making, and a general framework to study the relationship between the structure of these neighbourhoods and the process of social learning is proposed and analysed. In [Reference Bala and Goyal8], an approach to network formation is presented assuming that the link formed by one agent with another allows the former access, in part and in due course, to the benefits available to the latter via their own links, and that the cost of formation of a link is incurred only by the agent who initiates the formation, thereby allowing the network formation process to be formulated as a non-cooperative game. In [Reference Watts99], the process of network formation in a dynamic framework is analysed, with agents being allowed to form and sever links with one another, while in [Reference Mele73], agents are assumed to meet sequentially at random, myopically updating their links. More about the topic of social learning, as well as about learning models based on networks of agents, can be found, in, for example, [Reference Brown and Reingen21], [Reference Goldenberg, Libai and Muller45], [Reference Goldenberg, Libai and Muller46], [Reference Banerjee and Fudenberg10], [Reference Fudenberg and Levine41], [Reference Goyal47], [Reference Goyal48], and [Reference Mobius and Rosenblat78].

As is evident from the description presented in Subsection 1.2, in our model of social learning, an agent located at a vertex v decides upon the technology to adopt for a particular epoch entirely on the basis of the technologies chosen, and the outcomes achieved thereby, by the agents located at the children of v during the previous epoch. If we identify an agent with the vertex at which it is stationed, then the above implies that a vertex ‘learns’ from its children. This aspect of our model is inspired by the notion of pure altruism, commonly used in models of intergenerational altruism, such as in [Reference Barro12] and [Reference Loury70]. As described in [Reference Galperti and Strulovici42], which proposes an axiomatic theory of pure, direct altruism with altruistic, forward-looking preferences, a generation exhibits pure altruism if it derives utility, besides possibly from its own consumptions, from its descendants’ overall utility or well-being. Altruism is said to be direct if it directly depends on the well-being of all future generations (for instance, environmental policies chosen with a regard to all future generations reflect direct altruism towards these generations). The approach adopted in [Reference Barro12] is also examined in [Reference Michel, Vidal, Thibault, Kolm and Mercier Ythier74]—this approach to intergenerational altruism assumes that successive generations are linked by recursive altruistic preferences, and that individuals have an altruistic concern only for their children, who, in turn, have altruistic feelings towards their own children, and so on. In [Reference Becker and Barro13], too, the model studied assumes the dependence of a parent’s utility on the children’s.

Models for social learning serve as frameworks for the dissemination of technologies throughout a population of agents forming a specified network. In [Reference Chatterjee and Xu25], in a population of myopic, memoryless agents stationed at the integer points of $\mathbb{Z}$ , each agent, at each time step, performs an experiment using one of two technologies available to them, then observes the technology choices and the corresponding outcomes of its two nearest neighbours and of itself. Two learning rules are considered, with the first allowing an agent to change its technology only if it has experienced a failure, and the second allowing each agent to update its technology on the basis of the neighbourhood average. In [Reference Bandyopadhyay, Roy and Sarkar9], each $x \in \mathbb{Z}$ is occupied by an agent, and each agent, at each time step, is allowed to adopt one of two available technologies: B and R. An agent retains the technology it adopted in the previous time step if it achieves success using that technology. Otherwise, it observes the technologies adopted, and the outcomes achieved as a consequence, by its two nearest neighbours, and it opts for a change, say from B to R, only if, among its neighbours and itself, the proportion of successes with R is strictly bigger than the proportion of successes with B. In [Reference Young102], models for (i) the spread of a contagion, (ii) the spread of social influence, and (iii) social learning are formulated at a high level of generality, allowing there to be essentially any distribution of heterogeneous characteristics among the agents concerned, and key differences in their dynamical structures and in their patterns of acceleration are pointed out. In [Reference Lamberson62], agents decide whether to adopt a new technology, with unknown pay-offs, on the basis of their prior beliefs and the experiences of their neighbours in the network, and it is shown, with use of the mean-field approximations, that this process of diffusion always has at least one stable equilibrium. In [Reference Sethi and Yildiz89], each agent (i) possesses unobservable perspectives, (ii) receives private information about the current state and forms an opinion, and (iii) chooses a target agent (different from itself) and observes the target’s opinion.

In [Reference Chatterjee and Dutta24], an individual outside the network, termed the firm, has private information regarding the quality of the technology it seeks to diffuse throughout the network, and may pay some agent in the network, known as an implant, to propagate its product or idea. Each agent observes the actions of its neighbours over time in order to decide whether to adopt the new technology. Agents are either innovators who always adopt the new technology or standard players who are fully rational and make decisions based on utility maximization. What the firm knows about the interactions of agents with other agents is restricted to the neighbours of the implant chosen, if any exists. In such a model, learning occurs via strategic choices by agents, and this plays a role in determining whether diffusion occurs throughout the whole population or dies out within some finite distance of the origin. In [Reference Bharathi, Kempe and Salek17], a game of innovation diffusion with multiple competing innovations, such as when multiple companies market competing products using viral marketing, is studied, wherein an individual’s decision whether to adopt a product or innovation is highly dependent on the choices made by the individual’s peers or neighbours in the underlying social network. In [Reference Domingos and Richardson35], it is proposed that, instead of simply comparing the cost of marketing to a customer with the expected profit to be generated from that customer, one should take into account the customer’s network value, i.e. the expected profit from sales to customers whose choices the customer may influence directly or in a recursive manner. In [Reference Kempe, Kleinberg, Tardos, Caires, Italiano, Monteiro, Palamidessi and Yung60], the target set selection problem is studied for the decreasing cascade model, i.e. [Reference Kempe, Kleinberg, Tardos, Caires, Italiano, Monteiro, Palamidessi and Yung60] investigated the choice of the initial set of active vertices such that the cascade (which is the extent to which an innovation or behaviour spreads through the social network under consideration when the influence that an individual’s friends and acquaintances have over that individual’s decision to purchase or adopt the innovation is leveraged) resulting from this initial active set is as large as possible in expectation. We also mention here [Reference Mossel and Roch79], in which a conjecture of [Reference Kempe, Kleinberg, Tardos, Caires, Italiano, Monteiro, Palamidessi and Yung60] is established. In [Reference Watts100], a sparse random network of interacting agents, in which each agent’s decision is determined by the actions of its neighbours via a simple threshold rule, is studied, and two regimes, in which the network is susceptible to very large cascades or global cascades, are identified. In [Reference Lelarge64] (see also [Reference Lelarge63]), a model of diffusion, with two available strategies, is studied wherein each agent, at each point in time, chooses the strategy with the best pay-off, given the strategies currently adopted by its neighbours. In [Reference Lelarge64], criteria under which one of the strategies becomes widespread throughout a random network are proposed, the game’s equilibria are analysed, and conditions under which both strategies may coexist in large connected sets are identified. Numerous other studies exist in the literature on models studying the diffusion of technologies, such as [Reference Tsakas95], [Reference Namatame, Morita and Matsuyama82], [Reference Tsakas96], and [Reference Namatame, Pan, Tsihrintzis and Virvou81].

A third motivation for studying our model arises from its interpretation as a PTA. PTAs admit a very general definition, such as discussed in [Reference Ellis38], but in this case it suffices to define a PTA (on $\mathbb{T}_{m}$ ) as a state machine that consists of two components, namely (i) a finite set $\mathcal{A}$ of symbols or colours known as the alphabet and (ii) a stochastic update rule given by a stochastic matrix $\varphi\,:\, \mathcal{A}^{m} \times \mathcal{A} \rightarrow [0, 1]$ . For any vertex $v \in V(\mathbb{T}_{m})$ , letting $v_{1}, v_{2}, \ldots, v_{m}$ denote its children, and conditioned on $\left(\eta_{t}(v_{1}), \eta_{t}(v_{2}), \ldots, \eta_{t}(v_{m})\right)$ , where $\eta_{t}(v_{i}) \in \mathcal{A}$ denotes the symbol assigned to $v_{i}$ at time step t for each $i \in \{1,2,\ldots,m\}$ , the symbol assigned to v at time step $t+1$ is a random variable $\eta_{t+1}(v)$ whose probability distribution is given by

\begin{align*}\operatorname{\mathbb{P}} {\big[\eta_{t+1}(v)=\alpha\big| {\eta_{t}(v_{1})},{ \eta_{t}(v_{2})}, \ldots, {\eta_{t}(v_{m})}\big]} = \varphi {\left(\left(\eta_{t}(v_{1}), {\eta_{t}(v_{2})}, \ldots,{ \eta_{t}(v_{m})}\right), \alpha\right)} \,\,\, {\text{for each}} \ {\alpha} {\in} {\mathcal{A}}. \\[-10pt]\end{align*}

The update from $\eta_{t}(v)$ to $\eta_{t+1}(v)$ is assumed to happen independently over all $v \in V(\mathbb{T}_{m})$ . One of the primary questions asked about a PTA is the enumeration and characterization of all its fixed points: a joint law $\nu$ of $\left\{\eta_{0}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}$ is called a fixed point of the PTA under consideration if the joint law of $\left\{\eta_{1}(v)\,:\, v \in V(\mathbb{T}_{m})\right\}$ is also $\nu$ . This is also the question we seek to answer in this paper for our model. More on PTAs (and their deterministic counterparts, endowed with update rules that are deterministic), as well as their applications, can be found in, for example, [Reference Cohen, Kimelfeld and Sagiv27], [Reference Bernabeu, Calera-Rubio, Iñesta and Rizo15], [Reference Carayol, Haddad and Serre22], and [Reference Comon, Dauchet, Gilleron, Jacquemard, Lugiez, Löding, Tison and Tommasi28].

We conclude this section with [Reference Pemantle84], which provides an extensive survey of the tools and techniques—primarily (i) martingales and the stochastic approximation and (ii) dynamical systems and their stochastic counterparts—that are used in the analysis of stochastic processes with reinforcements (such as urn processes, reinforced random walks, reinforced diffusions, and processes with negative reinforcement such as self-avoiding walks). Stochastic models involving learning, such as the one studied in this paper, often exhibit reinforced behaviour (in the sense that the agents are often more inclined to select technologies that seem to bring greater rewards), and we speculate that the array of tools and techniques described in [Reference Pemantle84] would prove to be very useful in the analysis of many such models that are dictated by complicated learning rules.

1.5. Organization of this paper

The rest of this paper is organized as follows. The proof of Theorem 1 is presented in Section 2, with Subsections 2.1, 2.2, and 2.3 respectively addressing parts 1, 1, and 1. The proof of Theorem 2 is outlined in Section 3. Theorem 3 is proved in Section 4, and this section includes, as part of the proof, the statements and proof of the crucial Theorem 5, Lemma 1, and Theorem 6. In Subsection 4.1, the value of p(m), as defined in the statement of Theorem 3, is explicitly computed, by analytical means, for $m=3$ and $m=4$ . The proof of Theorem 4 is provided in Section 5. Finally, since we are not able to provide a mathematically rigorous analysis even for relatively small values of m (such as $m=3$ ) when completely arbitrary values of $(\, p_{B},p_{R}) \in [0,1)^{2}$ are considered, Section 6 is dedicated to a detailed discussion, culminating in a conjecture and supported by several examples, of what we believe happens when we consider general values of $p_{B}$ and $p_{R}$ for $m=3$ .