Usefulness of the Age-Structured SIR Dynamics in Modelling COVID-19

Rohit Parasnis Department of Electrical and Computer Engineering, University of California San Diego Ryosuke Kato Department of Electrical and Computer Engineering, University of California San Diego Amol Sakhale Department of Electrical and Computer Engineering, University of California San Diego Massimo Franceschetti Department of Electrical and Computer Engineering, University of California San Diego Behrouz Touri Email: rparasni,rkato,asakhale,mfranceschetti,[email protected] Department of Electrical and Computer Engineering, University of California San Diego

Abstract

We examine the age-structured SIR model, a variant of the classical Susceptible-Infected-Recovered (SIR) model of epidemic propagation, in the context of COVID-19. In doing so, we provide a theoretical basis for the model, perform an empirical validation, and discover the limitations of the model in approximating arbitrary epidemics. We first establish the differential equations defining the age-structured SIR model as the mean-field limits of a continuous-time Markov process that models epidemic spreading on a social network involving random, asynchronous interactions. We then show that, as the population size grows, the infection rate for any pair of age groups converges to its mean-field limit if and only if the edge update rate of the network approaches infinity, and we show how the rate of mean-field convergence depends on the edge update rate. We then propose a system identification method for parameter estimation of the bilinear ODEs of our model, and we test the model performance on a Japanese COVID-19 dataset by generating the trajectories of the age-wise numbers of infected individuals in the prefecture of Tokyo for a period of over 365 days. In the process, we also develop an algorithm to identify the different phases of the pandemic, each phase being associated with a unique set of contact rates. Our results show a good agreement between the generated trajectories and the observed ones.

1 INTRODUCTION

The global COVID-19 death toll has crossed 6 million [1], and it is no surprise that researchers all over the world have been forecasting the evolution of this pandemic to propose control policies aimed at minimizing its medical and economic impacts [2, 3, acemoglu2020optimal, 4, 5, 6]. Their efforts have typically relied on classical epidemiological models or their variants (for an overview see [7] and the references therein). One such classical epidemic model is the Susceptible-Infected-Recovered (SIR) model. Proposed in [8], the SIR model is a compartmental model in which every individual belongs to one of three possible states at any given time instant: the susceptible state, the infected state, and the recovered state. The continuous-time SIR dynamics models the time-evolution of the fraction of individuals in any of these states using a set of ordinary differential equations (ODEs) parameterized by two quantities: the infection rate (the rate at which a given infected individual infects a given susceptible individual) and the recovery rate of infected individuals.

Even though the continuous-time SIR model is a deterministic model, it models an inherently random phenomenon in a large (but discrete) population. To bridge between the deterministic continuous-time SIR model and the underlying random processes over a finite population, researchers have shown that the associated (continuous-time) ODEs are the mean-field limits of continuous-time Markovian epidemic processes over a finite population [9, 10]. Similar results have been obtained for variants of the original model, such as for the SIR dynamics on a configuration model network [11, 12]. These results theoretically justify the SIR model ODEs.

Classical SIR models, however, (continuous and discrete-time) are homogeneous – the same infection and recovery rates apply to the whole social network despite differences in the individuals’ age, gender, race, immunity level, and pre-existing medical conditions. For COVID-19, this assumption is inconsistent with studies showing that the contact rates between individuals and the recovery rates of infected individuals depend on factors such as age and location [13, 14, 15, 16]. In addition, [17] argues that homogeneous models can introduce significant biases in forecasting the epidemic, including overestimation of the number of infections required to achieve herd immunity, overestimation of the strictness of optimal control policies, overestimation of the impact of policy relaxations, and incorrect estimation of the time of onset of the pandemic.

We therefore need to shift our focus to variants of the classical SIR model with heterogeneous contact rates. Examples include the multi-risk SIR model [4] and the age-stratified SIR models considered in [18, 19, 20], in which the population is partitioned into multiple groups and the rates of infection and recovery vary across groups. See [17] for a survey of these papers.

However, the models considered in the above works have two main shortcomings. On the one hand, barring exceptions such as [21], they are typically not validated using real data. On the other hand, they do not have a strong theoretical foundation because the dynamical processes studied in these works have not been established as the mean field limits of stochastic epidemic processes evolving on time-varying random graphs. We emphasize that even the convergence results obtained for homogeneous SIR models [9, 10, 11, 12] make the unrealistic assumption that the network of physical contacts (in-person interactions) existing in the population is time-invariant. As such, we cannot justify the use of these models in designing optimal control policies aimed at minimizing the impact of any epidemic. We therefore address the aforementioned shortcomings using the age-structured SIR model, a multi-group SIR model that partitions the population of a given region into different age groups and assigns different infection rates and recovery rates to the age groups. We note that, although we adopt the term age-structured in our paper, our analysis also applies to populations partitioned on the basis of differences in geographical location, sex, immunity level, etc. Moreover, among existing heterogeneous models [17], the age-structured SIR model is the simplest and hence more mathematically and computationally tractable than other models.

The contributions of this paper are as follows:

1.

Modeling: We extend our previously proposed stochastic epidemic model [22] to a more general model that incorporates (a) a random and time-varying network of physical contacts (in-person interactions between pairs of individuals) that are updated asynchronously and at random times, (b) random transmissions of disease-causing pathogens from infected individuals to their susceptible neighbors, and (c) recoveries of infected individuals that occur at random times. We analyze the resulting dynamics and show that under certain independence assumptions, the expected trajectories of the fractions of susceptible/infected/recovered individuals in any age group converge in mean-square to the solutions of the age-structured SIR ODEs as the population size goes to $\infty$ .
2.

Convergence Rate Analysis: We derive a lower bound on the effective infection rate for a given pair of age groups in the stochastic model. This bound, as we show, is approximately linear in the reciprocal of the network update rate, which leads to the infection rate converging to its limit (specified by the ODEs) as fast as the reciprocal of the network update rate vanishes.
3.

Validation: We validate our age-structured model empirically by estimating the parameters of our model using a Japanese COVID-19 dataset and, subsequently, by generating the age-wise numbers of infected individuals as functions of time. In this process, we leverage the crucial fact that the ODEs defining our model are linear in the model parameters (transmission and recovery rates), which enables us to use a least-squares method for the system identification.
4.

A Method to Detect Changes in Social Behavior: We design a simple algorithm that can be used to detect changes in social behavior throughout the duration of the pandemic. Given the age-wise daily infection counts, the algorithm estimates the dates around which the inter-age-group contact rates change significantly.
5.

Insights into Epidemic Spreading: We interpret the results of our phase detection algorithm to identify the least and the most infectious age groups and the least and the most vulnerable age groups. Additionally, we analyze the data for the entire period from March 2020 to April 2021 to explain how certain social events influenced the propagation of COVID-19 in the prefecture of Tokyo.

The structure of our paper is as follows: We introduce the age-structured SIR model and our stochastic epidemic model in Section 2. We establish the age-structured SIR ODEs as the mean-field limits of our stochastic model in Section 3. We also discuss the limitations of (converse result for) our model in Section 3. Next, we describe the empirical validation of our model (in the context of the COVID-19 outbreak in Tokyo) in Section 5. We conclude with a brief summary and future directions in Section 6.

Related Works: [23] proposes a heterogeneous epidemic model with time-varying parameters to show that heterogeneous susceptibility to infection results in a temporary weakening of the COVID-19 pandemic but not in herd immunity. The model is validated using the death tolls (and not the case numbers) reported for New York and Chicago for a period of about 80 days. [19] uses the age-structured SEIQRD model to predict the number of deaths with a reasonable accuracy, but unlike our work, it does not use the proposed model to generate the number of new cases as a function of time. [24] uses heterogeneous variants of the SEIR model to study the impact of the lockdown policy implemented in France, but it does not validate these models empirically. [15] reports contact rate matrices for the population of the UK based on the self-reported data of 36,000 volunteers. However, the study ignores the time-varying nature of these contact rates, which we capture in our phase detection algorithm (Section 5). Another study that uses time-invariant model parameters is [25], which proposes the age-structured SEIRA model and uses it to simulate the number of new infections in different social groups of Chile.

[26] uses a heterogeneous SEIRD model to predict the effects of various relaxation policies on infection counts in certain regions of Italy. The model therein is empirically validated only using the data obtained during the first 60 days of the pandemic. In [20], the authors propose an age-structured SIRD model and calibrate it with the data obtained from [2]. Unlike our paper, however, [20] divides the population into only two age groups, and does not compare the model-generated values of the number of infections with the official case counts. Two other studies that use two-age-group SIR models are [27] and [28]. While [27] argues that in Florida, old and socially inert adults have been possibly infected by the young, [28] argues that age-group-targeted policies are more effective than uniform policies in reducing the economic impact of COVID-19. [29] proposes a heterogeneous SIR model with feedback and forecasts the economic and medical impacts of various policies aimed at controlling the pandemic in Chile. Unlike our study, however, [29] ignores the time-varying nature of contact rates. [21] proposes the SEIR-HC-SEC-AGE model, a heterogeneous SEIR model that sub-divides each age-group further into risk sectors with different vulnerabilities to the SARS-CoV-2 virus. The model therein, which is calibrated to predict the effects of different lockdown policies in certain regions of Italy, simulates the time-evolution of the observed death toll with a high accuracy. By contrast, we pick a much simpler heterogeneous model and examine whether it fits the observed case numbers well. [18] and [4] use an age-structured SIR model to show that control policies that target different age groups differently perform better than uniform policies. However, these results assume that inter-age-group contact rates are the same for all pairs of age groups, an assumption that is inconsistent with our empirical results (Section 5). Hence, deriving optimal policies in the framework of the age-structured SIR model under more general assumptions is an important open problem.

Notation: We let $\mathbb{N}$ denote the set of natural numbers and $\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$ . We let $[l]:=\{1,2,\ldots,\ell\}$ for $\ell\in\mathbb{N}$ . We denote the set of real and positive real numbers by $\mathbb{R}$ and $\mathbb{R}_{+}$ , respectively. For $x\in\mathbb{R}$ , we let $x_{+}:=\max\{x,0\}$ denote the positive part of $x$ .

The symbols $t$ and $k$ are used as a continuous-time and discrete-time indices, respectively. We use the notation $z(t)$ for functions $z:\mathbb{R}_{+}\cup\{0\}\to\mathbb{R}$ and $z[k]$ for functions $z:\mathbb{N}\to\mathbb{R}$ . We occasionally omit the time index $(t)$ when the value of $t$ is clear from the context.

We use the Bachmann-Landau asymptotic notation $O(f(n))$ for a given function $f:\mathbb{N}\rightarrow\mathbb{R}$ in the context of $n\rightarrow\infty$ . We use $o(\Delta t)$ in the context of $\Delta t\rightarrow 0$ . In addition, for a given function $g:[0,\infty)\rightarrow\mathbb{R}$ , we use the notation $g^{\prime}=g^{\prime}(t)$ to denote $\frac{dg}{dt}$ , the first derivative of $g$ with respect to time.

For a set $\mathcal{S}$ , we let $|\mathcal{S}|$ denote the cardinality of $\mathcal{S}$ . In this paper, all random events and random variables are with respect to a probability space $(\Omega,\mathcal{F},\text{Pr})$ , where $\Omega$ is the sample space, $\mathcal{F}$ is the set of events, and $\text{Pr}(\cdot)$ is the probability measure on this space. We denote random variables and random events using capital letters, and for a random event $C$ , we define $1_{C}$ to be the indicator random variable associated with $C$ , i.e, $1_{C}:\Omega\to\mathbb{R}$ is the random variable with $1_{C}(\omega)=1$ if $\omega\in C$ and $1_{C}(\omega)=0$ , otherwise. For an event $C\in\mathcal{F}$ , $\bar{C}$ represents the complement of $C$ . For a random variable $X$ , $\mathbb{E}[X]$ denotes the expected value of $X$ and $\mathbb{E}[X\mid C]$ denotes the conditional expectation of $X$ given the event $C$ . For random variables $X$ and $Y$ and a random event $C$ , we define

\mathbb{E}[X\mid Y,C]=\frac{\mathbb{E}[X1_{C}\mid Y]}{\mathbb{E}[1_{C}\mid Y]}.

Therefore, for an event $F\in\mathcal{F}$

\text{Pr}(F\mid Y,C)=\mathbb{E}[1_{F}\mid Y,C]=\frac{\mathbb{E}[1_{F\cap C}\mid Y]}{\mathbb{E}[1_{C}\mid Y]}.

We denote tuples of length $r>1$ using bold-face letters and random tuples using bold-face capital letters. For a tuple $\mathbf{x}$ of length $r\in\mathbb{N}$ and an index $\ell\in[r]$ , we let $x_{\ell}=(\mathbf{x})_{\ell}$ denote the $\ell$ -th entry of $\mathbf{x}$ .

For $n\in\mathbb{N}$ and $E\subset[n]\times[n]$ , we use $G=([n],E)$ to denote the directed graph (digraph) with vertex set $[n]$ and edge set $E$ . Finally, for a graph $G=([n],E)$ , given two distinct nodes $a,b\in[n]$ , we let $\langle a,b\rangle:=(a-1)(n-1)+b-\chi_{b-a}$ , where $\chi_{\alpha}=1$ if $\alpha>0$ and $\chi_{\alpha}=0$ , otherwise. Note that $\langle\cdot,\cdot\rangle$ maps the edges between (distinct) nodes of the graph to the numbers $1,\ldots,n^{2}-n$ in lexicographic order.

2 PROBLEM FORMULATION

We now introduce two epidemic models, of which the first describes a deterministic dynamical system and the second describes a stochastic process on a finite population. One of the main objectives of this work is to relate these models, which is achieved in Section 3.

2.1 The Age-Structured SIR Model

Consider a population of individuals spanning $m$ age groups¹¹1As mentioned before, throughout this paper, we could generalize the discussions involving age groups to subpopulations distinguished by geographical locations, pre-existing health conditions, sex, etc.. Suppose a part of this population contracts a communicable disease at time $t=0$ . Let $s_{i}(t),\beta_{i}(t)$ , and $r_{i}(t)$ denote, respectively, the fractions of susceptible, infected, and recovered individuals in the $i$ -th age group at (a continuous) time $t\geq 0$ , so that $s_{i}(t)+\beta_{i}(t)+r_{i}(t)$ equals the fraction of individuals in the $i$ -th age group for all $t\geq 0$ . As the disease spreads across the population, susceptible individuals get infected, and infected individuals recover in accordance with the system of ODEs given by

$\displaystyle\dot{s}_{i}(t)$	$\displaystyle=-s_{i}(t)\sum_{j=1}^{m}A_{ij}\beta_{j}(t),$	(1)
$\displaystyle\dot{\beta}_{i}(t)$	$\displaystyle=s_{i}(t)\sum_{j=1}^{m}A_{ij}\beta_{j}(t)-\gamma_{i}\beta_{i}(t),$	(2)
$\displaystyle\dot{r}_{i}(t)$	$\displaystyle=\gamma_{i}\beta(t),$

where for each $i,j\in[m]$ , the constant $A_{ij}$ represents the rate of infection transmission from an individual in age group $j$ to an individual in age group $i$ , and $\gamma_{i}$ denotes the recovery rate of an infected individual in age group $i$ . Hereafter, we refer to $A_{ij}$ as the contact rate of age group $j$ with age group $i$ . Note that the third equation in (1) can be obtained from the first two equations simply by using the fact that $\dot{s}_{i}(t)+\dot{\beta}_{i}(t)+\dot{r}_{i}(t)=0$ for all $t\geq 0$ . Also, if $m=1$ , the above model reduces to the classical (homogeneous and continuous-time) SIR model.

2.2 A Stochastic Epidemic Model

Let us now define a continuous-time Markov chain that describes an age-structured process of epidemic spreading occurring over a finite (atomic) population composed of individuals that are connected through a random, time-varying network $G(t)$ .

2.2.1 Age Groups

Let $n\in\mathbb{N}$ denote the total population size, and let $[n]$ be the vertex set of the time-varying graph $G(t)$ , so that the vertex set indexes all the individuals/nodes in the network. We assume that $[n]$ is partitioned into $m$ age groups $\{\mathcal{A}_{i}\}_{i=1}^{m}$ and that $|\mathcal{A}_{i}|$ (the number of individuals in the $i$ -th age group) scales linearly with $n$ for all $i\in[m]$ . In the following, $i,j\in[m]$ are generic age group indices.

2.2.2 State Space

The state space of our random process is the space $\mathbb{S}=\{-1,0,1\}^{n}\times\{0,1\}^{2n(n-1)}$ . The network state is a tuple $\mathbf{x}=(x_{1},x_{2},\ldots,x_{2n^{2}-n})\in\mathbb{S}$ , where

(i)

$\{x_{\ell}\}_{\ell\in[n]}$ denotes the disease states of the nodes in the network, i.e., for $\ell\in[n]$ , we set $x_{\ell}=0$ , $1$ , or $-1$ accordingly as node $\ell$ is susceptible, infected, or recovered, respectively.
(ii)

For $\ell\in\{n+1,n+2,\ldots,n^{2}\}$ , we let $x_{\ell}$ denote the edge state of the $\ell$ -th pair in the following lexicographic order of pairs of distinct nodes: $(1,2),\ldots,(1,n),(2,1),\ldots,(2,n),\ldots,(n,1),\ldots,(n,n-1)$ . In other words, for any node pair $(a,b)\in[n]\times[n]$ such that $a\neq b$ , we set $x_{\langle a,b\rangle}=1$ if there is a directed edge from $b$ to $a$ in the network $G$ , and $x_{\langle a,b\rangle}=0$ , otherwise. For notational convenience, we let $1_{(a,b)}(\mathbf{x}):=x_{\langle a,b\rangle}$ .
(iii)

For $\ell\in\{n^{2}+1,\ldots,2n^{2}-n\}$ , we let $x_{\ell}$ be a binary variable whose value flips (becomes $1-x_{\ell}$ ) whenever the $(\ell-n^{2})$ -th edge state gets updated (re-initialized). However, the direction of this flip (whether $x_{\ell}$ changes from 0 to 1 or from 1 to 0) carries no significance.

2.2.3 State Attributes

For all $\mathbf{x}\in\mathbb{S}$ , we let $\mathcal{S}_{i}(\mathbf{x}):=\{a\in\mathcal{A}_{i}:x_{a}=0\}$ , $\mathcal{I}_{i}(\mathbf{x}):=\{a\in\mathcal{A}_{i}:x_{a}=1\}$ , and $\mathcal{R}_{i}(\mathbf{x}):=\{a\in\mathcal{A}_{i}:x_{a}=-1\}$ denote, respectively, the set of susceptible individuals, the set of infected individuals, and the set of recovered individuals in $\mathcal{A}_{i}$ given that the network state is $\mathbf{x}$ . We let $\mathcal{S}(\mathbf{x}):=\cup_{i=1}^{m}\mathcal{S}_{i}(\mathbf{x})$ and $\mathcal{I}(\mathbf{x}):=\cup_{i=1}^{m}\mathcal{I}_{i}(\mathbf{x})$ . Additionally, for every node $a\in[n]$ , we let $E_{j}^{(a)}(\mathbf{x}):=\sum_{c\in\mathcal{I}_{j}(\mathbf{x})}1_{(a,c)}(\mathbf{x})$ be the number of arcs from $\mathcal{I}_{j}(\mathbf{x})$ to $a$ .

2.2.4 The Markov Process

Let $\mathbf{X}(t)\in\mathbb{S}$ denote the state of the network at any time $t\geq 0$ . Then we assume that $\{\mathbf{X}(t):t\geq 0\}$ is a right-continuous time-homogeneous Markov process in which every transition from a state $\mathbf{x}\in\mathbb{S}$ to a state $\mathbf{y}\in\mathbb{S}\setminus\{\mathbf{x}\}$ belongs to one of the following categories:

1.

Infection transition: This occurs when a node $a\in\mathcal{S}_{i}(\mathbf{x})$ gets infected by a node in $\cup_{k=1}^{m}\mathcal{I}_{k}(\mathbf{x})$ , while the disease states of all other nodes and the edge states of all the node pairs remain the same. In other words, $x_{a}=0$ , $y_{a}=1$ , and $x_{\ell}=y_{\ell}$ for all $\ell\neq a$ . Denoting the state-independent rate of pathogen transmission from a node in $\mathcal{I}_{k}(\mathbf{x})$ to an adjacent node in $\mathcal{S}_{i}(\mathbf{x})$ by $B_{ik}$ , we note that the rate of infection transmission from any node $c\in\mathcal{I}_{k}(\mathbf{x})$ to $a$ is $B_{ik}1_{(a,c)}(\mathbf{x})$ . Hence, the total rate at which $a$ receives pathogens from $\mathcal{I}_{k}$ is $\sum_{c\in\mathcal{I}_{k}(\mathbf{x})}B_{ik}1_{(a,c)}(\mathbf{x})=B_{ik}E_{k}^{(a)}(\mathbf{x})$ , assuming that different edges transmit the infection independently of each other during vanishingly small time intervals. As a result, the effective rate at which $a$ gets infected is $\sum_{k=1}^{m}B_{ik}E_{k}^{(a)}(\mathbf{x})$ . We denote the successor state $\mathbf{y}$ of $\mathbf{x}$ , where the node $a$ turns from susceptible to infected, by $\mathbf{x}_{\uparrow a}$ .
2.

Recovery transition: This occurs when a node $a\in\mathcal{I}_{i}(\mathbf{x})$ recovers, i.e., $x_{a}=1$ , $y_{a}=-1$ , and $x_{\ell}=y_{\ell}$ for all $\ell\neq a$ . We let $\gamma_{i}$ denote the rate at which an infected node in $\mathcal{A}_{i}$ (such as $a$ ) recovers. For such a transition, we denote $\mathbf{y}=\mathbf{x}_{\downarrow a}$ .
3.

Edge update transition: This occurs when $x_{\langle a,b\rangle}$ , the edge state of a node pair $(a,b)\in\mathcal{A}_{i}\times\mathcal{A}_{j}$ , is updated or re-initialized, i.e., $y_{n^{2}+\langle a,b\rangle}=1-x_{n^{2}+\langle a,b\rangle}$ , and $y_{\ell}=x_{\ell}$ for all $\ell\notin\{\langle a,b\rangle,n^{2}+\langle a,b\rangle\}$ . We let $\lambda$ denote the edge update rate or the rate at which an edge state is updated. In addition, given that the edge state of $(a,b)$ is updated at time $t\geq 0$ , the probability that $1_{(a,b)}(t)=1$ (i.e., the edge $(a,b)$ exists after the re-initialization) equals $\frac{\rho_{ij}}{n}$ , where $\rho_{ij}>0$ is constant in time. Therefore, if $y_{\langle a,b\rangle}=1$ (meaning that $(a,b)$ exists as an arc in $G$ in the network state $\mathbf{y}$ ), then the rate of transition from $\mathbf{x}$ to $\mathbf{y}$ equals $\lambda\frac{\rho_{ij}}{n}$ , whereas if $y_{\langle a,b\rangle}=0$ , then the rate of transition from $\mathbf{x}$ to $\mathbf{y}$ equals $\lambda\left(1-\frac{\rho_{ij}}{n}\right)$ . In the former case, we write $\mathbf{y}=\mathbf{x}_{\uparrow(a,b)}$ , while in the latter case, we write $\mathbf{y}=\mathbf{x}_{\downarrow(a,b)}$ . Note that the rate of transition from $\mathbf{x}$ to $\mathbf{x}_{\downarrow(a,b)}$ or $\mathbf{x}_{\uparrow(a,b)}$ does not depend on $\mathbf{x}$ .

The edge update transition of $(a,b)$ can be described informally as follows. Throughout the evolution of the pandemic, $a$ and $b$ decide whether or not to meet each other at a constant rate $\lambda>0$ , i.e., their decision times $\{T_{\ell}^{(a,b)}\}_{\ell=1}^{\infty}$ form a Poisson process with rate $\lambda$ . Each time they make such a decision, they decide to interact with probability $\frac{\rho_{ij}}{n}$ , and they decide not to interact with probability $1-\frac{\rho_{ij}}{n}$ , independently of their past decisions. The probability of interaction is assumed to scale inversely with $n$ so that the mean degree of every node is constant with respect to $n$ .

To summarize, the rate of transition from any state $\mathbf{x}\in\mathbb{S}$ to any state $\mathbf{y}\in\mathbb{S}\setminus\{\mathbf{x}\}$ is given by $\mathbf{Q}$ , the infinitesimal generator of the Markov chain $\{\mathbf{X}(t):t\geq 0\}$ , where for $\mathbf{x}\not=\mathbf{y}$

\displaystyle\mathbf{Q}(\mathbf{x},\mathbf{y}):=\begin{cases}\sum_{k=1}^{m}B_{ik}E_{k}^{(a)}(\mathbf{x})\,&\text{if }\mathbf{y}=\mathbf{x}_{\uparrow a}\text{ for some }a\in\mathcal{S}_{i}(\mathbf{x}),i\in[m]\\ \gamma_{i}\quad&\text{if }\mathbf{y}=\mathbf{x}_{\downarrow a}\text{ for some }a\in\mathcal{I}_{i}(\mathbf{x}),i\in[m]\\ \lambda\frac{\rho_{ij}}{n}\quad&\text{if }\mathbf{y}=\mathbf{x}_{\uparrow(a,b)}\text{ for some }(a,b)\in\mathcal{A}_{i}\times\mathcal{A}_{j},i,j\in[m]\\ \lambda\left(1-\frac{\rho_{ij}}{n}\right)\quad&\text{if }\mathbf{y}=\mathbf{x}_{\downarrow(a,b),}\text{ for some }(a,b)\in\mathcal{A}_{i}\times\mathcal{A}_{j},i,j\in[m]\\ 0\quad&\text{otherwise}\end{cases},

and $\mathbf{Q}(\mathbf{x},\mathbf{x}):=-\sum_{\mathbf{y}\in\mathbb{S}\setminus\{\mathbf{x}\}}\mathbf{Q}(\mathbf{x},\mathbf{y})$ . In addition, we say that $\mathbf{y}$ succeeds $\mathbf{x}$ potentially iff $\mathbf{Q}(\mathbf{x},\mathbf{y})>0$ .

3 MAIN RESULT

To provide a rigorous mean-field derivation of the dynamics (1), we now consider a sequence of social networks with increasing population sizes such that each network obeys the theoretical framework described in Section 2. Given a network from this sequence with population size $n\in\mathbb{N}$ , we let $\mathcal{S}^{(n)}_{j}(t):=\mathcal{S}_{j}(\mathbf{X}(t))$ , $\mathcal{I}^{(n)}_{j}(t):=\mathcal{I}_{j}(\mathbf{X}(t))$ , and $\mathcal{R}^{(n)}_{j}(t):=\mathcal{R}_{j}(\mathbf{X}(t))$ denote the (random) sets of infected, susceptible, and infected individuals in the $j$ -th age group, respectively, and we let $s_{j}^{(n)}(t):=\frac{1}{n}|\mathcal{S}_{j}^{(n)}(t)|$ , $\beta_{j}^{(n)}(t):=\frac{1}{n}|\mathcal{I}_{j}^{(n)}(t)|$ and $r_{j}^{(n)}(t):=\frac{1}{n}|\mathcal{R}_{j}^{(n)}(t)|$ denote the fractions of susceptible, infected, and recovered individuals in the $j$ -th age group, respectively. As for the absolute numbers, we let $S_{j}^{(n)}(t):=|\mathcal{S}_{j}^{(n)}(t)|$ , $I_{j}^{(n)}(t):=|\mathcal{I}_{j}^{(n)}(t)|$ , and $R_{j}^{(n)}(t):=|\mathcal{R}_{j}^{(n)}(t)|$ . Additionally, we let $E^{(n)}(t)$ denote the edge set of the network at time $t$ , and we drop the superscript ⁽ⁿ⁾ when the context makes our reference to the $n$ -th network clear.

Another quantity that varies with $n$ is $\lambda^{(n)}$ , the edge update rate. To obtain the desired mean-field limit in Theorem 1, we assume that $\lambda^{(n)}\rightarrow\infty$ as $n\rightarrow\infty$ . To interpret this assumption, consider any pair of individuals $(a,b)\in\mathcal{A}_{i}\times\mathcal{A}_{j}$ that are in contact with each other at time $t\geq 0$ during the epidemic. Since the edge state of $(a,b)$ is updated to $0$ (the state of non-existence) at a time-invariant rate of $\lambda^{(n)}\left(1-\frac{\rho_{ij}}{n}\right)$ , the assumption implies that the mean interaction time of $b$ with $a$ , which is $\frac{1}{\lambda^{(n)}}+O\left(\frac{1}{n\lambda^{(n)}}\right)$ , vanishes as the population size increases. This is a possible real-world scenario, because as $n$ increases, the population density of the given geographical region increases, which could result in overcrowding and rapidly changing interaction patterns in the network. This may be especially true in the case of public places such as supermarkets and subway stations at a time when the society is already aware of an evolving epidemic. Another implication of $\lim_{n\rightarrow\infty}\lambda^{(n)}=\infty$ is that the rate at which a given infected node contacts and transmits pathogens to a given susceptible node vanishes as the population size goes to $\infty$ (see Remark 1 for an explanation). This implication is weaker than the often-assumed condition that the rate of pathogen transmission is proportional to the reciprocal of the population size [30, 31].

We are now ready to state our main result. Its proof is based on the theory of continuous-time Markov chains and an analysis of how the disease propagation process is affected by random updates occurring in the network structure at random times (which results in Propositions 1 and 2) in addition to the proof techniques used in [30]. The proofs of all these results are available in the appendix.

Theorem 1.

Suppose that $\lim_{n\rightarrow\infty}\lambda^{(n)}=\infty$ and that for every $i\in[m]$ , there exist $s_{i,0},\beta_{i,0}\in[0,1]$ such that $\lim_{n\to\infty}s_{i}^{(n)}(0)=s_{i,0}$ and $\lim_{n\rightarrow\infty}\beta_{i}^{(n)}(0)=\beta_{i,0}$ . Then for each $i\in[m]$ ,

{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lim_{n\to\infty}}\mathbb{E}\left[\left\|\left(s_{i}^{(n)}(t),\beta_{i}^{(n)}(t)\right)-\left(y_{i}(t),w_{i}(t)\right)\right\|_{2}^{2}\right]=0.

on any finite time interval $[0,T_{0}]$ , where $(y_{i}(t),w_{i}(t))$ is the solution to the ODE system given by the first two equations in (1), i.e., $(y_{i}(t),w_{i}(t))$ satisfies

(I).

$\quad\dot{y}_{i}=-y_{i}\sum_{j=1}^{m}A_{ij}w_{j},\quad y_{i}(0)=s_{i,0}$ ,
(II).

$\quad\dot{w}_{i}=y_{i}\sum_{j=1}^{m}A_{ij}w_{j}-\gamma_{i}w_{i},\quad w_{i}(0)=\beta_{i,0}$ ,

and $A\in\mathbb{R}^{m\times m}$ is defined by $A_{ij}:=\rho_{ij}B_{ij}$ .

Theorem 1 relies on the following proposition.

Proposition 1.

For each $i,j\in[m]$ , let

\chi_{ij}=\chi_{ij}(t,\mathcal{S},\mathcal{I}):=\mathbb{E}[1_{(a,b)}(t)\mid\mathcal{S}(t),\mathcal{I}(t)]=\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))

be the random variable that denotes the conditional probability that a pair of nodes $(a,b)\in\mathcal{S}_{i}(t)\times\mathcal{I}_{j}(t)$ are in physical contact at time $t$ given the state of the network at time $t$ . Then the following equations hold for all $t\geq 0$ :

(i).

