---
# System prepended metadata

title: Chapter 21. Epidemics

---

# Chapter 21. Epidemics

[TOC]

> The arrival of Europeans in the Americas(Smallpox)[^130]
> Bubonic plague(Black Death)[^293]

[^130]: 123
[^293]: 123

## 21.1 Diseases and the Networks That Transmit Them

### Contact Network
- nodes as person
- edges as the spread of disease between two nodes

> travel patterns within a city[^149][^295]
> worldwide airline network[^119]
> the 2001 foot-and-mouth outbreak in the United Kingdom[^211]
> plant disease[^139]
> computer viruses[^241]
> computer viruses between nearby mobile devices[^251]

[^149]:
[^295]:
[^119]:
[^211]:
[^139]:
[^241]: 
[^251]:

## 21.2 Branching Processes
- $T$ be a tree with infinite depth
- each node has $k$ children
- initially, mark root as infected
- for each step, a infected node will infect its each children with probability $p$



| Initial | ![](https://i.imgur.com/AqbnNVY.png) | 
| -------- | -------- | 
| Example | ![](https://i.imgur.com/s4JftRe.png)| 
| Terminate|![](https://i.imgur.com/Jm7tZDw.png)|

:::success
**Definition.**
The *basic reproductive number*, denoted by $R_0$ is the expected number of new cases of the disease caused by a single individual
:::
In this case, $R_0=pk$.
:::info
**Theorem.**
If $R_0<1$, then the probability that the disease dies out before wave $t$ increases to $1$ as $t\to\infty$. If $R_0>1$, then the probability that the disease goes forever is greater than $0$
:::
## 21.3 The SIR Epidemic Model
SIR stands for
- *Susceptible*. susceptible to infection from its neighbors
- *Infectious*. has some probability of infecting each of its susceptible neighbors
- *Removed*. After an infectious period, remove from consideration

The process is
- initially, some nodes are in **I** state, and the other in **S** state
- node $v$ in **I** has porbability $p$ to infect neighbor $w$ in **S**
- after $t_I$ steps in **I**, $v$ turns into **R**
![](https://i.imgur.com/Rb35Nrr.png)

Some extension
- more detailed states
- probability varies, $p_{v,w}$
- probability $q$ to recover before $t_I$ steps 

# Percolation
- static view of the process
- assume $t_I=1$
- decide $p$ for each edge first
![](https://i.imgur.com/f8ZS6Zo.png)


> static view of SIR process[^44][^173]

[^44]:
[^173]: 1

## 21.4 The SIS Epidemic Model
- for node $v$ in **I**, after $t_I$ steps, turn into $S$ again
![](https://i.imgur.com/YR3ZFpf.png)

- probability that the disease dies out before step $t$ tends to $1$ as $t\to\infty$

> knife-edge between die-out quickly and persistence[^52][^278]

[^52]:
[^278]:

### Time-Expanded Contact Network
- SIS as a special case of SIR
    - assume $t_I=1$
    - create infinite copy of origin graph for time $t=0,1,2,\ldots$
    - create edges from $t$ to $t+1$

![](https://i.imgur.com/0lS6BTn.png)


## 21.5 Synchronization

> measles[^196][^213]
> the prevalence of syphilis across the United States[^195]
> oscillations and synchronization[^195][^267]

[^196]:
[^213]:
[^195]:
[^267]:

### SIRS Model
After $t_I$ in **I**, recover to be **R** for $t_R$ steps, and turn into **S** again

> small-world properties to synchronization[^411][^267]

[^411]:

![](https://i.imgur.com/29EC37K.png)
> syphilis and gonorrhea[^195]
> out-of-phase synchronization[^196]
> more rule to explain such properties[^213]

## 21.6 Transient Contacts and the Dangers of Concurrency
- HIV/AIDS
    - progresses over many years
    - very few contacts at any single point in time

![](https://i.imgur.com/7jnzZRp.png)
> sociology[^182][^305][^258]
> epidemiology[^307][^406]
> mathematics[^106]
> computer science[^53][^239]

### Concurrency
- overlap of time interval

> average number and duration of partnerships matters[^307]

[^182]:
[^305]:
[^258]:
[^307]:
[^406]:
[^106]:
[^53]:
[^239]:
## 21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve

> Mitochondrial Eve[^94]

- Wright–Fisher model
    - each node in generation $g$, uniformly connect with a node in generation $g-1$

![](https://i.imgur.com/HPhl6jY.png)
![](https://i.imgur.com/l0FPoAW.png)



[^94]:

## 21.8 Advanced Material: Analysis of Branching and Coalescent Processes
### A. Analysis of Branching Processes
![](https://i.imgur.com/pyN2D9A.png)
- *basic reproductive number* $R_0=pk$
- $q_n$: Probability that the epidemic survives for at least $n$ waves
- $q^∗$: limit of $q_n$ as $n$ goes to inﬁnity
- Claim: (a) If $R_0 < 1$ then $q^∗ = 0$. (b) If $R_0 > 1$ then $q^∗ > 0$.
#### The Expected Number of Infected Individuals
- The number of individuals at level $n$ is $k^n$
- Let $X_n$ be a random variable equal to the number of infected individuals at level $n$.
- $X_n = Y_{n1} + Y_{n2} + · · · + Y_{nm}$
    - For each individual $j$ at level $n$, $Y_{nj}$ equals to $1$ if $j$ is infected, and equals to $0$ otherwise.
    - $m = k^n$
- $E[X_n]= E [Y_{n1}] + E [Y_{n2}] + · · · + E [Y_{nm}]$
    - $E[Y_{nj}] = 1 × Pr [Y_{nj} = 1] + 0 × Pr [Y_{nj} = 0] =Pr [Y_{nj} = 1]$
- Individual $j$ at depth $n$ is infected with probability $p^n$ $\Rightarrow E[Y_{nj}] = p^n$
    - ![](https://i.imgur.com/y5jvdKg.png)
- Therefore, $E[X_n]= p^nk^n = (pk)^n = {R_0}^n.$
#### From Expected Values to Probabilities of Persistence
- Proof of (a) If $R_0 < 1$ then $q^∗ = 0$
    - $E [X_n] = 1 × Pr [X_n = 1] + 2 × Pr [X_n = 2] + 3 × Pr [X_n = 3] + · · ·$$=Pr [X_n ≥ 1] + Pr [X_n ≥ 2] + Pr [X_n ≥ 3] + · · ·$$\Rightarrow E [X_n] ≥ Pr [X_n ≥ 1]=q_n$
    - $E [X_n] = {R_0}^n$, which is converging to $0$ as n grows
    - Hence, $q_n$ must also be converging to $0$. 
    - This shows that $q^∗ = 0$ when $R_0 < 1$.
#### A Formula for $q_n$
![](https://i.imgur.com/wlaRayl.png)
- $1 − q_n = (1 − pq_{n−1})^k$$\Rightarrow q_n = 1 − (1 − pq_{n−1})^k$
- $q_0 = 1$

#### Following the Values $q_n$ to a Limit
- Deﬁne $f (x) = 1 − (1 −px)^k \Rightarrow q_n = f (q_{n−1})$
- sequence of values $1, f (1), f (f (1)), . . .$ = sequence $q_0, q_1, q_2, . . .$
- plot function $f$
    - $f (0) = 0$ and $f (1) = 1 − (1 − p)k < 1$.
    - $f^{'} (x) = pk(1 − px)k$<br> $f^{'} (x)$ is positive but monotonically decreasing as $x$ ranges between $0$ and $1$.
    - $f^{'}(0) = pk = R_0$.<br>When $R_0 > 1$, $f$ starts out above $y = x$.
    - Thus, $y = f (x)$ must cross $y = x$ somewhere in the interval between $0$ and $1$, at a point $x^∗ > 0$.
    - ![](https://i.imgur.com/I6dotF4.png)
- When $R_0 > 1$, the probability that the epidemic persists for $n$ levels converges to a positive value as $n$ goes to inﬁnity.
- ![](https://i.imgur.com/xaPkPeP.png)
- ![](https://i.imgur.com/2EpTDwv.png)

### B. Analysis of Coalescent Processes
- Focus on a small sample of $k$ individuals in a large population of size $N$.
- Consider the time until the lineages of these $k$ individuals merge into a common ancestor.
- Example
    - $N=27$
    - $k=6$
    - ![](https://i.imgur.com/OIirBCj.png)
#### The Probability That Lineages Collide in One Step.
- We have a set of $j$ distinct lineages
- Estimate the probability of colliding
- Compute the probability that no two lineages collide = $(1 − \frac1N)(1 − \frac2N)(1 − \frac3N)\cdot \cdot \cdot (1 − \frac{j-1}N)$$=1 − (\frac{1 + 2 + 3 + · · · + j − 1}{N}) +\frac{g(j)}{N^2}$$\approx 1 − (\frac{1 + 2 + 3 + · · · + j − 1}{N})$$=1 −\frac{j(j − 1)}{2N}$
- If two lineages collide
    -  Collision between two of the lineages
    -  More than two lineages collide in a single generation
        -  A collision among three lineages
            -  For a set of 3 lineages, the probability this happens is  $\frac{1}{N^2}$
            -  Since there are fewer than $j^3$ sets of three lineages, the probability $\lt \frac{j^3}{N^2}$. 
        -  Two different pairs of lineages each have a separate, two-way collision
            -  Suppose that $A$ collides with $B$, and $C$ collides with $D$
            -  Both of the probability of two collision events is $\frac1N$
            -  For this particular choice of four lineages, both collisions happen with probability $\frac{1}{N^2}$
            -  Since there are fewer than $j^4$ ways of choosing $A, B, C,$ and $D$, the probability $< \frac{j^4}{N^2}$

#### The Expected Time Until Coalescence. 
- Approx. view of the process
    - Starting with $k$ distinct lineages.
    - In each generation, probability of colliding $= \frac{k(k−1)}{2N}$.
    - Once a collision happens, we have $k − 1$ distinct lineages.
    - Repeat until $k$ becomes $1$
    - Example of $k=6$
        - ![](https://i.imgur.com/xqcPJIR.png)
- $X = X_k + X_{k−1} + X_{k−2} + · · · + X_2$
    - $X_j$: Beginning with $j$ lineages, the number of steps until this number of lineages is reduced to $j − 1$
- $E[X] = E [X_k] + E [X_{k−1}] + · · · + E [X_2]$
    - $E[X_j] = Pr[X_j≥ 1] + Pr [X_j ≥ 2] + Pr [X_j ≥ 3] + · · ·$$=1 + (1 − p) + {(1 − p)}^2 + {(1 − p)}^3 + · · ·$$=\frac{1}{1 − (1 − p)} = \frac1p$$=\frac{2N}{j(j − 1)}$
- $E[X]=\frac{2N}{2\times 1}+\frac{2N}{3\times 2}+\frac{2N}{4\times 3}+\cdot \cdot \cdot+\frac{2N}{k(k-1)}$$=2N[ \frac{1}{2\times 1}+\frac{1}{3\times 2}+\frac{1}{4\times 3}+\cdot \cdot \cdot+\frac{1}{k(k-1)}]$$=2N[(\frac11-\frac12)+(\frac12-\frac13)+\cdot \cdot \cdot+(\frac{1}{k-1}-\frac1k)]$$=2N(1-\frac1k)$
- observations
    - Once $k$ becomes large, the expected time to coalescence depends only very weakly on $k$; it is roughly $2N$ as $k$ grows.
    - The breakdown of $X$ lets us appreciate where most of the time is being spent.




