key: cord-0148440-93o2d2j5 authors: Fibich, Gadi; Nordmann, Samuel title: Exact description of SIR-Bass epidemics on 1D lattices date: 2021-02-01 journal: nan DOI: nan sha: ce895c376aae1183a155a65859cf3808dc056ee6 doc_id: 148440 cord_uid: 93o2d2j5 This paper is devoted to the study of a stochastic epidemiological model which is a variant of the SIR model to which we add an extra factor in the transition rate from susceptible to infected accounting for the inflow of infection due to immigration or environmental sources of infection. This factor yields the formation of new clusters of infections, without having to specify a priori and explicitly their date and place of appearance.We establish an {exact deterministic description} for such stochastic processes on 1D lattices (finite lines, semi-infinite lines, infinite lines, circles) by showing that the probability of infection at a given point in space and time can be obtained as the solution of a deterministic ODE system on the lattice. Our results allow stochastic initial conditions and arbitrary spatio-temporal heterogeneities on the parameters.We then apply our results to some concrete situations and obtain useful qualitative results and explicit formulae on the macroscopic dynamics and also the local temporal behavior of each individual. In particular, we provide a fine analysis of some aspects of cluster formation through the study of {patient-zero problems} and the effects of {time-varying point sources}.Finally, we show that the space-discrete model gives rise to new space-continuous models, which are either ODEs or PDEs, depending on the rescaling regime assumed on the parameters. This paper is devoted to the study of a stochastic epidemic model on 1D (directed or undirected) lattices with a general epidemic source term and arbitrary heterogeneity on the parameters and initial conditions. Our model is a variant of the stochastic SIR model, originally introduced in its deterministic version by Kermack and McKendrick [39] , which forms the framework of almost any model used in epidemiology. Despite the extensive literature on the SIR model (see, e.g., the books of Bailey [6] , Anderson and May [1] , Mollison [43] and the review of Heathcote [30] ), some fundamental and practical questions remain open. In the current context of the propagation of the COVID-19, an in-depth study of this model and its variants is a major challenge. In addition to the usual mechanism of contagion occurring in epidemics, we also assume the presence of an epidemiological source term, qualified as "external influences". This term acts as an additional mechanism that leads to the transition from susceptible to infected, which does not depend on the level of infection in the population, and accounts for the inflow of infection due to immigration or environmental sources of infection. In our framework, it is allowed to depend on space and time. From a modeling point of view, dealing with external influences is important since they yield the formation of new clusters of infections, without having to specify a priori and explicitly their date and place of appearance. Such external influences are not traditionally included in the SIR model and refer more to the Bass model [10] , originally introduced to describe the diffusion of new products. In the marketing context, external influences account for the spontaneous adoptions of the product induced by advertising or mass media, while "social imitation" and "word of mouth" are formally regarded as a "contagion" mechanism. In turn, the population of potential adopters of a product (resp. adopters) are seen as formal analogs of the population of susceptible (resp. infected) in the epidemiology context. Although each modeling situation has its own specificities, we keep a unified approach to both phenomena. In what follows, we use more frequently the terminology borrowed from epidemiology, but our considerations can be transposed to the context of the adoption of a new product. Let us mention that the recovery of infected individuals operating in the SIR model is also relevant in the marketing context even though it has not been included in the Bass model until recently [23] . Similar models are also used in other social situations: propagation of riots [11, 22] , rumours [14, 20] , etc. The main goal of the present paper is to establish an exact deterministic description for such stochastic SIR-Bass epidemics on 1D lattices. Specifically, we show that the probability of infection at a given point in space and time can be obtained as the solution of a deterministic ODE system on the lattice. We then apply our results to some concrete situations and obtain useful qualitative results and explicit formulae. In particular, we provide a fine analysis of some aspects of cluster formation through the study of patient-zero problems and the effects of time-varying point sources. For simplicity and a clear presentation of our results and methodology, we focus in this paper on 1D lattices (i.e., finite, semi-infinite, and infinite lines) where the infection only occurs from a node to its direct neighbors. Our approach can be adapted without difficulties to the case where the contact network is a tree (i.e., a graph with no cycles). Some of our ideas may also apply to a more general context, which will be the subject of future works. As a counterpart to the strong assumption on the structure of the graph, we try to keep the assumptions on the parameters and initial conditions as broad as possible by allowing any type of spatial-temporal heterogeneity of the coefficients. Understanding the effect of such local heterogeneities, even for simple networks, is still a major challenge in epidemiology [44, Section 1] . We emphasize that our results provide an exact description of the process at the individualscale, that is, we describe both the macroscopic dynamics of the epidemics and the local temporal behavior of each individual. This takes us one step further than the usual description at the population-scale through aggregate quantities such as the expected fraction of infected individuals in the population. Such a spatial-temporal description at the local scale is required for predicting population-level dynamics from individual-level observations, all the more in the situation of strong heterogeneities. Outline. We give a brief state of the art of the mathematical epidemiology literature in Section 1.2, which allow us to present the context of our study, to motivate it, and to highlight the novelty of our results. Our mathematical framework and its link with classical models are presented in Sections 2 and 3. We first present and prove our results dealing with 1D one-sided lattices in which the contagion can only occur in one direction. We focus in Section 4 on the Bass model when there is no recovery. Section 5 deals with the full SIR-Bass model. Our main results (Theorem 1, Theorem 8) establish that the probability of a certain node to be susceptible at some time satisfies a differential equation which is continuous in time and discrete in space. This provides an exact spatial-temporal deterministic description of the stochastic process, for any type of heterogeneity on the parameters and stochastic initial conditions. We then use these results to perform a further analysis and derive explicit formulae in several typical situations, such as the spatially homogeneous case (Proposition 4, Proposition 10), the patient-zero problem (Proposition 5, Proposition 13), and the case of a timevarying point sources (Proposition 7, Proposition 12). We also propose a further analysis on the speed of propagation of epidemics (Proposition 6) as well as a detailed comparison of our model with the classical aggregate SIR model (Section 5.3). In Section 6, we extend our results to two-sided 1D lattices (corresponding to an undirected underlying graph) in which epidemics can propagate in both directions. We derive a new useful formula that expresses the probability of infection in a two-sided lattice in terms of the probabilities of infections in one-sided lattices. In Section 7, we discuss two different space rescalings giving rise to either a limiting space-continuous ODE or a limiting PDE coupling time and space. Finally, we give some concluding remarks in Section 8. To present the context of our work, we provide a brief overview of the mathematical study of epidemiological models. Most epidemiological models proposed in the literature fall into two broad categories: a deterministic approach using either ODEs [31, 38] or PDEs of the reaction-diffusion type [17, 18, 46, 52] , and a stochastic approach using individual-centered Poisson processes (agentbased models) [1, 6] . The deterministic and stochastic approaches have mostly developed in parallel in the literature. In general, deterministic models can be obtained as the "mean-field" limits [40, 50] of stochastic models. Mean-field models describe the average dynamics and typically apply to sufficiently large populations where stochastic fluctuations and individual variabilities are negligible [41] . They have the advantage of being more amenable to analysis and to give a clear idea of some qualitative aspects of epidemic dynamics. Deterministic models are particularly useful to study the spatial speed of propagation and the shape of the propagation front of epidemics [4, 19, 32] . On the other hand, stochastic models are capable of reproducing observed data way more accurately, both quantitatively and qualitatively, see, e.g., [6, Section 5.1 & 7] and [43] . The main reasons for this are, firstly, that stochasticity may have a dramatic influence on the overall dynamics since small populations are involved (for example during the outbreak of an epidemic) and, secondly, that the stochastic framework is readily well suited for the incorporation of strong heterogeneities or complex social structures which are known to be of tremendous importance in epidemics propagation. The simplest models, referred to as aggregate or compartmental models, assume that the population is homogeneously mixed [6, Section 5.10] , that is, the connectivity between two individuals is constant among all pairs of individuals. In this situation, individuals are interchangeable and so the behavior of the system can be described by aggregate quantities (such as the expected fraction of infected individuals). The classical analysis of these models relies on strong symmetry assumptions on the parameters and initial conditions [40, 41] . However, many studies reveal that homogeneous mixing only holds in small groups but not in large populations, see e.g. [6, Section 5.10] and [37] . Intuitively, at the scale of a city, it does not make sense to assume that an individual interacts as much with members of his family as with a socially unrelated individual living on the other side of the city. The limited number of interactions of each individual tends to hinder the spread of infection and to cause the formation of localized clusters. For these reasons, the network within which social interactions occur has a dramatic impact on the epidemic propagation, and so aggregate models turn out to be inaccurate to describe the spatial-temporal dynamics of the epidemics. A more elaborate approach is to consider that each individual interacts only with a relatively small subset of the population. The connectivity between individuals is usually encoded by a weighted graph, called contact network in the epidemiology context [3, 36] . We point out that this formalism assumes that social interactions are fixed once and for all, which is not a problem when considering a sufficiently short epidemic episode (evolving networks have also been proposed, see [21, 34] and references therein). Contact networks are typically sparse and may embed various social variables such as place of residence, age, profession, etc. The different classes of contact networks considered in the literature can be roughly classified according to their clustering level [5, 35] reflecting the extent to which the system is capable of generating and maintaining localized clusters of infections. For example, lattice networks [42, 47, 48] regard the population as placed on a regular grid of points with spatially localized connections, yielding a high clustering level; on the contrary, random networks [2, 8, 16] have a low clustering level since connections between individuals occur randomly regardless of their locations. Lattices and random networks appear as two opposite extreme instances, each one focusing on certain aspects of the dynamics observed in epidemics and discarding others. Small-world or scale-free networks have been proposed as examples of more realistic configurations, combining both localized and rare long-range connections, which display intermediate clustering levels. For more details, we refer the reader to the reviews of Keeling & Eames [37] , Britton [13] and Danon et. al. [15] . Let us emphasize here that lattices, especially 2D lattices, are the physically relevant contact networks when considering contagion phenomena that primarily depend on the physical distance between the infected and susceptible individuals, which happens to be the case in the propagation of some diseases such as Measles [29] or the diffusion of some products such as solar panels [12, 28] . Most of the approaches developed for studying complex networks make strong assumptions of homogeneity and symmetry at the individual-scale and are mainly concerned with aggregate quantities (such as the total number of infected) which describe the dynamics at the population level but fail to precisely grasp the dynamics at the individual-scale. It remains nevertheless a major challenge to understand the local behavior and the effects of strong heterogeneity [44, Section 1] . For example, the study of the patient-zero problem (where the epidemics spread from a single infected individual at initial time) or the influence of a spatially localized source of infection gives significant insights into the spatial propagation of epidemic clusters. Several approximation methods have been proposed to deal with complex networks with a high level of heterogeneity. The goal of these approaches is to provide deterministic approximations that go beyond the insufficient mean-field approximation, but that are still less computationally demanding and more amenable to analysis than the full stochastic models. The pair-approximation method [36, 45] consists in formally neglecting the possible intercorrelation between the nodes induced by cycles in the contact network. Under this formal approximation, the dynamics can be described by a system of ODEs featuring aggregate quantities such as the average number of neighbors per node and the ratio of triples of nodes which form an interconnected triangle (this quantity reflects the level of clustering of the contact network). While this method offers great flexibility and results which are quite in agreement with numerical simulations of the stochastic process, its theoretical ground is far from being completely understood. Other approximations have been proposed [9, 33] , such as degree-based models, probability generating function (PGF) formalism, edgebased compartment modeling, but all these methods can be derived from the pair-approximation method [33] . Regarding theoretical results and exact deterministic descriptions of the stochastic process, most of the studies, if not all, assume a tree-like structure on the contact network at some level. If the contact network is a tree-graph (i.e. a loopless graph), it is well known that the pair-wise approximation is exact [49] and yields an exact description of the stochastic process, namely, the probabilities of infection satisfy a system of ODEs. This allows a fine theoretical analysis of the dynamics. Results are also available when the graph has a local tree-like structure (such as random configuration networks [15] ) at the limit as the population size becomes large and under homogeneity assumptions [7, 15, 16] . As mentioned in the introduction, the present paper deals with 1D lattices, which are particular cases of tree-graphs, and for which exact equations are available. The novelty of our approach is in the combination of the following ingredients. Firstly, we study the SIR-Bass model, that is, we add to the classical SIR model an external source term accounting for a spontaneous inflow of infection; secondly we allow any heterogeneity on the coefficients and allow stochastic initial conditions; thirdly, we use the obtained exact deterministic description to perform a further analysis at a local scale and derive explicit formulae on some specific typical epidemiological instances; finally we show that the space-discrete model gives rise to new space-continuous models, which are either ODEs or PDEs, depending on the rescaling regime assumed on the parameters. In this paper, we consider time-discrete stochastic processes that converge to time-continuous processes as the time step tends to zero. Discrete and continuous models each have their own advantages: the former can be simulated numerically directly, while the latter is more amenable for analysis. Let us fix a time-step 0 < ∆t 1 and consider random processes represented by a family of random variables ((x n k ) k∈K ) n∈N , where x n k represents the state of individual k ∈ K at time t n := n∆t. The set K can be finite K = {1, . . . , K}, infinite K = Z d , or semi-infinite K = N. The state of individual/node k at time t n can be susceptible (x n k = s), infected (x n k = i), or recovered (x n k = r). We define the following events: S n k is the event that x n k = s, I n k is the event that x n k = i, R n k is the event that x n k = r, and denote their probabilities by The events S n k , I n k , R n k are disjoint and complementary, and so We assume that the stochastic dynamics in the time-interval (t n , t n+1 ) = (n∆t, (n + 1)∆t) is governed by the following mechanisms: • If node k is susceptible at t n , it can become infected -by a source term ("external influence") at a rate of p n k , -and by contagion from infected individual i ("internal influence") at a rate of q n ik . These effects are additive. • If a node k is infected at t n , it can recover at a rate of r n k . • If node k is recovered at t n , it remains so for all later times. The transition probabilities are thus given by where X n = (x n k ) k∈K is the state of the network at time t n , and by The parameters p n k , q n ik , r n k are nonnegative and may depend on space k and time n. We also assume that X n+1 is a family of random variables that are mutually independent when conditioned with respect to X n . This way, the process is well defined. The matrix (q ik ) K represents the weighted directed edges of the contact graph between the nodes. The state variables (x n k ) are coupled through the sum i∈K q n ik 1 I n i , see (2a). This term, which embeds the structure of the graph, has a central role in the analysis. As noted previously, in this paper we focus on the case of 1D (directed or undirected) lattices, where q n ik ≡ 0 when i = k ± 1. The starting point of the stochastic dynamics (2) is the initial conditions which are assumed to be uncorrelated random variables taking values in {s, i, r}. Thus, in terms of the probabilities [S n k ], [I n k ] and [R n k ], we consider the initial conditions In some applications, it is natural to consider deterministic (pure) initial conditions, where the initial state of each node is given in a deterministic way. This is a special case of (3), when x 0 k is determined with probability 1 among the possible states {s, i, r}. For example, in the SIR model, it is standard to assume that the epidemics start from "patients zero", and so that initially, all nodes are susceptible, except for a few which are infected. In the Bass model, the standard assumption is that the whole population is susceptible (non-adopters) when the new product is first introduced into the market. In this paper, we analyze the more general case (3) where the initial state of each node is given by a random variable. In addition to being more general from a mathematical point of view, dealing with stochastic initial conditions is important from an application point of view. For example, in the context of epidemiology, it may be that the only available information is the percentage of the population in each area which are infected. Similarly, in the context of the diffusion of a new product, sometimes only the fraction of the population that has adopted the product in each area is available, rather than a precise description of the state of each individual. As noted, the n superscript denotes a state variable evaluated at the discrete time t n = n∆t. Throughout the paper, we assume the following: Time-continuous limit assumptions. The parameters p n k , q n k and r n k in (2) converge to some functions p k (t), q k (t) and r k (t) respectively, as ∆t → 0 and n → +∞ so that t = n∆t is constant. Then, we classically have that the time-discrete process (x n k ) converges to a time-continuous Poisson-type process (x k (t)). We use the same notations as in the time-discrete setting, by replacing the dependence on n with a dependence on t. Thus, The time-continuous process is a Poisson-type process, defined as follows. The transition of individual k from susceptible to infected at time t occurs through an exponential law with the rate λ s→i , and from infected to recovered with the rate λ i→r k (t) = r k (t). The aggregate version of the above model (2) is obtained when the parameters and initial conditions do not depend on k, which corresponds to the case where the underlying graph is homogeneous and complete. In this case, in the limit as the population size becomes infinite, the dynamics is governed by the aggregate SIR-Bass model [23] which is given by the system of ODEs where S, I, and R represent the fraction of susceptible, infected, and recovered, respectively (or equivalentely the probability that any node is susceptible, infected, or recovered respectively). Similarily to (1), we have that If we take p = 0 in (4), i.e., we assume that there is no source term, then the SIR-Bass model reduces to the classical aggregate SIR model (see e.g. [31] ) To have a non-trivial dynamics in (6), we need to assume the presence of patient(s) zero, i.e., Alternatively, if we take r = 0 and R(t = 0) = 0 (i.e. assume that there is no recovery), then R(t) ≡ 0 and so by (5) we have I = 1 − S. Hence, (4) reduces to the original Bass model [10] : If we further assume that I(0) = 0, this leads to the Bass formula Finally, assuming no recovery (r = R(t = 0) = 0) and no source term (p = 0), the SIR-Bass model (4) reduces to the classical SI model We begin our analysis with the case of a 1D one-sided lattice, that is, when Therefore, infection of node k at time-step n can be caused either by a source term at the rate p n k , or by contagion from its left neighbor at the rate q n k . Hence, (2a) reduces to 1 and (2b) remains unchanged, that is: In this section, we focus on the Bass model case when there is no recovery, i.e., when This implies that [R n k ] ≡ 0 and so by (1), Therefore, (12a) and (12b) reduce to In what follows, we show that the probability [S n k ](t) of node k to be susceptible at time t n satisfies a deterministic discrete PDE (here, the term "discrete" means that the time and space derivatives are replaced by finite differences). We then let ∆t → 0 to deduce that the probabilities [S k ](t) satisfy a system of differential equations. Theorem 1 Assume that the nodes are placed on a 1D one-sided graph, see (10) , that the initial conditions are stochastic and uncorrelated, see (3) , and that there is no recovery, see (13) , so that the stochastic dynamics are governed by (15) where K is either a finite, semi-infinite or infinite line. Then for all k ∈ K, as ∆t → 0, [S k ] satisfies the differential equation In particular, if p ≡ p n k and q ≡ p n k are independent of k and n, then (16) reads 1 In the case of the semi-infinite line K = N, the transition probability for the boundary node k = 0 is Proof A straightforward computation gives In principle, we now have to deal with the term P(S n k ∩ S n k−1 ) which involves the 2-marginals of the process through the joint laws of x n k−1 and x n k . The 2-marginals, however, can be expressed through the 1-marginal ([S k ]) k∈K as follows. Let us write and compute each term of the product separately. First, since the initial conditions are uncorrelated, the variables x 0 k and x n k−1 are independent, hence This identity follows from the fact that there is no path from k to k − 1, therefore the computation of the probability P(S n k−1 ) through (15) does not involve x 0 k . Second, if k is not infected at initial time and k − 1 is not infected by t n , then k can only become infected through the source term p k . In this case, node k remains susceptible during the time interval (t n , t n+1 ) with a probability 1 − p n k , i.e., Note by the way that identities (20)- (21) does not hold if the graph is a circle (i.e. K = Z/KZ) since, roughly speaking, node k − 1 can become infected by an epidemic starting from k. Substituting (21) and (20) in (19), we derive the closure identity Finally, plugging (22) into (18), one gets Letting ∆t → 0 gives the result. The key element in the proof is the closure identity (22) . This identity holds pointwise whenever a node is only influenced by a single node. Therefore, even if we drop the assumption that the graph is 1D and let it be general, relation (16) still holds pointwise at any node which is only influenced by a single node. The initial conditions [S 0 k ] explicitely appear in ODE (16) for [S k ], and not just in the initial conditions. As mentioned already, the case of deterministic initial conditions is a special case where [S 0 k ] ∈ {0, 1}. Theorem 1 provides a spatial-temporal deterministic description of the stochastic dynamics (15) . Once compute the solution [S k ](t) through equation (16), we can complete the description of the stochastic process, as follows: [I k ] is deduced from (14), the second-order marginals can be computed using the closure identity (22) , and any higher-order marginal can be computed using the same methodology. We emphasize that equation (16) on [S k ](t) is exact and does not result from any approximation (such as the mean-field approximation) or from the assumption that the population is infinite. In the spatially-homogeneous case, one can obtain explicit solutions of (16): do not depend on space k (we allow, however, p and q to depend on time t), then [S k ](t) = [S](t) does not depend on k, and is given by Proof By translation symmetry, [S k ](t) does not depend on k. Hence, equation (16) reads Expression (24) follows from a straightforward integration of the above equation. If, in addition to the assumptions of Proposition 4 , p and q do not depend on t, then This expression was already obtained in [25] for p > 0 and [S 0 ] ≡ 1. Another situation where an explicit solution can be calculated is that of a semi-infinite line when the boundary node is infected at t = 0 and all other nodes are initially susceptible: Assume the conditions of Theorem 1, let p k (t) ≡ p and q k (t) ≡ q be independent of k and t, and let the nodes be placed on the semi-inifinite line (17) is given by In addition, if we denote by N K (t) = K k=1 1 x k (t)=i the total number of infected nodes among nodes {1, . . . , K}, then Proof Expression (26) can be verified by direct substitution in (17) . Expression (27) , follows from (14), (26) and some elementary computations detailed in Appendix A.1 Let us briefly justify the importance of the patient-zero Bass problem considered in Proposition 5. When the source term p is much smaller than the contagion term q, the dynamics of the population can be formally described in two time scales: propagation of clusters through contagion in a fast time-scale, and spontaneous creation of new seeds in a slow time-scale [25] . The patient-zero Bass problem thus models the fast time-scale evolution of clusters. Passing to the limit in (26), we have that This limit coincides with the expression for [S k ] in the homogeneous case with [S 0 k ] ≡ 1, see (25), since the effect of patient zero vanishes as k → +∞. Note also that, as K → +∞, the expected fraction of infected nodes is given by, see (27), which expresses again the fact that the solution of the patient zero problem converges to the homogeneous solution given by (25) as K → +∞. In Proposition 5, the epidemic is triggered by two distinct mechanisms: firstly, by contagion from "patient-zero" located at k = 0, secondly, by spontaneous infection from the source term p. Expression (26) indicates how these two effects combine nonlinearly. To focus on the effect of the source term, we may remove "patient zero" and assume that all the individuals on the half-line are initially susceptible. In this case, it can be shown that the probability [S k ](t) coincides with the probability of a node to be susceptible on a finite circle of length k. Therefore, it can be computed explicitly, see [27] for more details. If, on the other hand, we only focus on the effect of contagion from "patient-zero", we may discard the source term by letting p → 0 in (26) . This gives the solution of the patient-zero SI problem By (30), for any k ≥ 1 and t > 0, we have on the one hand that S k (t) > 0, implying that the epidemics propagates instantaneously from "patient zero" to any other node. On the other hand, lim k→+∞ S k (t) = 1 for any t > 0 implying that the propagation occurs at a finite asymptotic speed. In fact, we can show that the asymptotic speed of propagation is q: Proposition 6 (Speed of propagation) Assume the conditions of Proposition 5 and assume furthermore that p = 0 (SI patient-zero problem). Denote by k(t) = sup{k ≥ 0 : x k (t) = i} the location of the propagation front of the epidemic. Then, for all α ∈ R, Proof The process k(t) is equivalent to a standard Poisson process with parameter q. It is then classical that the mean value of k(t) is t. Then, by the central limit theorem, we have that k(t)−t √ t converges in probability when t → +∞ to a Gaussian with mean 0 and variance q √ t, hence the result. Thus the epidemics propagate through space at an average speed q, such that the exact location of the front has a variance q √ t around its mean value. Therefore, we can make a formal analogy between the propagation of the epidemics and the propagation of particles whose density u(t, x) is given by the advection-diffusion equation [51] This equation describes the evolution of a density of particles subject to advection towards x > 0 at speed q (resulting in propagation at average speed q) and to diffusion (i.e., each particle follows a Brownian motion) with diffusivity q 2 (resulting in a variance q for the location of the propagation front). Finally, we compute an explicit solution for a time-varying source term located at the boundary of a semi-infinite line: Assume that q k (t) ≡ q > 0 is constant, that p k (t) ≡ 0 for all k ≥ 1, and allow a single time-varying source term p 0 (t) ≥ 0 at k = 0. Then Proof Under the above assumptions, equation (16) reduces to and The expression of [S 0 ](t) in (31) is obtain by a straightforward integration of (33). Using (14) , equation (34) yields Hence, By induction, we infer that where we have used the associativity of the convolution product. Now, In addition, a straightforward induction shows that Plugging (37) and (38) into (36) gives (31) . Let us now prove (32) . For a fixed k ∈ {0, 1, . . . }, by the dominated convergence theorem, we have this concludes the proof of (32). The limit (32) does not depend on k and, in particular, coincides with the limit as t → +∞ of p0 . This limit can be obtained formally by passing to the limit in (16) . Note also that, for a fixed t ≥ 0, as k → +∞ in (31), we get that [S k ](t) → 1. This expresses the fact that, with probability 1, the source term located at k = 0 does not influence far-away nodes in finite time, since the epidemics propagates at a finite speed (see Proposition 6) . Note that by formally putting p 0 (t) := Kδ t=0 in (31), where K > 0 and δ t=0 denotes the Dirac mass centered at 0, then we recover the formula (26) with p = 0 for the patient-zero problem as K → +∞. We now consider the more general 1D one-sided case, when recovery is not neglected, see (12). We begin by deriving from the discrete stochastic model (12) a system of differential equations for [S k ](t): Theorem 8 Assume that the nodes are placed on a 1D one-sided lattice, see (10) , that the stochastic dynamics are governed by (12) , and that the initial conditions are stochastic and uncorrelated, see (3) . For any k ∈ K, if q k (t) > 0 for all t ≥ 0, then [S k ](t) satisfies Proof In the following calculations, we frequently make use of the identities We have that and so P S n+1 k − P (S n k ) ∆t + p n k P(S n k ) + q n k P S n k ∩ I n k−1 = 0. Using the closure relation (22), we deduce that Substituting this expression into (41), we deduce Letting ∆t → 0, we finally deduce Next, let us derive an equation for [S k ∩ R k−1 ]: Using (22) and the relation At this stage, equations (44) and (46) Using equations (44) and (46) Therefore, and so Substituting the above expression in (43), we find (39a). To derive equation (39b) for [R k ](t), we note that Using (1) and letting ∆t → 0 in the above equality gives (39b). [S k ] + p k + q k + r k [S k ] = e − t 0 p k [S 0 k ] q k [S k−1 ] + q k [R 0 k−1 ] + r k , [S k ](0) = [S 0 k ].(48 We can solve equations (39a)-(39b) explicitely in the homogeneous case. Proof By translation symmetry, [S k ] and [R k ] do not depend on k. The result follows from a straighforward integration of equations (39a)-(39b). [24, Lemma 4.2] for [S 0 ] ≡ 1 and [R 0 ] ≡ 0. We can also explicitely solve the case of a time-dependent source term located at k = 0. ≡ 0 for all k > 0, and allow a source term p 0 (t) ≥ 0 at k = 0. Then Proof Under our assumptions, equation (39a) reduces to p0 and it can be verified by direct substitution that the solution for k ≥ 1 is given by where Note also that the constant 1 is a fixed point of the recursion relationship (53), namely, Therefore, for all k > 0, where we have used the associativity of the convolution product. A straightforward induction shows that which proves (51) . Let us now prove (52) . For a fixed k ∈ {0, 1, . . . }, by the dominated convergence theorem, Using the relation completes the proof of (52). Thus, the limit (52) depends on space k if and only if r > 0. Note also that, for a fixed t ≥ 0, as k → +∞ in (51), we get that [S k ](t) → 1. This expresses again the fact that a source term located at k = 0 cannot influence far nodes in finite time. From (52), we observe that This expression is actually equal to the probability that node k + 1 will eventually become infected knowing that node k has been infected. When p n k ≡ 0, i.e., when there are no source terms, the model (12) reduces to the SIR model on a 1D one-sided lattice. Assuming that the parameters and initial conditions are homogeneous (they do not depend on time nor space), if we let p → 0 in (49)-(50), then 1−e −pt p → t, and so we obtain and Therefore, and Let us now solve explicitely the "patient-zero" problem for the SIR model: Proposition 13 (Patient-zero SIR problem) Assume that p n k ≡ 0, q n k ≡ q and r n k ≡ r in (12) , that the nodes are placed on a semi-inifinite line K = {0, 1, 2, . . . } and that, initially, Then, the solution of (39a) is given by If we denote by N K (t) = K k=1 1 x k (t)=s the total number of susceptibles on a finite line of length K + 1 > 0, then (59) Proof See Appendix A.2. We see from (58) that lim k→+∞ [S k (t)] = 1, i.e., that the effect of patient-zero vanishes as we move far away from k = 0. It is instructive to compare the SIR model on a 1D-one sided lattice to the classical aggregate SIR model (6) . Since (6) corresponds to a complete graph whereas (12) corresponds to a structured sparse graph, this comparison reveals the effect of the network structure on the dynamics. • First, we emphasize that equation (39a) for [S k ] does not include [I k ] and [R k ], or higher-order marginals such as [S k ∩ S k−1 ]. This property is unique to 1D one-sided graphs. Indeed, for the aggregate SIR model (6), it is not possible to derive an equation on S which does not involve I and R. Let us mention that the system (4), and therefore also (6) obtained from (4) by taking p = 0, can also be reduced to a single equation on u(t) := • The aggregate SIR model satisfies the same threshold condition (56) for the outbreak of an epidemic from a small initial number of infected, see [31] . • When (56) holds, the behavior after the outbreak of an epidemic can be quite different for the 1D one-sided case (12) and the aggregate model (6) . In particular, a remarkable difference is the dependence of the final state on the initial conditions. From (55), we observe that is an increasing function of [S 0 ]: the more susceptible individuals at initial time, the more for large times, In contrast, for the aggregate SIR model (6) We now allow both the left and the right neighbors to spread the infection. We denote byq L,n k := q k−1,k and q R,n k := q k+1,k the influence of the left and right neighbors on node k, respectively, and we assume that Hence, (2a) becomes The transition rates (2b) from i to r remain unchanged, that is: Theorem 14 Assume that the individuals are placed on a 1D two-sided lattice K (which is either a finite, semi-infinite, or infinite line), see (60), that the dynamics are governed by (61), and that the initial conditions are uncorrelated, see (3) . Let p n k , q n k and r n k converge as ∆t → 0 to p k (t), q k (t) and r k (t). Then for all k ∈ K, is the probability that node k is susceptible by time t if we discard the influences of the left neighbors by setting q L,n k ≡ 0 in (61a) (resp. the influences of the right neighbors by setting q R,n k ≡ 0). In addition, [R k (t)] is given by Proof Let us first introduce some notations. We denote by [S k |q L k = 0] the probability of the event S k (t) := {x k (t) = s} wherex k is the process defined identically as x k but in which we put q L k ≡ 0 in (61a). We use the name notation if S k is replaced by any event or intersection of events, and if q L,n k = 0 is replaced by other conditions on the parameters. For example, with these notations, we We deduce that Similarily, we have Relations (63) and (64) can also be proved using the indifference principle of [27] . The last ingredient in our proof is a spatial Markovian property establishing that the state of nodes k − 1 and k + 1 are independent if conditioned with respect to S k . This is where the assumption on the graph (namely that it is 1D with no cylces) comes into play. x This standard result is proved separately in a slightly more general form, see Lemma 21 in appendix A.3. Lemma 15 can also be deduced from the funnel node theorem [26] . Using Lemma 15, we have that Substituting (63) and (64) and To prove this, first recall that from Theorem 8 we have Then, we derive (67) from the identities (62a) and (63). Note also that Using Theorem 14, the results of the previous sections dealing with the spatially homogeneous case, the patient zero problem, and time-varying point sources can be adapted to the case of a two-sided 1D lattice. We now briefly present the obtained explicit formula. For simplicity, we focus on the Bass model, i.e., we assume that there is no recovery. [S 0 k ] ≡ [S 0 ] and the parameters p k (t) ≡ p(t), q R k (t) ≡ q R (t), q L k (t) ≡ q L (t) do not depend on space k, then [S k ](t Proof The result is proved by a direct application of Theorem 14 and (24) . Note that expression (71) coincides with (24) in the one-sided case by setting q(t) := q R (t) + q L (t). We now turn to the patient-zero problem. Assume the conditions of Theorem 14, let r k (t) ≡ 0, p k (t) ≡ p, q R k (t) ≡ q R , q L k (t) ≡ q L , be independent of k and t, and let the nodes be placed on a semi-inifinite line K = N. Assume that, initially, we place a patient zero at k = 0, i.e., Proof Note that [S R k ] is given by the solution (24) of the one-sided Bass homogeneous problem with q = q R , and that [S L k ] is given by the solution (26) of the one-sided Bass patient-zero problem with q = q L . We conclude by using (62a). We now present the solution in the case of a time-varying point source. Assume that q k (t) ≡ q > 0 is constant, that p k (t) ≡ 0 for all k ≥ 1, and allow a single time-varying source term p 0 (t) ≥ 0 at k = 0. Then where [S L k ] is given by (31) . Proof The proof follows from (62a), the fact that [S R k ] ≡ 1 and that [S L k ] is given by (31). In this section, we discuss the space-continuous models that can be obtained after a space rescaling in our space-discrete process. Since we have shown in Theorem 14 that 1D two-sided lattices reduce to 1D one-sided lattices, we focus on the latter case to make the presentation clearer. Equation (39a) can be rewritten as Since the term [S k ] − [S k−1 ] is a discrete spatial derivative, this suggests that we can derive a space-continuous PDE by a proper space rescaling. To do that, assume that the individuals are placed on the inifinite line K = Z, fix 0 < ∆x 1, and proceed to the space-rescaling We can similarily define p(t, The limit of (73) as ∆x → 0 depends on some additional assumptions on how the parameters rescale. In the present paper, we shall only discuss the formal passage to the limit and leave the rigorous proof to future works. First, let us make the following assumptions: Rescaling Assumption 1. the parameters p k (t), q k (t), r k (t) and the initial conditions [S 0 k ], [R 0 k ] converge as ∆x → 0 locally uniformly in C 1 in time and space to some smooth functions p(t, x), q(t, x) > 0, r(t, x), [S 0 (x)], and [R 0 (x)], respectively. Under these assumptions, we have that Hence, S(t, x; ∆x) converges to the solution of the (integrodifferential) ODE (75) In particular, if p, q, and r do not depend on time (but are allowed to depend on space), we can integrate the above ODE and get the explicit expression (76) Note that the solution (76) is equal pointwise to the spatially-uniform solution (49) . Intuitively, this is because under Rescaling Assumptions 1, the spatial heterogeneity becomes locally uniform as ∆x → 0 and there are infinitely many nodes between two distinct points x, x ∈ R. Therefore, the solution can be computed at each point as a spatially constant solution. The solution (76) is thus spatially homogeneous in the short spatial scale O(dx), but inhomogeneous on the long spatial scale x = O(1). This multiple-scale property occurs in many situations, e.g., the slowly-varying amplitude approximation in optics. The convergence of the solution of (73) to the solution of the limiting ODE (75) as ∆x → 0 under Rescaling Assumptions 1 is illustrated in Figure 1 . • The gap problem, when q(x) and p(x) are spatially compactly supported or periodic • The time-control (or "optimal duration campaign" problem) when p and q are piecewise constant with respect to time and change value at some time t 0 > 0. The former rescaling gives a limiting ODE for which space can be viewed as a parameter since there is no derivative with respect to the variable x. In other words, there is no spatial coupling in the system as ∆x → 0, as expressed in (74). Intuitively, this is because the influence of any node on its right neighbors propagates at the speed c(t, x) := [S 0 ]qe − t 0 p ∆x, see (73). Thus, c(t, x) → 0 as ∆x → 0 and so the limiting equation is spatially decoupled. Therefore, in order to get a limiting equation that includes space derivative, one has to rescale q by a factor of 1/∆x, namely, to assume that q =q ∆x for a functionq independent of ∆x (or which converges locally uniformly as ∆x → 0). This way, the term q ([S](t, x) − [S](t, x − ∆x)) is of order 1 and converges toq∇ x [S] as ∆x → 0. If we assume, however, that the contagion coefficient becomes large as the space-step ∆x vanishes, i.e., that q is of order 1/∆x, we also need to rescale the other parameters. Indeed, we see from equation (73) that, in order not to get the singular limit S(t, x) ≡ 0 as ∆x → 0 and q = O(1/∆x), we need the term 1 − [S 0 ]e −pt to be of order O(∆x) as ∆x → 0. To fullfill thoses conditions, we make the following Rescaling Assumption 2. Assume that q k (t) > 0 and that the ratio r k (t) q k (t) does not depend on time. on the real line contains infinitely many nodes, therefore the epidemics do not propagate on the line in finite time. This explains why the obtained limiting (integrodifferential) ODE (75) is spatially decoupled. The (integrodifferential) ODE limit (75) is relevant from the modeling point of view when the contagion phenomenon occurs at a small space-scale. • In contrast, the PDE limit (79) obtained in Section 7.2 corresponds to a contagion phenomenon that is driven by the metric distance between nodes rather than on their discrete distance on the graph. In this case, the propagation of the epidemic occurs at a finite speed q on the line, as expressed by the explicit form of the solution in (80). It is then natural to consider the parameter p and initial conditions [I 0 ] and [R 0 ] as space-densities, as suggested by the Rescaling Assumptions (77). The PDE limit (79) has the advantage to qualitatively reproduce the spatial propagation at finite speed occurring in the discrete model (73). This PDE rescaling is also relevant when the contagion rate outweighs the source term (i.e., p q). In the present paper, we establish an exact deterministic description of stochastic SIR-Bass epidemics on 1D lattices by showing that the probability of infection at a given point in space and time can be obtained as the solution of a deterministic ODE system on the lattice. Our framework allows any type of heterogeneity on the parameters and initial conditions. In addition, our results precisely describe the spatio-temporal dynamics at a local scale, which is still a major challenge in epidemiology [44] . Our results focus on 1D lattices (i.e., finite, semi-infinite, and infinite lines) where the infection only occurs from a node to its direct neighbors. This is the first step towards more realistic contact networks, such as 2D lattices, scale-free networks, small-world networks, as well as other types of networks that are relevant from the application point of view in the context of epidemiology or marketing. Most likely, an exact deterministic description such as the one obtained in this paper cannot be obtained for 2D lattices or other contact networks 2 . We believe however that the analytical tools introduced in the present paper will be useful for further analysis of epidemiological models in complex networks under the pair-approximation assumption [33] . and that By assumption on the initial conditions, this property holds for n = 0. Assume that the above property holds for some n ≥ 0. Then, conditionning with respect to Y n − ∩ Y n + and using (40), we have From the assumption that the (x n+1 k ) k∈K are all independent if we condition by (x n k ) k∈K , we deduce Moreover, from the assumption that K is a 1D two-side lattice, we further deduce that Besides, the induction assumption (83) implies that Injecting (85) and (86) into (84), we derive which proves that (83) holds at the rank n + 1. We have thus proved that (83) holds for all n ≥ 0, from which we immediately deduce (81). Property (82) is deduced as a particular instance of (81). In constrast with Lemma 21, we have that The reason is that the condition I n k only prescribes the state of x n k at time t n and not the states (x m k ) 0≤m 0, p =p(t, x; ∆x)∆x, r =r, [I 0 (x)] = [Ĩ 0 (x; ∆x)]∆x, [R 0 (x)] = [R 0 (x; ∆x)]∆x, (77) where the "tilde functions" are assumed to converge locally uniformly as ∆x → 0.Since we assume that r (t,x) q(t,x) does not depend on time, equation (73) boils down toUnder Rescaling Assumptions 2, the terms in (78) have the following limit for any fixed t ≥ 0 as ∆x → 0:The convergence of the solution of (78) to the solution of the limiting PDE (79) as ∆x → 0 under Rescaling Assumptions 2 is illustrated in Figure 2 . The PDE (79) is solved numerically using a standard explicit finite-difference Euler scheme.Equation (79) can be solved using the method of the caracteristics. For example, assuming for simplicity that there is no recovery (i.e., [R 0 ] ≡r ≡ 0), no source term (i.e., p ≡ 0) and that q(t, x) ≡q is contant, the solution reads The two space-continuous models proposed above are obtained by different rescalings, each of which corresponding to a different modeling situation:• The (integrodifferential) ODE limit (75) discussed in Section 7.1 corresponds to the case where the contagion between two consecutive nodes is driven by their discrete distance on the graph rather than by their metric distance on the line. In this case, the propagation of the epidemic propagates at finite speed q on the graph. When the rescaling factor ∆x goes to 0, any interval A Appendix. Expression (26) can be verified by direct substitution in (17) . To show (27), we first notice that We obtain (27) from the change of variable l = K − l in the above expression.To show (29), note that above expression givesThen, we conclude that, as K → +∞, A straightforward substitution shows that expression (58) solves equation (39a) and satisfies the initial conditions (57).To prove (59), first note that, and so, using (58), we findThen, we get (59) from a change of variable l = K − l in the above expression. The proof of Theorem 14 relies on the spatial Markovian property stated in Lemma 21. This section is devoted to the proof of this result. For the sake of generality, we actually prove the following more general statement. Assume that the individuals are placed on a 1D two-sided lattice (see (60)) and that the initial conditions are uncorrelated, see (3) .For any integer k ∈ Z, denote by X n k− := (x n l ) lk the left and right neighbors of k. We have thatmeaning that the state of the left and right neighbors of k are independent under the conditioning with respect to the state of k for all preceeding times. In particular,Proof Let (x n k−1 ,x n k+1 ) ∈ {s, i, r} 2 be a possible realization of (x n k−1 , x n k+1 ), and let us denote by Y n − := x n k−1 =x n k−1 and Y n + := x n k+1 =x n k+1 the events that x n k+1 and x n k−1 equal this realization respectively. For clarity, we also dentote by X n k := (x m k ) 0≤m