$\mathbb{E}[s_{i}]^{\prime}=-\sum_{j=1}^{m}B_{ij}\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}]$ ,
(ii).

$\mathbb{E}[\beta_{i}]^{\prime}=\sum_{j=1}^{m}B_{ij}\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}]-\gamma_{i}\mathbb{E}[\beta_{i}]$ ,
(iii).

$\mathbb{E}[s_{i}^{2}]^{\prime}=-\sum_{j=1}^{m}\big{(}2B_{ij}\mathbb{E}[n\chi_{ij}s_{i}^{2}\beta_{j}]-B_{ij}\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}]/n\big{)}$ ,
(iv).

$\mathbb{E}[\beta_{i}^{2}]^{\prime}=\sum_{j=1}^{m}B_{ij}(2\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}\beta_{i}]+\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}]/n)-\gamma_{i}\left(2\mathbb{E}[\beta_{i}^{2}]-\mathbb{E}[\beta_{i}]/n\right)$ .

We point out that if $\chi_{ij}=\frac{\rho_{ij}}{n}$ then Equations (i) and (ii) have the same coefficients as (I) and (II). It is then natural to ask: how does the conditional edge probability $\chi_{ij}$ compare to the unconditional edge probability $\frac{\rho_{ij}}{n}$ ? The following proposition provides an answer. As we show in Remark 1, our answer helps characterize the rate at which the infection transmission rates converge to their respective limits, an analysis missing from other works such as [30] and [31].

Proposition 2.

For all $t\geq 0$ , $n\in\mathbb{N}$ and $i,j\in[m]$ ,

\frac{\rho_{ij}}{n}\left(1-\frac{B_{ij}}{\lambda^{(n)}}\left(1-e^{-\lambda^{(n)}t}\right)\right)\leq\chi_{ij}\leq\frac{\rho_{ij}}{n}.

Remark 1.

Given $(\mathcal{S}(t),\mathcal{I}(t))$ , note that the conditional probability that a given infected node in $\mathcal{A}_{j}$ infects a given susceptible node in $\mathcal{A}_{i}$ during a time interval $[t,t+\Delta t)$ is $B_{ij}\chi_{ij}(t,\mathcal{S},\mathcal{I})\Delta t+o(\Delta t).$ In light of Proposition 2, this means that the associated conditional infection rate $B_{ij}\chi_{ij}(t,\mathcal{S},\mathcal{I})$ belongs to the interval

\left[\frac{1}{n}A_{ij}\left(1-\frac{B_{ij}}{\lambda^{(n)}}(1-e^{-\lambda^{(n)}t})\right),\frac{1}{n}A_{ij}\right].

On taking expectations, we realize that the same applies to the associated unconditional infection rate as well. Hence, the total rate of infection transmission from all of $\mathcal{A}_{j}$ to any given node of $\mathcal{A}_{i}$ is at least $I_{j}^{(n)}(t)\times\frac{1}{n}A_{ij}\left(1-\frac{B_{ij}}{\lambda^{(n)}}(1-e^{-\lambda^{(n)}t})\right)=A_{ij}\beta_{j}^{(n)}(t)\left(1-\frac{B_{ij}}{\lambda^{(n)}}(1-e^{-\lambda^{(n)}t})\right)$ and at most $A_{ij}\beta_{j}^{(n)}(t)$ . Since we assume $\lim_{n\rightarrow\infty}\lambda^{(n)}=\infty$ , this further implies that the concerned rate is approximately $A_{ij}\beta_{j}^{(n)}(t)$ for large $n$ , thereby giving us an interpretation of the ‘contact rate’ $A_{ij}$ as a normalized infection rate. That is, in the limit as $n\rightarrow\infty$ , the matrix $A$ quantifies the infection transmission rates between any two age groups relative to the level of infectedness (fraction of infected persons) of the transmitting age group. Moreover, Proposition 2 also implies that the difference between the age-wise infection transmission rates and their respective mean-field limits (which exist as per Theorem 1) is $O\left(\frac{1}{\lambda^{(n)}}\right)$ .

4 A CONVERSE RESULT

The purpose of this section is to argue that the age-structured SIR dynamics does not model an epidemic well if the infection rates $B_{ij}$ are high enough to be comparable to the edge update rate of the network.

Theorem 2.

Suppose $\lambda_{\infty}:=\lim_{n\rightarrow\infty}\lambda^{(n)}<\infty$ and that for every $p\in[m]$ , there exist $s_{p,0},\beta_{p,0}\in[0,1]$ such that $s_{p}^{(n)}(0)\rightarrow s_{p,0}$ and $\beta_{i}^{(n)}(0)\rightarrow\beta_{p,0}$ as $n\rightarrow\infty$ . In addition, let $\{(y_{q}(t),w_{q}(t))\}_{q\in[m]}$ be the solutions of the ODEs (I) and (II). Then, there exists no interval $[t_{1},t_{2}]\subset[0,\infty)$ for which $\min_{p,q\in[m]}\min_{t\in[t_{1},t_{2}]}y_{p}(t)w_{q}(t)>0$ and on which the pairs $\left\{\left(s_{q}^{(n)}(t),\beta_{q}^{(n)}(t)\right)\right\}_{q=1}^{m}$ uniformly converge in probability to the corresponding pairs in $\{(y_{q}(t),w_{q}(t))\}_{q=1}^{m}$ . More precisely, for every interval $[t_{1},t_{2}]\subset\mathbb{R}$ such that $y_{p}(t)>0$ and $w_{p}(t)>0$ for all $p\in[m]$ and $t\in[t_{1},t_{2}]$ , there exists a $q\in[m]$ and an $\varepsilon_{q}>0$ such that

\liminf_{n\rightarrow\infty}\sup_{t\in[t_{1},t_{2}]}\text{Pr}\left(\left\|\left(s_{q}^{(n)}(t),\beta_{q}^{(n)}(t)\right)-\left(y_{q}(t),w_{q}(t)\right)\right\|_{2}>\varepsilon_{q}\right)>0.

Proof.

Suppose, on the contrary, that there exists a time interval $[t_{1},t_{2}]\subset[0,\infty)$ such that $y_{p}(t)>0$ and $w_{p}(t)>0$ for all $p\in[m]$ and $t\in[t_{1},t_{2}]$ , and the following holds for all $q\in[m]$ and all $\varepsilon_{q}>0$ :

\liminf_{n\rightarrow\infty}\sup_{t\in[t_{1},t_{2}]}\text{Pr}\left(\left\|\left(s_{q}^{(n)}(t),\beta_{q}^{(n)}(t)\right)-\left(y_{q}(t),w_{q}(t)\right)\right\|_{2}>\varepsilon_{q}\right)=0,

i.e., for a fixed $\varepsilon>0$ , there exists a sequence $\{\pi(n)\}_{n=1}^{\infty}\subset\mathbb{N}$ such that

\lim_{n\rightarrow\infty}\sup_{t\in[t_{1},t_{2}]}\text{Pr}\left(\left\|\left(s_{q}^{(\pi(n))}(t),\beta_{q}^{(\pi(n))}(t)\right)-\left(y_{q}(t),w_{q}(t)\right)\right\|_{2}>\varepsilon\right)=0.

We then arrive at a contradiction, as shown below.

We first choose an $\eta>2\left(1+\frac{A_{\max}}{\lambda_{\infty}}\right)$ (where $A_{\max}:=\max\{A_{pq}:p,q\in[m]\}$ ) and a $t\in(t_{1},t_{2})$ . By our hypothesis and norm equivalence, for $\kappa_{0}:=\frac{1}{\eta\lambda_{\infty}}$ and for every $\delta>0$ , there exists an $N_{\varepsilon,\delta}\in\mathbb{N}$ such that

\text{Pr}\left(\left\|\left(s_{q}^{(\pi(n))}\left(\tau\right),\beta_{q}^{(\pi(n))}\left(\tau\right)\right)-\left(y_{q}\left(\tau\right),w_{q}\left(\tau\right)\right)\right\|_{1}\leq\varepsilon\right)\geq 1-\delta

for all $n\geq N_{\varepsilon,\delta}$ and all $\tau\in[t-\kappa_{0},t]$ .

We now define $\alpha_{0}:=\min_{p,q\in[m]}\min_{t\in[t_{1},t_{2}]}y_{p}(t)w_{q}(t)$ and we let $a$ and $b$ be any two nodes such that $(a,b)\in\mathcal{S}_{i}(t)\times\mathcal{I}_{j}(t)$ for arbitrary $i,j\in[m]$ . Additionally, we let $K:=t-\inf\{\tau\geq 0:b\in\mathcal{I}(\tau)\}$ denote the (random) time elapsed between the time at which $b$ gets infected and time $t$ . We then have

$\displaystyle\text{Pr}\left(K\leq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t)\right)$	$\displaystyle=\text{Pr}\left(b\text{ is infected during }[t-\kappa_{0},t]\mid\mathcal{S}(t),\mathcal{I}(t)\right)$	(3)
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}1-e^{-A_{\max}\kappa_{0}}$	(4)
	$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}A_{\max}\kappa_{0}$	(5)
	$\displaystyle=\frac{A_{\max}}{\eta\lambda_{\infty}},$	(6)

where $(b)$ holds because $1-e^{-u}\leq u$ for all $u\geq 0$ , and $(a)$ can be explained as follows: given $(\mathcal{S}(\tau),\mathcal{I}(\tau))$ and an infected node $c\in\mathcal{I}_{q}(\tau)$ for some time $\tau\in[t-\kappa_{0},t)$ , and given that $b\in\mathcal{S}_{j}(\tau)$ , we know from Proposition 2 that the conditional probability of the edge $(b,c)$ existing in the network at time $\tau$ is at most $\frac{\rho_{jq}}{\pi(n)}$ . Also, as per the definition of our stochastic epidemic model, given that $(b,c)\in E(\tau)$ and given $(\mathcal{S}(\tau),\mathcal{I}(\tau))$ (and hence, also that $(b,c)\in\mathcal{S}_{j}(\tau)\times\mathcal{I}_{q}(\tau)$ ), the conditional rate of infection transmission from $c$ to $b$ at time $\tau$ is $B_{jq}$ . Hence, given $(\mathcal{S}(\tau),\mathcal{I}(\tau))$ (and hence, that $(b,c)\in\mathcal{S}_{j}(\tau)\times\mathcal{I}_{q}(\tau)$ ), the conditional rate of infection transmission from $c$ to $b$ is at most $B_{jq}\frac{\rho_{jq}}{\pi(n)}=\frac{A_{jq}}{\pi(n)}$ . Under our modelling assumption that distinct edges transmit the infection independently of each other during vanishingly small time intervals, this means that, conditional on $\mathcal{S}(\tau)$ and $\mathcal{I}(\tau)$ , the conditional total rate at which $b$ receives infection is at most

\sum_{q\in[m]}\sum_{c\in\mathcal{I}_{q}(\tau)}\frac{A_{jq}}{\pi(n)}=\sum_{q\in[m]}|\mathcal{I}_{q}(\tau)|\frac{A_{jq}}{\pi(n)}=\sum_{q\in[m]}\beta_{q}^{(\pi(n))}(\tau)A_{jq}\leq A_{\max}\sum_{q\in[m]}\beta_{q}^{(\pi(n))}(\tau)\leq A_{\max}\cdot 1.

Note that this upper bound is time-invariant and does not depend on $\mathcal{S}(\tau)$ or $\mathcal{I}(\tau)$ for any time $\tau$ . It thus follows that, conditional on $(\mathcal{S}(t),\mathcal{I}(t))$ , the rate at which $b$ gets infected is at most $A_{\max}$ throughout the interval $[t-\kappa_{0},t)$ and hence, the probability that $b$ does not get infected during an interval of length $\kappa_{0}$ is at least $e^{-A_{\max}\kappa_{0}}$ . This implies $(a)$ .

We now infer from (3) that

\displaystyle~{}\text{Pr}\left(K\geq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t)\right)\geq 1-\frac{A_{\max}}{\eta\lambda_{\infty}}.

(7)

Next, we lower-bound $\text{Pr}(T\geq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))$ . To this end, note from Proposition 2 that $\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))\leq\frac{\rho_{ij}}{\pi(n)}$ . As a result, we have

	$\displaystyle\|\text{Pr}(T\geq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))-\text{Pr}(T\geq\kappa_{0}\mid(a,b)\notin E(t),\mathcal{S}(t),\mathcal{I}(t))\|$
	$\displaystyle=\|\text{Pr}(T\geq\kappa_{0}\mid(a,b)\notin E(t),\mathcal{S}(t),\mathcal{I}(t))(1-\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t)))$
	$\displaystyle\quad+\text{Pr}(T\geq\kappa_{0}\mid(a,b)\in E(t),\mathcal{S}(t),\mathcal{I}(t))\cdot\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))$
	$\displaystyle\quad-\text{Pr}(T\geq\kappa_{0}\mid(a,b)\notin E(t),\mathcal{S}(t),\mathcal{I}(t))\|$
	$\displaystyle\leq\frac{\rho_{ij}}{\pi(n)},$

which also means that

\displaystyle|\text{Pr}(T<\kappa_{0}\mid(\mathcal{S}(t),\mathcal{I}(t)))-\text{Pr}(T<\kappa_{0}\mid(a,b)\notin E(t),(\mathcal{S}(t),\mathcal{I}(t)))|\leq\frac{\rho_{ij}}{\pi(n)}.

(8)

Moreover, for any realization $(\mathcal{S}_{0},\mathcal{I}_{0})$ of $(\mathcal{S}(t),\mathcal{I}(t))$ , Remark 5 asserts that

\displaystyle\text{Pr}(T\leq\kappa_{0}\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t))\leq 1-e^{-\lambda\kappa_{0}}

for all $0\leq\kappa\leq t$ . Since the right-hand-side above is independent of both $\kappa$ and $(\mathcal{S}_{0},\mathcal{I}_{0})$ , it follows that

\displaystyle\text{Pr}(T\leq\kappa_{0}\mid(\mathcal{S}(t),\mathcal{I}(t)),(a,b)\notin E(t))\leq 1-e^{-\lambda\kappa_{0}}\leq\lambda\kappa_{0}.

(9)

Therefore, as a consequence of (7), (8), (9), and the union bound, we have

$\displaystyle\text{Pr}(T\geq\kappa_{0},K\geq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))$	$\displaystyle=1-\text{Pr}(\{T<\kappa_{0}\}\cup\{K<\kappa_{0}\}\mid\mathcal{S}(t),\mathcal{I}(t))$	(10)
	$\displaystyle\geq 1-\text{Pr}(T<\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))-\text{Pr}(K<\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))$	(11)
	$\displaystyle\geq 1-\frac{A_{\max}}{\eta\lambda_{\infty}}-\frac{\lambda^{(\pi(n))}}{\eta\lambda_{\infty}}-\frac{\rho_{ij}}{\pi(n)}.$	(12)

This further yields,

$\displaystyle\chi_{ij}(t,\mathcal{S},\mathcal{I})$	$\displaystyle=\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))$	(13)
	$\displaystyle=\text{Pr}((a,b)\in E(t)\mid T\geq\kappa_{0},K\geq\kappa_{0},\mathcal{S}(t),\mathcal{I}(t))\cdot\text{Pr}(T\geq\kappa_{0},K\geq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))$	(14)
	$\displaystyle\quad+\text{Pr}((a,b)\in E(t)\mid\{T<\kappa_{0}\}\cup\{K<\kappa_{0}\},\mathcal{S}(t),\mathcal{I}(t))\cdot\text{Pr}(\{T<\kappa_{0}\}\cup\{K<\kappa_{0}\}\mid\mathcal{S}(t),\mathcal{I}(t))$	(15)
	$\displaystyle\leq\frac{\rho_{ij}}{\pi(n)}e^{-B_{ij}\kappa_{0}}\left(1-\frac{A_{\max}}{\eta\lambda_{\infty}}-\frac{\lambda^{(\pi(n))}}{\eta\lambda_{\infty}}-\frac{\rho_{ij}}{\pi(n)}\right)+\left(\frac{A_{\max}}{\eta\lambda_{\infty}}+\frac{\lambda^{(\pi(n))}}{\eta\lambda_{\infty}}+\frac{\rho_{ij}}{\pi(n)}\right)\frac{\rho_{ij}}{\pi(n)}$	(16)
	$\displaystyle=\frac{\rho_{ij}}{\pi(n)}e^{-\frac{B_{ij}}{\eta\lambda_{\infty}}}\left(1-\frac{A_{\max}}{\eta\lambda_{\infty}}-\frac{\lambda^{(\pi(n))}}{\eta\lambda_{\infty}}-\frac{\rho_{ij}}{\pi(n)}\right)+\left(\frac{A_{\max}}{\eta\lambda_{\infty}}+\frac{\lambda^{(\pi(n))}}{\eta\lambda_{\infty}}+\frac{\rho_{ij}}{\pi(n)}\right)\frac{\rho_{ij}}{\pi(n)}$	(17)

where the inequality is a consequence of (10) and Remark 4. Recall that $\lim_{n\rightarrow\infty}\lambda^{(n)}=\lambda_{\infty}$ , which means that the right hand side can be made smaller than $(1+\varepsilon)\frac{\rho_{ij}}{\pi(n)}e^{-\frac{B_{ij}}{\eta\lambda_{\infty}}}$ by choosing $n$ large enough. Moreover (13) holds for all $t\in[t_{1},t_{2}]$ .

Proposition 1 now implies that for all $t\in[t_{1},t_{2}]$ and large enough $n$ ,

\displaystyle\mathbb{E}[s_{i}]^{\prime}=-\sum_{j=1}^{m}B_{ij}\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}]>-\sum_{j=1}^{m}A_{ij}(1+\varepsilon)e^{-\frac{B_{ij}}{\eta\lambda_{\infty}}}\mathbb{E}[s_{i}\beta_{j}],

(18)

Now, observe that for any $t\in[t_{1},t_{2}]$ , we have

	$\displaystyle\mathbb{E}[s_{i}(t)\beta_{j}(t)]$		(19)
	$\displaystyle\leq 1\cdot\text{Pr}\left(\left\\|\left(s_{q}^{(n)}\left(\tau\right),\beta_{q}^{(n)}\left(\tau\right)\right)-\left(y_{q}\left(\tau\right),w_{q}\left(\tau\right)\right)\right\\|_{1}>\varepsilon\right)$		(20)
	$\displaystyle\quad+(w_{i}(t)+\varepsilon)(y_{j}(t)+\varepsilon)\cdot\text{Pr}\left(\left\\|\left(s_{q}^{(n)}\left(\tau\right),\beta_{q}^{(n)}\left(\tau\right)\right)-\left(y_{q}\left(\tau\right),w_{q}\left(\tau\right)\right)\right\\|_{1}\leq\varepsilon\right)$		(21)
	$\displaystyle\leq\delta+y_{i}(t)w_{j}(t)+2\varepsilon+\varepsilon^{2}.$		(22)

Therefore, assuming that $\delta$ and $\varepsilon$ are small enough to satisfy $\delta+2\varepsilon+\varepsilon^{2}<\alpha_{0}\left(\frac{e^{\frac{B_{ij}}{\eta\lambda_{\infty}}}}{1+\varepsilon}-1\right)$ , (18) implies the existence of a constant $\varepsilon^{\prime}>0$ such that :

\mathbb{E}[s_{i}]^{\prime}=-\sum_{j=1}^{m}B_{ij}\mathbb{E}[n\chi_{ij}s_{i}\beta_{j}]\geq-\sum_{j=1}^{m}A_{ij}y_{i}(t)w_{j}(t)+\varepsilon^{\prime}=y_{i}^{\prime}(t)+\varepsilon^{\prime}.

Since this holds for all $t\in[t_{1},t_{2}]$ , we have

\mathbb{E}[s_{i}^{(\pi(n))}(t_{2})]-y_{i}(t_{2})\geq\mathbb{E}[s_{i}^{(\pi(n))}(t_{1})]-y_{i}(t_{1})+(t_{2}-t_{1})\varepsilon^{\prime}

for all sufficiently large $n$ . Here, we observe that $\{s_{i}^{(n)}(t_{1}),\beta_{j}^{(n)}(t_{1}):i,j\in[m],n\in\mathbb{N}\}$ are bounded by the constant function $1$ , which is integrable with respect to probability measures. Therefore, $\{s_{i}^{(n)}(t_{1}):i,j\in[m],n\in\mathbb{N}\}$ are uniformly integrable. Since they converge in probability to $\{y_{i}(t_{1}):i,j\in[m]\}$ (by hypothesis), it follows by Vitali’s Convergence Theorem that they also converge in $L^{1}$ -norm. Thus, $\mathbb{E}[s_{i}^{(n)}(t_{1})]-y_{i}(t_{1})\rightarrow 0$ as $n\rightarrow\infty$ , thereby implying that

\liminf_{n\rightarrow\infty}\left(\mathbb{E}[s_{i}^{(\pi(n))}(t_{2})]-y_{i}(t_{2})\right)\geq(t_{2}-t_{1})\varepsilon^{\prime}.

(23)

On the other hand, Vitali’s Convergence Theorem and our hypothesis also imply that $\mathbb{E}[s_{i}^{(n)}(t_{2})]\rightarrow y_{i}(t_{2})$ as $n\rightarrow\infty$ , which contradicts (23). Hence, our hypothesis that $\{s_{q}^{(n)}(t),\beta_{q}^{(n)}(t)\}_{q\in[m]}$ converge in probability to the solutions of (I) and (II) uniformly on the interval $[t_{1},t_{2}]$ is false. This completes the proof.

Before interpreting Theorem 2, we first note that the result only applies to the time intervals on which $\{y_{i}(t)w_{j}(t):i,j\in[m]\}$ are positive throughout the interval. Although this condition appears stringent, it is mild from the viewpoint of epidemic spreading in the real world. This is because, in practice we are only interested in time periods during which every age group has infected cases (which ensures that $\beta_{j}(t)>0$ for all $j\in[m]$ ), and most epidemics leave behind uninfected individuals (thereby ensuring that $s_{i}(t)>0$ for all $i\in[m]$ ). Therefore, Theorem 2 applies to all time intervals of practical interest.

Restricting our focus to such intervals, Theorem 2 asserts that, if the edge update rate does not go to $\infty$ with the population size, then there exists a positive lower bound on the probability of the age-wise infected and susceptible fractions differing significantly from the corresponding solutions of the age-structured SIR ODEs at one or more points of time in the considered time interval. At this point, we remark that for large populations, the edge update rate $\lambda$ is approximately the reciprocal of the mean duration of every interaction in the network. This means that the greater the value of $\lambda$ , the faster will be the changes that occur in the social interaction patterns of the network. Therefore, in conjunction with Theorem 1, Theorem 2 enables us to draw the following inference: the age-structured SIR model can be expected to approximate a real-world epidemic spreading in a large population accurately if and only if the social interaction patterns of the network change rapidly with time. This is more likely to be the case in crowded public places such as supermarkets and airports.

There is another way to interpret Theorems 1 and 2. Note that we have assumed that the sequence of edge states realized during the timeline of the epidemic are independent for every pair of nodes in the network. Therefore, for greater values of $\lambda$ , the network structure becomes more unrecognizable from its past realizations. Thus, the age-structured SIR model can be expected to approximate epidemic spreading well if and only if the network is highly memoryless, i.e., if and only if the network continually “forgets” its past interaction patterns throughout the timeline of the epidemic under study.

Remark 2.

Observe from the proof of Theorem 2 that the difference between $\mathbb{E}[s_{i}]^{\prime}$ , the first derivative of the expected fraction of infected nodes in $\mathcal{A}_{i}$ , and $y_{i}^{\prime}$ , the first derivative of the corresponding ODE solution $y_{i}(t)$ , is small only if $e^{-\frac{B_{ij}}{\eta\lambda_{\infty}}}$ is close to 1, which happens when $\lambda_{\infty}\gg B_{ij}$ . Moreover, this observation is consistent with Remark 1, according to which the total infection rate from $[n]=\cup_{j=1}^{m}\mathcal{A}_{j}$ to any given susceptible node in $\mathcal{A}_{i}$ is close to $\sum_{j=1}^{m}A_{ij}\beta_{j}(t)$ (and hence, in close agreement with the ODEs (1)) when $\frac{B_{ij}}{\lambda^{(n)}}\ll 1$ . Along with Theorems 1 and 2, this means that the age-structured SIR model is likely to approximate real-world epidemic spreading well if and only if the infection transmission rates are negligible when compared to the social mixing rate $\lambda$ .

Intuitively, when $\frac{B_{ij}}{\lambda}\ll 1$ , the time scales (the mean duration of time) over which the concerned disease spreads from any age group to any other age group are orders of magnitude greater than the time scale over which the network is updated. As a result, the independence of the sequences of edge state updates ensures that most of the possible realizations of the network structure are attained over the time scale of infection transmission. Equivalently, from the viewpoint of the pathogens causing the disease, the effective network structure (the network topology averaged over any of the age-wise infection timescales) is close to being a complete graph. Hence, by extrapolating the existing results on mean-field limits of epidemic processes on complete graphs (such as [30]) to heterogeneous epidemic models, we can assert that the age-structured SIR ODEs are able to approximate the epidemic propagation with a high accuracy.

On the other hand, if the infection rates $B_{ij}$ are too high (and hence, comparable to the social mixing rate $\lambda$ , which is always finite in reality), the pathogens perceive a randomly generated network even on the time scale of infection transmission. Since this random network is sparse (because we assume the expected node degrees to be constant, which results in the edge probability scaling inversely with the population size), it follows that the number of transmissions occurring in any given time period is likely to be smaller than in the case of a complete graph. Thus, the age-structued SIR ODEs overestimate the rate of growth of age-wise infected fractions. This is further confirmed by the sign of the inequality in (23).

5 EMPIRICAL VALIDATION

We now validate the age-structured SIR model in the context of the COVID-19 pandemic in Japan as follows: we first estimate the model parameters using the data provided by the Government of Japan, and we then compare the trajectories generated by the model with the reference data.

5.1 Dataset

We use a dataset provided by the Government of Japan at [32]. This dataset partitions the population of the prefecture of Tokyo into $m=5$ age groups: 0 - 19, 20 - 39, 40 - 59, 60 - 79, and 80+ years old individuals. For each age group $i\in[m]$ and each day $k$ in the year-long timeline $\Gamma=\{\text{March 10, 2020},\ldots,\text{April 9, 2021}\}$ , the dataset lists the total number of people infected in the age group until date $k$ . We denote this number by $I_{i}^{T}[k]$ .

5.2 Preprocessing

Due to several factors, such as lack of reporting/testing on the weekends, the raw data has missing information and is contaminated with noise. Therefore, using a moving average filter with a window size of 15 days, we de-noise the raw data to obtain the estimated total number of infected individuals by day $k$ in age group $i$ , denoted by $I_{i}^{T}[k]$ . We then estimate from the smoothed data the number of susceptible, infected, and recovered individuals in age group $i\in[m]$ on day $k$ , denoted by $S_{i}[k]$ , $I_{i}[k]$ , and $R_{i}[k]$ , respectively. We do this as follows: for any age group $i\in[m]$ and day $k\in\Gamma$ , we have $I_{i}^{T}[k]=I_{i}[k]+R_{i}[k]$ , because the cumulative number of infections $I_{i}^{T}[k]$ includes both active COVID-19 cases and closed cases (cases of individuals who were infected in the past but recovered/succumbed by day $k$ ). Therefore, to estimate $I_{i}[k]$ and $R_{i}[k]$ from $I_{i}^{T}[k]$ , we assume that every infected individual takes exactly $T_{R}=14$ days to recover. This assumption is consistent with WHO’s criteria for discharging patients from isolation (i.e., discontinuing transmission-based precautions) [33] after a period involving the first 10 days from the onset of symptoms and 3 additional symptom-free days (if the patient is originally symptomatic) or after 10 days from being tested positive for SARS-CoV-2 (if the patient is asymptomatic). After the required period, the patients were not required to re-test. Under such an assumption on the recovery time, we have $R_{i}[k]=I_{i}^{T}[k-T_{R}]$ and $I_{i}[k]=I_{i}^{T}[k]-I_{i}^{T}[k-T_{R}]$ . Next, we obtain $S_{i}[k]$ by subtracting $I_{i}^{T}[k]$ from the total population of $\mathcal{A}_{i}$ , which is obtained from the age distribution and the total population of Tokyo.

We must mention that in the subsequent analysis, all infected individuals are considered infectious, i.e., they can potentially transmit the SARS-CoV-2 virus to their susceptible contacts. This assumption, on which the classical SIR model and all its variants are based, is consistent with the CDC’s understanding of the first wave of SARS-CoV-2 infection, which claims that every infected individual remains infectious for up to about 10 days from the onset of symptoms, though the exact duration of the period of infectiousness remains uncertain [34].

5.3 Parameter Estimation Algorithm

Before estimating the parameters of our model, we discretize the ODEs (1) with a step size of 1 day and obtain the following:

$\displaystyle s_{i}[k+1]-s_{i}[k]$	$\displaystyle=-s_{i}[k]\sum^{m}_{j=1}A_{ij}\beta_{j}[k],$	(24)
$\displaystyle\beta_{i}[k+1]-\beta_{i}[k]$	$\displaystyle=s_{i}[k]\sum^{m}_{j=1}A_{ij}\beta_{j}[k]-\gamma_{i}\beta_{i}[k],$	(25)
$\displaystyle r_{i}[k+1]-r_{i}[k]$	$\displaystyle=\gamma_{i}\beta_{i}[k],$

A key observation here is that these equations are linear in the model parameters. Therefore, given the sets of fractions $\{s_{i}[k]:i\in[m],k\in\Gamma\}$ , $\{\beta_{i}[k]:i\in[m],k\in\Gamma\}$ , and $\{r_{i}[k]:i\in[m],k\in\Gamma\}$ (which we obtain by implementing the data processing steps described above) for all $i\in[m]$ , we can express (24) in the form of a matrix equation $Cx=d$ , where the column vector $x\in\mathbb{R}^{m^{2}+m}$ is a stack of the parameters $\{A_{ij}:1\leq i,j\leq m\}$ and $\{\gamma_{i}:1\leq i\leq m\}$ , the column vector $d$ is a stack of the increments $\{s_{i}[k+1]-s_{i}[k]:i\in[m],k\in\Gamma\}$ , $\{\beta_{i}[k+1]-\beta_{i}[k]:i\in[m],k\in\Gamma\}$ , and $\{r_{i}[k+1]-r_{i}[k]:i\in[m],k\in\Gamma\}$ , and $C$ is a matrix of coefficients. Thus, solving the least-squares problem (26) gives us the best estimates of the model parameters ${\{A_{ij}:i,j\in[m]\}\cup\{\gamma_{i}:i\in[m]\}}$ in the mean-square sense.

\displaystyle\hat{x}=\underset{x\geq 0}{\text{argmin}}\|Cx-d\|_{2}.

(26)

However, the values of the contact rates $A_{ij}$ change as and when the patterns of social interaction in the network change during the course of the pandemic. For this reason, we assume that the pandemic timeline splits up into multiple phases, say $\Gamma_{1},\ldots,\Gamma_{s}$ , with the contact rates varying across phases, and we perform the required optimization separately for each phase. At the same time, we do not expect the contact rates to make quantum leaps (or falls) from one phase to the next. Therefore, for every $\ell\geq 2$ , in the objective function corresponding to Phase $\ell$ we introduce a regularization term that penalizes any deviation of the optimization variables from the model parameters estimated for the previous phase (Phase $\ell-1$ ). Adding this term also ensures that our parameter estimation algorithm does not overfit the data associated with any one phase. Our optimization problem for Phase $\ell$ thus becomes

