key: cord-0669468-8gyi4h1n
authors: Barlow, M. T.
title: A branching process with contact tracing
date: 2020-07-31
journal: nan
DOI: nan
sha: d57b33a501bcdada39ab45d57ab1c02dc6cc0576
doc_id: 669468
cord_uid: 8gyi4h1n

We consider a supercritical branching process and define a contact tracing mechanism on its genealogical tree. We calculate the growth rate of the post tracing process, and give conditions under which the tracing is strong enough to drive the process to extinction.

In this paper we present a simple model for contact tracing during an epidemic. The epidemic is taken to be a standard (discrete time) Bienaymé-Galton-Watson branching process (Z n , n ≥ 0) with mean λ; the case of interest is when the process is supercritical, so λ > 1. (See [1, 6] for background on these processes.) We assume that b generations after infection, an infected individual is detected with probability p. If an individual is detected as infected, an attempt is made to trace all this individual's contacts, both forwards and backwards. We assume that for each infection link the probability of a successful trace is α, and that it can be determined with probability 1 whether or not a traced individual has been infected. If a traced individual is detected as infected, then in turn all contacts of that individual are traced, and this process is repeated throughout the genealogy of the epidemic. It is assumed that detected individuals are quarantined and so can be removed from the pool of infectious individuals. (See the next section for a more precise definition.) We write Z CT for the branching process after contact tracing.

If α = 1 then all traces are successful, and as soon as one individual is detected every infected individual will be traced and isolated, so bringing the epidemic to an end. For smaller values of α there is the possibility that the epidemic will remain supercritical: we are interested in how large α needs to be to control the epidemic for a fixed b and p.

Our main result is as follows. Let We do not know of any case where we can give exact expressions for (v n ), but unless p is small the series for (h n ) converges very rapidly.

If α is not large enough to control the epidemic, we can still ask how quickly Z CT grows. Define the Malthusian parameter of (v n ) to be the unique θ such that ∞ n=1 e −nθ v n = 1.

(1. 6) We are concerned with the case when v n > 1, so θ > 0. An easy argument (see Lemma 2.4) shows that there is a function e b (p) such that the epidemic becomes extinct with probability one if α > e b (p), and survives with positive probability if α < e b (p). (The function e b (p) depends on the offspring distribution of the original branching process.) In Section 4 we study the function e b (p) close to the critical points where it crosses the axes.

There is a very extensive applied epidemiological literature on contact tracing, but we did not find very many papers containing exact calculations. One quite closely related paper is [2] , which looks at forward contact tracing for a continuous time epidemic. In the case of an exponential infection time they obtain an exact formula for the reproduction number of the epidemic after contact tracing. As in our paper, they look at the discrete time process of untraced individuals -called there unnamed individuals. [3] looks at some extensions of this model, including allowing a latent period, and tracing delays. The papers [8, 11, 10] also all consider various kinds of contact tracing for a continuous time branching processes.

We need to keep track of not just the size of the original branching process, but also its genealogical structure. So we write Λ 0 = {0}, Λ n = N n and set

A point x = (x 1 , . . . , x n ) ∈ N n represents a potential individual in the nth generation; we write |x| = n, say that x is in generation n, and define its ancestor to be a(x) = (x 1 , . . . x n−1 ). For x ∈ N we set a(x) = 0. We take Λ to be a graph with edge set

Let (ξ x , x ∈ Λ) be independent r.v. with distribution (p k ). We will define η : Λ → {0, 1}, and set Γ = {x ∈ Λ : η(x) = 1}; this will be the set of individuals in the original process. We define η(0) = 1. Once η is defined on Λ[0, n] we extend it to Λ[0, n + 1] as follows. Let x = (x , x n+1 ) ∈ Λ n+1 ; we set η(x) = 1 if η(x ) = 1 and x n+1 ≤ ξ x , and take η(x) = 0 otherwise. Let Z n = |{x ∈ Λ n : η(x) = 1}|, so that (Z n ) is a branching process with offspring distribution (p k ). We consider Γ as a graph with edge

Let b ∈ Z + , and probabilities p ∈ [0, 1] and α ∈ [0, 1]. Define i.i.d. random variable η D (x) with a Ber(p) distribution, and i.i.d. η T (x) with a Ber(α) distribution. If η D (x) = 1 we say x is detectable or detected. If η T (x) = 1 then we say the edge {x, a(x)} is open or traceable. Thus (η T ) defines a bond percolation process on Γ -see [5] . A path (i.e. sequence of edges) in (Γ, E Γ ) is traceable if each edge in the path is traceable. For x ∈ Γ we write C(x) for the set of y ∈ Γ such that x and y are connected by an traceable path; we call C(x) the connected cluster of x (at time n). We always have x ∈ C(x).

