key: cord-0647834-tx21z2hr
authors: Bastopcu, Melih; Ulukus, Sennur
title: Timely Tracking of Infection Status of Individuals in a Population
date: 2020-12-24
journal: nan
DOI: nan
sha: f1452a07db68edd104894414f422115c5183e7b1
doc_id: 647834
cord_uid: tx21z2hr

We consider real-time timely tracking of infection status (e.g., covid-19) of individuals in a population. In this work, a health care provider wants to detect infected people as well as people who recovered from the disease as quickly as possible. In order to measure the timeliness of the tracking process, we use the long-term average difference between the actual infection status of the people and their real-time estimate by the health care provider based on the most recent test results. We first find an analytical expression for this average difference for given test rates, and given infection and recovery rates of people. Next, we propose an alternating minimization based algorithm to minimize this average difference. We observe that if the total test rate is limited, instead of testing all members of the population equally, only a portion of the population is tested based on their infection and recovery rates. We also observe that increasing the total test rate helps track the infection status better. In addition, an increased population size increases diversity of people with different infection and recovery rates, which may be exploited to spend testing capacity more efficiently, thereby improving the system performance. Finally, depending on the health care provider's preferences, test rate allocation can be altered to detect either the infected people or the recovered people more quickly.

We consider the problem of timely tracking of an infectious disease, e.g., covid-19, in a population of n people. In this problem, a health care provider wants to detect infected people as quickly as possible in order to take precautions such as isolating them from the rest of the population. The health care provider also wants to detect people who recovered from the disease as soon as possible since these people need to return to work which is especially critical in sectors such as health care, food retail, and public transportation. Ideally, the health care provider should test all people all the time. However, as the total test rate is limited, the question is how frequently the health care provider should apply tests on these people when their infection and recovery rates are known. In a broader sense, this problem is related to timely tracking of multiple processes in a resource-constrained setting where each process takes binary values of 0 and 1 with different change rates.

Recent studies have shown that people who recovered from infectious diseases such as covid-19 can be reinfected. Furthermore, the recovery times of individuals from the disease may vary significantly. For these reasons, in this problem, the ith This work was supported by NSF Grants CCF 17-13977 and ECCS 18-07348. person gets infected with rate λ i which is independent of the others. Similarly, the ith person recovers from the disease with rate µ i . 1 We denote the infection status of the ith person as x i (t) (shown with the black curves on the left in Fig. 1 ) which takes the value 1 when the person is infected and the value 0 when the person is healthy. The health care provider applies tests to people marked as healthy with rate s i and to people marked as infected with rate c i . Based on the test results, the health care provider forms an estimate for the infection status of the ith person denoted byx i (t) (shown with the blue curves on the right in Fig. 1 ) which takes the value 1 when the most recent test result is positive and the value 0, otherwise.

We measure the timeliness of the tracking process by the difference between the actual infection status of people and the real-time estimate of the health care provider which is based on the most recent test results. We note that the difference can occur in two different cases: i) when the person is sick (x i (t) = 1) and the health care provider maps this person as healthy (x i (t) = 0), and ii) when the person recovers from the disease (x i (t) = 0) but the health care provider still considers this person as infected (x i (t) = 1). The former case represents the error due to late detection of infected people, while the latter case represents the error due to late detection of healed people. Depending on the health care provider's preferences, detecting infected people may be more important than detecting recovered people, or vice versa.

Age of information has been proposed to measure timeliness of information in communication systems, and studied in the context of queueing networks, caching systems, energy harvesting systems, scheduling in networks, multi-hop multicast networks, remote estimation, lossless and lossy source coding, computation-intensive systems, vehicular, IoT, UAV systems, and so on [1]- [36] . Most relevant to our work, the real-time timely estimation of a single and multiple counting processes [22] , [23] , a Wiener process [24] , a random walk process [25] , a binary Markov source [26] have been studied. The work that is closest to our work is reference [26] where the remote estimation of a symmetric binary Markov source is studied in a time-slotted system by finding the optimal sampling policies via formulating a Markov Decision Process (MDP) for realtime error, AoI and AoII metrics. Different from [26] , in our work, we consider real-time timely estimation of multiple nonsymmetric binary sources for a continuous time system. We note that in our work, the sampler (the health care provider) does not know the states of the sources (infection status of people), and thus takes the samples (applies medical tests) randomly with fixed rates. Thus, in our work, we optimize the test rates of people to minimize the real-time estimation error.