\displaystyle\hat{x}^{(\ell)}=\underset{x\geq 0}{\text{argmin}}\left(\|Cx-d\|_{2}+\lambda\|x^{(\ell)}-x^{(\ell-1)}\|_{2}\right),

(27)

where $x^{(\ell)}$ is the parameter vector estimated for Phase $\ell$ .

We now summarize this parameter estimation algorithm for Phase $\ell\in[s]$ .

Algorithm 1 Parameter Estimation Algorithm for Phase

\ell

Input: $(s_{i}[k],\beta_{i}[k],r_{i}[k])$ for all $i\in[m]$ and $k\in\Gamma_{\ell}$
Output: $\hat{x}$

1:function Get_Parameters(

(s_{i}[k],\beta_{i}[k],r_{i}[k])

)

2: for each day, each age group do

3: Stack the difference equations (24) vertically

4: Obtain the matrix equation

Cx=d

5: Solve Least Squares Problem (27)

6: return

\hat{x}

5.4 Phase Detection Algorithm

We now provide an algorithm that divides the timeline of the pandemic into multiple phases in such a way that the beginning of each new phase indicates a significant change in one or more of the contact rates $\{A_{ij}:i,j\in[m]\}$ .

Given the pandemic timeline $\{p_{0},\ldots,p_{s}\}$ (where $p_{0}$ denotes March 10, 2020 and $p_{s}$ denotes April 9, 2021), our phase detection algorithm outputs $s-1$ phase boundaries $p_{1}\leq p_{2}\leq\cdots\leq p_{s-1}$ that divide $[p_{0},p_{s})$ into $s$ phases, namely $\Gamma_{1}=[p_{0},p_{1}),\Gamma_{2}=[p_{1},p_{2}),\ldots,\Gamma_{s}=[p_{s-1},p_{s})$ . Central to the algorithm are the following optimization problems:

Problem (a): Unconstrained Optimization

\displaystyle\underset{x\geq 0}{\text{minimize}}\ \ \ \|C_{[p,p+w)}x-d_{[p,p+w)}\|_{2}.

(28)

Problem (b): Constrained Optimization

	$\displaystyle\underset{x\geq 0}{\text{minimize}}\ \ \$	$\displaystyle\\|C_{[p,p+w)}x-d_{[p,p+w)}\\|_{2},$		(29)
	subject to	$\displaystyle\\|x-\bar{x}_{[p,p+w)}\\|_{2}\leq\varepsilon\\|\bar{x}_{[p-\Delta p,p-\Delta p+w)}\\|_{2}.$		(30)

In these problems, $p\in\Gamma$ denotes the start date (chosen recursively as described in Algorithm 2), $w\in\mathbb{N}$ is the optimization window, $\Delta p<w$ is the algorithm step size, $[p,p+w)$ denotes a $w$ -day period from day $p$ , $C_{[p,p+w)}$ and $d_{[p,p+w)}$ are obtained from $\{(s_{i}[k],\beta_{i}[k],r_{i}[k]):i\in[m],k\in\{p,\ldots,p+w\}\}$ by using the procedure described in Section 5.3, and $\bar{x}:=\operatornamewithlimits{argmin}_{x\geq 0}\|C_{[p,p+w)}x-d_{[p,p+w)}\|_{2}$ is the parameter vector estimated by Problem (a). We set $w=30$ (days), and the quantities $\Delta p$ and $\varepsilon$ are pre-determined algorithm parameters whose choice is discussed in the next subsection.

Observe that both Problem and Problem (b) result in the minimization of the mean-square error (31), where ${\{(\hat{s}_{i}[k],\hat{\beta}_{i}[k],\hat{r}_{i}[k]):i\in[m],k\in\{p,\ldots,p+w\}\}}$ are the model-generated values (estimates) of the susceptible, infected, and recovered fractions $\{(s_{i}[k],\beta_{i}[k],r_{i}[k]):i\in[m],k\in\{p,\ldots,p+w\}\}$ . Also note that Problem (a) performs this minimization while ignoring all the previously estimated model parameters, whereas Problem (b) performs the same minimization while constraining $x$ to remain close to the parameter vector estimated for the period $[p-\Delta p,p-\Delta p+w)$ . However, if the contact rates do not change significantly around day $p$ , then the additional constraint imposed in Problem (b) should be satisfied automatically (without imposition) in Problem (a), which should in turn result in the same mean-square error for both the problems.

\displaystyle\mathcal{E}=\frac{1}{3m(w+1)}\sum_{i\in[m]}\sum_{k\in\{p,\ldots,p+w\}}\bigg{(}(s_{i}[k]-\hat{s}_{i}[k])^{2}+(\beta_{i}[k]-\hat{\beta}_{i}[k])^{2}+(r_{i}[k]-\hat{r}_{i}[k])^{2}\bigg{)}.

(31)

Therefore, after solving Problems (a) and (b), our phase detection algorithm compares $\mathcal{E}_{(a)p}$ (the mean-square error for Problem (a)) with $\mathcal{E}_{(b)p}$ (the mean-square error for Problem (b)) as follows: using (31), the algorithm first computes $\mathcal{E}_{(a)p}$ and $\mathcal{E}_{(b)p}$ . It then compares $\frac{|\mathcal{E}_{(b)p}-\mathcal{E}_{(a)p}|}{\mathcal{E}_{(a)p}}$ with $\delta$ , a positive threshold whose choice is discussed in the next subsection. If

\displaystyle\frac{|\mathcal{E}_{(b)p}-\mathcal{E}_{(a)p}|}{\mathcal{E}_{(a)p}}>\delta,

(32)

then $p$ is identified as a phase boundary. Otherwise, the algorithm increments the value of $p$ by $\Delta p$ , checks whether the interval $[p,p+w)$ is part of the timeline $\Gamma$ , and repeats the entire procedure described above.

Finally, the algorithm merges every short phase (length $\leq 20$ days) with its predecessor by deleting the appropriate phase boundary(s). There are two reasons for this step. First, the contact rates are believed to change not instantly but with a transition period of positive duration. Second, since the data used is noisy, to avoid overfitting the data it is necessary for the number of data points per phase (given by $2m$ times the number of days per phase) to significantly exceed $m^{2}+m$ , the number of model parameters to be estimated per phase.

We now provide the pseudocode for the entire algorithm. Observe that Problems (a) and (b) are both convex optimization problems. This enables us to use the Embedded Conic Solver (ECOS) [35] of CVXPY [36, 37] to implement our algorithm.

Algorithm 2 Phase Detection Algorithm

Input: $(s_{i}[k],\beta_{i}[k],r_{i}[k])$ for all $i\in[m]$ and $k\in\Gamma$
Output: Set of phase boundaries $\mathcal{B}$

1:function Detect_Phases(

(s_{i}[k],\beta_{i}[k],r_{i}[k])

)

2: Initialize set of phase boundaries

\mathcal{B}\leftarrow\phi

3: Initialize start date

p\leftarrow\Delta p

4: while

p\in\Gamma

5: Solve Problem (a) for window

[p,p+w)

6: Solve Problem (b) for window

[p,p+w)

7: if condition (32) holds then

\mathcal{B}\leftarrow\mathcal{B}\cup\{p\}

p\leftarrow p+\Delta p

10: Initialize

p_{\text{start}}\leftarrow 0

11: Initialize

\mathbf{b}\leftarrow\text{list}(\mathcal{B})

12: Sort

\mathbf{b}

in ascending order

13: for

p\in\mathbf{b}

14: if

p-p_{\text{start}}\leq 20

then

15:

\mathcal{B}\leftarrow\mathcal{B}\setminus\{p\}

16: else

17:

p_{\text{start}}=p

18: return

\mathcal{B}

5.5 Selection of Algorithm Parameters

We now explain our parameter choices for the algorithms described above.

5.5.1 Phase Detection Algorithm

As mentioned earlier, for Algorithm 2, we set $\Delta p=5$ days and the optimization window $w=30$ days. This ensures that the optimization window is large enough for the number of model parameters to be significantly smaller than the number of data points used to estimate these parameters in Problems (a) and (b). In addition, we set $\delta=3$ , and $\varepsilon=10^{-4}$ for the following reasons:

1.

$\varepsilon=10^{-4}$ : If both $[p,p+w)$ and $[p-\Delta p,p-\Delta p+w)$ are sub-intervals of the same phase, then the same set of contact rates (and hence the same parameter vector $x$ ) should apply to the network during both the time intervals.
2.

$\delta=3$ : If day $p$ marks the beginning of a new phase (i.e., a new set of contact rates), we expect the least-squares error (31) to increase significantly upon the imposition of the constraint introduced in (29).

5.5.2 Parameter Estimation Algorithm

We set $\lambda=10^{-5}$ in (27). This small but non-zero value is consistent with our belief that around every phase boundary, contact rates change gradually but significantly during a transition period involving the phase boundary.

5.6 Results

We now present the results of implementing both the algorithms on our chosen dataset.

5.6.1 Phase Detection

Algorithm 2 detects the following phases.

Phase	From	To	Corresponding Events
1	Mar 10 2020	Mar 28 2020	Closure of Schools
2	Mar 28 2020	April 23 2020	Issuance of State of Emergency
3	April 23 2020	May 20 2020
4	May 20 2020	Jun 22 2020
5	Jun 22 2020	Jul 24 2020	Summer Vacation
6	Jul 24 2020	Aug 25 2020	Obon, Summer Vacation
7	Aug 25 2020	Sep 23 2020	Summer Vacation
8	Sep 23 2020	Oct 20 2020	“Go to Travel” Campaign
			Relaxation of Immigration Policy
9	Oct 20 2020	Nov 14 2020	“Go to Eat” Campaign
			“Go to Travel” Campaign
10	Nov 14 2020	Dec 19 2020
11	Dec 19 2020	Jan 12 2021	Issuance of State of Emergency
			Winter Vacation
12	Jan 12 2021	Feb 07 2021
13	Feb 07 2021	Apr 09 2021

Table 1: Phases Detected by Algorithm 2 [38, 39]

Although some of the detected phases can be accounted for by identifying changes in governmental policies and major social events, many of them seem to result from changes in social interaction patterns that cannot be explained using public information sources (such as news websites). However, this is consistent with out intuition that social behavior is inherently dynamic – it displays significant changes even in the absence of government diktats and important calendar events. Moreover, except for the first phase, the length of every phase is at least 25 days, which points to the likely scenario that it takes at least 3 to 4 weeks for the contact rates to change significantly. This could be true because social behavior is often unorganized. In particular, the interaction patterns of any one individual are often not in synchronization with those of others.

Another noteworthy inference to be drawn from Table 1 and Figure 1 is that policy changes initiated by governments have a delayed effect at times. For example, the “Go to Travel” and the “Go to Eat” campaigns, launched between mid-September and mid-November (Phases 8 and 9), seem to have caused a spike in daily case counts in the subsequent phases (Phases 10 and 11). Likewise, the State of Emergency issued in Phase 11 seems to have come to fruition in Phase 12 and its effects appear to have remained until the last phase (Phase 13).

5.6.2 Parameter Estimation and Its Implications

Figure 1 below plots the original and the model-generated fractions of infected individuals in each age group as functions of time.

Refer to caption — Figure 1: Age-wise Daily Fractions of Infected Individuals in Tokyo, Japan: Original and Generated Trajectories

Figure 2 plots the estimated contact rates and labels the 10 most significant ones among the 25 rates.

As seen in Figure 1, three COVID-19 surges or “waves” occur during the considered timeline. For each wave, we explain below the corresponding contact rate variations and their implications with the help of the mobility data of Tokyo (Figure 3) collected by Google [40].

The First Wave (March 2020 - June 2020, Phases 1 - 3)

This wave corresponds to a rapid surge in daily cases across the world followed by various governmental measures such as issuance of national emergencies, tightening of immigration policies, home quarantines, and school closures. In Japan, the national emergency consisted of various measures such as restrictions on service times in restaurants and bars, enforcement of work from home, and a limit on the number of people attending public events. As a result of these measures, the mobility of workplaces, retail and recreation, and transit stations dropped dramatically in April 2020 and remained low for over a month (Figure 3).

This drop is reflected in our simulation results (Figure 2), which show that the three greatest contact rates decreased steadily from April to June. However, Figure 2 also shows that contact rates from the age group 60-79 to most other age groups (shown in blue) remained remarkably high throughout the timeline $\Gamma$ . This may be because most people admitted to nursing homes are aged above 60 and frequently come in contact with the relatively younger care-taking staff. More strikingly, the contact rate from age group 60-79 to age group 80+ is consistently high. This could be because there is a significant number of married couples with members from both these age groups (thereby resulting in a high value of $\rho_{ij}$ for $(i,j)=(m,m-1)$ ) and because the age group 80+ has the lowest immunity levels, which leads to a large effective $B_{ij}$ (infection rate) for $(i,j)=(m,m-1)$ .

The Second Wave (July 2020 - September 2020, Phases 4 - 7)

The most intriguing aspect of the second wave is that the wave subsided without any significant governmental interventions (such as the issuance of a nationwide emergency). To explain this phenomenon, some researchers point out that (i) the rate of PCR testing increased in July and thus more infections were detected in the first few weeks of the second wave, and (ii) people’s mobility decreased in August during the Japanese summer vacation period called “Obon” [39]. As we can infer from Figure 3, this decrease in mobility occurs primarily at workplaces and transit stations [39].

Besides Figure 3, our simulation results provide some insight into the second wave. Figure 1 shows that the contact rates from age group 60-79 to other age groups do not show any increase during the first few weeks of the wave. However, the intra-group contact rate of the age group 20-39 increases rapidly before this period and drops significantly in August, corresponding to a decrease in daily cases. This strongly suggests that the social activities of those aged between 20-39 played a key role in the second wave. Meanwhile, contact rates from the age group 60-79 decreased after the first wave, possibly because of an increase in the proportion of quarantined individuals among the elderly, which in turn could have resulted from an increased public awareness of older age groups’ higher susceptibility to the virus.

The Third Wave (October 2020 - January 2021, Phases 8 - 11)

This wave was the most severe of the three because in October, a policy promoting domestic travel (the “Go to Travel” campaign) was implemented in the Tokyo prefecture and eating out was promoted as well (as part of the “Go to Eat” campaign). In addition, Japan started relaxing its immigration policy in October. [39] points out that the “major factors for this rise include the government’s implementation of further policies to encourage certain activities, relaxed immigration restrictions, and people not reducing their level of activity”. This observation is supported by Figure 3, which shows that there is no drop in mobility in any category during the third wave. As a result, daily infection counts dropped only after the second state of emergency was issued by the government on January 7, 2021.

In agreement with these observations are our simulation results (Figure 1), which show that the age group 60-79 remained the most infectious throughout the third wave, and that the contact rates from the age group 20-39 gradually increased in the early weeks of the wave. This was followed by a remarkable decrease in the intra-group contact rate of the age group 60-79 from mid-January onwards.

Comparing the Age Groups on the Basis of Infectiousness and Susceptibility

It is evident from Figure 2 that among all the five age groups, members of the youngest age group (0-19) are the least likely to contract COVID-19. This validates the current understanding of the scientific community that children and teenagers are more immune to the disease than adults. At the opposite extreme, the age groups 80+ and 20-39 appear to be the most vulnerable, possibly because members of the former group have the lowest immunity levels and the latter group exhibits the highest levels of mobility and social activity.

Besides throwing light on how the likelihood of receiving infection varies across age groups, Figure 2 also throws light on how the likelihood of transmitting the infection varies across age groups. From the figure, the two most infectious age groups are clearly 60-79 and 20-39. Surprisingly, the age group 80+ is found to be less infectious than the group 60-79, perhaps because of the lower social mobility of the former. The figure also shows that the age groups 0-19, 40-59 and 80+ are remarkably less infectious than the other two age groups. However, we need additional empirical evidence to validate these findings, and it would be interesting to see whether our inferences are echoed by future empirical studies.

6 CONCLUSION AND FUTURE DIRECTIONS

We have analyzed the age-structured SIR model of epidemic spreading from both theoretical and empirical viewpoints. Starting from a stochastic epidemic model, we have shown that the ODEs defining the age-structured SIR model are the mean-field limits of a continuous-time Markov process evolving over a time-varying network that involves random, asynchronous interactions if and only if the social mixing rate grows unboundedly with the population size. We have also provided a lower-bound on the associated convergence rates in terms of the social mixing rate. As for empirical validation, we have proposed two algorithms: a least-square method to estimate the model parameters based on real data and a phase detection algorithm to detect changes in contact rates and hence also the most significant social behavioral changes that possibly occurred during the observed pandemic timeline. We have validated our model empirically by using it to approximate the trajectories of the numbers of susceptible, infected, and recovered individuals in the prefecture of Tokyo, Japan, over a period of more than 12 months. Our results show that for the purpose of forecasting the future of the COVID-19 pandemic and designing appropriate control policies, the age-structured SIR model is likely to be a strong contender among compartmental epidemic models.

Our analysis, however, has a few limitations. First, it is not clear whether the large number of phases detected by Algorithm 2 indicates rapidly changing social interaction patterns or simply that our model is unable to approximate the pandemic over timescales significantly longer than a month. Second, the outputs of our algorithms have a few surprising implications that are as yet unconfirmed by independent empirical studies. For example, the estimated contact rates indicate that the age group 60-79 is consistently more infectious than the age group 20-39, a finding that is inconsistent with the widely held belief that younger age groups are significantly more mobile than the older ones. Such apparent anomalies highlight the need for age-stratified mobility datasets that would enable further investigation into the dynamic interplay between social behavior and epidemic spreading.

References

[1] Worldometer, “COVID-19 Coronavirus Pandemic,” World Health Organization, www.worldometers.info/coronavirus, last accessed 2021, November 11.
[2] N. Ferguson, D. Laydon, G. Nedjati-Gilani, N. Imai, K. Ainslie, M. Baguelin, S. Bhatia, A. Boonyasiri, Z. Cucunubá, G. Cuomo-Dannenburg, et al., “Report 9: Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand,” Imperial College London, vol. 10, no. 77482, pp. 491–497, 2020.
[3] F. E. Alvarez, D. Argente, and F. Lippi, “A simple planning problem for COVID-19 lockdown,” tech. rep., National Bureau of Economic Research, 2020.
[4] D. Acemoglu, V. Chernozhukov, I. Werning, and M. D. Whinston, “A multi-risk SIR model with optimally targeted lockdown,” NBER working paper, no. w27102, 2020.
[5] K. Chatterjee, K. Chatterjee, A. Kumar, and S. Shankar, “Healthcare impact of COVID-19 epidemic in India: A stochastic mathematical model,” Medical Journal, Armed Forces, India, vol. 76, no. 2, pp. 147–155, 2020.
[6] P. E. Paré, J. Liu, C. L. Beck, A. Nedić, and T. Başar, “Multi-competitive viruses over time-varying networks with mutations and human awareness,” Automatica, vol. 123, p. 109330, 2021.
[7] F. Bullo, “Current epidemiological models: Scientific basis and evaluation,” Health, vol. 4, p. 14, 2020.
[8] W. O. Kermack and A. G. McKendrick, “A contribution to the mathematical theory of epidemics,” Proceedings of the Royal Society of London, Series A, vol. 115, no. 772, pp. 700–721, 1927.
[9] T. G. Kurtz, “Solutions of ordinary differential equations as limits of pure jump Markov processes,” Journal of Applied Probability, vol. 7, no. 1, pp. 49–58, 1970.
[10] M. Benaim and J.-Y. Le Boudec, “A class of mean field interaction models for computer and communication systems,” Performance Evaluation, vol. 65, no. 11-12, pp. 823–838, 2008.
[11] E. Volz, “SIR dynamics in random networks with heterogeneous connectivity,” Journal of Mathematical Biology, vol. 56, no. 3, pp. 293–310, 2008.
[12] L. Decreusefond, J.-S. Dhersin, P. Moyal, V. C. Tran, et al., “Large graph limit for an SIR process in random network with heterogeneous connectivity,” The Annals of Applied Probability, vol. 22, no. 2, pp. 541–575, 2012.
[13] J. Mossong, N. Hens, M. Jit, P. Beutels, K. Auranen, R. Mikolajczyk, M. Massari, S. Salmaso, G. S. Tomba, J. Wallinga, et al., “Social contacts and mixing patterns relevant to the spread of infectious diseases,” PLoS Medicine, vol. 5, no. 3, p. e74, 2008.
[14] K. Prem, A. R. Cook, and M. Jit, “Projecting social contact matrices in 152 countries using contact surveys and demographic data,” PLoS Computational Biology, vol. 13, no. 9, p. e1005697, 2017.
[15] P. Klepac, A. J. Kucharski, A. J. Conlan, S. Kissler, M. L. Tang, H. Fry, and J. R. Gog, “Contacts in context: large-scale setting-specific social mixing matrices from the BBC Pandemic Project,” MedRxiv, 2020.
[16] I. Voinsky, G. Baristaite, and D. Gurwitz, “Effects of age and sex on recovery from COVID-19: Analysis of 5769 Israeli patients,” Journal of Infection, vol. 81, no. 2, pp. e102–e103, 2020.
[17] G. Ellison, “Implications of heterogeneous SIR models for analyses of COVID-19,” tech. rep., National Bureau of Economic Research, 2020.
[18] D. Acemoglu, V. Chernozhukov, I. Werning, and M. D. Whinston, “Optimal targeted lockdowns in a multigroup SIR model,” American Economic Review: Insights, vol. 3, no. 4, pp. 487–502, 2021.
[19] D. Baqaee, E. Farhi, M. J. Mina, and J. H. Stock, “Reopening scenarios,” tech. rep., National Bureau of Economic Research, 2020.
[20] A. A. Rampini, “Sequential lifting of COVID-19 interventions with population heterogeneity,” tech. rep., National Bureau of Economic Research, 2020.
[21] C. A. Favero, A. Ichino, and A. Rustichini, “Restarting the economy while saving lives under COVID-19,” 2020. CEPR Discussion Paper No. DP14664.
[22] R. Parasnis, A. Sakhale, R. Kato, M. Franceschetti, and B. Touri, “A Case for the Age-Structured SIR Dynamics for Modelling COVID-19,” in 2021 60th IEEE Conference on Decision and Control (CDC), pp. 5508–5513, IEEE, 2021.
[23] A. V. Tkachenko, S. Maslov, A. Elbanna, G. N. Wong, Z. J. Weiner, and N. Goldenfeld, “Time-dependent heterogeneity leads to transient suppression of the COVID-19 epidemic, not herd immunity,” Proceedings of the National Academy of Sciences, vol. 118, no. 17, 2021.
[24] J. Dolbeault and G. Turinici, “Heterogeneous social interactions and the COVID-19 lockdown outcome in a multi-group SEIR model,” Mathematical Modelling of Natural Phenomena, vol. 15, p. 36, 2020.
[25] S. Contreras, H. A. Villavicencio, D. Medina-Ortiz, J. P. Biron-Lattes, and Á. Olivera-Nappa, “A multi-group SEIRA model for the spread of COVID-19 among heterogeneous populations,” Chaos, Solitons & Fractals, vol. 136, p. 109925, 2020.
[26] A. Viguerie, G. Lorenzo, F. Auricchio, D. Baroli, T. J. Hughes, A. Patton, A. Reali, T. E. Yankeelov, and A. Veneziani, “Simulating the spread of COVID-19 via a spatially-resolved Susceptible–Exposed–Infected–Recovered–Deceased (SEIRD) model with heterogeneous diffusion,” Applied Mathematics Letters, vol. 111, p. 106617, 2021.
[27] J. E. Harris, “Data from the COVID-19 epidemic in Florida suggest that younger cohorts have been transmitting their infections to less socially mobile older adults,” Review of Economics of the Household, vol. 18, no. 4, pp. 1019–1037, 2020.
[28] M. Giagheddu and A. Papetti, “The macroeconomics of age-varying epidemics,” Available at SSRN 3651251, 2020.
[29] A. Janiak, C. Machado, and J. Turén, “COVID-19 contagion, economic activity and business reopening protocols,” Journal of Economic behavior & Organization, vol. 182, pp. 264–284, 2021.
[30] B. Armbruster and E. Beck, “Elementary proof of convergence to the mean-field model for the SIR process,” Journal of Mathematical Biology, vol. 75, no. 2, pp. 327–339, 2017.
[31] P. L. Simon and I. Z. Kiss, “From exact stochastic to mean-field ODE models: a new approach to prove convergence results,” The IMA Journal of Applied Mathematics, vol. 78, no. 5, pp. 945–964, 2013.
[32] Tokyo Metropolitan Government, “COVID-19 Information Website,” https://stopcovid19.metro.tokyo.lg.jp/en, last accessed 2021, September 28.
[33] W. H. Organization, “Criteria for releasing COVID-19 patients from isolation,” https://www.who.int/news-room/commentaries/detail/criteria-for-releasing-covid-19-patients-from-isolation, last accessed 2021, September 28.
[34] C. for Disease Control and Prevention, “Clinical Questions about COVID-19: Questions and Answers / When is someone infectious?,” https://www.cdc.gov/coronavirus/2019-ncov/hcp/faq.html#Transmission, last accessed 2021, September 28.
[35] A. Domahidi, E. Chu, and S. Boyd, “ECOS: An SOCP solver for embedded systems,” in 2013 European Control Conference (ECC), pp. 3071–3076, IEEE, 2013.
[36] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016.
[37] A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd, “A rewriting system for convex optimization problems,” Journal of Control and Decision, vol. 5, no. 1, pp. 42–60, 2018.
[38] Wikipedia, “Timeline of the COVID-19 pandemic in Japan,” last accessed 2021, September 28.
[39] K. Karako, P. Song, Y. Chen, W. Tang, and N. Kokudo, “Overview of the characteristics of and responses to the three waves of COVID-19 in japan during 2020-2021,” BioScience Trends, 2021.
[40] Google, “COVID-19 Community Mobility Reports,” https://www.google.com/covid19/mobility/, last accessed 2021, September 28.
[41] S. P. Lalley, “Continuous Time Markov Chains,” Lecture Notes on Stochastic Processes II, 2012. galton.uchicago.edu/~lalley/Courses/313/ContinuousTime.pdf.

Appendix

Our first aim is to prove Proposition 1, which is based on the Lemma 1. This lemma describes a known property of continuous-time Markov chains, but we prove it nevertheless. The proof is based on the concept of jump times, defined below.

Definition 1 (Jump Times).

The jump times of the Markov chain $\{\mathbf{X}(\tau):\tau\geq 0\}$ are the random times defined by $J_{0}:=0$ and $J_{\ell}:=\inf\{\tau\geq 0:\mathbf{X}(J_{\ell-1}+\tau)\neq\mathbf{X}(J_{\ell-1})\}$ for all $\ell\in\mathbb{N}$ .

Note that jump times are simply the times at which the Markov chain jumps or transitions to a new state.

Lemma 1.

Let $\mathbf{x}\in\mathbb{S}$ and let $[t,t+\Delta t)\subset[0,\infty)$ . Given that $\mathbf{X}(t)=\mathbf{x}$ , the conditional probability that more than one state transitions occur during $[t,t+\Delta t)$ is $o(\Delta t)$ .

Proof.

Let $\mathbf{y},\mathbf{z}\in\mathbb{S}$ be any two states such that $\mathbf{y}$ and $\mathbf{z}$ potentially succeed $\mathbf{x}$ and $\mathbf{y}$ , respectively. Also, let $\{\mathbf{X}(J_{i})\}_{i=0}^{\infty}$ be the embedded jump chain of $\{\mathbf{X}(\tau)\}_{\tau\geq 0}$ (where $J_{0}:=0$ ). Then, given that $\mathbf{X}(0)=\mathbf{x}$ , $\mathbf{X}(J_{1})=\mathbf{y}$ , and $\mathbf{X}(J_{2})=\mathbf{z}$ , the holding times $J_{1}$ and $J_{2}-J_{1}$ are conditionally independent exponential random variables with parameters $q_{x}:=|\mathbf{Q}(\mathbf{x},\mathbf{x})|$ and $q_{y}:=|\mathbf{Q}(\mathbf{y},\mathbf{y})|$ , respectively. Therefore, given that the original Markov chain makes its first and second transitions from $\mathbf{x}$ to $\mathbf{y}$ and from $\mathbf{y}$ to $\mathbf{z}$ respectively, the conditional probability that both of these transitions occur during $[0,\Delta t)$ is given by

	$\displaystyle\text{Pr}(J_{2}<\Delta t\mid(\mathbf{X}(0),\mathbf{X}(J_{1}),\mathbf{X}(J_{2}))=(\mathbf{x},\mathbf{y},\mathbf{z}))$		(33)
	$\displaystyle\leq\text{Pr}(J_{2}-J_{1}<\Delta t,J_{1}<\Delta t\mid(\mathbf{X}(0),\mathbf{X}(J_{1}),\mathbf{X}(J_{2}))=(\mathbf{x},\mathbf{y},\mathbf{z}))$		(34)
	$\displaystyle=\text{Pr}(J_{2}-J_{1}<\Delta t\mid(\mathbf{X}(0),\mathbf{X}(J_{1}),\mathbf{X}(J_{2}))=(\mathbf{x},\mathbf{y},\mathbf{z}))\cdot\text{Pr}(J_{1}<\Delta t\mid(\mathbf{X}(0),\mathbf{X}(J_{1}),\mathbf{X}(J_{2}))=(\mathbf{x},\mathbf{y},\mathbf{z}))$		(35)
	$\displaystyle=(1-e^{-q_{y}\Delta t})(1-e^{-q_{x}\Delta t})$		(36)
	$\displaystyle=o(\Delta t).$		(37)