The contact tracing procedure operates as follows. At time n ≥ 0 we will define a subset A n of Γ ∩ Λ[0, n]. If b > 0 or b = 0 and η D (0) = 0 we take A 0 = {0}. If b = 0 and η D (0) = 1 then we set A 0 = ∅. (In this case the founding individual is detected at time 0 and the process immediately becomes extinct.)

To construct A n from A n−1 , let

thus A * n is A n−1 together with the offspring of the individuals in A n−1 ∩ Λ n−1 . We now look at the r.v. η D (y) for y ∈ A * n ∩ Λ n−b , and if η D (y) = 1 then we remove C(y) from A * n . Thus we set

The current generation of the process (A n ) is A CG n = A n ∩ Λ n . The size of the current generation is Z CT n = |A CG n |.

Since A * n ⊂ Γ ∩ Λ n , Z CT n ≤ Z n . We call the process A = (A n , n ≥ 0) the (b, p, α)-contact tracing process or CTP(b, p, α). The parameter space is

(2.1)

We write E b,p,α for expectations when we wish to emphasize the dependence on the parameters.

Note that not all points are removed -for example if η D (y) = η T (y) = 0 and y has no descendants then y ∈ A n for all large n. If however for some n we have A CG n = ∅ then A CG n+k = ∅ for all k ≥ 0. To clarify our terminology we define what we mean by survival or extinction of a random process. Definition 2.1. Let X = (X n , n ≥ 0) be a random process on Z + with the property that {X n = 0} ⊂ {X n+1 = 0}. We define

If P(X becomes extinct ) = 1 we say X becomes extinct, and if P(X becomes extinct ) < 1 we say X survives with positive probability or survives wpp. Sometimes we will shorten 'survives wpp' to 'survives'. For a set valued process such as A CG = (A CG n ) we define extinction or survival as whether or not the process |A CG n | becomes extinct, or survives. We are interested in characterizing the set of parameter values such that Z CT becomes extinct, and define the following subsets of P:

We begin with some easy properties of the sets E and S.

(e) If α = 1 and p > 0 then Z CT becomes extinct.

Proof. (a) Let (A n ) be the process A, but where at time n+1 only the detected individuals are removed. Then A n ⊂ A n , and the process Z n = |A n ∩Λ n | is a simple branching process with offspring distribution mean (λ(1 − p)); if λ(1 − p) ≤ 1 then Z becomes extinct, and therefore Z CT also becomes extinct. (b) In this case detection never removes individuals in the current generation, so |A CG n | is just a branching process with offspring distribution (p k ), and therefore it survives wpp. (c) If we just consider the new points y which satisfy η T (y) = η D (y) = 0, we have a process A U N which is smaller than A, and is a branching process with offspring distribution with mean λ(1 − p)(1 − α), and if this process survives then A survives. (d) and (e) are clear.

We will treat the case p = 1 when b ≥ 1 in Lemma 3.5 below.

Remark 2.3. The 'heavy tailed' situation when p k = ∞ does not seem to be interesting in this context. If p = 0 or α = 1 then Lemma 2.2(d),(e) still hold. If p = 1 and α < 1 the process becomes extinct if b = 0 and survives otherwise, while if p ∈ (0, 1) and α < 1 then the argument of Lemma 2.2(c) implies that the process survives wpp.

Proof. We write η T (x) for the detection and tracing processes with parameters p and α respectively, and couple them so that they are monotone in p and α respectively. Write A (b,p,α) for the associated contact tracing process. Then the construction of A gives that A

From Proposition 2.6 we will obtain the bound

Lemma 2.2 covers the cases when p = 0, so from now on we assume

For x ∈ Γ ∩ Λ n let V x be the number of offspring of x, and V T x and V U x be the number of traceable and untraceable offspring.

We can decompose A n into a collection of disjoint connected traceable clusters C 1 , . . . , C kn , and an analysis of the evolution of a traceable cluster is a key step in our proofs.

We will call y ∈ Γ with η T (y) = 0 a cluster seed. The edge {a(y), y)} is untraceable, and so if |y| = n and y ∈ A n then y will only be removed from the process (A n+k , k ≥ 0) if some descendent of y is detected and is connected to y by a traceable path. A key observation is that the evolution of the part of (A n+k , k ≥ 0) containing y and its descendants is independent of the rest of (A n+k , k ≥ 0).

