key: cord-0490099-vh3fkb1x
authors: Braca, Paolo; Gaglione, Domenico; Marano, Stefano; Millefiori, Leonardo M.; Willett, Peter; Pattipati, Krishna
title: Quickest Detection of COVID-19 Pandemic Onset
date: 2020-11-20
journal: nan
DOI: nan
sha: cc19dbc5dde5fbfcc6af9ff59b240cca739bc4d8
doc_id: 490099
cord_uid: vh3fkb1x

When should restrictive measures be taken to contain the COVID-19 pandemic explosion? An important role for interpreting the pandemic data in a fully rational manner, and thus proactively supporting the political decision makers, is played by signal processing tools. In this paper, we exploit quickest-detection theory applied to pandemic time-series to predict the explosion of COVID-19 infection on a large scale. We develop a version of the celebrated Page's CUSUM test, specifically tailored to pandemic data. Its application to the publicly-available sequence of new positive individuals per day, from different countries, is detailed in [1].

onset of the pandemic explosion. To this aim, we consider an abbreviated observation model, built on the basic concept that the pandemic evolution is essentially a multiplicative phenomenon.

We model the number of new positive individuals on day n, say p n , as the number p n−1 of new positive individuals on day n − 1, multiplied by a random variable x n . Further including a "noise" term w n , yields the iterative scheme p n = p n−1 x n + w n , n ≥ 1,

for some p 0 . Model (1) , under various assumptions for the sequences {(x n , w n )}, is known as a perpetuity and appears in many disciplines [23] - [25] . We assume that the noise term in (1) is negligible, yielding 1 :

for some p 0 > 0. In this article, we refer to model (2) , in which x 1 , x 2 , . . . are independent random variables. This is akin to the popular random walk model, with the difference that the independence of the increments of the random walk is replaced with the independence of the ratios p n /p n−1 . Model (2) has been derived from SIR-like models and validated on COVID-19 pandemic data in [1] , where it is also shown that the x k 's closely follow a Gaussian distribution with (unknown) time-varying expected value Ex k , and a common standard deviation 2 σ. As long as Ex k < 1, the sequence {p n } tends to decrease exponentially fast, while, for Ex n > 1, {p n } tends to increase exponentially fast. We are interested in quickly detecting the passage from the former situation (a controlled regime) to the latter (critical). Detecting this change of regime can be cast in terms of a binary decision problem between two hypotheses, referred to as the null and the alternative, as discussed next.

Along the same lines of the derivations of Page's test, see e.g., [12, Sec. 2.2.3] or [26, Sec. 8.2] , we consider the following decision problem involving two statistical hypotheses with independent data:

null :

x k ∼ N (µ 0,k , σ), k = 1, . . . , n,

alternative :

In (3), {x k } n k=1 are the data available to the decision maker, 1 ≤ j ≤ n + 1 is an unknown deterministic change time and the standard deviation σ is assumed known. Note in (3) that in the case j = n + 1, the alternative hypothesis is equivalent to the null one, i.e., there is no change of regime. Different from the classical assumption of Page's test, in our problem, the expected values before and after the change are unavailable. Accordingly, we model {µ 0,k } n k=1 and {µ 1,k } n k=1 as unknown deterministic sequences and we assume that they satisfy the following constraints:

Thus, model (3) contains 2n + 1 unknown parameters: the index of change j and the two sequences of the expected values. In (4), the most natural choice is δ ℓ = δ u = 1, but it is convenient to consider the general case having an implied hysteresis. For example, δ u may be specified based on tolerable time to reach hospital capacity, while δ ℓ may be specified based on time people can endure restrictions before reopening the economy or tolerable level of positive cases. One might also consider

in place of (4). In some sense this might be more natural, since the mean levels before and after the change remain assumed unknown, but are merely constant. However, formulation (5) does not admit a recursive Page-like procedure whereas MAST that results from (4) does.

According to the Generalized Likelihood Ratio Test (GLRT) principle [8] , [27] , the decision statistic for problem (3) is 

where the equality follows by recognizing that each factor of the products involves a single value of µ 0,k or µ 1,k and making explicit the constraints in (4). The suprema over µ 0,k and µ 1,k appearing in the above expression can be computed in closed form, as follows:

sup

which means that the ML (maximum likelihood) estimates of the unknown parameters are, respectively,

This yields the GLRT statistic in the form

or, equivalently, taking the logarithm:

where

The passage from the controlled to the critical regime is declared at the smallest n such that

where the threshold level γ is selected to trade-off decision delay and risk, two quantities that will be defined in Sec. III. The test in (12) will be referred to as MAST(δ ℓ , δ u ) -an acronym for mean-agnostic sequential test -with boundaries δ ℓ and δ u . The subscript n appended to T n (δ ℓ , δ u ) denotes its dependence on the stream of data x 1 , . . . , x n , and the subscript j : n appended to T j:n (δ ℓ , δ u ) denotes its dependence on x j , . . . , x n . Finally, by introducing the non-linearity