Therefore, $\text{Pr}(J_{2}<\Delta t\mid\mathbf{X}(0)=\mathbf{x})$ , which is at most $\max_{\mathbf{y},\mathbf{z}\in\mathbb{S}}\text{Pr}(J_{2}<\Delta t\mid(\mathbf{X}(0),\mathbf{X}(J_{1}),\mathbf{X}(J_{t})=(\mathbf{x},\mathbf{y},\mathbf{z}))$ , is $o(\Delta t)$ . Hence, given that $\mathbf{X}(0)=\mathbf{x}$ , the conditional probability that at least two state transitions occur during $[0,\Delta t)$ is $o(\Delta t)$ . By time-homogeneity, this means the following: given that $\mathbf{X}(t)=\mathbf{x}$ , the conditional probability that at least two state transitions occur during $[t,t+\Delta t)$ is $o(\Delta t)$ .

Proof of Proposition 1

Proof.

We derive the equations one by one.

Proof of (i):

Consider any state $\mathbf{x}\in\mathbb{S}$ . Then, by the definition of $\mathbf{Q}$ , for any $i\in[n]$ and $a\in\mathcal{S}_{i}(\mathbf{x})$ , we have

\displaystyle~{}\text{Pr}(\mathbf{X}(t+\Delta t)=\mathbf{x}_{\uparrow a}\mid\mathbf{X}(t)=\mathbf{x})

\displaystyle=\mathbf{Q}(\mathbf{x},\mathbf{x}_{\uparrow a})\Delta t+o(\Delta t)=\left(\sum_{k=1}^{m}B_{ik}E_{k}^{(a)}(\mathbf{x})\right)\Delta t+o(\Delta t).

(38)

We now use (38) to evaluate the probability of the event $\{S_{i}(t+\Delta t)=S_{i}(t)-1\}$ . To this end, let $D_{\ell}(U,t,\Delta t))$ denote the event that exactly $\ell$ nodes in a given set $U\subset[n]$ recover during $[t,t+\Delta t)$ (i.e., there exist exactly $\ell$ indices $r_{1},\ldots,r_{\ell}$ in $U$ such that $X_{r_{k}}(t)=1$ and $X_{r_{k}}(t+\Delta t)=-1$ ). Similarly, let $\mathscr{I}_{\ell}(U,t,\Delta t)$ denote the event that exactly $\ell$ nodes in $U$ get infected during $[t,t+\Delta t)$ . Then,

	$\displaystyle\text{Pr}(S_{i}(t+\Delta t)-S_{i}(t)=-1\mid\mathbf{X}(t)=\mathbf{x})$		(39)
	$\displaystyle=\text{Pr}(\mathscr{I}_{1}(\mathcal{A}_{i},t,\Delta t)\mid\mathbf{X}(t)=\mathbf{x})$		(40)
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{Pr}(D_{0}([n],t,\Delta t)\cap\mathscr{I}_{0}([n]\setminus\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{1}(\mathcal{A}_{i},t,\Delta t)\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(41)
	$\displaystyle=\text{Pr}\left(\cup_{a\in\mathcal{S}_{i}(\mathbf{x})}\{\mathbf{X}(t+\Delta t)=\mathbf{x}_{\uparrow a}\}\mid\mathbf{X}(t)=\mathbf{x}\right)+o(\Delta t)$		(42)
	$\displaystyle=\sum_{a\in\mathcal{S}_{i}(\mathbf{x})}\text{Pr}(\mathbf{X}(t+\Delta t)=\mathbf{x}_{\uparrow a}\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(43)
	$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\left(\sum_{a\in\mathcal{S}_{i}(\mathbf{x})}\sum_{j=1}^{m}B_{ij}E_{j}^{(a)}(\mathbf{x})\right)\Delta t+o(\Delta t)$		(44)
	$\displaystyle=\left(\sum_{j=1}^{m}\sum_{a\in\mathcal{S}_{i}(\mathbf{x})}\sum_{b\in\mathcal{I}_{j}(\mathbf{x})}B_{ij}1_{(a,b)}(\mathbf{x})\right)\Delta t+o(\Delta t).$		(45)

where $(a)$ is a straightforward consequence of Lemma 1, and $(b)$ follows from (38). Since this holds for all $\mathbf{x}\in\mathbb{S}$ , we have

\displaystyle\text{Pr}(S_{i}(t+\Delta t)-S_{i}(t)=-1\mid\mathbf{X}(t))=\left(\sum_{j=1}^{m}\sum_{a\in\mathcal{S}_{i}(t)}\sum_{b\in\mathcal{I}_{j}(t)}B_{ij}1_{(a,b)}(t)\right)\Delta t+o(\Delta t),

(46)

where $\mathcal{S}_{i}(t)$ , $\mathcal{I}_{i}(t)$ , and $1_{(a,b)}(t)$ stand for $\mathcal{S}_{i}(\mathbf{X}(t))$ , $\mathcal{I}_{i}(\mathbf{X}(t))$ , and $1_{(a,b)}(\mathbf{X}(t))$ , respectively. Since $\mathcal{S}(t)$ and $\mathcal{I}(t)$ are determined by $\mathbf{X}(t)$ , we may express (46) as

\displaystyle\text{Pr}(S_{i}(t+\Delta t)-S_{i}(t)=-1\mid\mathcal{S}(t),\mathcal{I}(t),\mathbf{X}(t))=\left(\sum_{j=1}^{m}\sum_{a\in\mathcal{S}_{i}(t)}\sum_{b\in\mathcal{I}_{j}(t)}B_{ij}1_{(a,b)}(t)\right)\Delta t+o(\Delta t).

(47)

As a result, we have

\displaystyle\text{Pr}(S_{i}(t+\Delta t)-S_{i}(t)=-1\mid\mathcal{S}(t),\mathcal{I}(t))=\left(\sum_{j=1}^{m}\sum_{a\in\mathcal{S}_{i}(t)}\sum_{b\in\mathcal{I}_{j}(t)}B_{ij}\mathbb{E}[1_{(a,b)}(t)\mid\mathcal{S}(t),\mathcal{I}(t)]\right)\Delta t+o(\Delta t).

(48)

At this point we note that

\mathbb{E}[1_{(a,b)}(t)\mid\mathcal{S}(t),\mathcal{I}(t)]=\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))=\chi_{ij}(t,\mathcal{S},\mathcal{I}).

We thus have the following for $\Delta_{t}S_{i}:=S_{i}(t+\Delta t)-S_{i}(t)$ :

$\displaystyle\mathbb{E}[\Delta_{t}S_{i}\mid\mathcal{S}(t),\mathcal{I}(t)]$	$\displaystyle=-\text{Pr}(\Delta_{t}S_{i}=-1\mid\mathcal{S}(t),\mathcal{I}(t))-\sum_{\ell=2}^{n}\ell\cdot\text{Pr}(\Delta_{t}S_{i}=-\ell)$	(49)
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}-\text{Pr}(\Delta_{t}S_{i}=-1\mid\mathcal{S}(t),\mathcal{I}(t))+o(\Delta t)$	(50)
	$\displaystyle=-\left(\sum_{j=1}^{m}\sum_{a\in\mathcal{S}_{i}(t)}\sum_{b\in\mathcal{I}_{j}(t)}B_{ij}\chi_{ij}(t)\right)\Delta t+o(\Delta t)$	(51)
	$\displaystyle=-\left(\sum_{j=1}^{m}B_{ij}\chi_{ij}(t)S_{i}(t)I_{j}(t)\right)\Delta t+o(\Delta t),$	(52)

where (a) follows from Lemma 1. Taking expectations on both sides of (49) and dividing the resulting relation by $\Delta t$ now yields

\displaystyle\mathbb{E}\left[\frac{S_{i}(t+\Delta t)-S_{i}(t)}{\Delta t}\right]

\displaystyle=-\sum_{j=1}^{m}B_{ij}\mathbb{E}[n\chi_{ij}(t)s_{i}(t)I_{j}(t)]+\frac{o(\Delta t)}{\Delta t},

(53)

where we used that $S_{i}(t)=ns_{i}(t)$ . On letting $\Delta t\rightarrow 0$ and then dividing both the sides of (53) by $n$ , we obtain (i).

Proof of (ii):

Observe that for any $\mathbf{x}\in\mathbb{S}$ , we have

		$\displaystyle\text{Pr}(I_{i}(t+\Delta t)-I_{i}(t)=1\mid\mathbf{X}(t)=\mathbf{x})$		(54)
		$\displaystyle=\text{Pr}(\|\mathcal{I}_{i}(\mathbf{X}(t+\Delta t))\|-\|\mathcal{I}_{i}(\mathbf{X}(t))\|=1\mid\mathbf{X}(t)=\mathbf{x})$		(55)
		$\displaystyle=\text{Pr}(\cup_{\ell=0}^{n}(D_{\ell}(\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{\ell+1}(\mathcal{A}_{i},t,\Delta t))\mid\mathbf{X}(t)=\mathbf{x})$		(56)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{Pr}(D_{0}(\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{1}(\mathcal{A}_{i},t,\Delta t)\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(57)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\text{Pr}(D_{0}([n],t,\Delta t)\cap\mathscr{I}_{0}([n]\setminus\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{1}(\mathcal{A}_{i},t,\Delta t)\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(58)
		$\displaystyle=\text{Pr}\left(\cup_{c\in\mathcal{S}_{i}(\mathbf{x})}\{\mathbf{X}(t+\Delta t)=\mathbf{x}_{\uparrow c}\}\mid\mathbf{X}(t)=\mathbf{x}\right)+o(\Delta t)$		(59)
		$\displaystyle=\sum_{c\in\mathcal{S}_{i}(\mathbf{x})}\text{Pr}(\mathbf{X}(t+\Delta t)=\mathbf{x}_{\uparrow c}\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(60)
		$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\left(\sum_{c\in\mathcal{S}_{i}(\mathbf{x})}\sum_{j=1}^{m}B_{ij}E_{j}^{(c)}(\mathbf{x})\right)\Delta t+o(\Delta t),$		(61)

where $(a)$ and $(b)$ follow from Lemma 1 and $(c)$ follows from (38).

On the other hand,

		$\displaystyle\text{Pr}(I_{i}(t+\Delta t)-I_{i}(t)=-1\mid\mathbf{X}(t)=\mathbf{x})$		(62)
		$\displaystyle=\text{Pr}(\cup_{\ell=0}^{n}(D_{\ell+1}(\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{\ell}(\mathcal{A}_{i},t,\Delta t))\mid\mathbf{X}(t)=\mathbf{x})$		(63)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{Pr}(D_{1}(\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{0}(\mathcal{A}_{i},t,\Delta t)\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(64)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\text{Pr}(D_{1}(\mathcal{A}_{i},t,\Delta t)\cap D_{0}([n]\setminus\mathcal{A}_{i},t,\Delta t)\cap\mathscr{I}_{0}([n],t,\Delta t)\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(65)
		$\displaystyle=\sum_{c\in\mathcal{I}_{i}(\mathbf{x})}\text{Pr}(\mathbf{X}(t+\Delta t)=\mathbf{x}_{\downarrow c}\mid\mathbf{X}(t)=\mathbf{x})+o(\Delta t)$		(66)
		$\displaystyle=\sum_{c\in\mathcal{I}_{i}(\mathbf{x})}(\mathbf{Q}(\mathbf{x},\mathbf{x}_{\downarrow c})\Delta t+o(\Delta t))+o(\Delta t)$		(67)
		$\displaystyle=\sum_{c\in\mathcal{I}_{i}(\mathbf{x})}\gamma_{i}\Delta t+o(\Delta t)$		(68)
		$\displaystyle=\gamma_{i}\|I_{i}(\mathbf{x})\|\Delta t+o(\Delta t).$		(69)

As a result of (54), (62), and Lemma 1, we have

\displaystyle\mathbb{E}[I_{i}(t+\Delta t)-I_{i}(t)\mid\mathbf{X}(t)]=\left(\sum_{c\in\mathcal{S}_{i}(\mathbf{x})}\sum_{j=1}^{m}B_{ij}E_{j}^{(c)}(\mathbf{X}(t))-\gamma_{i}|\mathcal{I}_{i}(\mathbf{X}(t))|\right)\Delta t+o(\Delta t).

By repeating the arguments used in the proof of (i), we can use the above to prove that

\displaystyle\mathbb{E}[I_{i}(t+\Delta t)-I_{i}(t)\mid\mathcal{S}(t),\mathcal{I}(t)]=\left(\sum_{j=1}^{m}B_{ij}\chi_{ij}(t)S_{i}(t)I_{j}(t)-\gamma_{i}I_{i}(t)\right)\Delta t+o(\Delta t),

which implies that

\displaystyle\mathbb{E}\left[\frac{I_{i}(t+\Delta t)-I_{i}(t)}{\Delta t}\right]=\sum_{j=1}^{m}B_{ij}\mathbb{E}[n\chi_{ij}(t)s_{i}(t)I_{j}(t)]-\gamma_{i}\mathbb{E}[I_{i}(t)]+\frac{o(\Delta t)}{\Delta t}.

On dividing both sides by $n$ and then letting $\Delta t\rightarrow 0$ , we obtain (ii).

Proof of (iii):

Observe that when $\Delta_{t}S_{i}=-1$ , we have $S_{i}^{2}(t+\Delta t)-S_{i}^{2}(t)=1-2S_{i}(t)$ . Therefore,

	$\displaystyle\mathbb{E}[S_{i}^{2}(t+\Delta t)-S_{i}^{2}(t)\mid\mathcal{S}(t),\mathcal{I}(t)]$	$\displaystyle=(1-2S_{i}(t))\cdot\text{Pr}(\Delta_{t}S_{i}=-1\mid\mathcal{S}(t),\mathcal{I}(t))+o(\Delta t)$
		$\displaystyle=\left(\sum_{j=1}^{m}B_{ij}\chi_{ij}S_{i}I_{j}\Delta t-2\sum_{j=1}^{m}B_{ij}\chi_{ij}S_{i}^{2}I_{j}\Delta t\right)+o(\Delta t).$

Taking expectations on both sides, dividing by $\Delta t$ , letting $\Delta t\rightarrow 0$ , and dividing both sides by $n^{2}$ yields (iii).

Proof of (iv):

Observe that if $\Delta_{t}I_{i}(t)=-1$ , we have $I_{i}^{2}(t+\Delta t)-I_{i}^{2}(t)=1-2I_{i}(t)$ , and if $\Delta_{t}I_{i}(t)=1$ , we have $I_{i}^{2}(t+\Delta t)-I_{i}^{2}(t)=1+2I_{i}(t)$ .

Thus,

	$\displaystyle\mathbb{E}[I_{i}^{2}(t+\Delta t)-I_{i}^{2}(t)\mid\mathcal{S}(t),\mathcal{I}(t)]$
	$\displaystyle=(1-2I_{i}(t))\cdot\text{Pr}(\Delta_{t}I_{i}=-1\mid\mathcal{S}(t),\mathcal{I}(t))+(1+2I_{i}(t))\cdot\text{Pr}(\Delta_{t}I_{i}=1\mid\mathcal{S}(t),\mathcal{I}(t))+o(\Delta t)$

On substituting the probabilities above with the expressions derived earlier, taking expectations on both sides, dividing by $n^{2}\Delta t$ and letting $\Delta t\rightarrow 0$ , we obtain (iv).

Lemma 2.

Let $a\in\mathcal{A}_{i}$ and $b\in\mathcal{A}_{j}$ be any two nodes, let $t\in[0,\infty)$ be any time, and let $T\in[0,t]$ be the random variable such that $t-T$ is the time at which $1_{(a,b)}$ is updated for the last time during the interval $[0,t]$ . Then the random variables $T$ and $1_{(a,b)}(t)$ are independent.

Proof.

For $\tau\in[0,t]$ , let $N_{\tau}$ denote the number of times $1_{(a,b)}$ is updated in the open interval $(t-\tau,t)$ , and let $U_{\tau}$ denote the zero-probability event that $1_{(a,b)}$ is updated at time $t-\tau$ . Note that $\mathbf{Q}(\mathbf{x},\mathbf{x}_{\uparrow(a,b)})+\mathbf{Q}(\mathbf{x},\mathbf{x}_{\downarrow(a,b)})=\lambda$ for all $\mathbf{x}\in\mathbb{S}$ , which means that the rate at which $1_{(a,b)}$ is updated is time-invariant and independent of the network state. This means that the sequence of times at which $1_{(a,b)}$ is updated is a Poisson process, which further means that the updates of $1_{(a,b)}$ occurring in disjoint time intervals are independent. It follows that $N_{\tau}$ is a Poisson random variable (with mean $\lambda\tau$ ) that is independent of ${U_{\tau}}$ and $1_{(a,b)}(t-\tau)$ . As a result,

	$\displaystyle\text{Pr}((a,b)\in E(t)\mid T=\tau)$	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{Pr}((a,b)\in E(t-\tau)\mid U_{\tau},N_{\tau}=0)$
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{\text{Pr}(N_{\tau}=0\mid(a,b)\in E(t-\tau),U_{\tau})}{\text{Pr}(N_{\tau}=0\mid U_{\tau})}\cdot\text{Pr}((a,b)\in E(t-\tau)\mid U_{\tau})$
		$\displaystyle=\frac{\text{Pr}(N_{\tau}=0\mid 1_{(a,b)}(t-\tau)=1,U_{\tau})}{\text{Pr}(N_{\tau}=0\mid U_{\tau})}\cdot\text{Pr}((a,b)\in E(t-\tau)\mid U_{\tau})$
		$\displaystyle=\frac{\text{Pr}(N_{\tau}=0)}{\text{Pr}(N_{\tau}=0)}\cdot\text{Pr}((a,b)\in E(t-\tau)\mid U_{\tau})$
		$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\frac{\rho_{ij}}{n},$

where (a) follows from the definition of $T$ , $(b)$ follows from Bayes’ rule, and $(c)$ follows from the model definition (Section 2). Thus, $\text{Pr}(1_{(a,b)}(t)=1\mid T=\tau)$ and $\text{Pr}(1_{(a,b)}(t)=0\mid T=\tau)$ do not depend on $\tau$ , which means that $T$ and $1_{(a,b)}(t)$ are independent.

The proof of Proposition 2 is based on the concepts of transition sequences and agnostic transition sequences, which we define below.

Definition 2 (Transition Sequence).

Consider any time $t\geq 0$ , integer $r\in\mathbb{N}_{0}$ , tuples $\mathbf{x}^{(1)},\mathbf{x}^{(2)},\ldots,\mathbf{x}^{(r)}\in\mathbb{S}$ , and times $0\leq t_{1}<t_{2}<\cdots<t_{r}\leq t$ . Let $F=\{\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\mathbf{x}^{(1)}\stackrel{{\scriptstyle t_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}^{(r)}\stackrel{{\scriptstyle t}}{{\rightarrow}}\mathbf{x}^{(r)}\}$ denote the event that the embedded jump chain $\{\mathbf{X}(J_{\ell}):\ell\in\mathbb{N}_{0}\}$ satisfies $\mathbf{X}(J_{\ell})=\mathbf{x}^{(\ell)}$ and $J_{\ell}=t_{\ell}$ for all $\ell\in[r]$ , and $J_{r+1}>t$ . Then $F$ is said to be a transition sequence for the time interval $[0,t]$ .

Note that if $F$ is a transition sequence for $[0,t]$ , then for every tuple $\mathbf{x}\in\mathbb{S}$ , we either have $F\subset\{\mathbf{X}(t)=\mathbf{x}\}$ or $F\subset\{\mathbf{X}(t)\neq\mathbf{x}\}$ .

Definition 3 ( $(a,b)$ -Complement).

Let $\mathbf{x}\in\mathbb{S}$ . Then the $(a,b)$ -complement of $\mathbf{x}$ , denoted by $\mathbf{x}_{(\overline{a,b})}$ , is defined by

\displaystyle(\mathbf{x}_{(\overline{a,b})})_{\ell}=\begin{cases}x_{\ell}\quad&\text{if }\ell\in[2n^{2}-n]\setminus\{\langle a,b\rangle\},\\ 1-x_{\ell}\quad&\text{if }\ell=\langle a,b\rangle.\end{cases}

Definition 4 ( $(a,b)$ -Agnostic Transition Sequence).

Let $a,b\in[n]$ , and let $F=\{\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\mathbf{x}^{(1)}\stackrel{{\scriptstyle t_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}^{(r)}\stackrel{{\scriptstyle t}}{{\rightarrow}}\mathbf{x}^{(r)}\}$ be a transition sequence for a time interval $[0,t]$ . Further, define

\Lambda_{(a,b)}(F)=\begin{cases}\max\left\{\ell\in[r]:\mathbf{x}^{(\ell)}\in\{\mathbf{x}^{(\ell-1)}_{\uparrow(a,b)},\mathbf{x}^{(\ell-1)}_{\downarrow(a,b)}\}\right\}\quad&\text{if }\left\{\ell\in[r]:\mathbf{x}^{(\ell)}\in\{\mathbf{x}^{(\ell-1)}_{\uparrow(a,b)},\mathbf{x}^{(\ell-1)}_{\downarrow(a,b)}\}\right\}\neq\emptyset\\ 0\quad&\text{otherwise.}\end{cases}

Then the $(a,b)$ -agnostic transition sequence for $F$ is the event $F_{?(a,b)}=F\cup F_{(\overline{a,b})}$ , where $F_{(\overline{a,b})}$ , defined by

	$\displaystyle F_{(\overline{a,b})}:=$	$\displaystyle\Big{\{}\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{\Lambda_{(a,b)}(F)-1}}}{{\rightarrow}}\mathbf{x}^{({\Lambda_{(a,b)}(F)-1})}\stackrel{{\scriptstyle t_{\Lambda_{(a,b)}(F)}}}{{\rightarrow}}\mathbf{x}^{({\Lambda_{(a,b)}(F)})}_{(\overline{a,b})}$
		$\displaystyle\quad\stackrel{{\scriptstyle t_{\Lambda_{(a,b)}(F)+1}}}{{\rightarrow}}\mathbf{x}^{({\Lambda_{(a,b)}(F)+1})}_{(\overline{a,b})}\stackrel{{\scriptstyle t_{\Lambda_{(a,b)}(F)+2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}^{(r)}_{(\overline{a,b})}\stackrel{{\scriptstyle t}}{{\rightarrow}}\mathbf{x}^{(r)}_{(\overline{a,b})}\Big{\}},$

is called the $(a,b)$ -complement of $F$ .

Given that $F$ occurs, $t_{\Lambda_{(a,b)}(F)}$ denotes the time at which the edge state of $(a,b)$ is updated for the last time during the time interval $[0,t]$ (note that, if the edge state of $(a,b)$ is not updated during $[0,t]$ , then $t_{\Lambda_{(a,b)}(F)}=t_{0}:=0$ ). Therefore, the only difference between $F$ and $F_{(\overline{a,b})}$ is that the last edge state of $(a,b)$ to be realized during the interval $[0,t]$ is different for $F$ and $F_{(a,b)}$ . Stated differently, if $F\subset\{(a,b)\in E(t)\}$ , then $F_{(\overline{a,b})}\subset\{(a,b)\notin E(t)\}$ , and vice-versa. As a result, the event $F_{?(a,b)}$ is $(a,b)$ -agnostic in that the occurrence of this event does not provide any information about the edge state of $(a,b)$ at time $t$ .

Note that if $F$ is a transition sequence, then $F$ , $F_{(\overline{a,b})}$ , and $F_{?(a,b)}$ are all zero-probability events. We now approximate these events with the help of suitable positive-probability events.

Definition 5 ( $\delta$ -Approximation).

Let $F=\{\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\mathbf{x}^{(1)}\stackrel{{\scriptstyle t_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}^{(r)}\stackrel{{\scriptstyle t}}{{\rightarrow}}\mathbf{x}^{(r)}\}$ be a transition sequence. Then, for a given $\delta>0$ , the $\delta$ -approximation of $F$ is the event $F^{\delta}:=\{\mathbf{X}(0)=\mathbf{x}^{(0)},\ldots,\mathbf{X}(J_{r})=\mathbf{x}^{(r)},\Delta_{1}J\in[\Delta_{1}t,\Delta_{1}t+\delta),\ldots,\Delta_{r}J\in[\Delta_{r}t,\Delta_{r}t+\delta),\Delta_{r+1}J>t-t_{r}\}$ , where $\Delta_{\ell}J:=J_{\ell}-J_{\ell-1}$ , $\Delta_{\ell}t:=t_{\ell}-t_{\ell-1}$ , and $t_{0}:=0$ . Also, the $\delta$ -approximation of $F_{?(a,b)}$ is the event $F_{?(a,b)}^{\delta}:=F^{\delta}\cup F_{(\overline{a,b})}^{\delta}$ (where $F^{\delta}_{(\overline{a,b})}$ is the $\delta$ -approximation of $F_{(\overline{a,b})}$ ).

The following lemma evaluates the probability of occurrence of a $\delta$ -approximation event.

Lemma 3.

e^{-q_{r}(t-t_{r})}\prod_{\ell=1}^{r}q_{\ell-1,\ell}(e^{-q_{\ell-1}(t_{\ell}-t_{\ell-1})}\delta+o(\delta)),

where $t_{0}:=0$ , $q_{\ell}:=-\mathbf{Q}(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell)})$ , and $q_{\ell,\ell+1}:=\mathbf{Q}(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell+1)})$ for each $\ell\in[r]$ .

Proof.

Observe that

	$\displaystyle\frac{\text{Pr}(F^{\delta})}{\text{Pr}(\mathbf{X}(0)=\mathbf{x}^{(0)})}$	$\displaystyle=\text{Pr}(\cap_{\ell\in[r]}\{\mathbf{X}(J_{\ell})=\mathbf{x}^{(\ell)},\Delta_{\ell}J\in[\Delta_{\ell}t,\Delta_{\ell}t+\delta)\}\mid\mathbf{X}(0)=\mathbf{x}^{(0)})$
		$\displaystyle\quad\times\text{Pr}(\Delta_{r+1}J>t-t_{r}\mid\cap_{\ell\in[r]}\{\mathbf{X}(J_{\ell})=\mathbf{x}^{(\ell)},\Delta_{\ell}J\in[\Delta_{\ell}t,\Delta_{\ell}t+\delta)\})$
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\prod_{\ell=1}^{r}\text{Pr}(\Delta_{\ell}J\in[\Delta_{\ell}t,\Delta_{\ell}t+\delta),\mathbf{X}(J_{\ell})=\mathbf{x}^{(\ell)}\mid\mathbf{X}(J_{\ell-1})=\mathbf{x}^{(\ell-1)})$
		$\displaystyle\quad\times\text{Pr}(\Delta_{r+1}J>t-t_{r}\mid\mathbf{X}(J_{r})=\mathbf{x}^{(r)})$
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\prod_{\ell=1}^{r}\text{Pr}(\Delta_{1}J\in[\Delta_{\ell}t,\Delta_{\ell}t+\delta),\mathbf{X}(J_{1})=\mathbf{x}^{(\ell)}\mid\mathbf{X}(0)=\mathbf{x}^{(\ell-1)})$
		$\displaystyle\quad\times\text{Pr}(\Delta_{1}J>t-t_{r}\mid\mathbf{X}(0)=\mathbf{x}^{(r)})$
		$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\prod_{\ell=1}^{r}\Big{(}\text{Pr}(\Delta_{1}J\in[\Delta_{\ell}t,\Delta_{\ell}t+\delta)\mid\mathbf{X}(0)=\mathbf{x}^{(\ell-1)})\cdot\text{Pr}(\mathbf{X}(J_{1})=\mathbf{x}^{(\ell)}\mid\mathbf{X}(0)=x^{(\ell-1)})\Big{)}$
		$\displaystyle\quad\times\text{Pr}(\Delta_{1}J>t-t_{r}\mid\mathbf{X}(0)=\mathbf{x}^{(r)})$
		$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\prod_{\ell=1}^{r}\left(\left(q_{\ell-1}e^{-q_{\ell-1}\Delta_{\ell}t}\delta+o(\delta)\right)\frac{q_{\ell-1,\ell}}{q_{\ell-1}}\right)\times e^{-q_{r}(t-t_{r})}$
		$\displaystyle=e^{-q_{r}(t-t_{r})}\prod_{\ell=1}^{r}q_{\ell-1,\ell}\left(e^{-q_{\ell-1}(t_{\ell}-t_{\ell-1})}\delta+o(\delta)\right),$

where $(a)$ follows from the strong Markov property and the fact that jump times are stopping times, $(b)$ follows from Proposition 3.2 of [41], $(c)$ follows from the fact that $\mathbf{X}(J_{1})$ and $\Delta_{1}J$ (which equals $J_{1}$ ) are conditionally independent given $\mathbf{X}(0)$ (see Proposition 3.1 of [41]), and $(d)$ follows from the following two facts:

1.

$\Delta_{1}J$ is conditionally exponentially distributed with mean $q_{\ell-1}^{-1}$ given that $\mathbf{X}(0)=\mathbf{x}^{(\ell-1)}$ .
2.

For the embedded jump chain, the probability of transitioning from $\mathbf{x}\in\mathbb{S}$ to $\mathbf{y}\in\mathbb{S}$ is $\frac{\mathbf{Q}(\mathbf{x},\mathbf{y})}{|\mathbf{Q}(\mathbf{x},\mathbf{x})|}$ .

For the rest of the appendix, let $a\in\mathcal{A}_{i}$ and $b\in\mathcal{A}_{j}$ be any two nodes, let $t\in[0,\infty)$ be any time instant, let $T\in[0,t]$ be the random variable such that $t-T$ is the time at which $1_{(a,b)}$ is updated for the last time during the interval $[0,t)$ , and let $K:=t-\min\{t,\inf\{\tau:b\in\mathcal{I}(\tau)\}\}$ , where $\inf\{\tau:b\in\mathcal{I}(\tau)\}$ is the time at which $b$ gets infected.

Lemma 4.

The PDF of $T$ has $[0,t]$ as its support and is given by

f_{T}(\tau)=\lambda e^{-\lambda\tau}+e^{-\lambda t}\delta_{D}(\tau-t),

where $\delta_{D}(\cdot)$ is the Dirac-delta function.

Proof.

The definition of $T$ implies that the support of its PDF is $[0,t]$ . To derive the required closed-form expression for this PDF, recall that $\mathbf{Q}(\mathbf{x},\mathbf{x}_{\uparrow(a,b)})+\mathbf{Q}(\mathbf{x},\mathbf{x}_{\downarrow(a,b)})=\lambda$ for all $\mathbf{x}\in\mathbb{S}$ , which means that the edge state of $(a,b)$ is updated at a constant rate of $\lambda$ at all times. Therefore, for any $\tau\in[0,t)$ , the quantity $\text{Pr}(T>\tau)$ (the probability that $1_{(a,b)}$ is not updated during $[t-\tau,t]$ ) is given by $e^{-\lambda\tau}$ . However, $\text{Pr}(T>t)=0$ , implying that $\text{Pr}(T=t)=\text{Pr}(T\geq t)=\lim_{\tau\rightarrow t^{-}}\text{Pr}(T>\tau)=e^{-\lambda t}$ . Hence, the CDF of $T$ is $F(\tau)=1-e^{-\lambda\tau}$ for all $\tau\in[0,t)$ , and $F(t)=1$ . Taking the first derivative of this CDF now yields the required expression for $f_{T}$ .

To prove the next lemma, we need the notion of agnostic superstates, which is defined below.

Definition 6 ( $(a,b)$ -Agnostic Superstate).

Given a node pair $(a,b)\in[n]\times[n]$ , a collection of states $\mathbb{X}\subset\mathbb{S}$ is an $(a,b)$ -agnostic superstate if $\mathbb{X}$ can be expressed as $\mathbb{X}=\left\{\mathbf{x},\mathbf{x}_{(\overline{a,b})},\mathbf{y},\mathbf{y}_{(\overline{a,b})}\right\}$ for a pair of states $\mathbf{x},\mathbf{y}\in\mathbb{S}$ satisfying $y_{n^{2}+\langle a,b\rangle}=1-x_{n^{2}+\langle a,b\rangle}$ and $x_{\ell}=y_{\ell}$ for all $\ell\in[2n^{2}-n]\setminus\{n^{2}+\langle a,b\rangle\}$ .

Note that an $(a,b)$ -agnostic superstate specifies the disease states of all the nodes and the edge states of all the node pairs except $(a,b)$ .

Definition 7 ( $(a,b)$ -Agnostic Jump Times).

Given $(a,b)\in[n]\times[n]$ , the $(a,b)$ -agnostic jump times of the chain $\{\mathbf{X}(\tau):\tau\geq 0\}$ , denoted by $\{L_{k}\}_{k=0}^{\infty}$ , are defined by $L_{0}:=0$ and $L_{k}:=\inf\{J_{\ell}:\ell\in\mathbb{N},J_{\ell}>L_{k-1},\mathbf{X}(J_{\ell})\notin\{(\mathbf{X}(J_{\ell-1}))_{\uparrow(a,b)},(\mathbf{X}(J_{\ell-1}))_{\downarrow(a,b)}\}\}$ for all $k\in\mathbb{N}$ .

Note that $\{L_{k}\}_{k=0}^{\infty}\subset\{J_{\ell}\}_{\ell=0}^{\infty}$ and that the $(a,b)$ -agnostic jump times of $\{\mathbf{X}(\tau)\}$ are the jump times of the chain at which the edge state of $(a,b)$ is not updated.

Lemma 5.

$K$ is independent of $(T,1_{(a,b)}(t))$ .

Proof.

Note that $K$ is a function of $\tilde{K}:=\inf\{\tau\geq 0:b\in\mathcal{I}(\tau)\}$ , the time at which $b$ gets infected. Hence, it suffices to prove that $\tilde{K}$ is independent of $(T,1_{(a,b)}(t))$ .

Consider now any $\kappa\geq 0$ and note that $\{\tilde{K}\geq\kappa\}=\cup_{N=0}^{\infty}\left(\{\tilde{K}=L_{N}\}\cap\{L_{N}\geq\kappa\}\right)$ . To examine the probability of $\{\tilde{K}=L_{N}\}$ , we let $\mathcal{F}_{N}(\kappa)$ denote the set of all the events of the form $F=\{\mathbf{X}(0)\in\mathbb{X}^{(0)},\mathbf{X}(L_{1})\in\mathbb{X}^{(1)},\ldots,\mathbf{X}(L_{N})\in\mathbb{X}^{(N)}\}$ (where $\mathbb{X}^{(0)},\ldots,\mathbb{X}^{(N)}$ are $(a,b)$ -agnostic superstates satisfying $\mathbb{X}^{(k)}\neq\mathbb{X}^{(k-1)}$ for all $k\in[N]$ ) that satisfy $F\subset\{\tilde{K}=L_{N}\}$ , and we observe that $\{\tilde{K}=L_{N}\}=\cup_{F\in\mathcal{F}_{N}(\kappa)}F$ .

We now examine $\text{Pr}(F)$ for an arbitrary $F=\{\mathbf{X}(0)\in\mathbb{X}^{(0)},\mathbf{X}(L_{1})\in\mathbb{X}^{(1)},\ldots,\mathbf{X}(L_{N})\in\mathbb{X}^{(N)}\}\in\mathcal{F}_{N}(\kappa)$ . Pick any $k\in[N]$ and $\mathbf{x}\in\mathbb{X}^{(k-1)}$ . Note that $F\subset\{\tilde{K}=L_{N}\}$ implies that $b\in\mathcal{S}(\mathbf{x})$ . In view of our definition of $\mathbf{Q}$ , this means that $\mathbf{Q}(\mathbf{x},\mathbf{x})=-\sum_{\mathbf{z}\in\mathbb{S}\setminus\{\mathbf{x}\}}\mathbf{Q}(\mathbf{x},\mathbf{z})$ , which possibly depends on the disease states $\{x_{1},\ldots,x_{n}\}$ and on the edge states $\{1_{(c,d)}(\mathbf{x}):(c,d)\in[n]\times[n]:d\in\mathcal{I}(\mathbf{x})\}$ , does not depend on $1_{(a,b)}(\mathbf{x})$ . We next observe that, by the definitions of $(a,b)$ -agnostic states and jump times, none of the possible transitions from $\mathbb{X}^{(k-1)}$ to $\mathbb{X}^{(k)}$ involves an edge state update for $(a,b)$ , which means that the values of both $X_{\langle a,b\rangle}=1_{(a,b)}(\mathbf{X})$ and $X_{n^{2}+\langle a,b\rangle}$ are preserved in such transitions. Therefore, for every $\mathbf{x}\in\mathbb{X}^{(k-1)}$ , there exists at most one state $\mathbf{y}\in\mathbb{X}^{(k)}$ that potentially succeeds $\mathbf{x}$ . For such a state $\mathbf{y}$ , the transition rate $\mathbf{Q}(\mathbf{x},\mathbf{y})$ , given by

\displaystyle\mathbf{Q}(\mathbf{x},\mathbf{y})=\begin{cases}\sum_{q=1}^{m}\sum_{d\in\mathcal{I}_{q}(\mathbf{x})}B_{pq}1_{(c,d)}(\mathbf{x})\,&\text{if }\exists\,\,c\in\mathcal{S}_{p}(\mathbf{x})\text{ such that }\mathbf{y}=\mathbf{x}_{\uparrow c}\\ \gamma_{p}\quad&\text{if }\exists\,\,c\in\mathcal{I}_{p}(\mathbf{x})\text{ such that }\mathbf{y}=\mathbf{x}_{\downarrow c},\\ \lambda\frac{\rho_{pq}}{n}\quad&\text{if }\exists\,\,(c,d)\in\mathcal{A}_{p}\times\mathcal{A}_{q}\setminus\{(a,b)\}\text{ such that }\mathbf{y}=\mathbf{x}_{\uparrow(c,d),}\\ \lambda\left(1-\frac{\rho_{pq}}{n}\right)\quad&\text{if }\exists\,\,(a,b)\in\mathcal{A}_{p}\times\mathcal{A}_{q}\setminus\{(a,b)\}\text{ such that }\mathbf{y}=\mathbf{x}_{\downarrow(c,d)},\end{cases}

does not depend on $x_{\langle a,b\rangle}=y_{\langle a,b\rangle}$ or on $x_{n^{2}+\langle a,b\rangle}=y_{n^{2}+\langle a,b\rangle}$ , because $b\notin\mathcal{I}(\mathbf{x})$ implies that $(a,b)\notin\cup_{p=1}^{m}\cup_{c\in\mathcal{S}_{p}(\mathbf{x})}\cup_{q=1}^{m}\{(c,d):d\in\mathcal{I}_{q}(\mathbf{x})\}$ . It follows that the rate at which the Markov chain $\{\mathbf{X}(\tau)\}$ transitions from $\mathbf{x}$ to a state in $\mathbb{X}^{(k)}$ , given by $\sum_{\mathbf{z}\in\mathbb{X}^{(k)}}\mathbf{Q}(\mathbf{x},\mathbf{z})=\mathbf{Q}(\mathbf{x},\mathbf{y})$ , is time-invariant and takes the same value for every $\mathbf{x}\in\mathbb{X}^{(k-1)}$ . This means that, as long as the Markov chain $\{\mathbf{X}(\tau):\tau\geq 0\}$ does not leave the $(a,b)$ -agnostic superstate $\mathbb{X}^{(k-1)}$ , the rate at which the chain transitions to $\mathbb{X}^{(k)}$ remains the same regardless of transitions within $\mathbb{X}^{(k-1)}$ . We can express this formally as

\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}(\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)\in\mathbb{X}^{(k-1)},\mathbf{X}(\tau)=\mathbf{x})}{\Delta\tau}=\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})

for all $\tau\geq 0$ and $\mathbf{x}\in\mathbb{X}^{(k-1)}$ , where

\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)}):=\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}(\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)\in\mathbb{X}^{(k-1)})}{\Delta\tau}

