# Dynamic Infection Spread Model Based Group Testing
## 4 Proposed Algorithms and Analysis
### Dynamic Individual Testing Algorithm  
In dynamic individual testing algorithm, we do not utilize the group testing approach, and uniformly randomly select \(T\) individuals to individually test at each time instance \(t\geq 1\), from the non-isolated individuals. In order to analyze the performance of our dynamic individual testing algorithm, we use the general result of Theorem 1. First, we show that the dynamic individual testing algorithm satisfies the symmetry and convergence criteria in (3) and (4). Since the process of selection of individuals to be tested is repeated at each time instance with uniformly random selections, as well as the infection spread process, dynamic individual testing algorithm is symmetric. We show that dynamic individual testing algorithm also satisfies the convergence criterion (4) in the following lemma. For the range of the testing capacity \(T\), we focus on the case of \(T<n\), since when \(T\geq n\), at one time instance, everyone can be tested individually and the infection will be under control trivially. **Lemma 6**: _For constant \(T\) and \(n\), dynamic individual testing algorithm satisfies the convergence criterion_  
\[\lim_{t\rightarrow\infty}P(U_{i}(t)=1)=0,\quad i\in[n] \tag{33}\]  
Proof. : First, the probability that an infected individual is detected at a time instance \(t\), denoted by \(1-p^{\prime}(t)\) is  
\[1-p^{\prime}(t) =E[1-p^{\prime}_{\gamma(t-1)}(t)] \tag{34}\] \[=E\bigg{[}\frac{T}{n-\gamma(t-1)}\bigg{]}\] (35) \[\geq\frac{T}{n} \tag{36}\]  
where \(p^{\prime}_{\gamma(t-1)}(t)\) denotes the probability of the conditional event that an infected individual is not detected at the time instance \(t\) given \(\gamma(t-1)\). Now, since the conditional events of detection given that the individual is infected are independent across time due to the uniform random selection of tested individuals at each time instance, and the fact that  
\[\sum_{i=1}^{\infty}(1-p^{\prime}(i))\geq\sum_{i=1}^{\infty}\frac{T}{n} \tag{37}\]  
since the right hand side of (37) grows to infinity, from the second Borel-Cantelli lemma, the conditional detection event occurs infinitely often, i.e., let \(D_{t}\) denote the event that the individual \(i\) is identified at time \(t\), then  
\[P(\limsup_{t\rightarrow\infty}D_{t})=1 \tag{38}\]  
which yields the desired result of \(\lim_{t\rightarrow\infty}P(U_{i}(t)=1)=0\). Next, we consider a weak version of our algorithm, where at each time instance, during the testing phase, instead of selecting \(T\) individuals to test from \(n-\gamma(t)\) non-isolated individuals, we select \(T\) individuals from \(n\) individuals, including the isolated ones, whose test results will be negative. For the weak version of the dynamic individual testing algorithm, we have  
\[1-p^{\prime}(t)=\frac{T}{n},\quad t>0 \tag{39}\]which is the identification probability of an individual at time \(t\). Moreover, since it is an upper bound for the identification probability of an individual for the original dynamic individual testing algorithm, we have  
\[\lim_{t\to\infty}E[\alpha_{orig}(t)]\geq\lim_{t\to\infty}E[\alpha_{weak}(t)] \tag{40}\]  
Since the weak dynamic individual testing algorithm is a symmetric and converging algorithm (note that the result of Lemma 6 still holds) and due to the fact that \(p^{\prime}(t)\) is constant in the weak dynamic individual testing algorithm, we can directly use the result of Lemma 5, due to the fact that the vanishing covariance criteria are already satisfied. Now, using Theorem 1, we have the following result for the weak dynamic individual testing algorithm.