# Dynamic Infection Spread Model Based Group Testing
## 4 Proposed Algorithms and Analysis  
In this section, we propose two algorithms and analyze their performances. The first algorithm does not utilize the group testing approach and it is based on the idea of dynamically and individually testing the population. The second algorithm consists of a group testing approach at each time instance, similar to the original idea of [PERSON] [1] in a dynamic setting. Before stating these two algorithms and further analyzing their performances individually, we first state general results. Symmetric and Converging Dynamic Testing Algorithms: In our analysis, we focus on symmetric and converging dynamic testing algorithms, which satisfy the symmetry criterion,  
\[ \begin{array}{c}P(U_{i}(t)=k)=P(U_{j}(t)=k),\quad i,j\in[n]\\ k\in\{0,1,2\}\quad t\geq 0\end{array}  \tag{3}\]  
and convergence criterion,  
\[\lim_{t\to\infty}P(U_{i}(t)=1)=o(1/n),\quad i\in[n] \tag{4}\]  
Furthermore, we assume that the probability of an individual not being identified in the tests at time \(t\), denoted by \(p^{\prime}(t)\), only depends on the testing capacity \(T\), \(\alpha(t)\), \(\lambda(t)\) and \(\gamma(t)\). Note that, \(\alpha(t)+\lambda(t)+\gamma(t)=n\) for all time instances \(t\). Infection Spread Probability: We consider \(q=o(1/n)\) for the infection spread probability \(q\). This is a practical assumption since \(q\) is the probability of the event of infection spread that is realized independently for every element of the set product of the infected individuals and susceptible individuals, at each time instance. We analyze the long term behavior of the system in the average-case, i.e., we focus on the terms \(E[\alpha(t)]\), \(E[\lambda(t)]\) and \(E[\gamma(t)]\) when \(t\) is large enough. **Lemma 1**. : _When a symmetric and converging dynamic testing algorithm is implemented,_  
\[\lim_{t\to\infty}E[\lambda(t)]=o(1) \tag{5}\]  
_and thus, the system approaches to steady state, in the average-case._  
Proof. : Note that all three system functions \(\alpha(t)\), \(\lambda(t)\) and \(\gamma(t)\) can be written as the summation of \(n\) indicator functions  
\[E[\lambda(t)] =E\Biggl{[}\sum_{i=1}^{n}\mathbb{1}\left\{U_{i}(t)=1\right\}\Biggr{]} \tag{6}\] \[=\sum_{i=1}^{n}E\Bigl{[}\mathbb{1}\left\{U_{i}(t)=1\right\}\Bigr{]}\] (7) \[=\sum_{i=1}^{n}P(U_{i}(t)=1)\] (8) \[=nP(U_{i}(t)=1) \tag{9}\]  
which results in \(\lim_{t\to\infty}E[\lambda(t)]=no(1/n)\), due to converging algorithm assumption (4), which is equal to \(o(1)\). Note that, when the system reaches a state where \(\lambda(t)=0\), then there will not be further change of the infection status of the individuals, i.e., the infection will be under control. The following lemma is useful for the justification of the average-case analysis of our system. **Lemma 2**. : _When a symmetric and converging dynamic testing algorithm is implemented, we have \(\lim_{t\to\infty}P(\lambda(t)>\epsilon)=o(1)\) for arbitrarily small, constant, \(\epsilon\in\mathbb{R}\)._Proof. : Since \(\lambda(t)\geq 0\) for all \(t\geq 0\), we can apply [PERSON]'s inequality,  
\[\lim_{t\to\infty}P(\lambda(t)>\epsilon) \leq\lim_{t\to\infty}\frac{E[\lambda(t)]}{\epsilon} \tag{10}\] \[=o(1) \tag{11}\]  
where (10) follows from the fact that \(P(\lambda(t)>\epsilon)\leq\frac{E[\lambda(t)]}{\epsilon}\) for all \(t\geq 0\), and (11) follows from the result of Lemma 1. The focus of our analysis is to give a lower bound for the number of susceptible individuals (who have never got infected throughout the process) when the infection is brought under control, in the average-case. In order to analyze the long term behavior of \(E[\alpha(t)]\), we have to analyze the long term behavior of \(P(U_{i}(t)=0)\). A direct calculation of this probability is not analytically tractable, however, by conditioning on \(\lambda(t-1)\), we give a recursive asymptotic calculation. Before stating the recursive relation, we first prove a lemma that will be useful.