denotes the time-invariant rate of transitioning from $\mathbb{X}^{(k-1)}$ to $\mathbb{X}^{(k)}$ .

By Markovity, this implies that²²2In this paper, conditioning an event $H$ on $\{\mathbf{X}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}$ means conditioning $H$ on every $\mathbf{X}(\tau^{\prime})$ for $0\leq\tau^{\prime}\leq\tau$ , i.e., conditioning H on the trajectory traced by the Markov chain during the interval $[0,\tau]$ and not just on the random set of tuples $\{\mathbf{X}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}$ . Conditioning on the set $\{\mathbf{X}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}$ is not sufficient because sets, by definition, are unordered.

\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}(\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)=\mathbf{x},\{\mathbf{X}(\tau^{\prime}):0\leq\tau^{\prime}<\tau\})}{\Delta\tau}=\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)}),

for all $\tau\geq 0$ and $\mathbf{x}\in\mathbb{X}^{(k-1)}$ , which means that the conditional rate at which the chain leaves $\mathbb{X}^{(k-1)}$ time $\tau$ is independent of the history $\{\mathbf{X}(\tau^{\prime}):\tau^{\prime}\in[0,\tau]\}$ . Since $\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}$ are determined by $\{\mathbf{X}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}$ , it follows that

\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}(\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\})}{\Delta\tau}=\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})

for all $\tau\geq 0$ and $\mathbf{x}\in\mathbb{X}^{(k-1)}$ . Now, let $T_{\uparrow}(\tau):=\inf\{\tau^{\prime}\geq 0:\mathbf{X}(\tau+\tau^{\prime})=(\mathbf{X}((\tau+\tau^{\prime})^{-}))_{\uparrow(a,b)}\}$ be the (random) time elapsed between time $\tau$ and the first of the updates of $1_{(a,b)}$ that occur after time $\tau$ and result in $1_{(a,b)}=1$ . Then, the following holds for all $\mathbf{x}\in\mathbb{X}^{(k-1)}$ , $\tau\geq 0$ , $\sigma>0$ and sufficiently small $\Delta\tau>0$ :

	$\displaystyle\text{Pr}(T_{\uparrow}(\tau)\geq\sigma\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)})$
	$\displaystyle=\text{Pr}(T_{\uparrow}(\tau+\Delta\tau)\geq\sigma-\Delta\tau\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)},T_{\uparrow}(\tau)\geq\Delta\tau)$
	$\displaystyle\quad\cdot\text{Pr}(T_{\uparrow}(\tau)\geq\Delta\tau\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)})$
	$\displaystyle=\text{Pr}(T_{\uparrow}(\tau+\Delta\tau)\geq\sigma-\Delta\tau\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)},$
	$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad X_{n^{2}+\langle a,b\rangle}(\tau^{\prime})=X_{n^{2}+\langle a,b\rangle}(\tau)\,\forall\,\tau^{\prime}\in[\tau,\tau+\Delta\tau))$
	$\displaystyle\quad\cdot\text{Pr}(T_{\uparrow}(\tau)\geq\Delta\tau\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)})$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}e^{-\lambda\frac{\rho_{ij}}{n}(\sigma-\Delta\tau)}\cdot\text{Pr}(T_{\uparrow}(\tau)\geq\Delta\tau\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)})$
	$\displaystyle\stackrel{{\scriptstyle\Delta\tau\rightarrow 0}}{{\longrightarrow}}e^{-\lambda\frac{\rho_{ij}}{n}\sigma}\cdot 1$
	$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\text{Pr}(T_{\uparrow}(\tau)\geq\sigma\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}),$

where $(a)$ and $(b)$ follow from Markovity and the fact that $\mathbf{Q}(\mathbf{z},\mathbf{z}_{\uparrow(a,b)})=\lambda\frac{\rho_{ij}}{n}$ for all $\mathbb{z}\in\mathbb{S}$ . Now, let $T^{(1)}_{\uparrow}(\tau):=T_{\uparrow}(\tau)$ and $T^{(\ell)}_{\uparrow}(\tau):=T_{\uparrow}(T^{(\ell-1)}_{\uparrow}(\tau))$ for all $\ell\in\mathbb{N}$ . Then, since $\{T_{\uparrow}^{(\ell)}\}_{\ell=1}^{\infty}$ are stopping times, similar arguments can be used to show the following for all $\sigma_{1},\sigma_{2},\ldots,\sigma_{\ell}\geq 0$ and all $\ell\in\mathbb{N}$ :

	$\displaystyle\lim_{\Delta\tau\rightarrow 0}$	$\displaystyle\text{Pr}\left(T_{\uparrow}^{(1)}(\tau)\geq\sigma_{1},\ldots,T_{\uparrow}^{(\ell)}(\tau)\geq\sigma_{\ell}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\right)$
		$\displaystyle=\text{Pr}\left(T_{\uparrow}^{(1)}(\tau)\geq\sigma_{1},\ldots,T_{\uparrow}^{(\ell)}(\tau)\geq\sigma_{\ell}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}\right).$

Similarly, if we let $T_{\downarrow}^{(1)}:=\inf\{\tau^{\prime}\geq 0:\mathbf{X}(\tau+\tau^{\prime})=(\mathbf{X}((\tau+\tau^{\prime})^{-}))_{\downarrow(a,b)}\}$ and $T^{(\ell)}_{\downarrow}(\tau):=T_{\downarrow}(T^{(\ell-1)}_{\downarrow}(\tau))$ for all $\ell\in\mathbb{N}$ , then we can show that for all $\sigma_{\uparrow 1},\ldots,\sigma_{\uparrow\ell},\sigma_{\downarrow_{1}},\ldots,\sigma_{\downarrow\ell^{\prime}}\geq 0$ and all $\ell,\ell^{\prime}\in\mathbb{N}$ ,

	$\displaystyle\lim_{\Delta\tau\rightarrow 0}\text{Pr}\Big{(}T_{\uparrow}^{(1)}(\tau)\geq\sigma_{\uparrow 1},\ldots,T_{\uparrow}^{(\ell)}(\tau)\geq\sigma_{\uparrow\ell},T_{\downarrow}^{(1)}(\tau)\geq\sigma_{\downarrow 1},\ldots,T_{\downarrow}^{(\ell^{\prime})}(\tau)\geq\sigma_{\downarrow\ell^{\prime}}$
	$\displaystyle\quad\quad\quad\quad\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\Big{)}$
	$\displaystyle=\text{Pr}\Big{(}T_{\uparrow}^{(1)}(\tau)\geq\sigma_{\uparrow 1},\ldots,T_{\uparrow}^{(\ell)}(\tau)\geq\sigma_{\uparrow\ell},T_{\downarrow}^{(1)}(\tau)\geq\sigma_{\downarrow 1},\ldots,T_{\downarrow}^{(\ell^{\prime})}(\tau)\geq\sigma_{\downarrow\ell^{\prime}}$
	$\displaystyle\quad\quad\quad\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}\Big{)}.$

As a result, we have the following for all $\sigma_{\uparrow 1},\ldots,\sigma_{\uparrow\ell},\sigma_{\downarrow_{1}},\ldots,\sigma_{\downarrow\ell^{\prime}}\geq 0$ and all $\ell,\ell^{\prime}\in\mathbb{N}$ :

	$\displaystyle\frac{\text{Pr}\Big{(}\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,\tau]},\{T_{\uparrow}^{(\xi)}(\tau)\geq\sigma_{\uparrow\xi}\}_{\xi=1}^{\ell},\{T_{\downarrow}^{(\xi)}(\tau)\geq\sigma_{\downarrow\xi}\}_{\xi=1}^{\ell^{\prime}}\Big{)}}{\Delta\tau}$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{\text{Pr}\Big{(}\{T_{\uparrow}^{(\xi)}(\tau)\geq\sigma_{\uparrow\xi}\}_{\xi=1}^{\ell},\{T_{\downarrow}^{(\xi)}(\tau)\geq\sigma_{\downarrow\xi}\}_{\xi=1}^{\ell^{\prime}}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,\tau]},\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\Big{)}}{\text{Pr}\Big{(}\{T_{\uparrow}^{(\xi)}(\tau)\geq\sigma_{\uparrow\xi}\}_{\xi=1}^{\ell},\{T_{\downarrow}^{(\xi)}(\tau)\geq\sigma_{\downarrow\xi}\}_{\xi=1}^{\ell^{\prime}}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,\tau]}\Big{)}}$
	$\displaystyle\quad\times\frac{\text{Pr}\Big{(}\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,\tau]}\Big{)}}{\Delta\tau}$
	$\displaystyle\stackrel{{\scriptstyle\Delta\tau\rightarrow 0}}{{\longrightarrow}}1\times\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)}),$

i.e.,

	$\displaystyle\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}\Big{(}\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,\tau]},\{T_{\uparrow}^{(\xi)}(\tau)\}_{\xi=1}^{\ell},\{T_{\downarrow}^{(\xi)}(\tau)\}_{\xi=1}^{\ell^{\prime}}\Big{)}}{\Delta\tau}$
	$\displaystyle=\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})$

for all $\ell,\ell^{\prime}\in\mathbb{N}$ . Now, observe that if we are given $\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq\tau\}$ , then $\{1_{(a,b)}(\tau^{\prime}):\tau\leq\tau^{\prime}\leq t\}$ are determined by a subset of the random variables $\{T_{\uparrow}^{(\ell)}\}_{\ell=1}^{\infty}\cup\{T_{\downarrow}^{(\ell)}\}_{\ell=1}^{\infty}$ and this subset is random but almost surely finite. Hence, the above limit implies the following for all $\mathbf{x}\in\mathbb{X}^{(k-1)}$ and $\tau\geq 0$ :

\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}\left(\mathbf{X}(\tau+\Delta\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\}\right)}{\Delta\tau}=\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)}).

Moreover, since the above arguments remain valid if we replace $\mathbb{X}^{(k)}$ with an arbitrary $(a,b)$ -agnostic superstate $\mathbb{Y}\neq\mathbb{X}^{(k-1)}$ , we can generalize the above to

\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}\left(\mathbf{X}(\tau+\Delta\tau)\in\mathbb{Y}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\}\right)}{\Delta\tau}=\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})

for all $(a,b)$ -agnostic superstates $\mathbb{Y}\neq\mathbb{X}^{(k-1)}$ . It follows that

\displaystyle\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}\left(\mathbf{X}(\tau+\Delta\tau)\notin\mathbb{X}^{(k-1)}\mid\mathbf{X}(\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\}\right)}{\Delta\tau}=\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})

(70)

for all $\mathbf{x}\in\mathbb{X}^{(k-1)}$ and all $\tau\geq 0$ . This means that, given $\{\mathbf{X}(L_{k-1})=\mathbf{x}\}$ for some $\mathbf{x}\in\mathbb{X}^{(k-1)}$ , the random quantity $L_{k}-L_{k-1}$ , which is the duration of time spent by the Markov chain in $\mathbb{X}^{(k-1)}$ , is conditionally exponentially distributed with rate $\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})$ and it is conditionally independent of $\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\}$ . Besides, the above deductions also imply the following: given $\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\}$ and given that the chain exits $\mathbb{X}^{(k-1)}$ from state $\mathbf{x}$ at time $\tau\geq 0$ , the conditional probability that it enters $\mathbb{X}^{(k)}$ at time $\tau$ is

	$\displaystyle\text{Pr}(\mathbf{X}(\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau^{-})=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\},\mathbf{X}(\tau)\notin\mathbb{X}^{(k-1)})$
	$\displaystyle=\lim_{\Delta\tau\rightarrow 0}\text{Pr}(\mathbf{X}(\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau-\Delta\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\},\mathbf{X}(\tau)\notin\mathbb{X}^{(k-1)})$
	$\displaystyle=\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}(\mathbf{X}(\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau-\Delta\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\})}{\text{Pr}(\mathbf{X}(\tau)\notin\mathbb{X}^{(k-1)}\mid\mathbf{X}(\tau-\Delta\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\})}$
	$\displaystyle=\lim_{\Delta\tau\rightarrow 0}\frac{\text{Pr}(\mathbf{X}(\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau-\Delta\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\})}{\Delta\tau}$
	$\displaystyle\quad\times\lim_{\Delta\tau\rightarrow 0}\left(\frac{\text{Pr}(\mathbf{X}(\tau)\notin\mathbb{X}^{(k-1)}\mid\mathbf{X}(\tau-\Delta\tau)=\mathbf{x},\{1_{(a,b)}(\tau^{\prime}):0\leq\tau^{\prime}\leq t\})}{\Delta\tau}\right)^{-1}$
	$\displaystyle=\frac{\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})}{\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})}.$

By invoking Markovity in the preceding arguments, the above can be generalized to

\displaystyle\text{Pr}(\mathbf{X}(\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau^{-})=\mathbf{x},\{\mathbf{X}(\tau^{\prime})\}_{\tau^{\prime}\in[0,\tau)},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]},\mathbf{X}(\tau)\notin\mathbb{X}^{(k-1)})=\frac{\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})}{\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})},

(71)

which implies that

	$\displaystyle\text{Pr}(\mathbf{X}(\tau)\in\mathbb{X}^{(k)}\mid\mathbf{X}(\tau^{\prime})=\mathbf{x}\,\forall\,\tau^{\prime}\in[L_{k-1},\tau),\{\mathbf{X}(\tau^{\prime})\}_{\tau^{\prime}\in[0,L_{k-1})}\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]},\mathbf{X}(\tau)\notin\mathbb{X}^{(k-1)})$
	$\displaystyle=\frac{\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})}{\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})}.$

Equivalently,

\text{Pr}(\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\mid\mathbf{X}(L_{k-1})=\mathbf{x},\{\mathbf{X}(\tau^{\prime})\}_{\tau^{\prime}\in[0,L_{k-1})},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]},L_{k}=\tau)=\frac{\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})}{\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})}.

for all $\tau>0$ and $\mathbf{x}\in\mathbb{X}^{(k-1)}$ . Hence,

\displaystyle\text{Pr}(\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\mid\mathbf{X}(L_{k-1})\in\mathbb{X}^{(k-1)},\{\mathbf{X}(\tau^{\prime})\}_{\tau^{\prime}\in[0,L_{k-1})},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]},L_{k})=\frac{\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})}{\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})}.

(72)

Since the entire analysis above holds for all $k\in[N]$ , we have the following for all $\sigma_{1},\sigma_{2},\ldots,\sigma_{N}\geq 0$ :

		$\displaystyle\text{Pr}\left(\left(\cap_{k=1}^{N}\{L_{k}-L_{k-1}\geq\sigma_{k}\}\right)\cap\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\right)\mid\mathbf{X}(0)\in\mathbb{X}^{(0)},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]}\right)$		(73)
		$\displaystyle=\prod_{k=1}^{N}\text{Pr}(\mathbf{X}(L_{k})\in\mathbb{X}^{(k)},L_{k}-L_{k-1}\geq\sigma_{k}\mid\{\mathbf{X}(L_{\xi})\in\mathbb{X}^{(\xi)},L_{\xi}-L_{\xi-1}\geq\sigma_{\xi}\}_{\xi=0}^{k-1},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]})$		(74)
		$\displaystyle=\prod_{k=1}^{N}\text{Pr}(L_{k}-L_{k-1}\geq\sigma_{k}\mid\{\mathbf{X}(L_{\xi})\in\mathbb{X}^{(\xi)},L_{\xi}-L_{\xi-1}\geq\sigma_{\xi}\}_{\xi=0}^{k-1},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]})$		(75)
		$\displaystyle\quad\times\prod_{k=1}^{N}\text{Pr}(\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\mid L_{k}-L_{k-1}\geq\sigma_{k},\{\mathbf{X}(L_{\xi})\in\mathbb{X}^{(\xi)},L_{\xi}-L_{\xi-1}\geq\sigma_{\xi}\}_{\xi=0}^{k-1},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]})$		(76)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\prod_{k=1}^{N}\text{Pr}(L_{k}-L_{k-1}\geq\sigma_{k}\mid\mathbf{X}(L_{k-1})\in\mathbb{X}^{(k-1)},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]})$		(77)
		$\displaystyle\quad\times\prod_{k=1}^{N}\text{Pr}(\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\mid L_{k}-L_{k-1}\geq\sigma_{k},\{\mathbf{X}(L_{\xi})\in\mathbb{X}^{(\xi)},L_{\xi}-L_{\xi-1}\geq\sigma_{\xi}\}_{\xi=0}^{k-1},\{1_{(a,b)}(\tau^{\prime})\}_{\tau^{\prime}\in[0,t]})$		(78)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\prod_{k=1}^{N}\exp\left(-\sigma_{k}\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})\right)\times\prod_{k=1}^{N}\frac{\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{X}^{(k)})}{\sum_{\mathbb{Y}\neq\mathbb{X}^{(k-1)}}\mathbf{Q}(\mathbb{X}^{(k-1)},\mathbb{Y})},$		(79)

where $(a)$ is a consequence of the strong Markov property and the fact that $\{L_{k}\}_{k=1}^{N}$ are stopping times, and (b) follows from (70) and (72). Since $\sigma_{1},\ldots,\sigma_{N}$ are arbitrary and since the above expression is independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ , we have shown that for the event

F\cap\{L_{N}\geq\kappa\}=\left\{\mathbf{X}(0)\in\mathbb{X}^{(0)},\ldots,\mathbf{X}(L_{N})\in\mathbb{X}^{(N)},\sum_{k=1}^{N}(L_{k}-L_{k-1})\geq\kappa\right\},

we have $\text{Pr}(F\cap\{L_{N}\geq\kappa\}\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\})=\text{Pr}(F\cap\{L_{N}\geq\kappa\})$ . As a result,

	$\displaystyle\text{Pr}(\{\tilde{K}=L_{N}\}\cap\{L_{N}\geq\kappa\}\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\})$
	$\displaystyle=\text{Pr}\left(\cup_{F\in\mathcal{F}_{N}(\kappa)}(F\cap\{L_{N}\geq\kappa\})\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\}\right)$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{F\in\mathcal{F}_{N}(\kappa)}\text{Pr}\left(F\cap\{L_{N}\geq\kappa\}\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\}\right)$
	$\displaystyle=\sum_{F\in\mathcal{F}_{N}(\kappa)}\text{Pr}(F\cap\{L_{N}\geq\kappa\})$
	$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\text{Pr}\left(\cup_{F\in\mathcal{F}_{N}(\kappa)}(F\cap\{L_{N}\geq\kappa\})\right)$
	$\displaystyle=\text{Pr}(\{\tilde{K}=L_{N}\}\cap\{L_{N}\geq\kappa\}),$

where $(a)$ and $(b)$ hold because the definition of $\mathcal{F}_{N}(\kappa)$ implies that $\mathcal{F}_{N}(\kappa)$ is a collection of disjoint events. Since $\{\tilde{K}\geq\kappa\}=\cup_{N=0}^{\infty}\left(\{\tilde{K}=L_{N}\}\cap\{L_{N}\geq\kappa\}\right)$ and since $\{\tilde{K}=L_{1}\}\cap\{L_{1}\geq\kappa\},\{\tilde{K}=L_{2}\}\cap\{L_{2}\geq\kappa\},\ldots$ are disjoint events, it follows that $\text{Pr}(\tilde{K}\geq\kappa\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\})=\text{Pr}(\tilde{K}\geq\kappa)$ . Moreover, since $\kappa\geq 0$ is arbitrary, this means that $\tilde{K}$ is independent of $\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ . Finally, since $K$ and $(T,1_{(a,b)}(t))$ are functions of $\tilde{K}$ and $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ , respectively, it follows that $K$ and $(T,1_{(a,b)}(t))$ are independent.

Remark 3.

Observe that in the proof of Lemma 5, $\eqref{eq:last_leg}$ implies that the event $\{L_{N}\geq\kappa\}\cap\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\right)$ is independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ (since $L_{N}=\sum_{k=1}^{N}(L_{k}-L_{k-1})$ and since the initial state $\mathbf{X}(0)$ is assumed to be non-random). Note that this is true for all the choices of $(a,b)$ -agnostic superstates $\{\mathbb{X}^{(k)}\}_{k=0}^{N}$ that satisfy $\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\subset\{\tilde{K}=L_{N}\}$ and hence also for all $\{\mathbb{X}^{(k)}\}_{k=0}^{N}$ that satisfy $\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\subset\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}$ , where $\mathbb{Y}$ is an arbitrary $(a,b)$ -agnostic superstate. Now, let us by $\mathcal{X}$ the set of all $\{\mathbb{X}^{(k)}\}_{k=0}^{N}$ satisfying $\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\subset\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}$ , we have

\cup_{\{\mathbb{X}^{(k)}\}_{k=0}^{N}\in\mathcal{X}}\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\right)=\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}.

Then, by the preceding arguments we have

	$\displaystyle\text{Pr}(\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}\cap\{L_{N}\geq\kappa\}\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\})$		(80)
	$\displaystyle=\text{Pr}\left(\cup_{\{\mathbb{X}^{(k)}\}_{k=0}^{N}\in\mathcal{X}}\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\right)\cap\{L_{N}\geq\kappa\}\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\}\right)$		(81)
	$\displaystyle=\sum_{\{\mathbb{X}^{(k)}\}_{k=0}^{N}\in\mathcal{X}}\text{Pr}\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\cap\{L_{N}\geq\kappa\}\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\}\right)$		(82)
	$\displaystyle=\sum_{\{\mathbb{X}^{(k)}\}_{k=0}^{N}\in\mathcal{X}}\text{Pr}\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\cap\{L_{N}\geq\kappa\}\right)$		(83)
	$\displaystyle=\text{Pr}\left(\cup_{\{\mathbb{X}^{(k)}\}_{k=0}^{N}\in\mathcal{X}}\left(\cap_{k=0}^{N}\{\mathbf{X}(L_{k})\in\mathbb{X}^{(k)}\}\cap\{L_{N}\geq\kappa\}\right)\right)$		(84)
	$\displaystyle=\text{Pr}(\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}\cap\{L_{N}\geq\kappa\}),$		(85)

which shows that $\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}\cap\{L_{N}\geq\kappa\}$ is independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ . Since $\{\tilde{K}\geq\kappa\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}=\cup_{N=0}^{\infty}\left(\{\tilde{K}=L_{N}\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}\cap\{L_{N}\geq\kappa\}\right)$ , it follows that $\{\tilde{K}\geq\kappa\}\cap\{\mathbf{X}(\tilde{K})\in\mathbb{Y}\}$ is independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ . As a consequence of this observation, the fact that $\mathbb{Y}$ is an arbitrary $(a,b)$ -agnostic superstate and the fact that $\kappa$ is an arbitrary non-negative number, we have that $(\mathbb{X}(\tilde{K}),\tilde{K})$ are independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ , where $\mathbb{X}(\tilde{K})$ denotes the $(a,b)$ -agnostic superstate of the chain at time $\tilde{K}$ .

In order to state the remaining lemmas, we need to introduce some additional notation. For two nodes $(a,b)\in[n]\times[n]$ , we let $b\stackrel{{\scriptstyle t}}{{\rightsquigarrow}}a$ denote the event that $b$ transmits pathogens to $a$ at time $t$ . For a given time interval $[t,t+\Delta t)\subset[0,\infty)$ , we let $\left\{b\stackrel{{\scriptstyle t,\Delta t}}{{\rightsquigarrow}}a\right\}:=\cup_{\tau\in[t,t+\Delta t)}\{b\stackrel{{\scriptstyle\tau}}{{\rightsquigarrow}}a\}$ . The complement of this event is denoted by $\left\{b\stackrel{{\scriptstyle t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}$ . For two given node sets $A,B\subset[n]$ , we use $\{B\stackrel{{\scriptstyle t}}{{\rightsquigarrow}}A\}$ to denote the event that some node(s) of $B$ infect(s) one or more nodes in $A$ at time $t$ .

We now provide a sequence of lemmas that we later use to prove Proposition 2.

Lemma 6.

Suppose $a\in\mathcal{A}_{i}$ , $b\in\mathcal{A}_{j}$ , $y\in\{0,1\}$ , and $t_{1},t_{2}\in[0,\infty)$ such that $t_{1}<t_{2}$ . Given that $b\in\mathcal{I}_{j}(t_{1}):=\mathcal{I}_{j}(\mathbf{X}(t_{1}))$ and that $1_{(a,b)}(\tau):=1_{(a,b)}(\mathbf{X}(\tau))=y$ for all $\tau\in[t_{1},t_{2})$ , the conditional probability that $b$ neither recovers nor infects $a$ during the interval $[t_{1},t_{2})$ is $e^{-(B_{ij}\delta_{1y}+\gamma_{j})(t_{2}-t_{1})}$ , where $\delta_{ij}$ is the Kronecker delta.

Proof.

Let $\mathbb{X}:=\{\mathbf{x}\in\mathbb{S}:b\in\mathcal{I}_{j}(\mathbf{x}),1_{(a,b)}(\mathbf{x})=y\}$ . Also, let $\Delta t>0$ . Since the rate of infection transmission from $b$ to $a$ at time $t_{1}$ is $B_{ij}1_{(a,b)}(\mathbf{X}(t_{1}))$ , we have the following for all $\mathbf{x}\in\mathbb{X}$ :

\text{Pr}\left(b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\rightsquigarrow}}a\Bigm{|}\mathbf{X}(t_{1})=\mathbf{x}\right)=B_{ij}\delta_{1y}\Delta t+o(\Delta t).

On the other hand, denoting the event that $b$ recovers during $[t_{1},t_{1}+\Delta t)$ by $D_{b}$ , we have

\text{Pr}(D_{b}\mid\mathbf{X}(t)=\mathbf{x})={\gamma_{j}}\Delta t+o(\Delta t).

