A contact process with mutations on a treeby Thomas M. Liggett∗, Rinaldo B. Schinazi, Jason Schweinsberg†University of California at Los Angeles,University of Colorado at Colorado Springsand University of Califor nia at San DiegoDecember 18, 200 6AbstractConsider the following stochastic model for immune response. Each pathogen gives birthto a new pathogen at rate λ. When a new pathogen is born, it has the same type as itsparent with probability 1 − r. With probability r, a mutation occurs, and the new pathogenhas a different type from all previous ly observed pathogens. When a new type appears inthe population, it survives for an exponential amount of time with mean 1, independentlyof all the other types. All pathogens of that type are killed simultaneously. Schinazi andSchweinsberg (2006) have shown that this model on Zdbehaves rather differently from itsnon-spatial version. In this paper, we show that this model on a homogeneous tree capturesfeatures from both the non-spatial version and the Zdversion. We also obtain comparisonresults between this mo del and the bas ic contact process.1 IntroductionSchinazi and Schweinsberg (2006) have recently introduced a non-spatial and a spatial versionof the following stochastic model for immune response. For the non-spatial version (Mod el 2 intheir paper), each pathogen gives bir th to a new pathogen at rate λ. When a new pathogen isborn, it has the same type as its parent with probability 1 − r. With probability r, a mutationoccurs, and the new pathogen has a different type f rom all p reviously observed pathogens. Whena new type app ears in the population, it survives for an exponential amount of time with mean1, indepen dently of all the other types. All pathogens of that type are killed simultaneously.For the spatial version (Model S2 in Schinazi and Schweinsberg (2006)), let S be the squarelattice Zdor the homogeneous tree Tdin which every vertex has d + 1 neighbors. Let x be a sitein S occupied by a pathogen and y be one of its nearest neighbors. There are 2d such neighborsin Zdand d + 1 in Td. After a random exponential time with rate λ, the pathogen on x gives∗Partially supported by NSF grant DMS-0301795†Partially supported by NSF grant DMS-0504882Key words and phrases: mutation, immune system, branching process, spatial stochastic model, contact process2000 Mathematics Subject Classification: 60K351birth on y, provided y is empty (if y is occupied nothing happens). With probability 1 − r th enew pathogen on y is of the same type as the parent pathogen on x. With probability r the newpathogen is of a d ifferent type. We assume that every new type that appears is different from alltypes that have ever appeared. As in the non-spatial mod el, we assume that each type survivesfor an exponential amount of time with mean 1, independently of all other types, and that allpathogens of a type are killed simultaneously.Biological motivation has been provided in Schinazi and Schweinsberg (2006). There is alsosome obvious motivation for such a model for the spread of a virus in computer n etworks. Inparticular, when a vir us is discovered in a computer network it is usually destroyed at once. It isalso interesting to test the influence of particular network topologies on th e spread of a virus; seefor instance Pastor-Sattoras and Vespignani (2001), Berger et. al. (2005), Ganesh et. al. (2005),and Draief et al. (2006).Schinazi and Schweinsberg (2006) have shown that the pathogens survive in the non-spatialmodel with positive probability if and only if λ > 1 and r > 0; see their Theorem 1.2. In contrast,for the spatial model on Zdthey have shown that if λ is large enough then th e pathogens survivewith positive probability for large r and die out with probability 1 for small r; see their Theorem4. Given that a ball of radius R has of the order of dRsites in the homogeneous tree Tdonemight conjecture that the behavior of the spatial model on Tdis similar to that of the non-spatialmodel (there are so many sites on the tree that space may not be a limitation). As the readerwill see in the next section, this is not so. In fact, the model on the tree captures both featuresfrom the model on Zdand from the non-spatial model. These results will be stated in Section 2and proved in Sections 4 and 5.The basic contact process may be thought of as being a particular case of this model withr = 1. See Liggett (1999) for background and results on the contact process. For r = 1, allpathogens are of different types and therefore only one pathogen dies at a time. Hence, onemight conjecture that the model with r = 1 has a better chance of surviving than any modelwith r < 1. This turns out to be true but requires nontrivial arguments. This will be done inSection 3. This comparison result applies to any graph.2 Phase transitionsWe say that the pathogens survive on a graph S if th ere is a positive probability that at all timesthere is at least one pathogen somewhere in S. If the pathogens do not survive they are said todie out.Theorem 1. Consider the contact process with mutations on the homogeneous tree Tdwith d ≥ 2,started with a single pathogen of type 1.1. If λ >1d−1then the pathogens survive for all r > 0.2. If λ ≤1d−1+2rthen the pathogens die out. In particular, if λ ≤1d+1, the pathogens die outfor all r ≥ 0.3. If1−d+√(d−1)(7+9d)2(d2−1)< λ <1d−1the pathogens die out for r close to 0 and survive for r closeto 1.2These results will be proved in Sections 4 and 5.Note that for all d ≥ 2, the left-hand side of the inequality in Theorem 1.3 is strictly smallerthan the right-hand side. Therefore, Theorem 1.3 shows that for intermediate values of λ thereis a phase transition in r. Moreover, the difference between the right and left sides of Theorem1.3 is asymp totic to23d2as d ↑ ∞. Combining Theorem 1.1 and 1.2 , we see that the set of λ’sfor which there is a phase transition in r is of size asymptotically at most2d2. So, up to a factorof three, we have found the correct size of this set.We now turn to another type of phase transition. L et Atbe the set of sites that are occupiedby any pathogen. The process is started with a single pathogen at the site x. Recall thatpathogens are said to survive ifP (At6= ∅, ∀t > 0) > 0. (1)The pathogen s are said to survive weakly if (1) holds andP (x /∈ Atfor sufficiently large t) = 1. (2)That is, with positive prob ability, there are pathogens somewhere in S for all