Infection in a village

Solution 1:

This answer uses programming to solve the above question, using principles from probability and Markov chains. No closed mathematical formula is provided, although results are shown for $m < 100$ and curve fitting is used to estimate the average survival time for larger numbers.

Initially, I simulated $1000$ runs of different configurations for $3 \lt m \lt 100$ and $0 \leqslant n \leqslant 4$, plotting the results using $95$% confidence intervals:

For the configuration in which $n = 1$, we find that, with $X$ being the week in which the disease last makes a new victim, the following probabilities apply:

$$\begin{cases} P(X = 1) = \frac{1}{m} \\ P(X = x) = \frac{m}{x - 1} \frac{m - x + 1}{m} \frac{x}{m} P(X = x - 1) \end{cases} \iff P(X = x) = \frac{x}{m^x} \frac{(m - 1)!}{(m - x)!}$$

For $n > 1$, Markov chains can be used. For any combination of $m, n$, let us define a state $\{k, l, w\}$ as a tuple containing the number of immune people $k$, the number of infectuous people $l$ and the current week $w$, with $k + l \leqslant m + 1$. From this state, we can transition to any of the states $\{k + l, 0, w + 1\}, \{k + l, 1, w + 1\}, \ldots, \{k + l, \min(n l, m + 1 - k - l), w + 1\}$.

The probability of each possible state transition can be calculated using recursion. The probability that $l$ infectuous people affect $0 \leqslant p \leqslant \min(n l, m + 1 - k - l)$ while $k$ people are immune, can be determined by first considering all possible actions of a single person. This person coughs onto $n$ random people, infecting $i \leqslant \min(n, p)$ people. To do so, this person must randomly choose $i$ healthy people and $n - i$ immune people, which happens with probability:

$$P(i) = \underbrace{\frac{m - k - l + 1}{m} \frac{m - k - l}{m - 1} \cdots \frac{m - k - l - i + 2}{m - i + 1}}_{\text{healthy people}} \\ \underbrace{\frac{k + l - 1}{m - i} \frac{k + l - 2}{m - i - 1} \cdots \frac{k + l - n + i}{m - n + 1}}_{\text{immune people}} {n \choose i}$$

Using this expression, the probability that a total of $p$ people are infected from a given state $\{k, l, w\}$ can be written as:

$$P(\{k + l, p, w + 1\} | \{k, l, w\}) = \sum_{i = 0}^{\min(p, n)} P(i) P(\{k + l, p - i, w + 1\} | \{k + i, l - 1, w\})$$

This formula can be solved recursively until $p = 0$ or $l = 0$. Considering the visited states, it is worth noting that we always start in the state $\{0, 1, 1\}$. Assuming that $m \geqslant n$, this state transitions to the state $\{1, n, 2\}$ with probability $1$. We can then calculate the probability of each successive state, resulting in different Markov chains.

Considering all chains that end in a state in which the number of infectuous people $l$ equals $0$, we can directly calculate the expected time of survival by considering the variable $w$. Using a Python-based implementation to do this for $3 \lt m \lt 100$ and $0 \leqslant n \leqslant 4$ results in:

The results show that the expected surival time is highest for $n = 2$ when $m \leqslant 43$, while it is highest for $n = 1$ when $m \geqslant 44$. Square root curve fitting results in $f(m) \approx 1.25 \sqrt{m} + 0.70$ for $n = 1$, while logarithmic curve fitting results in $f(m) \approx 2.68 \ln(m) - 1.12$ for $n = 2$. Values around the turning point are as follows:

$$\begin{array}{c|c|c} m & n = 1 & n = 2 \\ \hline \text{39} & 8.51 & 8.65 \\ \text{40} & 8.61 & 8.72 \\ \text{41} & 8.71 & 8.79 \\ \text{42} & 8.80 & 8.86 \\ \text{43} & 8.90 & 8.92 \\ \text{44} & 9.00 & 8.99 \\ \text{45} & 9.09 & 9.05 \\ \text{46} & 9.18 & 9.12 \\ \text{47} & 9.27 & 9.18 \\ \text{48} & 9.36 & 9.24 \end{array}$$

The full Python code has been made available here.