We look at the evolution in time of a traceable cluster, and for simplicity consider the cluster started at the root 0. Initially we consider the growth of the cluster without any detection. Let V 0 = {0}, and (V k , k ≥ 1) be the cluster at subsequent times, given by

We now introduce detection for this cluster. Let S be the generation number of the first detected vertex in the cluster. So

Write V T n for the number of points in the cluster taking detection into account, and V U n for the corresponding number of cluster seeds. We have

The difference between the two expressions above is because the detection process forces V T S+b = 0, while the cluster may still produce cluster seeds in generation S + b.) Thus the total number of cluster seeds produced by the cluster starting from 0 is 

Proof. Let X 0 = 0, X 0 = 1, and define for n ≥ 1

Then X = (X n ) is a branching process with offspring distribution equal in law to Y U ∞ . Since P( Y U ∞ = 1) < 1 the process X becomes extinct with probability 1 if and only if EX 1 ≤ 1, i.e. if and only if E Y U ∞ ≤ 1. It remains to show that A CG (a.s.) becomes extinct if and only if X becomes extinct. If A CG (a.s.) becomes extinct then the total family size n |A CG n | is finite, so the total number of cluster seeds is finite and thus X becomes extinct. On the other hand, if X becomes extinct then (as p > 0) each traceable cluster is finite, so the total family size n |A CG n | is finite, and thus A CG becomes extinct. Proof. We consider the traceable cluster (V n ) started at the origin. We explore the points in the traceable cluster, starting with the origin, and completing the exploration of each generation before starting on the next. Let X 1 , X 2 , . . . be the exploration process; the r.v. X i take values in the genealogical space Λ. This sequence is finite or infinite according to whether the cluster is finite or infinite. The total family size of (

Let T E = min{n ≥ 1 : X n = ∂}; then T E = Y + 1 and is a stopping time with respect to (F n ). Let T D = min{n ≥ 1 : η D (X n ) = 1}, and T = T D ∧ T E . Set U 0 = D 0 = M 0 = 0, and for n ≥ 1 let

Then M is a martingale with respect to (F n ). Hence for any n ≥ 0,

The total number of cluster seeds produced by the traceable cluster up to its extinction due to a detection is Y U ∞ . Note that Y U ∞ need not include the all r.v. V U x for x in the final generation, and so Y U ∞ ≤ U T . We have D T ≤ 1. Using Fatou's Lemma

The conclusion is now immediate from Theorem 2.5.

Hence

Proof. The first two expressions follow easily from (2.8).

Combining these equalities and taking expectations gives the expression for E( V U n ).

To calculate w n set for s, t ≥ 0, n ≥ 0

Note that H 0 (s, t) = st. Then

and so

Since p > 0 and V T n ≤ Y T n , the series for H n (1 − p, t) converges in a neighbourhood of 1, and there is no problem taking the derivative in (3.4) . A standard first generation branching process decomposition gives H n (s, t) = sG T (H n−1 (s, t)) = sG(1 − α + αH n−1 (s, t)).

H n (s, t) = sαG (1 − α + αH n−1 (s, t)) ∂ ∂t H n−1 (s, t). Proof of Theorem 1.1. This follows from Theorem 2.5, (3.2) and (3.9). We also have that v n as defined by (2.10) satisfies (1.4).

Note that the functions g n and h n depend on α but not on p. We collect some properties of these functions. (b) For s ∈ [0, 1), the sequence g n (s) is strictly decreasing in n. The limit g ∞ (s) satisfies g ∞ = sG T (g ∞ ) and sG T (g ∞ (s)) < 1.

.

Proof. (a) This is clear from the definition.

(b) Note that G T is strictly monotone. Fix s ∈ (0, 1). Then g 1 = sG T (s) < sG T (1) = s. If g n−1 < g n−2 then g n = sG T (g n−1 ) < sG T (g n−2 ) = g n−1 . Thus g n is decreasing in n, and as G T is continuous the limit must satisfy g ∞ = sG T (g ∞ ).

Let 1] , and as G T is strictly monotone it follows that this solution is unique, and therefore equals g ∞ . By the mean value theorem there exists ξ ∈ (g ∞ , 1) such that

, and thus f 2 (g ∞ ) < 1.

(c) Note that if V T n > 0 then Y T n ≥ n + 1, and that for