In this paper, we consider the real-time timely tracking of infection status of n people. We first find an analytical expression for the long-term average difference between the actual infection status of people and the estimate of the health care provider based on test results. Then, we propose an alternating minimization based algorithm to find the test rates s i and c i for all people. We observe that if the total test rate is limited, we may not apply tests on all people equally. Increasing the total test rate helps track the infection status of people better, and increasing the size of the population increases diversity which may be exploited to improve the performance. Finally, depending on the health care provider's priorities, we can allocate more tests to people marked as healthy to detect the infections more quickly or to people marked as infected to detect the recoveries more quickly.

We consider a population of n people. We denote the infection status of the ith person at time t as x i (t) (black curve in Fig. 2(a) ) which takes binary values 0 or 1 as follows,

In this paper, we consider a model where each person can be infected multiple times after recovering from the disease. We denote the time interval that the ith person stays healthy for the jth time as W i (j) which is exponentially distributed with rate λ i . We denote the recovery time for the ith person after infected with the virus for the jth time as R i (j) which is exponentially distributed with rate µ i .

A health care provider wants to track the infection status of each person. Based on the test results at times t i,ℓ , the health 1 − θ care provider generates an estimate for the status of the ith person denoted asx i (t) (blue curve in Fig. 2 (a)) bŷ

Whenx i (t) is 1, the health care provider applies the next test to the ith person after an exponentially distributed time with rate c i . Whenx i (t) is 0, the next test is applied to the ith person after an exponentially distributed time with rate s i . An estimation error happens when the actual infection status of the ith person, x i (t), is different than the estimate of the health care provider,x i (t), at time t. This could happen in two ways: when x i (t) = 1 andx i (t) = 0, i.e., when the ith person is sick, but it has not been detected by the health care provider, and when x i (t) = 0 andx i (t) = 1, i.e., when the ith person has recovered, but the health care provider does not know that the ith person has recovered.