Similarly, if we let $F_{(a,b)}$ denote the event that the edge state $1_{(a,b)}$ flips (i.e., changes from $y$ to $1-y$ ) during $[t_{1},t_{1}+\Delta t)$ , we have $\text{Pr}(F_{(a,b)}\mid\mathbf{X}(t)=\mathbf{x})=\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\Delta t+o(\Delta t)$ . As a result, we have

	$\displaystyle\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}\cap\bar{F}_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle=1-\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\rightsquigarrow}}a\right\}\cup D_{b}\cup F_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}1-\text{Pr}\left(b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\rightsquigarrow}}a\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)-\text{Pr}(D_{b}\mid\mathbf{X}(t_{1})=\mathbf{x})-\text{Pr}(F_{(a,b)}\mid\mathbf{X}(t_{1})=\mathbf{x}\})+o(\Delta t)$
	$\displaystyle=1-(B_{ij}\delta_{1y}\Delta t+o(\Delta t))-(\gamma_{j}\Delta t+o(\Delta t))-\left(\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\Delta t+o(\Delta t)\right)+o(\Delta t)$
	$\displaystyle=1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t),$

where (a) follows from Lemma 1 and the Inclusion-Exclusion principle. Since this holds for all $\mathbf{x}\in\mathbb{X}$ , the above implies that

	$\displaystyle\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}\cap\bar{F}_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1})\in\mathbb{X}\right)$
	$\displaystyle=1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t).$

Now, consider any $\ell\in\mathbb{N}_{0}$ . By replacing $t_{1}$ with $t_{1}+\ell\Delta t$ in the above relation, we obtain

	$\displaystyle\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1}+\ell\Delta t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}^{(\ell)}\cap\bar{F}^{(\ell)}_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1}+\ell\Delta t)\in\mathbb{X}\right)$
	$\displaystyle=1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t),$

where $D_{b}^{(\ell)}$ is the event that $b$ recovers during $[t_{1}+\ell\Delta t,t_{1}+(\ell+1)\Delta t)$ and $F_{(a,b)}^{(\ell)}$ is the event that $1_{(a,b)}$ flips during $[t_{1}+\ell\Delta t,t_{1}+(\ell+1)\Delta t)$ . Therefore, on setting $\Delta t=\frac{t_{2}-t_{1}}{N}$ for an arbitrary $N\in\mathbb{N}$ , it follows that

		$\displaystyle\text{Pr}\left(\{b\in\mathcal{I}(t)\}\cap\left\{b\stackrel{{\scriptstyle t_{1},t_{2}-t_{1}}}{{\centernot\rightsquigarrow}}a\right\}\cap\{1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$		(86)
		$\displaystyle=\prod_{\ell=1}^{N-1}\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1}+\ell\Delta t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}^{(\ell)}\cap\bar{F}_{(a,b)}^{(\ell)}\Bigm{\|}b\stackrel{{\scriptstyle t_{1},\ell\Delta t}}{{\centernot\rightsquigarrow}}a,\bar{D}_{b},\bar{D}_{b}^{(1)},\ldots,\bar{D}_{b}^{(\ell-1)},\bar{F}_{(a,b)},\ldots,\bar{F}_{(a,b)}^{(\ell-1)},\mathbf{X}(t_{1})=\mathbf{x}\right)$		(87)
		$\displaystyle\quad\quad\times\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}\cap\bar{F}_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$		(88)
		$\displaystyle=\prod_{\ell=1}^{N-1}\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1}+\ell\Delta t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}^{(\ell)}\cap\bar{F}_{(a,b)}^{(\ell)}\Bigm{\|}\mathbf{X}(t_{1}+\ell\Delta t)\in\mathbb{X},b\stackrel{{\scriptstyle t_{1},\ell\Delta t}}{{\centernot\rightsquigarrow}}a,\{\bar{D}_{b}^{(\sigma)}\}_{\sigma=0}^{\ell-1},\{\bar{F}_{(a,b)}^{(\sigma)}\}_{\sigma=0}^{\ell-1},\mathbf{X}(t_{1})=\mathbf{x}\right)$		(89)
		$\displaystyle\quad\quad\times\left(1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t)\right)$		(90)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\prod_{\ell=1}^{N-1}\left(1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t)\right)$		(91)
		$\displaystyle\quad\times\left(1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t)\right)$		(92)
		$\displaystyle=\left(1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\left(\frac{t_{2}-t_{1}}{N}\right)\right)^{N}+o\left(\frac{1}{N}\right),$		(93)

where (a) follows from the following observation: for any $\mathbf{y}\in\mathbb{X}$ , Markovity implies that

	$\displaystyle\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1}+\ell\Delta t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}^{(\ell)}\cap\bar{F}_{(a,b)}^{(\ell)}\Bigm{\|}\mathbf{X}(t_{1}+\ell\Delta t)=\mathbf{y},b\stackrel{{\scriptstyle t_{1},\ell\Delta t}}{{\centernot\rightsquigarrow}}a,\{\bar{D}_{b}^{(\sigma)}\}_{\sigma=0}^{\ell-1},\{\bar{F}_{(a,b)}^{(\sigma)}\}_{\sigma=0}^{\ell-1},\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle=\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1}+\Delta t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}^{(1)}\cap\bar{F}_{(a,b)}^{(1)}\Bigm{\|}\mathbf{X}(t_{1}+\Delta t)=\mathbf{y}\right)$
	$\displaystyle=1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t),$

which further implies that

	$\displaystyle\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1}+\ell\Delta t,\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}^{(\ell)}\cap\bar{F}_{(a,b)}^{(\ell)}\Bigm{\|}\mathbf{X}(t_{1}+\ell\Delta t)\in\mathbb{X},b\stackrel{{\scriptstyle t_{1},\ell\Delta t}}{{\centernot\rightsquigarrow}}a,\{\bar{D}_{b}^{(\sigma)}\}_{\sigma=0}^{\ell-1},\{\bar{F}_{(a,b)}^{(\sigma)}\}_{\sigma=0}^{\ell-1},\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle=1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t).$

Now, since (86) holds for all $N\in\mathbb{N}$ , it follows that

		$\displaystyle\text{Pr}\left(\{b\in\mathcal{I}(t)\}\cap\left\{b\stackrel{{\scriptstyle t_{1},t_{2}-t_{1}}}{{\centernot\rightsquigarrow}}a\right\}\cap\{1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$		(94)
		$\displaystyle=\lim_{N\rightarrow\infty}\left(\left(1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda y\left(1-\frac{\rho_{ij}}{n}\right)+\lambda\left(1-y\right)\frac{\rho_{ij}}{n}\right)\left(\frac{t_{2}-t_{1}}{N}\right)\right)^{N}+o\left(\frac{1}{N}\right)\right)$		(95)
		$\displaystyle=e^{-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\left(t_{2}-t_{1}\right)}.$		(96)

Similarly, we can show that

\displaystyle\text{Pr}\left(1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\Bigm{|}\mathbf{X}(t_{1})=\mathbf{x}\right)=e^{-\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\left(t_{2}-t_{1}\right)}.

(97)

As a result of (94) and (97),

	$\displaystyle\text{Pr}\left(\{b\in\mathcal{I}(t)\}\cap\left\{b\stackrel{{\scriptstyle t_{1},t_{2}-t_{1}}}{{\centernot\rightsquigarrow}}a\right\}\Bigm{\|}\{1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\},\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle=\frac{\text{Pr}\left(\{b\in\mathcal{I}(t)\}\cap\left\{b\stackrel{{\scriptstyle t_{1},t_{2}-t_{1}}}{{\centernot\rightsquigarrow}}a\right\}\cap\{1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)}{\text{Pr}\left(1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)}$
	$\displaystyle=e^{-(B_{ij}\delta_{1y}+\gamma_{j})(t_{2}-t_{1})}.$

Since the above holds for all $\mathbf{x}\in\mathbb{X}$ , it follows that

\text{Pr}\left(\{b\in\mathcal{I}(t)\}\cap\left\{b\stackrel{{\scriptstyle t_{1},t_{2}-t_{1}}}{{\centernot\rightsquigarrow}}a\right\}\Bigm{|}\{1_{(a,b)}(\tau)=y\,\forall\,\tau\in[t_{1},t_{2})\},\mathbf{X}(t_{1})\in\mathbb{X}\right)=e^{-(B_{ij}\delta_{1y}+\gamma_{j})(t_{2}-t_{1})},

which proves the lemma.

Lemma 7.

Let $T_{\text{on}}:=\int_{t-K}^{t-T}1_{(a,b)}(\sigma)d\sigma$ denote the total duration of time for which the edge $(a,b)$ exists in the network during $[t-K,t-T]$ . Then, for all $\kappa,\tau\in[0,t]$ and all $\tau_{\text{on}}\in\left[0,(\kappa-\tau)_{+}\right]$ , we have

\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)=e^{-B_{ij}\tau_{\text{on}}},

where we define $\mathcal{I}(\sigma^{-}):=\cup_{\varepsilon>0}\cap_{\tau^{\prime}\in[\sigma-\varepsilon,\sigma)}\mathcal{I}(\tau^{\prime})$ for all $\sigma\geq 0$ . In other words, $c\in\mathcal{I}(\sigma^{-})$ iff there exists an $\varepsilon>0$ such that $c\in\mathcal{I}(\tau^{\prime})$ for all $\tau^{\prime}\in[\sigma-\varepsilon,\sigma)$ .

Proof.

We first show that $\left\{b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\right\}$ is conditionally independent of $\{(a,b)\notin E(t)\}$ given $(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}})$ and $b\in\mathcal{I}(t-\tau)$ :

		$\displaystyle\text{Pr}\left((a,b)\in E(t)\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t-\tau),b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\right)$		(98)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{Pr}\left((a,b)\in E(t-\tau)\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t-\tau),b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\right)$		(99)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{\rho_{ij}}{n}$		(100)
		$\displaystyle=\text{Pr}\left((a,b)\in E(t-\tau)\mid T=\tau\right)$		(101)
		$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\text{Pr}((a,b)\in E(t)\mid T=\tau),$		(102)

where $(a)$ and $(c)$ hold because $1_{(a,b)}$ is not updated during the interval $[t-\tau,t)$ , and (b) follows from the modeling assumption that the probability of the edge $(a,b)$ existing in the network following an edge state update is $\frac{\rho_{ij}}{n}$ (independent of the past states $\{\mathbf{X}(\tau^{\prime}):0\leq\tau^{\prime}<t-\tau\}$ ), the fact that $\{b\in\mathcal{I}(t-\tau)\}=\{b\in\mathcal{I}((t-\tau)^{-})\}$ almost surely, and from the observation that $t-\tau$ is an update time for $1_{(a,b)}$ given $T=\tau$ .

In view of (98), the definitions of $K$ , $T$ , and $T_{\text{on}}$ imply that

		$\displaystyle\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)$		(103)
		$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)$		(104)
		$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t^{-})\right)$		(105)
		$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t-\tau),b\notin\cup_{\tau^{\prime}\in(t-\tau,t)}\mathcal{R}(\tau^{\prime})\right)$		(106)
		$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t-\tau)\right),$		(107)

where the last step holds because $\mathbf{Q}(\mathbf{x},\mathbf{x}_{\downarrow b})=\gamma_{j}$ for all $\mathbf{x}\in\mathbb{S}$ satisfying $x_{b}=1$ , which implies that, given $b\in\mathcal{I}(t-\tau)$ and any other conditioning event, node $b$ recovers during $(t-\tau,t)$ at a constant rate of $\gamma_{j}$ independently of all past edge states and past disease states (and therefore independently of past transmissions as well). Hence, $\left\{b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\right\}$ and $\{b\notin\cup_{\tau^{\prime}\in(t-\tau,t)}\mathcal{R}(\tau^{\prime})\}$ are conditionally independent given $(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}})$ and $b\in\mathcal{I}(t-\tau)$ .

We now evaluate the right-hand side of (103) as follows. Let $C$ denote the (random) number of times $1_{(a,b)}$ flips (changes) during $[t-K,t-T]$ , and let the times of these changes be $T_{1}<\cdots<T_{C}$ . We assume that $C$ is even (as the case of $C$ being odd is handled similarly) and that $1_{(a,b)}(\tau^{\prime})=0$ for $\tau^{\prime}\in[t-K,T_{1}]$ (the case $1_{(a,b)}(\tau^{\prime})=1$ for $\tau^{\prime}\in[t-K,T_{1}]$ is handled similarly). Then, for a given $c\in\mathbb{N}$ and a collection of times $t_{1},\ldots,t_{c},\tau_{\text{on}}$ , we have $\{C=c,T_{1}=t_{1},\ldots,T_{c}=t_{c}\}\subset\{T_{\text{on}}=\tau_{\text{on}}\}$ iff $\sum_{k=1}^{c/2}(t_{2k}-t_{2k-1})=\tau_{\text{on}}$ . Suppose this condition holds. Then, observe that

		$\displaystyle\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t-\tau)\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),C=c,(T_{1},\ldots,T_{c})=(t_{1},\ldots,t_{c})\right)$		(108)
		$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t-\tau)\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),1_{(a,b)}(\tau^{\prime})=1\text{ iff }\tau^{\prime}\in\cup_{k=1}^{c/2}[t_{2k-1},t_{2k}]\right)$		(109)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\prod_{k=1}^{c/2}\text{Pr}\left(b\stackrel{{\scriptstyle t_{2k-1},t_{2k}-t_{2k-1}}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t_{2k})\,\bigg{\lvert}\,1_{(a,b)}(\tau^{\prime})=1\,\forall\,\tau^{\prime}\in[t_{2k-1},t_{2k}],b\in\mathcal{I}(t_{2k-1})\right)$		(110)
		$\displaystyle\quad\times\prod_{k=1}^{c/2+1}\text{Pr}\left(b\stackrel{{\scriptstyle t_{2k-2},t_{2k-1}-t_{2k-2}}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t_{2k-1})\,\bigg{\lvert}\,1_{(a,b)}(\tau^{\prime})=0\,\forall\,\tau^{\prime}\in[t_{2k-2},t_{2k-1}],b\in\mathcal{I}(t_{2k-1})\right)$		(111)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\prod_{k=1}^{c/2}e^{-(B_{ij}+\gamma_{j})(t_{2k}-t_{2k-1})}\times\prod_{k=1}^{c/2+1}e^{-\gamma_{j}(t_{2k-1}-t_{2k-2})}$		(112)
		$\displaystyle=e^{-B_{ij}\sum_{k=1}^{c/2}(t_{2k}-t_{2k-1})}\cdot e^{-\gamma_{j}\sum_{k=1}^{c+1}(t_{k}-t_{k-1})}$		(113)
		$\displaystyle=e^{-B_{ij}\tau_{\text{on}}}e^{-\gamma_{j}(\kappa-\tau)},$		(114)

where $(b)$ follows from Lemma 6, and $(a)$ follows from the following fact: since the definition of our epidemic model implies that the rate of pathogen transmission from $b$ to $a$ at any time instant $t^{\prime}$ depends only on $1_{(a,b)}(t^{\prime})$ and the disease state of $b$ at time $t^{\prime}$ , transmission events corresponding to disjoint time intervals are conditionally independent if we are given $1_{(a,b)}$ and the disease state of $b$ as functions of time.

On the other hand, we have

		$\displaystyle\text{Pr}(b\in\mathcal{I}(t-\tau)\mid(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),C=c,(T_{1},\ldots,T_{c})=(t_{1},\ldots,t_{c}))$		(115)
		$\displaystyle=\text{Pr}(b\notin\mathbb{R}(t-\tau)\mid(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),C=c,(T_{1},\ldots,T_{c})=(t_{1},\ldots,t_{c}))$		(116)
		$\displaystyle=e^{-\gamma_{j}((t-\tau)-(t-\kappa))}$		(117)
		$\displaystyle=e^{-\gamma_{j}(\kappa-\tau)},$		(118)

where the second equality holds because our model assumes that the rate of recovery of an infected node is time-invariant and independent of all the edge states and the disease states of other nodes (precisely, $\mathbf{Q}(\mathbf{x},\mathbf{x}_{\downarrow b})=\gamma_{j}$ for all $\mathbf{x}\in\mathbb{S}$ such that $b\in\mathcal{I}(\mathbf{x})$ ).

As a result of (108) and (115), we have

	$\displaystyle\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t-\tau),(C,T_{1},\ldots,T_{C})=(c,t_{1},\ldots,t_{c})\right)$
	$\displaystyle=\frac{\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t-\tau)\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),(C,T_{1},\ldots,T_{C})=(c,t_{1},\ldots,t_{c})\right)}{\text{Pr}\left(b\in\mathcal{I}(t-\tau)\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),(C,T_{1},\ldots,T_{C})=(c,t_{1},\ldots,t_{c})\right)}$
	$\displaystyle=e^{-B_{ij}\tau_{\text{on}}}.$

Since $(c,t_{1},\ldots,t_{c})$ was an arbitrary tuple satisfying $\{(C,T_{1},\ldots,T_{C})=(c,t_{1},\ldots,t_{c})\}\subset\{T_{\text{on}}=\tau_{\text{on}}\}$ , it follows that

\text{Pr}\left(b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\in\mathcal{I}(t-\tau)\right)=e^{-B_{ij}\tau_{\text{on}}}.

Invoking (103) now completes the proof.

Observe that in the above proof, given that $K=\kappa$ and that $(a,b)\notin E(t)$ , $(C,T_{1},\ldots,T_{C})$ uniquely determines $\{1_{(a,b)}(\tau):t-K\leq\tau\leq t\}$ . Therefore, as an implication of the above proof, we have

\text{Pr}\left(b\stackrel{{\scriptstyle t-K,t}}{{\centernot\rightsquigarrow}}a\mid K=\kappa,\{1_{(a,b)}(\tau):t-K\leq\tau\leq t\},b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)=e^{-B_{ij}T_{\text{on}}}.

The dependence on the random variable $T_{\text{on}}$ holds because $T_{\text{on}}$ is a function of $\{1_{(a,b)}(\tau):t-K\leq\tau\leq t\}$ . By invoking Markovity, this result can be extended to

\text{Pr}\left(b\stackrel{{\scriptstyle t-K,t}}{{\centernot\rightsquigarrow}}a\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)=e^{-B_{ij}T_{\text{on}}},

which is equivalent to the following lemma.

Lemma 8.

\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\bigg{\lvert}\,K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)=e^{-B_{ij}T_{\text{on}}}.

Lemma 9.

Recall from Lemma 8 that $T_{\text{on}}=\int_{t-K}^{t-T}1_{(a,b)}(\sigma)d\sigma$ . Then for all $\kappa,\tau\in[0,t]$ , we have

	$\displaystyle\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\,\Big{\lvert}\,(K,T,T_{\text{on}})=(\kappa,\tau,\tau_{\text{on}}),b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,(a,b)\notin E(t),b\in\mathcal{I}(t^{-})\right)$
	$\displaystyle=\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\,\Big{\lvert}\,K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,(a,b)\notin E(t),b\in\mathcal{I}(t^{-})\right).$

Proof.

We first examine the following conditional probability for an arbitrary $(a,b)$ -agnostic superstate $\mathbb{Y}$ :

\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right).

To begin, note that the proof of Lemma 5, Remark 3, and the fact that $K$ is a function of $\tilde{K}$ together imply that

\displaystyle f_{K\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)}(\kappa)=f_{K}(\kappa)

and that

\displaystyle\text{Pr}(\mathbf{X}(\tilde{K})\in\mathbb{Y}\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t))=\text{Pr}(\mathbf{X}(\tilde{K})\in\mathbb{Y}\mid K=\kappa).

(119)

Next, for the event $\{b\in\mathcal{I}(t^{-})\}$ , we have

		$\displaystyle\text{Pr}\left(b\in\mathcal{I}(t^{-})\mid K=\kappa,\mathbf{X}(\tilde{K})\in\mathbb{Y},\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$		(120)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}e^{-\gamma_{j}(t-\kappa)}$		(121)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\text{Pr}\left(b\in\mathcal{I}(t^{-})\mid K=\kappa\right)$		(122)

where $(a)$ and $(b)$ follow from our modelling assumption that $\mathbf{Q}(\mathbf{x},\mathbf{x}_{\downarrow b})=\gamma_{j}$ for all $\mathbf{x}$ satisfying $x_{b}=1$ , which means that the recovery time of $b$ depends only on the time of infection of $b$ and is conditionally independent of all other disease states and all the edge states. Similarly, we have

		$\displaystyle\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t),b\in\mathcal{I}(t^{-})\right)$		(123)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t),b\in\mathcal{I}(t^{-})\right)$		(124)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}e^{-B_{ij}T_{\text{on}}}$		(125)

where $(a)$ follows from our modelling assumptions, which imply that the rate of infection transmission along an edge depends only on the edge state of the transmitting edge and the disease state of the transmitting node and is conditionally independent of other disease states and edge states (which are captured by the $(a,b)$ -agnostic superstate of the chain) and $(b)$ follows from Lemma 8. Note that $T_{\text{on}}$ is a function of $T$ and hence also of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ .

It remains for us to analyze

\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right).

To do so, we first let $L_{N}$ denote the time of the first $(a,b)$ -agnostic jump to occur after $b$ gets infected, i.e., $N:=\inf\{\ell\in\mathbb{N}:L_{\ell}\geq\tilde{K}\}$ , and we note the following: given the conditioning events and variables above (including the event that $b$ does not infect $a$ during $[0,t]$ ), the total conditional rate at which $a$ receives pathogens at any time $\tau\leq L_{N}$ is

\sum_{q=1}^{m}\sum_{d\in\mathcal{I}_{q}(\mathbf{X}(\tilde{K})\setminus\{b\}}B_{iq}1_{(a,d)}(\mathbf{X}(\tilde{K})),

which is determined uniquely by $\mathbb{Y}$ , the $(a,b)$ -agnostic superstate of the chain at time $\tilde{K}$ . Therefore, this rate is conditionally independent of $1_{(a,b)}(\tau)$ for any $\tau$ . Similarly, for all age groups $\ell\in[m]$ , given the conditioning events and variables above, the conditional rate at which a node $d\in\mathcal{I}_{\ell}(\mathbf{X}(\tilde{K}))$ recovers, which equals $\gamma_{\ell}$ , and the total conditional rate at which a node $c\in\mathcal{A}_{\ell}\setminus\{a\}$ receives pathogens, which equals $\sum_{q=1}^{m}\sum_{d\in\mathcal{I}_{q}(\mathbf{X}(\tilde{K}))}B_{\ell q}1_{(c,d)}(\mathbf{X}(\tilde{K}))$ , are both conditionally independent of $1_{(a,b)}(\tau)$ given that $\mathbf{X}(\tilde{K})\in\mathbb{Y}$ . Therefore, by using arguments similar to those made in the proof of Lemma 5, we can show that $(\mathcal{S}(L_{N}),\mathcal{I}(L_{N}))$ is conditionally independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ given the rest of the conditioning events and variables. Moreover, by repeating the above for subsequent $(a,b)$ -agnostic jumps, we can generalize this conditional independence assertion to $(\mathcal{S}(t),\mathcal{I}(t))$ , which means that

	$\displaystyle\text{Pr}\Big{(}(\mathcal{S}(t$	$\displaystyle),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\Big{)}$
		$\displaystyle=\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right).$		(127)

Combining (119), (120), (123) and (Proof.) now yields

	$\displaystyle\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),\mathbf{X}(\tilde{K})\in\mathbb{Y},b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$
	$\displaystyle=\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)$
	$\displaystyle\quad\times e^{-B_{ij}T_{\text{on}}}\times\text{Pr}(b\in\mathcal{I}(t^{-})\mid K=\kappa)\times\text{Pr}(\mathbf{X}(\tilde{K})\in\mathbb{Y}\mid K=\kappa)$

Summing both the sides of the above equation over the space of all $(a,b)$ -agnostic superstates $\mathbb{Y}$ gives

		$\displaystyle\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$
		$\displaystyle=e^{-B_{ij}T_{\text{on}}}\times\text{Pr}(b\in\mathcal{I}(t^{-})\mid K=\kappa)$		(128)
		$\displaystyle\quad\times\sum_{\mathbb{Y}}\Bigg{(}\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)$		(129)
		$\displaystyle\quad\quad\quad\quad\quad\cdot\text{Pr}(\mathbf{X}(\tilde{K})\in\mathbb{Y}\mid K=\kappa)\Bigg{)}.$		(130)

Here, we recall from our earlier arguments that

	$\displaystyle e^{-B_{ij}T_{\text{on}}}\times\text{Pr}(b\in\mathcal{I}(t^{-})\mid K=\kappa)$
	$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t),b\in\mathcal{I}(t^{-})\right)$
	$\displaystyle\quad\times\text{Pr}\left(b\in\mathcal{I}(t^{-})\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$
	$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right).$

In light of (Proof.), this means that

	$\displaystyle\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid K=\kappa,\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$
	$\displaystyle=\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$
	$\displaystyle\quad\times\sum_{\mathbb{Y}}\Bigg{(}\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)$
	$\displaystyle\quad\quad\quad\quad\quad\cdot\text{Pr}(\mathbf{X}(\tilde{K})\in\mathbb{Y}\mid K=\kappa)\Bigg{)}.$

Dividing both the sides of this equation by $\text{Pr}\left(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-})\mid\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$ gives

	$\displaystyle\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),\{1_{(a,b)}(\tau):0\leq\tau\leq t\},(a,b)\notin E(t)\right)$
	$\displaystyle=\sum_{\mathbb{Y}}\Bigg{(}\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid\mathbf{X}(\tilde{K})\in\mathbb{Y},K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right)$
	$\displaystyle\quad\quad\quad\quad\cdot\text{Pr}(\mathbf{X}(\tilde{K})\in\mathbb{Y}\mid K=\kappa)\Bigg{)}$
	$\displaystyle=\text{Pr}\left((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}),(a,b)\notin E(t)\right),$

where the last step holds because the summation is independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ given that $(a,b)\notin E(t)$ . We have thus shown the following: given $K=\kappa,b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a$ , and $b\in\mathcal{I}(t^{-})$ , the event $\{(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\}$ is conditionally independent of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ . Since $T$ and $T_{\text{on}}$ are functions of $\{1_{(a,b)}(\tau):0\leq\tau\leq t\}$ , the assertion of the lemma follows.

Proof of Proposition 2

Before we prove Proposition 2, we recall that for any transition sequence $F=\{\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\mathbf{x}^{(1)}\stackrel{{\scriptstyle t_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}^{(r)}\stackrel{{\scriptstyle t}}{{\rightarrow}}\mathbf{x}^{(r)}\}$ on a time interval $[0,t]$ , the index $\Lambda_{(a,b)}(F)$ indexes the transition in which $(a.b)$ is updated for the last time during $[0,t]$ given that $F$ occurs. We now define another similar index below:

\Gamma{(a,b)}(F)=\begin{cases}\min\left\{\ell\in[r]:\mathbf{x}^{(\ell)}=\mathbf{x}^{(\ell-1)}_{\uparrow b}\right\}\quad&\text{if }\left\{\ell\in[r]:\mathbf{x}^{(\ell)}=\mathbf{x}^{(\ell-1)}_{\uparrow b}\right\}\neq\emptyset\\ 0\quad&\text{otherwise.}\end{cases}

Observe that $\Gamma_{b}(F)$ indexes the transition in which $b$ gets infected given that $F$ occurs.

Proof.

Consider any realization $(\mathcal{S}_{0},\mathcal{I}_{0})$ of $(\mathcal{S}(t),\mathcal{I}(t))$ , and let $\mathcal{F}$ be the set of all the transition sequences for $[0,t]$ that result in the occurrence of $\{(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\}$ , so that $\{(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\}=\cup_{F\in\mathcal{F}}F$ .

Consider now any pair of nodes $(a,b)\in\mathcal{A}_{i}\cap\mathcal{S}_{0}\times\mathcal{A}_{j}\cap\mathcal{I}_{0}$ (so that we have $a\in\mathcal{S}_{i}(t)$ and $b\in\mathcal{I}_{j}(t)$ in the event that $(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})$ ), and note that for any transition sequence $F\in\mathcal{F}$ , we have $F_{(\overline{a,b})}\in\mathcal{F}$ , because both $F_{(\overline{a,b})}$ and $F$ involve the same node recoveries and disease transmissions (all of which occur along edges other than $(a,b)$ ). Therefore, $F_{?(a,b)}\subset\mathcal{F}$ for each $F\in\mathcal{F}$ , and it follows that $\{(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\}=\cup_{F\in\mathcal{F}}F_{?(a,b)}$ .

Hence, we can derive bounds on $\chi_{ij}(t)$ (defined to be $\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))$ ) by bounding $\text{Pr}((a,b)\in E(t)\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}))=\text{Pr}((a,b)\in E(t)\mid\cup_{F\in\mathcal{F}}F_{?(a,b)})$ . To this end, we pick $F\in\mathcal{F}$ and $\delta>0$ , and apply Bayes’ rule to $\text{Pr}((a,b)\in E(t)\mid F_{?(a,b)}^{\delta})$ as follows:

$\displaystyle\text{Pr}((a,b)\in E(t)\mid F_{?(a,b)}^{\delta})$	$\displaystyle=\left(\frac{\text{Pr}(F_{?(a,b)}^{\delta})}{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\in E(t))\cdot\text{Pr}((a,b)\in E(t))}\right)^{-1}$	(131)
	$\displaystyle=\left(1+\frac{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\notin E(t))}{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\in E(t))}\cdot\frac{\text{Pr}((a,b)\notin E(t))}{\text{Pr}((a,b)\in E(t))}\right)^{-1}$	(132)
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\left(1+\frac{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\notin E(t))}{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\in E(t))}\cdot\frac{1-\rho_{ij}/n}{\rho_{ij}/n}\right)^{-1},$	(133)

where $(a)$ holds because $\text{Pr}((a,b)\in E(t))=\frac{\rho_{ij}}{n}$ , which is the probability that the edge $(a,b)$ exists in the network after the last of the updates of $1_{(a,b)}$ to occur during $[0,t]$ .

We now estimate $\frac{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\notin E(t))}{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\in E(t))}$ . Note that if $\delta$ is small enough, either $F^{\delta}\subset\{(a,b)\in E(t)\}$ or $F^{\delta}\subset\{(a,b)\notin E(t)\}$ . Assume w.l.o.g. that $F^{\delta}\subset\{(a,b)\notin E(t)\}$ (equivalently, $F^{\delta}_{(\overline{a,b})}\subset\{(a,b)\in E(t)\}$ ), and observe that

	$\displaystyle\frac{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\notin E(t))}{\text{Pr}(F_{?(a,b)}^{\delta}\mid(a,b)\in E(t))}$	$\displaystyle=\frac{\text{Pr}(F_{?(a,b)}^{\delta}\cap\{(a,b)\notin E(t)\})}{\text{Pr}(F_{?(a,b)}^{\delta}\cap\{(a,b)\in E(t)\})}\cdot\frac{\text{Pr}(a,b)\in E(t)}{\text{Pr}(a,b)\notin E(t)}$		(134)
		$\displaystyle=\frac{\text{Pr}(F^{\delta})}{\text{Pr}(F^{\delta}_{(\overline{a,b})})}\left(\frac{\rho_{ij}/{n}}{1-\rho_{ij}/{n}}\right).$		(135)