we have T j:n (δ ℓ , δ u ) = n k=j g(x k ; δ ℓ , δ u ). As a sanity check, let us assume that values of x k closer to δ ℓ are confused with δ ℓ and, likewise, values of x k closer to δ u are confused with δ u . Then, we see from (11) that the contribution to T j:n (δ ℓ , δ u ) provided by the sample x k is ±(δ u − δ ℓ ) 2 /(2σ 2 ), where the negative sign applies to the former case and the positive one to the latter. In the actual operation of T j:n (δ ℓ , δ u ), the contribution given by the sample x k is regulated by its distance to the boundaries, as shown in (13):

• values x k ≤ δ ℓ give a negative contribution proportional to the square of the distance of x k from the upper boundary δ u ; • values δ ℓ ≤ x k < δ u give a linear contribution, whose sign depends on which boundary x k is closest to; • values x k > δ u give a positive contribution proportional to the square of the distance of x k from the lower boundary δ ℓ .

Using the non-linearity of (13) in (10), one gets

where we have used n j=n+1 g(x k ; δ ℓ , δ u ) = 0. The MAST(δ ℓ , δ u ) decision statistic (14) can be expressed in recursive form. To see this, let us define S m = max 1≤j≤m G m j , with G m j = m k=j g(x k ; δ ℓ , δ u ), m = 1, . . . , n. By using the notation (x) + = max[0, x], we see that (14) can be written as T n (δ ℓ , δ u ) = (S n ) + . Then, 

We have thus arrived at the recursive expression for the decision statistic: T 0 (δ ℓ , δ u ) = 0 and, for n ≥ 1, T n (δ ℓ , δ u ) = g(x n ; δ ℓ , δ u ) + T n−1 (δ ℓ , δ u ), if g(x n ; δ ℓ , δ u ) + T n−1 (δ ℓ , δ u ) ≥ 0, and T n (δ ℓ , δ u ) = 0, otherwise. Equivalently: T 0 (δ ℓ , δ u ) = 0, and, for n ≥ 1,

We now consider two special cases. First, let δ ℓ = δ u = δ, a case referred to as the MAST(δ) detector, with decision statistic T 0 (δ) = 0 and, for n ≥ 1, T n (δ) = max 0, T n−1 (δ) + (x n − δ) 2 2σ 2 sign(x n − δ) . (17) Further assuming δ = 1 in (17), yields a decision procedure that we simply call MAST, whose decision statistic T n (1) is denoted by T n : T 0 = 0 and, for n ≥ 1,

The second special case is when δ ℓ = 1−α and δ u = 1+α, for some 0 < α < 1, which is relevant in connection to Page's test, as discussed next. As is well-known, if the mean values of the observed sequence before and after the change are constant and known, say µ 0,n = 1 − α and µ 1,n = 1 + α, the statistic to be compared to a suitable threshold level would be the CUSUM [11] - [13] : Q 0 = 0 and, for n ≥ 1,

For 1 − α ≤ x k ≤ 1 + α, Eq. (13) gives g(x k ; 1 − α, 1 + α) = 2α σ 2 (x k − 1), which shows that the decision statistic T n (1 − α, 1+α) in (14) operates exactly as the Page's test for samples

The test based on (19) is the optimal quickest-detection Page's test. Different optimality criteria have been advocated for the Page's CUSUM test. The "first-order" criterion considers the asymptotic situation in which the mean time between false alarms goes to infinity and asserts that the CUSUM minimizes the worst-case mean delay, where the qualification "worst" refers to both the change time and the behavior of the process before change [12, p. 166 ]. The asymptotic setting is appropriate in the analysis of pandemic data, because one wants to ensure very small false alarm rates.

It is worth noting that the MAST statistic in (18) is formally obtained by replacing the unknown value of α appearing in the CUSUM statistic, with an estimate thereof α n = |x n − 1| (constant factors can be incorporated in the threshold). This suggests an analogy between MAST for quickest-detection problems and the energy detector for testing the presence of an unknown time-varying deterministic signal buried in Gaussian noise, in the classical hypothesis testing framework [27] .

The performance of MAST(δ ℓ , δ u ) is expressed in terms of mean delay time ∆ and false alarm probability P f . The mean delay ∆ is the difference between the time at which the MAST(δ ℓ , δ u ) statistic T n (δ ℓ , δ u ) crosses a preassigned threshold level γ, see (12) , and the time of passage from the controlled to the critical regime. In the critical regime, the pandemic grows exponentially fast and it is therefore important to ensure that ∆ is as small as possible. This requirement is in contrast with the requirement P f ≪ 1. The false alarm probability P f is defined as the reciprocal of the mean time between two false alarms 3 . In turn, the mean time between false alarms is the mean time between two threshold crossings, assuming that the decision statistic is reset to zero at any threshold crossing event, occurring in the controlled regime. Because of the huge social and economic impact of the measures presumably taken by the authorities when passage into the critical regime is detected, it is evident that P f must be extremely small. The same performance indices ∆ and P f used to characterize MAST(δ ℓ , δ u ) are used for the Page's test.