(d) If K is a compact subset of (0, 1]×[0, 1] then by (c) the functions h n converge uniformly to 0 in K. It is straightforward to verify that each term in the sum (3.2) is continuous in p, α; as the series is uniformly convergent the limit is continuous.

Proof. As y b is continuous in the region p > 0, and extinction occurs if y b (p, α) ≤ 1, extinction occurs in the critical case α = e b (p).

Remark 3.4. Note that y b is not continuous at (0, 1), since y b (0, 1) = 0 while for α ∈ (λ −1 , 1) we have y b (0, α) = ∞. Further e b (0) = 1, but (b, 0, 1) ∈ S, so the restriction to p > 0 in the Corollary above is necessary.

The following Lemma handles the case p = 1 and b ≥ 1. Proof. (a) Set Remark 3.6. In spite of the monotonicity given by Lemma 2.4, the function y b (p, α) is not monotone in α. An easy way to see this is to note that for b ≥ 1 we have 

In the previous section we saw that we can obtain accurate numerical estimates on e b (p) in regions of the parameter space when p is bounded away from zero. In this section we look at the some limiting behaviours of this function, beginning with the easy case of b → ∞.

Proposition 4.1. There exists b 0 , depending only on λ, and a constant c 3 (p, λ) such that

Proof. By (1.5) and (3.10) we have, writing

then bounding from below the sum of the left side of (4.2) by its final term,

Thus (b, p, α 1 ) ∈ S survives, and so by monotonicity (b, p, α) ∈ S for all α ∈ [0, α 1 ], and e b (p) ≥ α 1 .

For the lower bound we can assume that b is large enough so that α 1 λ − 1 > 1 2 (λ − 1). Then we obtain from (4.2) that

and taking α = 1 − c 3 λ −b , with c 3 small enough, the bound follows.

We now look at e 0 (p) close to the point p 0 = 1 − λ −1 ; for simplicity we restrict to the case when the offspring distribution has a finite second moment.

.

Proof. (a) Note that h 1 (s) = s 2 αG (1 − αp). So taking only the first two terms in the sum in (1.5) we have

and the result is then immediate from Theorem 2.5. (b) Write t = p 0 −p so that λ(1−p) = 1+λt. Note that G (1−αp) = λ−αpG (1)+o(α 2 ). We have

, and thus we have

which gives the limit (4.4).

Proof. Let α 0 ∈ (0, 1) be such that λα 0 > 1. Then it is easy to verify that there exist c 3 , c 4 such that for all n ≥ 1 and α ∈ [α 0 , 1], p) , and choose c 2 so that 2p ≥ p 1 ≥ p for p ∈ [0, c 2 ]. Let α ∈ [α 0 , 1]. Choose n so that λ n−1 T < p −1 ≤ λ n T . Then

By the second moment method

Let r = c 2 3 /4c 4 . Then P(Y T n > 2c 2 λ n T /r) ≤ 1 2 r, and thus P(V T n ≥ 1 2 λ n T , Y T n ≤ 2c 2 λ n T /r) ≥ 1 2 r. Hence writing s = 1 2 , t = 2c 2 /r,

Hence w 0 (α, p) ≥ c λ (1 − α)/p, which gives that e 0 (p) > 1 − c 1 p.

In the case when α is not large enough to make (Z CT n ) extinct, it is of interest to ask how quickly this process grows. We write

here Z U n and Z T n are the number of points x ∈ A CG n with η T (x) = 0 and η T (x) = 1 respectively. Recall from (2.10) the definition of v n , and (1.6) that of the Malthusian parameter θ of (v n ). We will be concerned with the case when (Z CT n ) survives wpp, so θ > 0.

Let (X n ) be the cluster seed process defined in the proof of Theorem 2.5. Let C n be the set of cluster seeds at time n. Define a process R n taking values in Z Z + + as follows. For a sequence x ∈ Z Z + + we write the ith component as x(i). Set R 0 (0) = 1, and R 0 (i) = 0 for i ≥ 1. Let C n be the set of cluster seeds at generation n, so

If x is a cluster seed and |x| = n write V U k (x) for the number of cluster seeds in generation n + k produced by the traceable cluster with seed x. Define

We have R n (k) = R n−1 (k + 1) +

The process R n is a branching process, with infinitely many types. For each k ≥ 1 an individual of type k produces with probability 1 one descendent of type k − 1. An individual of type 0 produces a random number of offspring, with distribution ( V U 1 , . . . ). Let M ij denote the mean number of offspring of a type i individual. Then