Thus, the next step is to evaluate $\frac{\text{Pr}(F^{\delta})}{\text{Pr}(F_{(\overline{a,b})}^{\delta})}$ . To do so, suppose $F=\{\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\mathbf{x}^{(1)}\stackrel{{\scriptstyle t_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}^{(r)}\stackrel{{\scriptstyle t_{r+1}}}{{\rightarrow}}x^{(r)}\}$ with $t_{r+1}:=t$ , $\Lambda_{(a,b)}(F)=\zeta\in\{0,1,\ldots,r\}$ , $\Gamma_{b}(F)=\xi\in\{0,1,\ldots,r\}$ , $t_{\Lambda_{(a,b)}(F)}=t_{\zeta}=t-\tau$ for some $\tau\in[0,t]$ , and $t_{\Gamma_{b}(F)}=t_{\xi}=t-\kappa$ for some $\kappa\in[0,\tau]$ . Then the assumption $F^{\delta}\subset\{(a,b)\notin E(t)\}$ implies that $\mathbf{x}^{(\zeta)}=\mathbf{x}^{(\zeta-1)}_{\downarrow(a,b)}$ and hence also that $\mathbf{x}^{(\zeta)}_{(\overline{a,b})}=\mathbf{x}^{(\zeta-1)}_{\uparrow(a,b)}$ . As a result,

\displaystyle F_{(\overline{a,b})}

\displaystyle=\Big{\{}\mathbf{x}^{(0)}\stackrel{{\scriptstyle t_{1}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{\zeta-1}}}{{\rightarrow}}\mathbf{x}^{(\zeta-1)}\stackrel{{\scriptstyle t-\tau}}{{\rightarrow}}\mathbf{x}_{\uparrow(a,b)}^{(\zeta-1)}\stackrel{{\scriptstyle t_{\zeta+1}}}{{\rightarrow}}\mathbf{x}_{(\overline{a,b})}^{(\zeta+1)}\stackrel{{\scriptstyle t_{\zeta+2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle t_{r}}}{{\rightarrow}}\mathbf{x}_{(\overline{a,b})}^{(r)}\stackrel{{\scriptstyle t}}{{\rightarrow}}\mathbf{x}_{(\overline{a,b})}^{(r)}\Big{\}}.

It now follows from Lemma 3 that

\displaystyle\frac{\text{Pr}(F^{\delta})}{\text{Pr}(F^{\delta}_{(\overline{a,b})})}=\frac{e^{-q_{r}(t-t_{r})}\prod_{\ell=\zeta}^{r}q_{\ell-1,\ell}(e^{-q_{\ell-1}(t_{\ell}-t_{\ell-1})}\delta+o(\delta))}{e^{-\bar{q}_{r}(t-t_{r})}\prod_{\ell=\zeta}^{r}\bar{q}_{\ell-1,\ell}(e^{-\bar{q}_{\ell-1}(t_{\ell}-t_{\ell-1})}\delta+o(\delta))},

(136)

where $q_{\ell-1,\ell}:=\mathbf{Q}(\mathbf{x}^{(\ell-1)},\mathbf{x}^{(\ell)})$ and $\bar{q}_{\ell-1,\ell}:=\mathbf{Q}(\mathbf{x}^{(\ell-1)}_{(\overline{a,b})},\mathbf{x}^{(\ell)}_{(\overline{a,b})})$ for all $\ell\in\{\zeta+1,\ldots,r\}$ , $q_{\ell}:=-\mathbf{Q}(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell)})$ and $\bar{q}_{\ell}:=-\mathbf{Q}(\mathbf{x}^{(\ell)}_{(\overline{a,b})},\mathbf{x}^{(\ell)}_{(\overline{a,b})})$ for all $\ell\in\{\zeta,\ldots,r\}$ , $q_{\zeta-1,\zeta}:=\mathbf{Q}(\mathbf{x}^{(\zeta-1)},\mathbf{x}^{(\zeta-1)}_{\downarrow(a,b)})=\lambda\left(1-\frac{\rho_{ij}}{n}\right)$ , $\bar{q}_{\zeta-1,\zeta}:=\mathbf{Q}(\mathbf{x}^{(\zeta-1)},\mathbf{x}^{(\zeta-1)}_{\uparrow(a,b)})=\lambda\frac{\rho_{ij}}{n}$ , and $\bar{q}_{\zeta-1}=q_{\zeta-1}:=-\mathbf{Q}(\mathbf{x}^{(\zeta-1)},\mathbf{x}^{(\zeta-1)})$ .

The above definitions imply that $\frac{q_{\zeta-1,\zeta}}{\bar{q}_{\zeta-1,\zeta}}=\frac{1-\rho_{ij}/n}{\rho_{ij}/n}$ . To evaluate $\frac{q_{\ell-1,\ell}}{\bar{q}_{\ell-1,\ell}}$ for $\ell\in\{\zeta+1,\ldots,r\}$ , observe that by the definition of $\Lambda_{(a,b)}(F)$ , we have $\mathbf{x}^{(\ell)}\notin\{\mathbf{x}^{(\ell-1)}_{\uparrow(a,b)},\mathbf{x}^{(\ell-1)}_{\downarrow(a,b)}\}$ for $\ell>\zeta=\Lambda_{(a,b)}(F)$ . Moreover, the facts $F\subset\{\mathcal{S}(t)=\mathcal{S}_{0}\}$ and $a\in\mathcal{S}_{0}$ together imply that $\mathbf{x}^{(\ell)}\neq\mathbf{x}^{(\ell-1)}_{\uparrow a}$ for all $\ell\in[r]$ . Hence, $\mathbf{x}^{(\ell)}\notin\{\mathbf{x}^{(\ell-1)}_{\uparrow(a,b)},\mathbf{x}^{(\ell-1)}_{\downarrow(a,b)},\mathbf{x}^{(\ell-1)}_{\uparrow a}\}$ for all $\ell>\zeta$ . It now follows from the definition of $\mathbf{Q}$ (Section 2) that $\mathbf{Q}(\mathbf{x}^{(\ell-1)},\mathbf{x}^{(\ell)})=\mathbf{Q}(\mathbf{x}^{(\ell-1)}_{(\overline{a,b})},\mathbf{x}^{(\ell)}_{(\overline{a,b})})$ for all $\ell\in\{\zeta+1,\ldots,r\}$ . Thus, $\frac{\prod_{\ell=\zeta}^{r}q_{\ell-1,\ell}}{\prod_{\ell=\zeta}^{r}\bar{q}_{\ell-1,\ell}}=\frac{1-\rho_{ij}/n}{\rho_{ij}/n}$ .

To relate $\bar{q}_{\ell}$ to $q_{\ell}$ , note that $F\subset\{(a,b)\notin E(t)\}$ implies that $\mathbf{x}^{(\ell)}_{\langle a,b\rangle}=0$ and hence also that $\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)_{\langle a,b\rangle}=1$ for $\ell\geq\zeta$ . Since $\mathbf{x}^{(\ell)}_{u}=\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)_{u}$ for all $u\neq\langle a,b\rangle$ , we have

	$\displaystyle\mathbf{Q}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})},\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)_{\uparrow a}\right)$	$\displaystyle=\sum_{k=1}^{m}B_{ik}E_{k}^{(a)}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)$
		$\displaystyle=\sum_{k=1}^{m}\sum_{c\in\mathcal{I}_{k}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)}B_{ik}1_{(a,c)}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)$
		$\displaystyle=\sum_{k=1}^{m}\sum_{c\in\mathcal{I}_{k}\left(\mathbf{x}^{(\ell)}\right)}B_{ik}1_{(a,c)}\left(\mathbf{x}^{(\ell)}\right)+B_{ij}1_{(a,b)}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)$
		$\displaystyle=\mathbf{Q}\left(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell)}_{\uparrow a}\right)+B_{ij}$

for all $\ell\in\{\zeta,\;\ldots,r\}$ such that $b\in\mathcal{I}_{j}(\mathbf{x}^{(\ell)})$ , and

\displaystyle\mathbf{Q}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})},\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)_{\uparrow a}\right)=\mathbf{Q}\left(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell)}_{\uparrow a}\right)

for all $\ell\in\{\zeta,\ldots,r\}$ such that $b\notin\mathcal{I}_{j}(\mathbf{x}^{(\ell)})$ . As a result,

\displaystyle\mathbf{Q}\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})},\left(\mathbf{x}^{(\ell)}_{(\overline{a,b})}\right)_{\uparrow a}\right)=\begin{cases}\mathbf{Q}\left(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell)}_{\uparrow a}\right)\quad&\text{if }\zeta\leq\ell<\xi\\ \mathbf{Q}\left(\mathbf{x}^{(\ell)},\mathbf{x}^{(\ell)}_{\uparrow a}\right)+B_{ij}\quad&\text{if }\max\{\zeta,\xi\}\leq\ell\leq r.\end{cases}

(137)

Moreover, using the definition of $\mathbf{Q}$ one can easily verify that regardless of whether the network is in state $\mathbf{x}^{(\ell)}$ or in state $\mathbf{x}^{(\ell)}_{(\overline{a,b})}$ , the rates of infection of nodes in $\mathcal{S}(\mathbf{x}^{(\ell)})\setminus\{a\}$ , the recovery rates of nodes in $\mathcal{I}(x^{(\ell)})$ , and the edge update rate (which is $\lambda$ ) are the same. Given that $\mathbf{Q}(\mathbf{x},\mathbf{x})=-\sum_{\mathbf{y}\in\mathbb{S}\setminus\{\mathbf{x}\}}\mathbf{Q}(\mathbf{x},\mathbf{y})$ for all $\mathbf{x}\in\mathbb{S}$ , it now follows from (137) that

\displaystyle\bar{q}_{\ell}-q_{\ell}=\begin{cases}0\quad&\text{if }\zeta\leq\ell<\xi\\ B_{ij}\quad&\text{if }\max\{\zeta,\xi\}\leq\ell\leq r.\end{cases}

(138)

Combining the above observations with (136) yields

	$\displaystyle\frac{\text{Pr}(F^{\delta})}{\text{Pr}(F^{\delta}_{(\overline{a,b})})}$	$\displaystyle=\left(\frac{1-{\rho_{ij}}/{n}}{{\rho_{ij}}/{n}}\right)e^{(\bar{q}_{r}-q_{r})(t-t_{r})}\prod_{\ell=\zeta-1}^{r-1}\left(e^{(\bar{q}_{\ell}-q_{\ell})(t_{\ell+1}-t_{\ell})}\delta+o(\delta)\right)$
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\left(\frac{1-{\rho_{ij}}/{n}}{{\rho_{ij}}/{n}}\right)\prod_{\ell=\zeta-1}^{r}\left(e^{(\bar{q}_{\ell}-q_{\ell})(t_{\ell+1}-t_{\ell})}\delta+o(\delta)\right)$
		$\displaystyle=\left(\frac{1-{\rho_{ij}}/{n}}{{\rho_{ij}}/{n}}\right)\prod_{\ell=\zeta-1}^{\max\{\zeta,\xi\}-1}(1+o(\delta))\prod_{\ell=\max\{\zeta,\xi\}}^{r}\left(e^{B_{ij}(t_{\ell+1}-t_{\ell})}\delta+o(\delta)\right)$
		$\displaystyle=\left(\frac{1-{\rho_{ij}}/{n}}{{\rho_{ij}}/{n}}\right)e^{B_{ij}\left(t-t_{\max\{\zeta,\xi\}}\right)}+o(\delta),$

which means that

\displaystyle\frac{\text{Pr}(F^{\delta})}{\text{Pr}(F^{\delta}_{(\overline{a,b})})}=\left(\frac{1-{\rho_{ij}}/{n}}{{\rho_{ij}}/{n}}\right)e^{B_{ij}\min\{\tau,\kappa\}}+o(\delta).

(139)

We now use (131) and (134) along with (139) to show that

	$\displaystyle\text{Pr}((a,b)\in E(t)\mid F^{\delta}_{?(a,b)})$	$\displaystyle=\left(1+\left(\frac{1-\rho_{ij}/n}{\rho_{ij}/n}\right)e^{B_{ij}\min\{\tau,\kappa\}}+o(\delta)\right)^{-1}$
		$\displaystyle=\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\min\{\tau,\kappa\}}}+o(\delta).$

In the limit as $\delta\rightarrow 0$ , this yields

\displaystyle\text{Pr}((a,b)\in E(t)\mid F_{?(a,b)})

\displaystyle=\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\min\{\tau,\kappa\}}}

(140)

Note that these bounds hold for all $F\in\mathcal{F}$ satisfying $t-t_{\Lambda_{(a,b)}(F)}=\tau$ and $t-t_{\Gamma_{b}(F)}=\kappa$ . We now recall that $T$ is the difference between $t$ and the time at which $1_{(a,b)}$ is updated for the last time during $[0,t]$ , so that we have $T=t-t_{\Lambda_{(a,b)}(F)}$ whenever $F_{?(a,b)}$ occurs. Likewise, $K=t-t_{\Gamma_{b}(F)}$ on $F_{?(a,b)}$ . Therefore, (140) holds for all $F\in\mathcal{F}$ satisfying $F\subset\{T=\tau\}\cap\{K=\kappa\}$ . As a result, we have

\text{Pr}((a,b)\in E(t)\mid\cup_{F\in\mathcal{F}}F_{?(a,b)},T=\tau,K=\kappa)=\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\min\{\tau,\kappa\}}}.

Since $\cup_{F\in\mathcal{F}}F_{?(a,b)}=\{(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\}$ as argued earlier, it follows that

\displaystyle\text{Pr}((a,b)\in E(t)\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),T=\tau,K=\kappa)=\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\min\{\tau,\kappa\}}}.

(141)

Observe that $0\leq\min\{\kappa,\tau\}\leq\tau$ , which means that

$\displaystyle\frac{\rho_{ij}}{n}$	$\displaystyle\geq\text{Pr}((a,b)\in E(t)\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),T=\tau,K=\kappa)$	(142)
	$\displaystyle\geq\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\tau}}$	(143)
	$\displaystyle\geq\frac{\rho_{ij}}{n}e^{-B_{ij}\tau}.$	(144)

Furthermore, since the above bounds do not depend on $\kappa$ , we can remove the conditioning on $K$ to obtain

\displaystyle\frac{\rho_{ij}}{n}

\displaystyle\geq\text{Pr}((a,b)\in E(t)\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),T=\tau)\geq\frac{\rho_{ij}}{n}e^{-B_{ij}\tau}.

(145)

Consequently,

	$\displaystyle\frac{\rho_{ij}}{n}$	$\displaystyle\geq\text{Pr}((a,b)\in E(t)\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}))$
		$\displaystyle\geq\frac{\rho_{ij}}{n}\int_{0}^{t}e^{-B_{ij}\tau}f_{T\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})}(\tau)d\tau$
		$\displaystyle\geq\frac{\rho_{ij}}{n}\left(1-\frac{B_{ij}}{\lambda}(1-e^{-\lambda t})\right),$

where the second inequality follows from Lemmas 11 and 12. Since $(\mathcal{S}_{0},\mathcal{I}_{0})$ is an arbitrary realization of $(\mathcal{S}(t),\mathcal{I}(t))$ , the assertion of the proposition follows.

Remark 4.

The proof of Proposition 2 enables us to make a stronger statement about the conditional probability of $b$ being in contact with $a$ at time $t$ . Indeed, consider (141) and observe that it holds for all realizations $(\mathcal{S}_{0},\mathcal{I}_{0})$ of $(\mathcal{S}(t),\mathcal{I}(t))$ that satisfy $a\in\mathcal{S}_{0}\cap\mathcal{A}_{i}$ and $b\in\mathcal{I}_{0}\cap\mathcal{A}_{j}$ . It follows that

\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t),T=\tau,K=\kappa)=\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\min\{\tau,\kappa\}}}

holds for all node pairs $(a,b)\in\mathcal{S}_{i}(t)\times\mathcal{I}_{j}(t)$ . Equivalently, the following holds for all $(a,b)\in\mathcal{S}_{i}(t)\times\mathcal{I}_{j}(t)$ :

\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t),T,K)=\frac{\rho_{ij}}{n}\cdot\frac{1}{\frac{\rho_{ij}}{n}\cdot 1+\left(1-\frac{\rho_{ij}}{n}\right)e^{B_{ij}\min\{T,K\}}}.

Lemma 10.

Let $\tau_{1},\tau_{2}\in[0,t]$ . Then

1\leq\frac{\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}}{\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}}\leq e^{B_{ij}(\tau_{2}-\tau_{1})}.

Proof.

Consider $T_{\text{on}}^{(\tau_{2})}:=\left(\int_{t-\kappa}^{t-\tau_{2}}1_{(a,b)}(\tau^{\prime})d\tau^{\prime}\right)_{+}$ , which denotes the duration of time for which $b$ is in contact with $a$ during the interval $[t-\kappa,t-\tau_{2})$ . Then, for any $\sigma\in[0,(\kappa-\tau_{2})_{+}]$ , we have

		$\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(146)
		$\displaystyle=\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{1}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(147)
		$\displaystyle=\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(148)
		$\displaystyle\quad\times\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\tau_{2},\tau_{2}-\tau_{1}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(149)
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}e^{-B_{ij}(\tau_{2}-\tau_{1})}$		(150)
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}e^{-B_{ij}\sigma}\cdot e^{-B_{ij}(\tau_{2}-\tau_{1})}$		(151)
		$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}e^{-B_{ij}(\tau_{2}-\tau_{1})}$		(152)
		$\displaystyle=\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}e^{-B_{ij}(\tau_{2}-\tau_{1})},$		(153)

where (a) follows from the fact that $\int_{t-\tau_{2}}^{t-\tau_{1}}1_{(a,b)}(\tau^{\prime})d\tau^{\prime}\leq\tau_{2}-\tau_{1}$ and from the observation that

	$\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\tau_{2},\tau_{2}-\tau_{1}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t),\int_{t-\tau_{2}}^{t-\tau_{1}}1_{(a,b)}(\tau^{\prime})d\tau^{\prime}\bigg{)}$
	$\displaystyle=e^{-B_{ij}\left(\int_{t-\tau_{2}}^{t-\tau_{1}}1_{(a,b)}(\tau^{\prime})d\tau^{\prime}\right)},$

the proof of which parallels the proof of Lemma 7, and $(b)$ and $(c)$ follow from the fact that

\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau^{\prime},(a,b)\notin E(t)\bigg{)}=e^{-B_{ij}\sigma}

holds for all $\tau^{\prime}\in[0,t]$ , the proof of which also parallels the proof of Lemma 7.

We now eliminate $T_{\text{on}}^{(\tau_{2})}$ from (146). To do so, we first note the following: given that $t-T\geq t-\tau_{2}$ , the random variable $T_{\text{on}}^{(\tau_{2})}$ is by definition conditionally independent of $t-T$ (the time of the last edge update of $(a,b)$ during $[t-\tau_{2},t]$ ) because the edge update process for $(a,b)$ is a Poisson process and hence, for any collection of disjoint time intervals, the times at which $1_{(a,b)}$ is updated during the intervals are independent of each other. Since $\{T=\tau_{2}\},\{T=\tau_{1}\}\subset\{t-T\geq t-\tau_{2}\}$ and since $\{t-T\geq t-\tau_{2}\}=\{T\leq\tau_{2}\}$ , it follows that

		$\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(154)
		$\displaystyle=\int_{0}^{(\kappa-\tau_{2})_{+}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(155)
		$\displaystyle\quad\quad\quad\quad\quad\quad\cdot f_{T_{\text{on}}^{(\tau_{2})}\mid b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)}(\sigma)d\sigma$		(156)
		$\displaystyle=\int_{0}^{(\kappa-\tau_{2})_{+}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$		(157)
		$\displaystyle\quad\quad\quad\quad\quad\quad\cdot f_{T_{\text{on}}^{(\tau_{2})}\mid b\in\mathcal{I}(t^{-}),K=\kappa,T\leq\tau_{2},(a,b)\notin E(t)}(\sigma)d\sigma,$		(158)

and likewise,

		$\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}$
		$\displaystyle=\int_{0}^{(\kappa-\tau_{2})_{+}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}$
		$\displaystyle\quad\quad\quad\quad\quad\quad\cdot f_{T_{\text{on}}^{(\tau_{2})}\mid b\in\mathcal{I}(t^{-}),K=\kappa,T\leq\tau_{2},(a,b)\notin E(t)}(\sigma)d\sigma.$

Therefore, taking conditional expectations on both sides of (146) (w.r.t. the PDF $f_{T_{\text{on}}^{(\tau_{2})}\mid b\in\mathcal{I}(t^{-}),K=\kappa,T\leq\tau_{2},(a,b)\notin E(t)}$ ) yields

	$\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$
	$\displaystyle\geq\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}e^{-B_{ij}(\tau_{2}-\tau_{1})},$

which proves the upper bound. For the lower bound, we again proceed as in (146), but reverse the inequality signs:

	$\displaystyle\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$
	$\displaystyle=\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$
	$\displaystyle\quad\times\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\tau_{2},\tau_{2}-\tau_{1}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$
	$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}$
	$\displaystyle\stackrel{{\scriptstyle}}{{=}}e^{-B_{ij}\sigma}$
	$\displaystyle\stackrel{{\scriptstyle}}{{=}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle t-\kappa,\kappa-\tau_{2}}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}$
	$\displaystyle=\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}^{(\tau_{2})}=\sigma,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}$

In light of (154) and (Proof.), the above inequality implies the required lower bound.

Lemma 11.

Let $T$ denote the random time defined earlier. Then

\displaystyle\int_{0}^{t}e^{-B_{ij}\tau}f_{T\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t)}(\tau)d\tau\geq 1-\frac{B_{ij}}{\lambda}(1-e^{-\lambda t}).

Proof.

We first use Bayes’ rule to note that for any $\kappa\in[0,t]$ ,

		$\displaystyle f_{T\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t)}(\tau)$		(159)
		$\displaystyle=\text{Pr}((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid T=\tau,K=\kappa,(a,b)\notin E(t))\cdot f_{K\mid T=\tau,(a,b)\notin E(t)}(\kappa)\cdot f_{T\mid(a,b)\notin E(t)}(\tau)$		(160)
		$\displaystyle\quad\cdot\bigg{(}\int_{0}^{t}\text{Pr}((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid T=\tau^{\prime},K=\kappa,(a,b)\notin E(t))\cdot f_{K\mid T=\tau^{\prime},(a,b)\notin E(t)}(\kappa)\cdot f_{T\mid(a,b)\notin E(t)}(\tau^{\prime})d\tau^{\prime}\bigg{)}^{-1}.$

We consider each multiplicand one by one. First, we use Lemmas 2 and 5 to note that $f_{K\mid T=\tau,(a,b)\notin E(t)}(\kappa)\cdot f_{T\mid(a,b)\notin E(t)}(\tau)=f_{K}(\kappa)f_{T}(\tau)$ . To deal effectively with the other multiplicands, we let $T_{\text{on}}:=\left(\int_{t-K}^{t-T}1_{(a,b)}(\tau^{\prime})d\tau^{\prime}\right)_{+}$ denote the total duration of time for which $b$ is in contact with $a$ during the time interval $[t-K,t-T]$ , and we observe that

	$\displaystyle\text{Pr}((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid T=\tau,K=\kappa,(a,b)\notin E(t))$
	$\displaystyle=\int_{0}^{(\kappa-\tau)_{+}}\Big{(}\text{Pr}((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid T=\tau,K=\kappa,T_{\text{on}}=\tau_{\text{on}},(a,b)\notin E(t))$
	$\displaystyle\quad\quad\quad\quad\quad\quad\cdot f_{T_{\text{on}}\mid K=\kappa,T=\tau,(a,b)\notin E(t)}(\tau_{\text{on}})\Big{)}d\tau_{\text{on}}$
	$\displaystyle=\int_{0}^{(\kappa-\tau)_{+}}\Big{(}\text{Pr}((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid T=\tau,K=\kappa,T_{\text{on}}=\tau_{\text{on}},(a,b)\notin E(t),b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}))$
	$\displaystyle\quad\quad\quad\quad\quad\quad\cdot\text{Pr}(b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\mid b\in\mathcal{I}(t^{-}),T=\tau,K=\kappa,T_{\text{on}}=\tau_{\text{on}},(a,b)\notin E(t))$
	$\displaystyle\quad\quad\quad\quad\quad\quad\cdot\text{Pr}(b\in\mathcal{I}(t^{-})\mid T=\tau,K=\kappa,T_{\text{on}}=\tau_{\text{on}},(a,b)\notin E(t))$
	$\displaystyle\quad\quad\quad\quad\quad\quad\cdot f_{T_{\text{on}}\mid K=\kappa,T=\tau,(a,b)\notin E(t)}(\tau_{\text{on}})\Big{)}d\tau_{\text{on}}$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\int_{0}^{(\kappa-\tau)_{+}}\Big{(}\text{Pr}((\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0})\mid K=\kappa,(a,b)\notin E(t),b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a,b\in\mathcal{I}(t^{-}))$
	$\displaystyle\quad\quad\quad\quad\quad\quad\cdot e^{-B_{ij}\tau_{\text{on}}}\cdot e^{-\gamma_{j}\kappa}\cdot f_{T_{\text{on}}\mid K=\kappa,T=\tau,(a,b)\notin E(t)}(\tau_{\text{on}})\Big{)}d\tau_{\text{on}},$

where $(a)$ follows from Lemmas 7 and 9 and from the modelling assumption that $b$ recovers at rate $\gamma_{j}$ independently of any edge state. On substituting the above expression into (159), we obtain

\displaystyle f_{T\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t)}(\tau)=\frac{\left(\int_{0}^{(\kappa-\tau)_{+}}e^{-B_{ij}\tau_{\text{on}}}\psi_{\kappa,\tau}(\tau_{\text{on}})d\tau_{\text{on}}\right)f_{T}(\tau)}{\int_{0}^{t}\left(\int_{0}^{(\kappa-\tau^{\prime})_{+}}e^{-B_{ij}\tau_{\text{on}}}\psi_{\kappa,\tau^{\prime}}(\tau_{\text{on}})d\tau_{\text{on}}\right)f_{T}(\tau^{\prime})d\tau^{\prime}},

(162)

where $\psi_{\kappa,\tau}(\cdot):=f_{T_{\text{on}}\mid K=\kappa,T=\tau,(a,b)\notin E(t)}(\cdot)$ . Now, Lemma 7 implies that

	$\displaystyle\int_{0}^{(\kappa-\tau)_{+}}e^{-B_{ij}\tau_{\text{on}}}\psi_{\kappa,\tau}(\tau_{\text{on}})d\tau_{\text{on}}$
	$\displaystyle=\int_{0}^{(\kappa-\tau)_{+}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}=\tau_{\text{on}},b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau,(a,b)\notin E(t)\bigg{)}\cdot f_{T_{\text{on}}\mid K=\kappa,T=\tau,(a,b)\notin E(t)}(\tau_{\text{on}})d\tau_{\text{on}}$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\int_{0}^{(\kappa-\tau)_{+}}\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,T_{\text{on}}=\tau_{\text{on}},b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau,(a,b)\notin E(t)\bigg{)}$
	$\displaystyle\quad\quad\quad\quad\quad\,\,\cdot f_{T_{\text{on}}\mid b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau,(a,b)\notin E(t)}(\tau_{\text{on}})d\tau_{\text{on}}$
	$\displaystyle=\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau,(a,b)\notin E(t)\bigg{)},$

where $(a)$ holds because the recovery time of $b$ is conditionally independent of $T_{\text{on}}$ given $K=\kappa$ (recall that $b$ recovers at rate $\gamma_{j}$ independently of any edge state (and hence independently of $T_{\text{on}}$ ), and $\{b\in\mathcal{I}(t^{-})\}$ is precisely the event that the recovery time of $b$ is at least $K$ ). Hence, (162) implies that for any $\tau_{1},\tau_{2}\in[0,t]$ satisfying $\tau_{1}\leq\tau_{2}$ , we have

\displaystyle\frac{g(\tau_{2})}{g(\tau_{1})}=\frac{\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{2},(a,b)\notin E(t)\bigg{)}}{\text{Pr}\bigg{(}b\stackrel{{\scriptstyle 0,t}}{{\centernot\rightsquigarrow}}a\,\Big{\lvert}\,b\in\mathcal{I}(t^{-}),K=\kappa,T=\tau_{1},(a,b)\notin E(t)\bigg{)}}\cdot\frac{f_{T}(\tau_{2})}{f_{T}(\tau_{1})},

(163)

where $g(\cdot):=f_{T\mid K=\kappa(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t)}(\cdot)$ .

As a consequence of (163) and Lemma 10, we have

\displaystyle\frac{g(\tau_{2})}{g(\tau_{1})}\leq e^{B_{ij}(\tau_{2}-\tau_{1})}\frac{f_{T}(\tau_{2})}{f_{T}(\tau_{1})}.

Since $f_{T}(\tau)=\lambda e^{-\lambda\tau}+e^{-\lambda t}\delta(\tau-t)$ for $\tau\in[0,t]$ (see Lemma 4), we have the following for all $0\leq\tau_{1}\leq\tau_{2}<t$ :

\displaystyle g(\tau_{2})\leq e^{-(\lambda-B_{ij})(\tau_{2}-\tau_{1})}g(\tau_{1}),

(164)

and for all $0\leq\tau<t$ , we have

\displaystyle\tilde{g}(t)\leq\frac{e^{-(\lambda-B_{ij})(t-\tau)}}{\lambda}g(\tau),

(165)

where $\tilde{g}(t)$ scales $\delta(0)$ so that $g(t)=\tilde{g}(t)\delta(0)$ . Since $\delta$ is the Dirac-delta function, (165) simply means that

\displaystyle\text{Pr}(T=t\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t))\leq\frac{e^{-(\lambda-B_{ij})(t-\tau)}}{\lambda}g(\tau).

Our next goal is to use (164) and (165) to show that

\displaystyle\int_{0}^{t}e^{-B_{ij}\tau}g(\tau)d\tau\geq\int_{0}^{t}e^{-B_{ij}\tau}\varphi(\tau)d\tau,

(166)

where $\varphi$ is the probability density function defined by $\varphi(\tau):=(\lambda-B_{ij})e^{-(\lambda-B_{ij})\tau}+e^{-(\lambda-B_{ij})t}\delta(\tau-t)$ for all $\tau\in[0,t]$ and $\varphi(\tau)=0$ for $\tau>t$ . To this end, we compare $g$ with $\varphi$ under the following two cases.

Case 1: There exists a time $\tau_{0}\in[0,t)$ such that $g(\tau_{0})<\varphi(\tau_{0})$ . In this case, (164) implies that for all $\tau\in[\tau_{0},t)$ ,

	$\displaystyle g(\tau)$	$\displaystyle\leq e^{-(\lambda-B_{ij})(\tau-\tau_{0})}g(\tau_{0})$
		$\displaystyle<e^{-(\lambda-B_{ij})(\tau-\tau_{0})}(\lambda-B_{ij})e^{-(\lambda-B_{ij})(\tau_{0})}$
		$\displaystyle=\varphi(\tau),$

which means that the set $\{\tau\in[0,t):g(\tau)<\varphi(\tau)\}$ is either $[\tau^{*},t)$ or $(\tau^{*},t)$ , where $\tau^{*}:=\inf\{\tau:g(\tau)<\varphi(\tau)\}$ . Also, by the definition of $\tau^{*}$ , we have $g(\tau)\geq\varphi(\tau)$ for all $\tau\in[0,\tau^{*})$ . Next, to compare $g$ and $\varphi$ at $\tau=t$ , we use (165) to note that

$\displaystyle g(t)$	$\displaystyle\leq\frac{e^{-(\lambda-B_{ij})(t-\tau_{0})}}{\lambda}g(\tau_{0})\delta(0)$	(167)
	$\displaystyle\leq\frac{e^{-(\lambda-B_{ij})(t-\tau_{0})}}{\lambda}(\lambda-B_{ij})e^{-(\lambda-B_{ij})\tau_{0}}\delta(0)$	(168)
	$\displaystyle=\left(1-\frac{B_{ij}}{\lambda}\right)e^{-(\lambda-B_{ij})t}\delta(0)$	(169)
	$\displaystyle\leq\varphi(t).$	(170)