We now investigate the performance of MAST(δ ℓ , δ u ) by computer experiments, limiting the analysis to the case δ ℓ = δ u = 1, i.e., the simple MAST. The performance of the Page's test is used as a benchmark. Let us consider the following "scenario 1". Fix α > 0. Suppose that the state of nature (mean value of the x n 's) is µ 0,n = 1 − α for all n in the controlled regime; likewise, suppose µ 1,n = 1 + α for all n in the critical regime. By standard Monte Carlo counting, for MAST we found that the delay ∆ varies almost linearly with the threshold level γ, and that log 10 P f varies almost linearly with γ. The same approximate behavior is found, again by standard Monte Carlo counting, for the clairvoyant Page's test aware of the mean values µ 0,n = 1 − α and µ 1,n = 1 + α: the mappings γ → ∆ and γ → log 10 P f are approximately linear. These numerical analyses are not detailed for the sake of brevity. The observed linear behavior is known for the Page's test, at least when the threshold γ is sufficiently large, in view of the Wald's approximation, see, e.g. [12, Eq. 5.2.44 ]. In the present Gaussian case, more accurate formulas -known as Siegmund's approximations -are also available for the performance of the Page's test [12, Eqs. 5.2.64, 5.2.65] .

We assume that the aforementioned linear mappings observed for MAST and Page's test hold true for any value of the threshold, and this assumption allows us to consider values of the mean delay and (especially) of false alarm probability that would be difficult to obtain by standard Monte Carlo analysis. In this way, we obtain the operational curve of the two decision systems shown in Fig. 1 . The operational curve is the relationship between log 10 P f and ∆. As expected, Page's test outperforms the mean-agnostic MAST, because the Page's test is optimal for the case addressed in scenario 1.

The same numerical analysis has been conducted for "scenario 2", also shown in Fig. 1 . In scenario 2, we suppose that in the controlled regime, any µ 0,n is an instantiation of a uniform random variable with support (1 − α, 1), while in the critical regime any µ 1,n is an instantiation of a uniform random variable with support (1, 1 + 10 α). To implement the Page's test, it is assumed that the mean values are constant, i.e., µ 0,n = 1 − α and µ 1,n = 1 + α, as in scenario 1. Of course, no assumption about the mean values is instead needed for implementing the MAST test, except that they are bounded by one. We see that MAST outperforms Page's test, confirming its effectiveness when the mean values {µ 0,n } and {µ 1,n } are unknown, except for being bounded as shown in (4), namely µ 0,n ≤ 1 and µ 1,n > 1, for all n.

This article derived a sequential test called MAST, which is used in [1] , to detect passage from the controlled regime in which the COVID-19 pandemic is restrained, to the critical regime in which the infection spreads exponentially fast. MAST is a variation of the celebrated Page's test based on the CUSUM statistic, designed for cases in which the expected values of the data are bounded below a lower barrier δ ℓ in the controlled regime, and above an upper barrier δ u in the critical one, but are otherwise unknown. We show that MAST admits a recursive form and in the simplest case δ ℓ = δ u = 1, is formally obtained from the Page's test with nominal expected values 1 ± α, by replacing α with an estimate thereof. The performance of MAST is investigated by computer experiments. If the the expected values of the data are constant and known, the performance loss of MAST with respect to the optimal Page's test is moderate. In pandemic scenarios, lacking knowledge of the expected values of the data, MAST can well overcome the Page's test designed with nominal values of the unknowns. Finally, we would like to stress that the domain of application of MAST goes beyond the specific example of COVID-19 pandemic addressed here, to cover different change-detection applications in the presence of data uncertainty.

Quickest detection of critical COVID-19 phases: When should restrictive measures be taken?

How will country-based mitigation measures influence the course of the COVID-19 epidemic

Feasibility of controlling COVID-19 outbreaks by isolation of cases and contacts

The socio-economic implications of the coronavirus pandemic (COVID-19): A review

COVID-19 pandemic, oil prices, stock market, geopolitical risk and policy uncertainty nexus in the US economy: Fresh evidence from the wavelet-based approach

Global supply-chain effects of COVID-19 control measures

Covid-19 impact on global maritime mobility

An Introduction to Signal Detection and Estimation

Testing Statistical Hypotheses

Mathematical Statistics

Continuous inspection schemes

Detection of abrupt changes: theory and application

Quickest Detection

Selective review of offline change point detection methods

A contribution to the mathematical theory of epidemics

Monitoring and prediction of an epidemic outbreak using syndromic observations

Evaluation and prediction of the COVID-19 variations at different input population and quarantine strategies, a case study in Guangdong province, China

Effective containment explains subexponential growth in recent confirmed COVID-19 cases in China

Adaptive Bayesian learning and forecasting of epidemic evolution -Data analysis of the COVID-19 outbreak

A primer on stochastic epidemic models: Formulation, numerical simulation, and analysis

Substantial undocumented infection facilitates the rapid dissemination of novel Coronavirus (SARS-CoV-2)

The effect of travel restrictions on the spread of the 2019 novel Coronavirus (COVID-19) outbreak

On a stochastic difference equation and a representation of non-negative infinitely divisible random variables

Perpetuities and random equations

Renorming divergent perpetuities

Sequential analysis: Hypothesis testing and changepoint detection

Detection Theory