It is straightforward to verify that if u(n) = e −nθ , for n ≥ 0 then u is a right eigenvector for M and M u = e θ u. Thus we have

is a martingale with respect to F R n = σ(R 0 , R 1 , . . . , R n ). The following Lemma follows easily from Markov's inequality and the convergence of Y . Let (X n ) be the cluster seed process, and let F be the event that (X n ) survives; set P(F ) = p F > 0. and it follows that we can choose N large enough so that θ − ε < θ N ≤ θ.

Let R (N ) be the process R, but with the offspring distribution for a type 0 individual given by (N ∧ V U 1 , . . . , N ∧ V U N , 0, . . . ). We can do the truncation a.s. on the probability space, so that R n (k) ≥ R (N ) n (k) for all n ≥ 0, k ≥ 0. As all individuals for R (N ) are of type 0, 1, . . . , N − 1, we can regard R (N ) as a multi-type branching process with finitely many types. Let M (N ) be the matrix of means of the truncated process R (N ) , and u (N ) (k) = e −θ N k for 0 ≤ k ≤ N − 1. Then M (N ) u (N ) = e θ N u (N ) . A classic limit theorem (see [1, p. 192] ) implies that e −kθ N R 

By the above, we have P(G ε ) = q > 0. Let m ≥ 1, and T m = min{k ≥ 0 : X k ≥ m}. We have P(T m < ∞|F ) = 1. Write x i , 1 ≤ i ≤ m for the first m cluster seeds in generation T m , R i for the associated multitype branching process, and G ε (i) for the event defined by (5.6) for R i . Then P(∪G ε (i)|T m < ∞) = 1 − q m . On the event ∪G ε (i) we have lim n→∞ ln Rn(0) n ≥ θ − ε, which implies that P(G ε ) ≥ P(F ) − q m .

Consequently, for any ε > 0 we have P(G ε ) ≥ P(F ), and (5.5) follows.

Then u R is a left eigenvector for M with eigenvalue e θ , and k u R (k)u L (k) < ∞. By Criteriion III of [12] the matrix M satisfies Case II of [9] , and it follows that

where W is a random variable with E(W ) = 1 and P(W > 0) = p F .

Theorem 5.4. Let (X n ) be the cluster seed process, and let F be the event that (X n ) survives. On F we have, a.s. Proof. We recall the construction of A * n from Section 2. We consider first the case b = 0. Let M n = |A * n ∩ Λ n |. Note that R n (0) = {x ∈ A * n ∩ Λ n : η T (x) = 0}, Z U n = {x ∈ A * n ∩ Λ n : η T (x) = η D (x)0}, and that Z CT n ≤ M n . Conditional on M n we have that R n ∼ Bin(M n , 1 − α). Hence (see [7] ), P(|R n − (1 − α)M n | > t|M n ) ≤ 2 exp(−t 2 /3M n ).

Let ε > 0, and set m n = e n(θ+ε) , a = 2/(1 − α). Then if n ≥ c 0 (α, p, ε), P(M n ≥ 2(1 − α) −1 m n ) ≤ P(M n ≥ 2(1 − α) −1 m n ), R n < m n ) + P(R n ≥ m n ) ≤ P(|(1 − α)M n − R n | > m n , M n ≥ 2(1 − α) −1 m n ) + e −εn ≤ exp(−m 2 n /6(1 − α) −1 m n ) + e −εn ≤ 2e −εn .

Thus we have lim sup n→∞ ln M n n ≤ θ, a.s., and the upper bound for ln Z CT n /n follows immediately. As M n ≥ R n (0), it is immediate that on F Question. Let (p k ) and (p k ) be offspring distributions, and E and E be the corresponding parameter sets for extinction. Suppose that (p k ) stochastically dominates (p k ). It follows that the branching process Z stochastically dominates Z. Is it the case that E ⊂ E?

Branching processes

Threshold behaviour of emerging epidemics featuring contact tracing

Stochastic epidemic models featuring contact tracing with delays

Modelling the effects of epidemiological contact tracing

Branching Processes

Large deviation inequalities for sums of indicator variables

The Effectiveness of Contact Tracing in Emerging Epidemics

Extensions of a limit theorem of Everett, Ulam and Harris on multitype branching processes to a branching process with countably many types

Contact tracing in stochastic and deterministic epidemic models

The effect of delay on contact tracing

Ergodic properties of nonnegative matrices

Acknowledgment. This work was stimulated by a seminar in the B.C. COVID-19 group by Nils Bruin on contact tracing -see [4] for the related paper.