Thus, $g(\tau)-\varphi(\tau)\geq 0$ for all $\tau\in[0,\tau^{*})$ and $g(\tau)-\varphi(\tau)\leq 0$ for all $\tau\in(\tau^{*},t]$ . Now, since $g$ and $\varphi$ are both PDFs, we must have $\int_{0}^{\infty}(g(\tau)-\varphi(\tau))d\tau=0$ or equivalently,

\int_{0}^{\tau^{*}}(g(\tau)-\varphi(\tau))d\tau=\int_{\tau^{*}}^{\infty}(\varphi(\tau)-g(\tau))d\tau.

Since both the integrands above are non-negative, we have

	$\displaystyle\int_{0}^{\tau^{*}}e^{-B_{ij}\tau}(g(\tau)-\varphi(\tau))d\tau$
	$\displaystyle\geq e^{-B_{ij}\tau^{}}\int_{0}^{\tau^{}}(g(\tau)-\varphi(\tau))d\tau$
	$\displaystyle=e^{-B_{ij}\tau^{}}\int_{\tau^{}}^{\infty}(\varphi(\tau)-g(\tau))d\tau$
	$\displaystyle\geq\int_{\tau^{*}}^{\infty}e^{-B_{ij}\tau}(\varphi(\tau)-g(\tau))d\tau.$

Adding $\int_{\tau^{*}}^{\infty}e^{-B_{ij}\tau}g(\tau)d\tau+\int_{0}^{\tau^{*}}e^{-B_{ij}\tau}\varphi(\tau)d\tau$ to both sides now yields (166).

Case 2: $g(\tau)\geq\varphi(\tau)$ for all $\tau\in[0,t)$ . In this case, we can simply set $\tau^{*}=t$ and repeat the arguments following (167) in Case 1 to show that (166) holds.

Next, we use the definition of $\varphi$ to evaluate $\int_{0}^{t}e^{-B_{ij}\tau}\varphi(\tau)d\tau$ , and we then restate (166) as follows:

\displaystyle\int_{0}^{t}e^{-B_{ij}\tau}f_{T\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t)}(\tau)d\tau\geq 1-\frac{B_{ij}}{\lambda}(1-e^{-\lambda t}).

(171)

Since this holds for all $\kappa\in[0,t)$ , the assertion of the lemma follows.

Using arguments very similar to the proof above, we can prove the following result.

Lemma 12.

Let $T$ denote the random time defined earlier. Then

\displaystyle\int_{0}^{t}e^{-B_{ij}\tau}f_{T\mid(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\in E(t)}(\tau)d\tau\geq 1-\frac{B_{ij}}{\lambda}(1-e^{-\lambda t}).

Remark 5.

In the proof of Lemma 11, if, instead of using (163) along with the upper bound in Lemma 10, we had used (163) along with the lower bound in Lemma 10, we would have obtained

\frac{g(\tau_{2})}{g(\tau_{1})}\geq\frac{f_{T}(\tau_{2})}{f_{T}(\tau_{1})}=e^{-\lambda(\tau_{2}-\tau_{1})}.

In addition, if we had subsequently replaced $t$ with a generic $\tau\in[0,t)$ and the weighting function $[0,\infty)\ni\tau\rightarrow e^{-B_{ij}\tau}\in(0,\infty)$ by the constant function $1$ , and if we had defined $\varphi$ by $\varphi(\tau):=\lambda e^{-\lambda\tau}+e^{-\lambda t}\delta(\tau-t)$ , then using the same arguments but with reversed inequality signs, we would have been able to prove that

\int_{0}^{\tau}1\cdot g(\tau^{\prime})d\tau^{\prime}\leq\int_{0}^{\tau}1\cdot\varphi(\tau^{\prime})d\tau^{\prime}.

Since the integral on the left-hand-side is $\text{Pr}(T\leq\tau\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t))$ and since the right-hand-side evaluates to $1-e^{-\lambda\tau}$ , we conclude that

\text{Pr}(T\leq\tau\mid K=\kappa,(\mathcal{S}(t),\mathcal{I}(t))=(\mathcal{S}_{0},\mathcal{I}_{0}),(a,b)\notin E(t))\leq 1-e^{-\lambda\tau}

for all $\tau\in[0,t)$ and all $\kappa\in[0,t]$ .

Some Auxiliary Lemmas

In addition to the above results, the proof of Theorem 1 relies on the following lemmas, which we reproduce from [30].

Lemma 13.

For random variables $Y$ and $Z$ , we have $\text{Var}[Y+Z]\leq 2(\text{Var}[Y]+\text{Var}[Z])$ .

Lemma 14.

For a random variable $Y\in[0,1]$ , we have $\text{Var}[Y^{2}]\leq 4\text{Var}[Y]$ .

Lemma 15.

For random variables $Y$ and $Z$ in $[0,1]$ ,

|\mathrm{E}[YZ]-\mathrm{E}[Y]\mathrm{E}[Z]|\leq(\operatorname{Var}[Y]+\operatorname{Var}[Z])/2

\left|\mathrm{E}\left[Y^{2}Z\right]-\mathrm{E}[Y]^{2}\mathrm{E}[Z]\right|\leq 2(\operatorname{Var}[Y]+\operatorname{Var}[Z]).

The following result is a straightforward consequence of the above lemmas.

Corollary 1.

For non-negative random variables $Y$ and $Z$ satisfying $0\leq Y+Z\leq 1$ , we have

\text{Var}[YZ]\leq 8(\text{Var}[Y]+\text{Var}[Z]).

Proof.

Note that

	$\displaystyle 4\text{Var}[YZ]=\text{Var}[2YZ]$	$\displaystyle=\text{Var}[(Y+Z)^{2}+(-1)(Y^{2}+Z^{2})]$
		$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2(\text{Var}[(Y+Z)^{2}]+(-1)^{2}\text{Var}[Y^{2}+Z^{2}])$
		$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2(4\text{Var}[Y+Z]+2(\text{Var}[Y^{2}]+\text{Var}[Z^{2}]))$
		$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2(4\text{Var}[Y+Z]+2(4\text{Var}[Y]+4\text{Var}[Z])),$

where (a) follows from Lemma 13, (b) from both Lemma 13 and Lemma 14, and (c) from Lemma 14 alone. Thus,

\text{Var}[YZ]\leq 2(\text{Var}[Y+Z]+2(\text{Var}[Y]+\text{Var}[Z]))\leq 8(\text{Var}[Y]+\text{Var}[Z]),

where the last inequality follows from Lemma 13.

Proof of Theorem 1

Proof.

The proof is based on Proposition 2 and it follows the approach used in [30]. We first modify Equations (i) - (iv) (Proposition 1) by expressing the expectations of cross-terms such as $\mathbb{E}[s_{i}\beta_{j}]$ in terms of expectations of individual terms such as $\mathbb{E}[s_{i}^{2}]$ and $\mathbb{E}[\beta_{j}]$ . To begin, we apply Lemma 15 to $\mathbb{E}[s_{i}(t)\beta_{j}(t)]$ and obtain

\displaystyle|\mathbb{E}[s_{i}(t)\beta_{j}(t)]-\mathbb{E}[s_{i}(t)]\mathbb{E}[\beta_{j}(t)]|\leq\frac{1}{2}(\text{Var}[s_{i}(t)]+\text{Var}[\beta_{j}(t)]).

Therefore, there exists a function $h_{i,j,1,n}:[0,\infty)\rightarrow[-1,1]$ such that

\displaystyle\mathbb{E}[s_{i}(t)\beta_{j}(t)]

\displaystyle=\mathbb{E}[s_{i}(t)]\mathbb{E}[\beta_{j}(t)]+\frac{h_{i,j,1,n}(t)}{2}(\text{Var}[s_{i}(t)]+\text{Var}[\beta_{j}(t)]).

Similarly, we can use Lemma 15 to show that there exists a function $h_{i,j,2,n}:[0,\infty)\rightarrow[-1,1]$ such that

\displaystyle\mathbb{E}[s_{i}^{2}(t)\beta_{j}(t)]

\displaystyle=\mathbb{E}[s_{i}(t)]^{2}\mathbb{E}[\beta_{j}(t)]+2h_{i,j,2,n}(t)(\text{Var}[s_{i}(t)]+\text{Var}[\beta_{j}(t)]).

Next, we use Corollary 1 to express $\mathbb{E}[s_{i}(t)\beta_{j}(t)\beta_{i}(t)]$ as

	$\displaystyle\mathbb{E}[s_{i}(t)\beta_{j}(t)\beta_{i}(t)]$	$\displaystyle=\mathbb{E}[s_{i}(t)\beta_{j}(t)]\mathbb{E}[\beta_{i}(t)]+\frac{h_{i,j,5,n}(t)}{2}(\text{Var}[s_{i}(t)\beta_{j}(t)]+\text{Var}[\beta_{i}(t)])$
		$\displaystyle=\Big{(}\mathbb{E}[s_{i}(t)]\mathbb{E}[\beta_{j}(t)]+\frac{h_{i,j,1,n}(t)}{2}(\text{Var}[s_{i}(t)]+\text{Var}[\beta_{j}(t)])\Big{)}\mathbb{E}[\beta_{i}(t)]$
		$\displaystyle\quad+\frac{h_{i,j,5,n}(t)}{2}(h_{i,j,6,n}(t)(8\text{Var}[s_{i}(t)]+8\text{Var}[\beta_{j}(t)])+\text{Var}[\beta_{i}(t)]),$

where $h_{i,j,5,n}(t)\in[-1,1]$ and $h_{i,j,6,n}(t)\in[0,1]$ .

We thus obtain the following relations:

(I)

$\mathbb{E}[s_{i}\beta_{j}]=\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]+\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])$ ,
(II)

$\mathbb{E}[s_{i}^{2}\beta_{j}]=\mathbb{E}[s_{i}]^{2}\mathbb{E}[\beta_{j}]+2h_{i,j,2,n}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])$ ,
(III)

$\mathbb{E}[s_{i}\beta_{j}\beta_{i}]=\Big{(}\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]+\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\Big{)}+\frac{h_{i,j,5,n}}{2}(h_{i,j,6,n}(8\text{Var}[s_{i}]+8\text{Var}[\beta_{j}])+\text{Var}[\beta_{i}]).$

To handle terms of the form $B_{ij}\mathbb{E}[n\cdot\chi_{ij}(t,\mathcal{S},\mathcal{I})\cdot U]$ where $U$ is some random variable, we use Proposition 2 to obtain

\displaystyle A_{ij}\left(1-\frac{B_{ij}}{\lambda^{(n)}}(1-e^{-\lambda^{(n)}t})\right)\mathbb{E}[U]\leq B_{ij}\mathbb{E}[n\chi_{ij}(t,\mathcal{S},\mathcal{I})U]\leq A_{ij}\mathbb{E}[U].

As a result, if $\text{Pr}(|U|\leq 1)=1$ , then there exists a function $h_{i,j,U,n}:[0,\infty)\rightarrow[0,B_{ij}A_{ij}]$ such that

\displaystyle B_{ij}\mathbb{E}[n\chi_{ij}(t,\mathcal{S},\mathcal{I})U]=A_{ij}\mathbb{E}[U]-\frac{h_{i,j,U,n}(t)}{\lambda^{(n)}}.

(172)

By making the above substitutions in (i) - (iv), and by using the identity $\text{Var}[Y]^{\prime}=\mathbb{E}[Y^{2}]^{\prime}-2\mathbb{E}[Y]\mathbb{E}[Y]^{\prime}$ , we obtain the following differential equations:

(I)

$\mathbb{E}[s_{i}]^{\prime}=\sum_{j=1}^{m}\frac{h_{i,j,7,n}}{\lambda^{(n)}}-\sum_{j=1}^{m}A_{ij}\left(\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]+\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\right)$ ,
(II)

$\mathbb{E}[\beta_{i}]^{\prime}=\sum_{j=1}^{m}A_{ij}\left(\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]+\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\right)-\sum_{j=1}^{m}\frac{h_{i,j,7,n}}{\lambda^{(n)}}-\gamma_{i}\mathbb{E}[\beta_{i}]$ ,

(III)

	$\displaystyle\text{Var}[s_{i}]^{\prime}$	$\displaystyle=-2\sum_{j=1}^{m}A_{ij}\big{(}\mathbb{E}[s_{i}]^{2}\mathbb{E}[\beta_{j}]+2h_{i,j,2,n}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\big{)}$
		$\displaystyle\quad+\sum_{j=1}^{m}A_{ij}\left(\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]+\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\right)\left(2\mathbb{E}[s_{i}]+\frac{1}{n}\right)$
		$\displaystyle\quad+\sum_{j=1}^{m}\left(\frac{2h_{i,j,8,n}}{\lambda^{(n)}}-\frac{h_{i,j,7,n}}{n\lambda^{(n)}}-2\mathbb{E}[s_{i}]\frac{h_{i,j,7,n}}{\lambda^{(n)}}\right),$

(IV)

	$\displaystyle\text{Var}[\beta_{i}]^{\prime}$	$\displaystyle=2\sum_{j=1}^{m}A_{ij}\bigg{(}\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]\mathbb{E}[\beta_{i}]+\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\mathbb{E}[\beta_{i}]$
		$\displaystyle\quad\quad\quad\quad\quad\quad+\frac{h_{i,j,5,n}}{2}\left(h_{i,j,6,n}(8\text{Var}[s_{i}]+8\text{Var}[\beta_{j}])+\text{Var}[\beta_{i}]\right)\bigg{)}$
		$\displaystyle\quad+\sum_{j=1}^{m}A_{ij}\left(\frac{1}{n}-2\mathbb{E}[\beta_{i}]\right)\Big{(}\mathbb{E}[s_{i}]\mathbb{E}[\beta_{j}]\frac{h_{i,j,1,n}}{2}(\text{Var}[s_{i}]+\text{Var}[\beta_{j}])\Big{)}-2\gamma_{i}\text{Var}[\beta_{i}]+\gamma_{i}\frac{\mathbb{E}[\beta_{i}]}{n}$
		$\displaystyle\quad-\sum_{j=1}^{m}\left(\frac{2h_{i,j,9,n}}{\lambda^{(n)}}+\frac{h_{i,j,7,n}}{n\lambda^{(n)}}\right),$

where $h_{i,j,7,n}$ , $h_{i,j,8,n}$ , and $h_{i,j,9,n}$ are functions from $[0,\infty)$ to $[0,B_{ij}A_{ij}]$ and are defined on the basis of (172).

The above equations constitute a proper system of differential equations with the same variables $\{\mathbb{E}[s_{i}]\}_{i=1}^{m}$ , $\{\text{Var}[s_{i}]\}_{i=1}^{m}$ , $\{\mathbb{E}[\beta_{i}]\}_{i=1}^{m}$ , and $\{\text{Var}[\beta_{i}]\}_{i=1}^{m}$ appearing on both the sides. To express these equations compactly, we define $z^{(n)}\in[0,1]^{4m}$ as the vector whose entries are given by $z_{i,1}^{(n)}:=z_{4(i-1)+1}^{(n)}:=\mathbb{E}[s_{i}^{(n)}]$ , $z_{i,2}^{(n)}:=z_{4(i-1)+2}^{(n)}:=\mathbb{E}[\beta_{i}^{(n)}]$ , $z_{i,3}^{(n)}:=z_{4(i-1)+3}^{(n)}:=\text{Var}[s_{i}^{(n)}]$ , and $z_{i,4}^{(n)}:=z_{4i}^{(n)}:=\text{Var}[\beta_{i}^{(n)}].$ Then $z^{(n)}(t)$ is a solution to the initial value problem $(z^{(n)})^{\prime}=g_{n}(t,z^{(n)};1/n,1/\lambda^{(n)})$ and $z(0)=z_{0}^{(n)}$ , where

(I)

$g_{i,n}^{(1)}(t,z;\varepsilon_{1},\varepsilon_{2}):=-\sum_{j=1}^{m}A_{ij}\Big{(}z_{i,1}z_{j,2}+\frac{h_{i,j,1,n}}{2}(z_{i,3}+z_{j,4})\Big{)}+\varepsilon_{2}\sum_{j=1}^{m}h_{i,j,7,n}$ ,
(II)

$g_{i,n}^{(2)}(t,z;\varepsilon_{1},\varepsilon_{2}):=\sum_{j=1}^{m}A_{ij}\left(z_{i,1}z_{j,2}+\frac{h_{i,j,1,n}}{2}(z_{i,3}+z_{j,4})\right)-\gamma_{i}z_{i,2}-\varepsilon_{2}\sum_{j=1}^{m}h_{i,j,7,n}$ ,

(III)

	$\displaystyle g_{i,n}^{(3)}(t,z;\varepsilon_{1},\varepsilon_{2})$	$\displaystyle:=-2\sum_{j=1}^{m}A_{ij}((z_{i,1})^{2}z_{j,2}+2h_{i,j,2,n}(z_{i,3}+z_{j,4}))$
		$\displaystyle\quad+\sum_{j=1}^{m}A_{ij}\Big{(}z_{i,1}z_{j,2}+\frac{h_{i,j,1,n}}{2}(z_{i,3}+z_{j,4})\Big{)}\left(2z_{i,1}+\varepsilon_{1}\right)$
		$\displaystyle\quad+\sum_{j=1}^{m}\left({2h_{i,j,8,n}}{\varepsilon_{2}}-{h_{i,j,7,n}}{\varepsilon_{1}\varepsilon_{2}}-2\mathbb{E}[s_{1}]h_{i,j,7,n}\varepsilon_{2}\right),$

(IV)

	$\displaystyle g_{i,n}^{(4)}(t,z;\varepsilon_{1},\varepsilon_{2})$	$\displaystyle=2\sum_{j=1}^{m}A_{ij}\Bigg{(}z_{i,1}z_{j,2}z_{i,2}+\frac{h_{i,j,1,n}}{2}(z_{i,3}+z_{j,4})z_{i,2}$
		$\displaystyle\quad\quad\quad\quad\quad\quad+\frac{h_{i,j,5,n}}{2}\left(h_{i,j,6,n}(8z_{i,3}+8z_{j,4})+z_{i,4}\Bigg{)}\right)$
		$\displaystyle\quad+\sum_{j=1}^{m}A_{ij}\left(\varepsilon_{1}-2z_{i,2}\right)\left(z_{i,1}z_{j,2}+\frac{h_{i,j,1,n}}{2}(z_{i,3}+z_{j,4})\right)$
		$\displaystyle\quad-2\gamma_{i}z_{i,4}+\varepsilon_{1}\gamma_{i}z_{i,2}-\sum_{j=1}^{m}\left(2{h_{i,j,9,n}}{\varepsilon_{2}}+{h_{i,j,7,n}}{\varepsilon_{1}\varepsilon_{2}}\right),$

(V)

$z_{0}^{(n)}=(s_{1}^{(n)}(0),\beta_{1}^{(n)}(0),0,0,s_{2}^{(n)}(0),\beta_{2}^{(n)}(0),0,0,\ldots,s_{m}^{(n)}(0),\beta_{m}^{(n)}(0),0,0)$ .

Observe that irrespective of the value of $n$ , the solution $(\bar{z}_{i,1}(t),\bar{z}_{i,2}(t),\bar{z}_{i,3}(t),\bar{z}_{i,4}(t)):=(y_{i}(t),w_{i}(t),0,0)$ solves the initial value problem $z^{\prime}=g_{n}(t,z;0,0)$ and $z(0)=z_{0}$ , where

z_{0}:=(s_{1,0},\beta_{1,0},0,0,s_{2,0},\beta_{2,0},0,0,\ldots,s_{m,0},\beta_{m,0},0,0).

Next, we need to bound $\left\|z^{(n)}(t)-\bar{z}(t)\right\|$ (where $\bar{z}(t)\in[0,1]^{4m}$ is the unique vector satisfying $\bar{z}_{4(i-1)+\ell}(t)=\bar{z}_{i,\ell}(t)$ for all $i\in[m]$ and $\ell\in[4]$ ). For this purpose, we will need the following lemma, which we borrow from [30].

Lemma 16.

Consider the initial value problems $x^{\prime}=f_{1}(t,x)$ , $x(0)=x_{1}$ and $x^{\prime}=f_{2}(t,x)$ , $x(0)=x_{2}$ with solutions $\varphi_{1}(t)$ and $\varphi_{2}(t)$ respectively. If $f_{1}$ is Lipschitz in $x$ with constant $L$ and $\|f_{1}(t,x)-f_{2}(t,x)\|\leq M,$ then $\left\|\varphi_{1}(t)-\varphi_{2}(t)\right\|\leq\left(\left\|x_{1}-x_{2}\right\|+M/L\right)e^{Lt}-M/L$ .

Now, note that the domain of $z$ for $g_{n}(t,z;\varepsilon_{1},\varepsilon_{2})$ can be chosen to be bounded because $0\leq\mathbb{E}[s_{i}],\mathbb{E}[\beta_{i}]\leq 1$ and $\text{Var}[s_{i}]\leq\mathbb{E}[s_{i}^{2}]\leq 1$ . Similarly, $\text{Var}[\beta_{i}]\leq 1$ . Also, we let $\varepsilon_{1},\varepsilon_{2}\in(0,1)$ and define $\varepsilon:=\max\{\varepsilon_{1},\varepsilon_{2}\}$ . Since $g_{n}(t,z;0,0)$ is a polynomial in $z$ , it is Lipschitz-continuous with some Lipschitz constant $L\in(0,\infty)$ . In addition, we use the bounds on $z$ and the functions $\{h_{i,j,\ell,n}:1\leq\ell\leq 9\}$ as follows:

	$\displaystyle\\|g_{n}(t,z;\varepsilon_{1},\varepsilon_{2})-g_{n}(t,z;0,0)\\|$	$\displaystyle\leq 2\sum_{i=1}^{m}\sum_{j=1}^{m}A_{ij}\varepsilon\left\|z_{i,1}z_{j,2}+\frac{h_{i,j,1,n}}{2}(z_{i,3}+z_{j,4})\right\|+\sum_{i=1}^{m}\gamma_{i}\varepsilon+10\sum_{i=1}^{m}\sum_{j=1}^{m}A_{ij}B_{ij}\varepsilon$
		$\displaystyle\leq\left(\sum_{i=1}^{m}\sum_{j=1}^{m}A_{ij}(4+10B_{ij})+\sum_{i=1}^{m}\gamma_{i}\right)\varepsilon,$

i.e.,

\displaystyle\|g_{n}(t,z;\varepsilon_{1},\varepsilon_{2})-g_{n}(t,z;0,0)\|\leq M(\varepsilon),

where $M(\varepsilon):=\left(\sum_{i=1}^{m}\sum_{j=1}^{m}A_{ij}(4+10B_{ij})+\sum_{i=1}^{m}\gamma_{i}\right)\varepsilon$ .

We now apply Lemma 16 after setting

\displaystyle f_{1}(t,x)=g_{n}(t,x;0,0),\quad f_{2}(t,x)=g_{n}(t,x;1/n,1/\lambda^{(n)}),\quad x_{1}=z_{0},\quad x_{2}=z_{0}^{(n)}.

Also, we let $\varphi_{1}=\bar{z}$ and $\varphi_{2}=z^{(n)}$ . Then we have

\left\|z^{(n)}(t)-\bar{z}(t)\right\|\leq\left(\left\|z_{0}-z_{0}^{(n)}\right\|+\frac{M\alpha_{n}}{L}\right)e^{Lt}-\frac{M\alpha_{n}}{L},

where $\alpha_{n}:=\max\left\{\frac{1}{n},\frac{1}{\lambda^{(n)}}\right\}$ . Thus, for all $t\leq T$ ,

\displaystyle\left\|z^{(n)}(t)-\bar{z}(t)\right\|\leq\left(\left\|z_{0}-z_{0}^{(n)}\right\|+\frac{M\alpha_{n}}{L}\right)e^{LT}-\frac{M\alpha_{n}}{L}.

(173)

Since $\lim_{\varepsilon\rightarrow 0}M(\varepsilon)=0$ , $\lim_{n\rightarrow\infty}z_{0}^{(n)}=z_{0}$ , and $\lim_{n\rightarrow\infty}\alpha_{n}=\lim_{n\rightarrow\infty}\max\left\{\frac{1}{n},\frac{1}{\lambda^{(n)}}\right\}=0$ , the right hand side of (173) goes to zero as $n\rightarrow\infty.$ Hence we have the uniform convergence $z^{(n)}\rightarrow\bar{z}$ over any finite time interval $[0,T]$ . The last step is to show that $z^{(n)}\rightarrow\bar{z}$ implies $L^{2}$ -convergence, i.e., $\mathbb{E}[\|(s_{i}^{(n)}-y_{i},\beta_{i}^{(n)}-w_{i})\|_{2}]\rightarrow 0$ as $n\rightarrow\infty$ . To this end, we have

	$\displaystyle\mathbb{E}[\\|(s_{i}^{(n)}-y_{i},\beta_{i}^{(n)}-w_{i})\\|_{2}^{2}]$	$\displaystyle=\mathbb{E}[(s_{i}^{(n)}-y_{i})^{2}]+\mathbb{E}[(\beta_{i}^{(n)}-w_{i})^{2}]$
		$\displaystyle=(\mathbb{E}[s_{i}^{(n)}]-y_{i}])^{2}+(\mathbb{E}[\beta_{i}^{(n)}]-w_{i})^{2}+\text{Var}[s_{i}^{(n)}]+\text{Var}[\beta_{i}^{(n)}]$
		$\displaystyle\leq\|\mathbb{E}[s_{i}^{(n)}]-y_{i}]\|+\|\mathbb{E}[\beta_{i}^{(n)}]-w_{i}]\|+\text{Var}[s_{i}^{(n)}]+\text{Var}[\beta_{i}^{(n)}]$
		$\displaystyle=\|z_{i,1}^{(n)}-\bar{z}_{i,1}\|+\|z_{i,2}^{(n)}-\bar{z}_{i,2}\|+\|z_{i,3}^{(n)}-\bar{z}_{i,3}\|+\|z_{i,4}^{(n)}-\bar{z}_{i,4}\|,$

where we used that $\bar{z}_{i,3}=\bar{z}_{i,4}=0$ , and the inequality holds because $y_{i},\mathbb{E}[s_{i}^{(n)}],w_{i},\mathbb{E}[\beta_{i}^{(n)}]\in[0,1]$ . Thus, the uniform convergence of $z^{(n)}$ to $\bar{z}$ over $[0,T]$ proves that $\mathbb{E}[\|(s_{i}^{(n)}-y_{i},\beta_{i}^{(n)}-w_{i})\|_{2}]\rightarrow 0$ as $n\rightarrow\infty$ .

	$\displaystyle\|\text{Pr}(T\geq\kappa_{0}\mid\mathcal{S}(t),\mathcal{I}(t))-\text{Pr}(T\geq\kappa_{0}\mid(a,b)\notin E(t),\mathcal{S}(t),\mathcal{I}(t))\|$
	$\displaystyle=\|\text{Pr}(T\geq\kappa_{0}\mid(a,b)\notin E(t),\mathcal{S}(t),\mathcal{I}(t))(1-\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t)))$
	$\displaystyle\quad+\text{Pr}(T\geq\kappa_{0}\mid(a,b)\in E(t),\mathcal{S}(t),\mathcal{I}(t))\cdot\text{Pr}((a,b)\in E(t)\mid\mathcal{S}(t),\mathcal{I}(t))$
	$\displaystyle\quad-\text{Pr}(T\geq\kappa_{0}\mid(a,b)\notin E(t),\mathcal{S}(t),\mathcal{I}(t))\|$
	$\displaystyle\leq\frac{\rho_{ij}}{\pi(n)},$

	$\displaystyle\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\centernot\rightsquigarrow}}a\right\}\cap\bar{D}_{b}\cap\bar{F}_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle=1-\text{Pr}\left(\left\{b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\rightsquigarrow}}a\right\}\cup D_{b}\cup F_{(a,b)}\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)$
	$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}1-\text{Pr}\left(b\stackrel{{\scriptstyle t_{1},\Delta t}}{{\rightsquigarrow}}a\Bigm{\|}\mathbf{X}(t_{1})=\mathbf{x}\right)-\text{Pr}(D_{b}\mid\mathbf{X}(t_{1})=\mathbf{x})-\text{Pr}(F_{(a,b)}\mid\mathbf{X}(t_{1})=\mathbf{x}\})+o(\Delta t)$
	$\displaystyle=1-(B_{ij}\delta_{1y}\Delta t+o(\Delta t))-(\gamma_{j}\Delta t+o(\Delta t))-\left(\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\Delta t+o(\Delta t)\right)+o(\Delta t)$
	$\displaystyle=1-\left(B_{ij}\delta_{1y}+\gamma_{j}+\lambda\left(y\left(1-\frac{\rho_{ij}}{n}\right)+(1-y)\frac{\rho_{ij}}{n}\right)\right)\Delta t+o(\Delta t),$

Usefulness of the Age-Structured SIR Dynamics in Modelling COVID-19

Abstract

1 INTRODUCTION

2 PROBLEM FORMULATION

2.1 The Age-Structured SIR Model

2.2 A Stochastic Epidemic Model

2.2.1 Age Groups

2.2.2 State Space

2.2.3 State Attributes

2.2.4 The Markov Process

3 MAIN RESULT

Theorem 1.

Proposition 1.

Proposition 2.

Remark 1.

4 A CONVERSE RESULT

Theorem 2.

Proof.

Remark 2.

5 EMPIRICAL VALIDATION

5.1 Dataset

5.2 Preprocessing

5.3 Parameter Estimation Algorithm

5.4 Phase Detection Algorithm

5.5 Selection of Algorithm Parameters

5.5.1 Phase Detection Algorithm

5.5.2 Parameter Estimation Algorithm

5.6 Results

5.6.1 Phase Detection

5.6.2 Parameter Estimation and Its Implications

The First Wave (March 2020 - June 2020, Phases 1 - 3)

The Second Wave (July 2020 - September 2020, Phases 4 - 7)

The Third Wave (October 2020 - January 2021, Phases 8 - 11)

Comparing the Age Groups on the Basis of Infectiousness and Susceptibility

6 CONCLUSION AND FUTURE DIRECTIONS

References

Appendix

Definition 1 (Jump Times).

Lemma 1.

Proof.

Proof of Proposition 1

Proof.

Proof of (i):

Proof of (ii):

Proof of (iii):

Proof of (iv):

Lemma 2.

Proof.

Definition 2 (Transition Sequence).

Definition 3 ((a,b)(a,b)-Complement).

Definition 4 ((a,b)(a,b)-Agnostic Transition Sequence).

Definition 5 (δ\delta-Approximation).

Lemma 3.

Proof.

Lemma 4.

Proof.

Definition 6 ((a,b)(a,b)-Agnostic Superstate).

Definition 7 ((a,b)(a,b)-Agnostic Jump Times).

Lemma 5.

Proof.

Remark 3.

Lemma 6.

Proof.

Lemma 7.

Proof.

Lemma 8.

Lemma 9.

Proof.

Proof of Proposition 2

Proof.

Remark 4.

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Remark 5.

Some Auxiliary Lemmas

Lemma 13.

Lemma 14.

Definition 3 ( $(a,b)$ -Complement).

Definition 4 ( $(a,b)$ -Agnostic Transition Sequence).

Definition 5 ( $\delta$ -Approximation).

Definition 6 ( $(a,b)$ -Agnostic Superstate).

Definition 7 ( $(a,b)$ -Agnostic Jump Times).