We denote the error caused by the former case, i.e., when x i (t) = 1 andx i (t) = 0, by ∆ i1 (t) (green areas in Fig. 2 

and we denote the error caused by the latter case, i.e., when Fig. 2 

Then, the total estimation error for the ith person ∆ i (t) is

where θ is the importance factor in [0, 1]. A large θ gives more importance to the detection of infected people, and a small θ gives more importance to the detection of recovered people. We define the long-term weighted average difference between x i (t) andx i (t) as

Then, the overall average difference of all people ∆ is

Our aim is to track the infection status of all people. Due to limited resources, there is a total test rate constraint

Thus, our aim is to find the optimal test rates s i and c i to minimize ∆ in (7) while satisfying this total test rate constraint. We formulate the following problem,

In the next section, we find the total average difference ∆.

We first find analytical expressions for ∆ i1 (t) in (3) and ∆ i2 (t) in (4). We note that ∆ i1 (t) can be equal to 1 when x i (t) = 0 and is always equal to 0 whenx i (t) = 1. Assume that at time 0, both x i (0) andx i (0) are 0. After an exponentially distributed time with rate λ i , which is denoted by W i , the ith person is infected, and thus x i (t) becomes 1. At that time, sincex i (t) = 0, ∆ i1 (t) becomes 1. ∆ i1 (t) will be equal to 0 again either when the ith person recovers from the disease which happens after R i which is exponentially distributed with rate µ i or when the health care provider performs a test on the ith person after D i which is exponentially distributed with rate s i . We define T m (i) as the earliest time at which one of these two cases happens, i.e., T m (i) = min{R i , D i }. We note that T m (i) is also exponentially distributed with rate µ i +s i , and we have P(T m (i) = R i ) = µi µi+si and P(T m (i) = D i ) = si µi+si . If the ith person recovers from the disease before testing, we return to the initial case where both x i (t) andx i (t) are equal to 0 again. In this case, this cycle repeats itself, i.e., the ith person becomes sick again after W i and ∆ i1 (t) remains as 1 until either the person recovers or the health care provider performs a test which takes another T m (i) duration. If the health care provider performs a test before the person recovers, thenx i (t) becomes 1. We denote the time interval for whicĥ x i (t) stays at 0 as I i1 which is given by

where

are exponentially distributed with rates s i and λisi µi+si , respectively.

Whenx i (t) = 1, the health care provider marks the ith person as infected. The ith person recovers from the virus after R i . After the ith person recovers, either the health care provider performs a test after Z i which is exponentially distributed with rate c i or the ith person is reinfected with the virus which takes W i time. We define T u (i) as the earliest time at which one of these two cases happens, i.e., T u (i) = min{W i , Z i }. Similarly, we note that T u (i) is exponentially distributed with rate λ i + c i , and we have P(T u (i) = W i ) = λi λi+ci and P(T m (i) = Z i ) = ci λi+ci . If the person is reinfected with the virus before a test is applied, this cycle repeats itself, i.e., the ith person recovers after another R i , and then either a test is applied to the ith person, or the person is infected again which takes another T u (i). If the health care provider performs a test to the ith person before the person is reinfected, the health care provider marks the ith person as healthy again, i.e.,x i (t) becomes 0. We denote the time interval thatx i (t) is equal to 1 as I i2 which is given by

where K 2 is geometric with rate P(T u (i) = Z i ) = ci λi+ci . Similarly, K2 ℓ=1 T u (i, ℓ) and K2 ℓ=1 R i (ℓ) are exponentially distributed with rates c i and ciµi λi+ci , respectively. As

We denote the time interval between the jth and (j + 1)th times thatx i (t) changes from 1 to 0 as the jth cycle I i (j) where I i (j) = I i1 (j) + I i2 (j). We note that ∆ i1 (t) is always equal to 0 during I i2 (j), i.e.,x i (t) = 1, and ∆ i1 (t) is equal to 1 when x i (t) = 1 in I i1 (j). We denote the total time duration when ∆ i1 (t) is equal to 1 as T e,1 (i, j) during the jth cycle where T e,1 (i, j) = K1 ℓ=1 T m (i, ℓ). Thus, we have E[T e,1 (i)] = 1 si . Then, using ergodicity, similar to [4] , ∆ i1 is equal to

Thus, we have

Next, we find ∆ i2 . We note that ∆ i2 (t) is equal to 1 when x i (t) = 0 in I i2 (j) and is always equal to 0 during I i1 (j). Similarly, we denote the total time duration where ∆ i2 (t) is equal to 1 in the jth cycle I i (j) as T e,2 (i, j) which is equal to T e,2 (i, j) = K2 ℓ=1 T u (i, ℓ). Thus, we have E[T e,2 (i)] = 1 ci . Then, similar to ∆ i1 in (13), ∆ i2 is equal to

By using (5), (14) , and (15), we obtain ∆ i as

Then, by inserting (16) in (7), we obtain ∆. In the next section, we solve the optimization problem in (8).

IV. OPTIMIZATION OF AVERAGE DIFFERENCE In this section, we solve the optimization problem in (8) . Using ∆ i in (16) in (7), we rewrite (8) as

We define the Lagrangian function [38] for (17) as

where β ≥ 0, ν i ≥ 0, and η i ≥ 0. The KKT conditions are

for all i. The complementary slackness conditions are

First, we find s i . From (19) , we have

When θ(c i + λ i ) ≥ (1 − θ)µ i , we solve (22) for s i as

where we used the fact that we either have s i > 0 and ν i = 0, or s i = 0 and ν i ≥ 0, due to (21) . Here, (·) + = max(·, 0). Finally, when θ(c i +λ i ) < (1−θ)µ i , we have ∂∆i ∂si > 0, and thus it is optimal to choose s i = 0 as our aim is to minimize ∆ in (7) . In this case, when s i = 0, we have ∆ i = θλi µi+λi which is independent of the value of c i . As we obtain the same ∆ i for all values of c i , and the total update rate is limited, i.e., n i=1 s i + c i ≤ C, in this case, it is optimal to choose c i = 0 as well (i.e., when s i = 0).

Next, we find c i . From (20) , we have

When (1 − θ)(µ i + s i ) ≥ θλ i , we solve (24) for c i as

where we used the fact that we either have c i > 0 and η i = 0, or c i = 0 and η i ≥ 0, due to (21) . Next, we show that in the optimal policy, if s i > 0 and c i > 0 for some i, then the total test rate constraint must be satisfied with equality, i.e.,

Lemma 1 In the optimal policy, if s i > 0 and c i > 0 for some i, then we have n i=1 s i + c i = C.

Proof: The derivatives of ∆ i with respect to s i and c i are

We note that s i > 0 in (23) implies that θ(c i +λ i ) > (1−θ)µ i . In this case, we have ∂∆i ∂si < 0. Similarly, c i > 0 in (25) implies that (1 − θ)(s i + µ i ) > θλ i . Thus, we have ∂∆i ∂ci < 0.

Therefore, in the optimal policy, if we have s i > 0 and c i > 0 for some i, then we must have n i=1 s i + c i = C. Otherwise, we can further decrease ∆ in (7) by increasing c i or s i .

Next, we propose an alternating minimization based algorithm for finding s i and c i . For this purpose, for given initial (s i , c i ) pairs, we define φ i as

Then, we define u i as

From (23) and (25), s i = u i and c i = u n+i , for i = 1, . . . , n. Next, we find s i and c i by determining β in (29) . First, assume that, in the optimal policy, there is an i such that s i > 0 and c i > 0. Thus, by Lemma 1, we must have n i=1 s i + c i = C. We initially take random (s i , c i ) pairs such that n i=1 s i + c i = C. Then, given the initial (s i , c i ) pairs, we immediately choose u i = 0 for φ i < 0. For the remaining u i with φ i ≥ 0, we apply a solution method similar to that in [4] . By assuming φ i ≥ β, i.e., by disregarding (·) + in (29), we solve 2n i=1 u i = C for β. Then, we compare the smallest φ i which is larger than zero in (28) with β. If we have φ i ≥ β, then it implies that u i ≥ 0 for all remaining i. Thus, we have obtained u i values for given initial (s i , c i ) pairs. If the smallest φ i which is larger than zero is smaller than β, then the corresponding u i is negative and we should choose u i = 0 for the smallest nonnegative φ i . Then, we repeat this procedure until the smallest non-negative φ i is larger than β. After determining all u i , we obtain s i = u i and c i = u n+i for i = 1, . . . , n. Then, with the updated values of (s i , c i ) pairs, we keep finding u i 's until the KKT conditions in (19) and (20) are satisfied.

We note that for indices (persons) i for which (s i , c i ) are zero, the health care provider does not perform any tests, and maps these people as either always infected, i.e.,x i (t) = 1 for all t, or always healthy, i.e.,x i (t) = 0. Ifx i (t) = 0 for all t, ∆ i = θλi µi+λi , and ifx i (t) = 1 for all t, ∆ i = (1−θ)µi µi+λi . Thus, for such i, the health care provider should choosex i (t) = 0 for all t, if θλi µi+λi < (1−θ)µi µi+λi , and should choosex i (t) = 1 for all t, otherwise, without performing any tests.

Finally, we note that the problem in (17) is not a convex optimization problem as the objective function is not jointly convex in s i and c i . Therefore, the solutions obtained via the proposed method may not be globally optimal. For that reason, we choose different initial starting points and apply the proposed alternating minimization based algorithm and choose the solution that achieves the smallest ∆ in (7).

In this section, we provide four numerical results. For these examples, we take λ i as where r = 0.9 and a is such that n i=1 λ i = 6. Also, we take µ i as

where q = 1.1 and b is such that n i=1 µ i = 4. Since λ i in (30) decreases with i, people with lower indices get infected more quickly compared to people with higher indices. Since µ i in (31) increases with i, people with higher indices recover more quickly compared to people with lower indices. Thus, low index people get infected quickly and get well slowly.

In the first example, we take the total number of people as n = 10, the total test rate as C = 16, and θ = 0.5. We start with randomly chosen s i and c i such that n i=1 s i + c i = 16, and apply the alternating minimization based method proposed in Section IV. We repeat this process for 30 different initial (s i , c i ) pairs and choose the solution that gives the smallest ∆. In Fig. 4(a) , we observe that the first three people are never tested by the health care provider. We note that s i , which is the test rate whenx i (t) = 0, initially increases with i but then decreases with i. This means that people who get infected rarely are tested less frequently when they are marked as healthy. Similarly, we observe in Fig. 4(a) that c i , which is the test rate whenx i (t) = 1, monotonically increases with i. In other words, people who recover from the virus quickly are tested more frequently when they are marked infected. In Fig. 4(b) , we plot ∆ i resulting from the solution found from the proposed algorithm, ∆ i when the health care provider applies tests to everyone in the population uniformly, i.e., s i = c i = C 2n for all i, and ∆ i when the health care provider applies no tests, i.e., s i = c i = 0 for all i. In the case of no tests, we have ∆ i = min{ θλi µi+λi , (1−θ)µi µi+λi }. We observe in Fig. 4 (b) that the health care provider applies tests on people whose ∆ i can be reduced the most as opposed to uniform testing where everyone is tested equally. Thus, the first three people who have the smallest ∆ i are not tested by the health care provider. With the proposed solution, by not testing the first three people, ∆ i are further reduced for the remaining people compared to uniform testing. For the people who are not tested, the health care provider choosesx i (t) = 1 all the time, i.e., marks these people always sick as θλi µi+λi > (1−θ)µi µi+λi . This is expected as these people have high λ i and low µ i , i.e., they are infected easily and they stay sick for a long time.

In the second example, we use the same set of variables except for the total test rate C. We vary the total test rate C in between 5 and 20. We plot ∆ with respect to C in Fig. 5 . We observe that ∆ decreases with C. Thus, with higher total test rates, the health care provider can tract the infection status of the population better as expected. In the third example, we use the same set of variables except for the total number of people n. In addition, we also use uniform infection and healing rates, i.e., λ i = 6 n and µ i = 4 n for all i, for comparison with λ i in (30) and µ i in (31), while keeping the total infection and healing rates the same, i.e., n i=1 λ i = 6 and n i=1 µ i = 4, for both cases. We vary the number of people n from 2 to 30. We observe in Fig. 6 that when the infection and healing rates are uniform in the population, the health care provider can track the infection status with the same efficiency, even though the population size increases (while keeping the total infection and healing rates fixed). For the case of λ i in (30) and µ i in (31), when we increase the population size, we increase the number of people who rarely get sick, i.e., people with high i indices, and also people who rarely heal from the disease, i.e., people with small i indices. Thus, it gets easier for the health care provider to track the infection status of the people. That is why when we use λ i in (30) and µ i in (31), we observe in Fig. 6 that the health care provider can track the infection status of the people better, even though the population size increases.

In the fourth example, we use the same set of variables as the first example except for the importance factor θ. Here, we vary θ in between 0.2 to 0.7. We plot ∆ in (7),∆ 1 which is Fig. 7(a) . Note that∆ 1 represents the average difference when people are infected, but they have not been detected by the health care provider, and∆ 2 represents the average difference when people have recovered, but the health care provider still marks them as infected. Note that when θ is high, we give importance to minimization of∆ 1 , i.e., the early detection of people with infection, and when θ is low, we give importance to minimization of∆ 2 , i.e., the early detection of people who recovered from the disease. That is why we observe in Fig. 7 (a) that∆ 1 decreases with θ while∆ 2 increases with θ.

We plot the total test rates n i=1 s i and n i=1 c i in Fig. 7(b) . We observe in Fig. 7(b) that if it is more important to detect the infected people, i.e., if θ is high, then the health care provider should apply higher test rates to people who are marked as healthy. In other words, n i=1 s i increases with θ. Similarly, if it is more important to detect people who recovered from the disease, then the health care provider should apply high test rates to people who are marked as infected. That is, n i=1 c i is high when θ is low. Therefore, depending on the priorities of the health care provider, a suitable θ needs to be chosen.

We considered timely tracking of infection status of individuals in a population. For exponential infection and healing processes with given rates, we determined the rates of exponential testing processes. We observed in numerical results that the test rates depend on individuals' infection and healing rates, the individuals' last known state of healthy or infected, as well as the health care provider's priorities of detecting infected people or recovered people more quickly.

Status updates through M/G/1/1 queues with HARQ

Age of information in G/G/1/1 systems

Age-optimal constrained cache updating

Information freshness in cache updating systems

Average age of information for status update systems with an energy harvesting server

Optimal status update for age of information minimization with an energy harvesting source

Age-ofinformation vs. value-of-information scheduling for cellular networked control systems

Sending information through status updates

Age of information minimization for an energy harvesting cognitive radio

Timely updates in energy harvesting two-hop networks: Offline and online policies

Optimizing information freshness in two-hop status update systems under a resource constraint

Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies

A reinforcement learning framework for optimizing age of information in RF-powered communication systems

Minimizing age of information with soft updates

Timely group updating

A reinforcement learning approach to age of information in multi-user networks

The age of information: Real-time status updating by multiple sources

Scheduling policies for minimizing age of information in broadcast wireless networks

Age of information: Whittle index for scheduling stochastic arrivals

Age of information scaling in large networks with hierarchical cooperation

Age of information in multihop multicast networks

Reconstruction of counting process in real-time: The freshness of information through queues

Who should Google Scholar update more often?

Remote estimation of the Wiener process over a channel with random delay

Optimal real-time monitoring of an information source under communication costs

Age of incorrect information for remote estimation of a binary Markov source

Remote estimation over a packet-drop channel with Markovian state

Optimal source codes for timely updates

Selective encoding policies for maximizing information freshness

Age of information with finite horizon and partial updates

Timely distributed computation with stragglers

Optimizing information freshness through computation-transmission tradeoff and queue management in edge computing

Age of information for updates with distortion

Not just age but age and quality of information

Age-optimal sampling and transmission scheduling in multi-source systems

Fundamental limits of ageof-information in stationary and non-stationary environments

Probability and Stochastic Processes

Convex Optimization