Are there needles in a moving haystack? Adaptive sensing for detection of dynamically evolving signals
Rui M. Castro Ervin Tánczos

empty


1]Rui M. Castro
2]Ervin Tánczos
[1]Technische Universiteit Eindhoven 
[2]University of Wisconsin - Madison

Are there needles in a moving haystack?  Adaptive sensing for detection of dynamically evolving signals
    [
    
=======================================================================================================




In this paper we investigate the problem of detecting dynamically evolving signals.  We model the signal as an n dimensional vector that is either zero or has s non-zero components.  At each time step t∈ℕ the non-zero components change their location independently with probability p.  The statistical problem is to decide whether the signal is a zero vector or in fact it has non-zero components.  This decision is based on m noisy observations of individual signal components collected at times t=1,…,m.  We consider two different sensing paradigms, namely adaptive and non-adaptive sensing.  For non-adaptive sensing the choice of components to measure has to be decided before the data collection process started, while for adaptive sensing one can adjust the sensing process based on observations collected earlier.  We characterize the difficulty of this detection problem in both sensing paradigms in terms of the aforementioned parameters, with special interest to the speed of change of the active components.  In addition we provide an adaptive sensing algorithm for this problem and contrast its performance to that of non-adaptive detection algorithms.




§ INTRODUCTION
 

Detection of sparse signals is a problem that has been studied with great attention in the past.  The usual setting of this problem involves a (potentially) very large number of items, of which a (typically) much smaller number may be exhibiting anomalous behavior.  A natural question one can ask if it is possible to reliably detect if there are indeed some items showing anomalous behavior?  Questions like this are encountered in a number of research fields.  Some examples include epidemiology where one wishes to quickly detect an outbreak or the environmental risk factors of a disease <cit.>, identifying changes between multiple images <cit.>, and microarray data studies <cit.> to name a few.

A common point in the examples above is that even though it is not known which items are anomalous, their identity remains fixed throughout the sampling/measurement process.  However, in certain situations the identity of these items may change over time.  

Consider for instance a signal intelligence setting where one wishes to detect covert communications.  Suppose that our task is to survey a signal spectrum, a small fraction of which may be used for communication, meaning that some frequencies would exhibit increased power.  On one hand we do not know beforehand which frequencies are used, but also the other parties may change the frequencies they communicate through over time.  This means we will be chasing a moving target.  This introduces a further hindrance in our ability to detect whether someone is using the surveyed signal spectrum for covert communications.  

Other motivating examples for such a problem include spectrum scanning in a cognitive radio system <cit.>, detection of hot spots of a rapidly spreading disease <cit.>, detection of momentary astronomical events <cit.> or intrusions into computer systems <cit.>.  The main question that we aim to answer in this paper is how the dynamical aspects of the signal affect the difficulty of the detection problem.

In the more classical framework of the signal detection problem, inference is based on observations that are collected non-adaptively.  However, dealing with time-dependent signals naturally leads to a setting where measurements can be obtained in a sequential and adaptive manner, using information gleaned in the past to guide subsequent sensing actions.  Furthermore, in certain situations it is impossible to monitor the entire system at once, but instead one can only partially observe the system at any given time.  

It is known that, in certain situations, adaptive sensing procedures can very significantly outperform non-adaptive ones in signal detection tasks <cit.>.  Hence our goal is to understand the differences between adaptive and non-adaptive sensing procedures when used for detecting dynamically evolving signals, in situations where the system can only be partially monitored.



  
Contributions:
In this paper we introduce a simple framework for studying the detection problem of time-evolving signals.  Our signal of interest is an n-dimensional vector x_t ∈^n, where t∈ denotes the time index.  We take a hypothesis testing point of view.  Under the null the signal is static and equal to the zero vector for all t, while under the alternative the signal is a time-evolving s-sparse vector.  At each time step t∈ we flip a biased coin independently for each non-zero signal component to decide if these will “move” to a different location.  Thus, the coin bias p encodes the speed of change of the signal support in some sense.  At each time step we are allowed to select one component of the signal to observe through additive standard normal noise, and we are allowed to collect up to m measurements.  Our goal is to decide whether the signal is zero or not, based on the collected observations.

We present an adaptive sensing algorithm that addresses the above problem, and show it is near-optimal by deriving the fundamental performance limits of any sensing and detection procedure.  We do this in both the adaptive sensing and non-adaptive sensing settings for a range of parameter values p and s.  It is easy to see that the above problem can not be solved reliably unless we are allowed to collect on the order of n/s measurements.  When the number of measurements is of this order, we can reliably detect the presence of the signal when the smallest non-zero component scales roughly like √(p log (n/s)) in the adaptive sensing setting (Theorems <ref> and <ref>).  In the non-adaptive sensing setting detection is possible only when the smallest non-zero component scales like √(log (n/s)) (Theorem <ref>).  Hence, under the adaptive sensing paradigm the speed of change influences the difficulty of the detection problem, with slowly changing signals being easier to detect.  Contrasting this, in the non-adaptive sensing setting the speed of change appears to have no strong effect in the problem difficulty when m is of the order n/s.  When the number of measurements m is significantly larger than n/s the picture changes quite a bit, and a theoretical analysis of that case is beyond the contribution of this paper.  Nevertheless we provide some simulation results indicating that, in the non-adaptive sensing setting, the signal dynamics will then influence the detection ability.

Despite its simplicity, the setting introduced in this paper provides a good starting point to understand the problem of detecting dynamically evolving signals.  Although we provide several answers in this setting many questions remain (both technical and conceptual).  We hope that this work opens the door for many interesting and exciting extensions and developments, some of which are highlighted in Section <ref>.  



  
Related work: The setting where the identity of the anomalous items is fixed over time has been widely studied in the literature.  Classically this problem has been addressed when each entry of the vector is observed exactly once.  In this context both the fundamental limits of the detection problem and the optimal tests are well understood (see <cit.> and references therein).

The same problem has been investigated in the adaptive sensing setting as well.  In <cit.> the authors provide an efficient adaptive sensing algorithm for identifying a few anomalous items among a large number of items.  These results were generalized in <cit.> to cope with a wide variety of distributions.  The algorithms outlined in these works can in principle also be used to solve the detection problem, that is where only the presence or absence of anomalous items needs to be decided.  In <cit.> and <cit.> bounds on the fundamental difficulty of the estimation problem were derived, whereas in <cit.> bounds for the detection problems were provided as well.  

Our work here has a similar flavor to all the above, but tackling the problem when the anomalous items may change positions while the measurement process is taking place.  This brings a new temporal dimension to the signal detection problems referenced above.  Statistical inference problems pertaining time-dependent signals have been investigated in various settings in the past.  However, the papers referenced below only have varying degrees of connection to the problem we are considering, as despite our best efforts, we were only able to find a few instances that resemble our setting.





A setting that has some degree of temporal dependence is the monitoring of multi-channel systems.  This problem was introduced in <cit.> and later revisited in <cit.> and <cit.>.  In this setting each channel of a multi-channel system contains a Wiener process, a few of which are anomalous and have a deterministic drift.  The observer is allowed to monitor one channel at a time with the goal to localize the anomalous channels as quickly as possible.

Although there is a clear temporal aspect to these problems, the anomalous channels identity is unchanged during the process.

Another prototypical example of inference concerning temporal data is change-point detection in a system involving multiple processes.  In this problem we have multiple sensors observing stochastic processes.  After some unknown time a change occurs in the statistical behavior of some of the processes, and our goal is to detect when such a change occurs as quickly as possible.  This setting has been studied in <cit.>, a Bayesian version of the problem was investigated in <cit.>, while the authors of <cit.> deal with a version of the above problem where only one of the sensors is compromised.

This setting shares similarities to ours, but there are some key differences.  In the change-point detection setting, once a process becomes anomalous it remains so indefinitely.  Since some processes are bound to exhibit anomalous behavior, the goal is to minimize the detection delay.  Contrasting this, in the setting we consider an anomalous process can revert back to the nominal state, and there is a possibility that none of the processes are anomalous at any time.  Hence our goal is to decide between the presence or absence of any anomalous processes over the measurement horizon.

A set of more closely related work is concerned with the spectrum scanning of multichannel cognitive radio systems.  Here the aim is to quickly and accurately determine the availability of each spectrum band of a multi-band system where the occupancy status changes over time.  Alternatively one might only aim to quickly find a single band that is available.  This problem has been studied in <cit.> and <cit.>, in which the authors provide efficient algorithms for the problem at hand.  A very similar problem was investigated in <cit.>, where one observes multiple ON/OFF processes and wishes to catch one in the ON state.

Although the underlying models of these problems come very close to the one we consider, these works are also change-point detection problems in spirit.  Hence a similar comment applies here as well, namely that the goal of the algorithms of <cit.> and <cit.> is to detect a change-point while minimizing some notion of regret (such as detection delay or sampling cost), which is somewhat different to the problem we are aiming to tackle.





  
Organization: Section <ref> introduces the problem setup, including the signal and observation models and the inference goals.  In Section <ref> we introduce an adaptive sensing algorithm and analyze its performance.  Section <ref> is dedicated to the characterization of the difficulty of the detection of dynamically evolving signals.  In particular we show that the algorithm presented in Section <ref> is near-optimal, and examine the difference between adaptive and non-adaptive sensing procedures.  In Section <ref> we present numerical evidence supporting a conjecture on the non-adaptive sensing performance limit in the regime when m is of the order n/s.  Concluding remarks and avenues for future research are provided in Section <ref>.










§ PROBLEM SETUP
 

For notational convenience let [k]={ 1,… ,k } where k∈.  In our setting the underlying (unobserved) signal at time t is a n-dimensional vector, where time t∈ is discrete.  Let μ>0 and denote the unknown signal at time t∈ by x⃗^(t)≡(x_1^(t),…,x_n^(t))∈^n, where

    x^(t)_i = {[             μ  if i ∈ S^(t);             0 if  i ∉ S^(t) ].   ,

and S^(t)⊂ [n] is the support of the signal at time t.  We refer to the components of x⃗^(t) corresponding to the support S^(t) as the active components of the signal at time t.  In Section <ref> we model the signal as a random process with the property that, at any time, the number of active components is much smaller than n.  

In this idealized model the active components of x⃗^(t) have all same value, which might seem restrictive at first.  However, when the active components have different signs and magnitudes, the arguments of all the proofs hold throughout the paper with μ playing the role of the minimum absolute value of the active components.  Although a more refined analysis is likely possible, where the minimum is replaced by a suitable function of the magnitudes of active components, we choose to sacrifice generality for the sake of clarity (see also Remark <ref> below).

The signal is only observable through m noisy coordinate-wise measurements of the form

    Y_t = x^(t)_A_t + W_t , t∈ [m] ,

where A_t ∈ [n] is the index of the entry of the signal measured at time t and W_t are independent and identically distributed (i.i.d.) standard normal random variables.  In the general adaptive sensing setting A_t is a (possibly random) measurable function of { Y_j ,A_j }_j∈ [t-1] and W_t is independent of {x⃗^(j),A_j }_j∈ [t] and {Y_j}_j∈[t-1].  This means the choice of signal component to be measured can depend on the past observations.  A more restrictive setting is that of non-adaptive sensing, where the choice of components to be measured has to be made before any data is collected.  Formally A_t is independent from {Y_j ,A_j }_j∈ [t-1] for all t∈[m].  


This measurement model is very similar to that of <cit.>, <cit.> and <cit.>, where measurements are of the form

    Y_t = x_A_t + Γ_t^-1 W_t , t=1,2,… ,

when x is a (time-independent) signal, A_t are as above, and Γ_t ∈ represent the precision of the measurements (that can be also chosen adaptively).  

In those papers the authors impose a restriction on the total precision used (and not on the number of measurements).  However, since often the precision is related to the amount of time we have for an observation it is somewhat more appealing to consider fixed precision measurements instead.  See also Remark <ref> for an alternative model closer in spirit to that of the above papers.



Recently <cit.> considered an extension of the classical sparse signal detection problem in which the measurements are heteroscedastic, and derived the asymptotic constants of the detection boundary.  In principle, a model similar in spirit to the one presented in that work could also be considered here as well, by assuming that measurements on active components not only have elevated means, but also variance different to 1.

The ideas of <cit.> can be used to modify our detection procedure (in particular the Sequential Thresholding Test – see Algorithm <ref>) to craft a procedure that can deal with measurements of different variances.  However, the question of heteroscedasticity for dynamically evolving signals is too rich to be dealt with in the present work.







 §.§ Signal dynamics


We consider what might be the simplest non-trivial stochastic model for the evolution of the signal.  Our goal is to model situations where the signal support S^(t) changes “slowly” over time.  

For concreteness consider first a particular situation, where we assume that at any time t there is a single active component (so |S^(t)|=1 for all t∈).  We model the support evolution as a Markov process: 

the support S^(1) is chosen uniformly at random over the set [n] (that is, the active component is equally likely to be any of the [n] components); for t≥ 1 we flip a biased coin with heads probability p∈[0,1] independent of all the past, and if the outcome is heads then S^(t+1) is chosen uniformly at random over [n], otherwise S^(t+1)=S^(t).
In words, at each time instant the active component stays in place with probability 1-p and “jumps” to another location with probability p.  Thus when p=1 the signal has a new support drawn uniformly at random at each time t∈, whereas in case p=0 the support is chosen randomly at the beginning and stays the same over time.  In general, the parameter p can be interpreted as the speed of change of the support, with larger values corresponding to a faster rate of change.  This basic model of signal dynamics can be easily generalized to multiple active components model as follows.

Let s∈[n] be the sparsity of our signal.  We enforce that |S^(t)|=s for t∈, meaning the signal sparsity does not change over time.  For t=1, S^(t) is chosen uniformly at random from the set {S⊆ [n] : |S|=s}.  For time t ≥ 1, we flip s independent biased coins, each corresponding to an active component, to decide which components move and which stay in the same place.  Formally take p∈[0,1] and let θ^(t)_i ∼ (p) be independent for every i ∈ [s], t∈.  Consider an enumeration of S^(t) as S^(t)≡{S_i^(t)}_i∈ [s].  If θ_i^(t)=0 component S_i^(t) will also be included in S^(t+1), otherwise it will move.  The support set S^(t+1) is chosen uniformly at random from the set

    { S ⊂ [n]: |S|=s, S∩ S^(t) = { S^(t)_i: θ^(t)_i =0 }} .

For illustration purposes we provide some simulated results in Figure <ref> (n is chosen quite small for visual clarity only).




Although we consider time to be discrete, continuous-time counterparts of this model are certainly possible (e.g., by taking the transition times to be generated by a Poisson process).  A realistic measurement model in this case would require the variance of the observation noise to be inversely proportional to the time between consecutive measurements, effectively playing a similar role to the precision parameter as in <cit.>.








 §.§ Testing if a signal is present


In the setting described one can envision several inference goals.  One might try to “track” the active components of the signal, attempting to minimize the total number of errors over time.  A somewhat different and in a sense statistically easier goal is to detect the presence of a signal, attempting to answer the question: are there any needles in this moving haystack?  This is the question we pursue in this paper, and it can be naturally formulated as a binary hypothesis test.

Under the null hypothesis there is no signal present, that is S^(t) = ∅ for every t∈.  Under the alternative hypothesis there is a signal support evolving according to the model described above, for some s∈[n] and p∈[0,1].  Ultimately, after we collected m observations we have to decide whether or not to reject the null hypothesis.  Formally, let Ψ : { A_t,Y_t }_t∈ [m]→{ 0,1 } be a test function where the outcome 1 indicates the null hypothesis should be rejected.  

We evaluate the performance of any test Ψ≡Ψ({ A_t,Y_t }_t∈ [m]) in terms of the maximum of the type I and type II error probabilities, which we call the risk of a test R(Ψ).  Namely we require

    R(Ψ)≡max_i=0,1_i (Ψ≠ i) ≤ε ,

with some fixed ε∈ (0,1/2), where _0 and _1 denote the probability measure of the observations and the null and alternative hypothesis, respectively.  Later on we also use the notation _i, i∈{0,1} to denote the expectation operator under the null and alternative hypothesis respectively.  Note that both the null and alternative hypothesis are simple in the current setup (as we assume p and μ to be known).  In particular, the density of the observations = (y_1,… ,y_m) under the alternative can be written as the following mixture:

    _1 ( ) = [ ∏_t∈ [m] g ( A_t | { y_j ,A_j }_j∈ [t-1]) ( { A_t ∈ S^(t)} f_μ (y_t) + { A_t ∉ S^(t)} f_0 (y_t) ) ]  ,

where f_μ is the density of a normal distribution with mean μ and variance 1, { S^(t)}_t∈ [m] are the supports evolving as defined in Section <ref>, and g(A_t | { y_j ,A_j }_j∈ [t-1] ) is the density of the sensing action at time t.  Note, however, that our detection procedures in Section <ref> do not require knowledge of μ or p.





The main goal of this work is to understand how large the signal strength μ needs to be, as a function of n,m,s,p and ε to ensure (<ref>) is satisfied.  To this end we first propose a specific adaptive sensing algorithm and evaluate its performance in Section <ref>.  Furthermore in Section <ref> we prove that, in several settings, this algorithm is essentially optimal, by showing lower bounds on μ that are necessary for detection by any sensing and testing strategy.  In the subsequent sections we will see that there is a complex interplay between the parameters n,m,s and p in how they affect the minimum signal strength required for reliable detection.

It is noteworthy to stress that even when we restrict ourselves to the case p=1 the nature of the optimal test changes radically depending on the interplay between the remaining parameters n,m and s.  In this case, the signal support is reset at every time t∈, which means that regardless of the sampling strategy (the choice of A_t) we are in the situation akin to a so-called sparse mixture model.  These models are now well understood (see <cit.>, <cit.>, <cit.> and references therein).  We know that in the case of mixture models, for very sparse signals a type of scan test (which is essentially a generalized likelihood-ratio test) performs optimally, whereas for less sparse signals a global test based on the sum of all the observations is optimal.  In our case the interplay between the parameters n,s and m determines the level of sparsity of the sample under the alternative.  This in turn means that when p=1 the optimal test and the scaling required for μ, depends on the relation between m and s/n.

The above phenomenon becomes even more complex when p<1.  Note, however, that unless m is at least of the order of n/s reliable detection is impossible (regardless of the value of p).  The reason behind this is that no sampling strategy will sample an active component under the alternative in fewer measurements with sufficiently large probability.  To see this consider the case p=0 and suppose there is no observation noise.  Let the sampling strategy be arbitrary and let Ω denote the event that the algorithm does not sample an active component.  When m≤ n/s we have

    _1 (Ω )    ≥n-s  m/n  m = (n-s)(n-s-1)… (n-s-m+1)/n(n-1)… (n-m+1)
       ≥( 1-s/n-m)^m ≥( 1-2s/n)^n/s .

The expression on the right is bounded away from zero when n/s is large enough.  Hence regardless of the sampling strategy, there is a strictly positive probability that no active components are sampled under the alternative, which shows that (<ref>) can not hold for ε smaller than ( 1-2s/n)^n/s.  When p> 0, sampling an active component becomes even harder, hence the same rationale holds.

In this paper we focus primarily on the regime where the number of measurements m is only slightly larger than n/s (what might be deemed to be the “small sample” regime).  If we are interested in scenarios where one needs a detection outcome as soon as possible this is the interesting regime to consider.  Interestingly, when m is significantly larger than n/s the optimal sensing and testing strategies, as well as the fundamental difficulty of the problem appears to be quite different than that of the small sample regime, and is an interesting and likely fruitful direction for future work.  In Section <ref> we conducted a small numerical experiment illustrating how the fundamental performance behavior changes in that regime.


The results in this paper can be very naturally generalized for signals with different signs and magnitudes, by considering the class of signals characterized by the minimum signal magnitude.  In the regime where m is of the order of n/s this is essentially the most natural characterization, since only a very small number of active components will actually be observed (so a very low magnitude component will hinder the performance of any method).  When m is significantly larger the picture changes quite significantly and pursuing these results is an interesting avenue for future research beyond the scope of this paper.








§ A DETECTION PROCEDURE
 



In this section we present an adaptive sensing detection algorithm for the setting in Section <ref> and analyze its performance.  To devise such a procedure we use a similar approach as taken by <cit.> — first devise a sensible procedure that works when there is no observation noise (i.e., when W_t≡ 0), and then make it robust to noise by using sequential testing ideas.

Consider a setting where there is no measurement noise, that is, when measuring a component of x⃗^(t) we know for sure whether that component is zero or not.  In such a setting if we find an active component we can immediately stop and deem Ψ =1.  Note that it is wasteful to make more than one measurement per component, and that, before hitting an active component, we have absolutely no prior knowledge on the location of active components.  Therefore an optimal adaptive sensing design is random component sampling without replacement.  If we look at a large enough number of randomly chosen components and only observe zeros, it becomes reasonable to conclude that there are no active components and so we deem Ψ=0.  Bear in mind though that in case we did not observe any active components we might have simply been unlucky, and missed them even though they are present.  Hence, there is always a possibility for a false negative decision regardless of how many components we observe, unless p=0 and m≥ n-s.

The procedure that we propose is a “robustified” version of the one explained above, so that it can deal with measurement noise.  This is done by performing a simple sequential test to gauge the identity of the component that we are observing.  A natural candidate for this is the Sequential Likelihood-Ratio Test (SLRT), introduced in <cit.>.
However, the dynamical nature of the signal causes some difficulties.  In particular the identity/activity of the component that we are observing might change while performing the test, creating many analytic hinderances in the study of the SLRT performance.  We instead use a simplified testing/stopping criteria that is easier to analyze in such a scenario.

The basic detection algorithm, presented in Algorithm <ref>, queries components uniformly at random one after another and tests their identity (whether they are active or not during the subsequent time period) using the sequential test to be described later.  Once a component is deemed to have been active we set Ψ =1 and stop collecting data.  If after examining T components or exhausting our measurement budget no components are deemed active we set Ψ = 0.  

Formally, let { Q_j }_j∈ [T] denote the components queried by Algorithm <ref>.  We choose Q_j, j∈ [T] to be independent ([n]) random variables.[In principle one could ensure these are sampled without replacement from [n], but this would only unnecessarily complicate the analysis without yielding significant performance gains.] The appropriate number of queries T≤ m will be chosen later.  For each Q_j we run a sequential test to determine the identity of that component.  We refer to our sequential test as Sequential Thresholding Test (STT).  

To gauge the identity of Q_j, j∈ [T], the STT algorithm makes multiple measurements at that coordinate.  The exact number of measurements depends on the observed values (in a way we describe in detail later), and hence it is random.  We denote the number of observations collected by STT at coordinate Q_j by N_j.  Formally, this means that A_t = Q_j for t∈[ 1+ ∑_i=1^j-1 N_i , ∑_i=1^j N_i ].

At the end of the jth run of STT (j=1,2,… ,T), the STT returns either that an active component was present at coordinate Q_j, or that no active component was present at that location.  In the former case there is no need to collect any more samples: Algorithm <ref> stops and declares Ψ =1.  Otherwise we continue with applying STT to coordinate Q_j+1.  If all T runs of STT found no signal, or we exhaust our measurement budget, Algorithm <ref> stops and returns Ψ =0.





The sequential test that we use to examine the identity of a queried component is based on the ideas of distilled sensing introduced and analyzed in <cit.> and the Sequential Thresholding procedure of <cit.>.  The distilled sensing algorithm is designed to recover the support of a sparse signal (whose active components remain the same during the sampling process).  The main idea there is to use the fact that the signal is sparse and try to measure active components as often as possible, while not wasting too many measurements on components that are not part of the support.  Our aim here is somewhat similar: on one hand we wish to quickly identify when the component that we are sampling is non-active so that we can move on to probe a different location of the signal.  On the other hand in case we are sampling an active component we wish to keep sampling it as long as it is active to collect as much evidence as possible.  However, unlike in the original setting of distilled sensing, we need to be able to quickly detect that we are sampling an active component, as it will eventually move away because of the dynamics.  To address the last point the STT algorithm in Algorithm <ref> uses an evolving threshold for detection depending on the number of observations collected.

We present STT in a way that emphasizes that it is a stand-alone routine plugged into the detection algorithm above, and not necessarily specific to the problem at hand.  Hence, when discussing STT, the observations the STT makes are denoted by X^(1),X^(2),….  In the context of Algorithm <ref>, for the jth call of STT we have X^(1),X^(2),… to be independent normal random variables with variance one and means respectively x^(T_j)_Q_j x^(T_j +1)_Q_j,…, where T_j=1+∑_i=1^j-1 N_i.



In words, STT collects at most k measurements sequentially and keeps track of the running average until one of the stopping conditions is met.  The first stopping condition says that once the running average drops below the threshold t_k we stop and declare that there is no signal present.  The second says that if the running average at step j exceeds a threshold t_j, we stop and conclude that a signal component is present.  Note that after each measurement the upper threshold decreases, eventually reaching t_k, hence the procedure necessarily terminates after at most k measurements.

Key to the performance of the STT is a good choice of k and { t_j }_j∈ [k], which is informed by the following heuristic argument:  the sample collected by the detection algorithm consists of T blocks of measurements, where each block corresponds to an application of STT.  Let the block lengths be denoted by { N_j }_j∈ [T].  Suppose for a moment that blocks entirely consist of either zero mean or non-zero mean measurements.  In this case we can simply think of each block j as a single measurement with mean multiplied by √(N_j) for all j∈ [T].  This would reduce the problem to a detection problem in a T-dimensional vector, each component being normally distributed and having unit variance.  This is a well-understood setting, and we know that in this case the signal strength needs to scale as √(log T) when there are not too many active components (see for instance <cit.> and the references therein).  Recall that we are concerned with the case where the number of measurements we are allowed to make is of the order n/s.  Hence we do not expect to encounter active components too many times.  This heuristic shows that we should calibrate STT in a way that when it encounters j consecutive measurements with elevated mean, it should be able to detect it when μ≈√(1jlog T)[In this informal discussion, the notations ≈ and ≳ hide constant factors and/or log (1/ε) terms.].  Furthermore, considering the tail properties of the Gaussian distribution, it is easy to see that we also need μ≳√(log1ε) for reliable detection.  Recalling that j≤ k, this shows that choosing k greater than log T does not buy us anything.  Informed by the above heuristic argument we choose the parameters of STT so that the following result holds.


Let ε∈ (0,1) and define the parameters of STT as

    k     = ⌊log (T/2) ⌋ , 
    
    t_j     = √(c(2ε /T)/jlog2T/ε) , j∈ [k]  ,

where

    c(x)= 2( 1+ loglog (1/x)/log (1/x)) .

Denote the observations available to the STT by X^(1),… ,X^(k) (note that the STT may terminate without observing all the variables).  Then the following holds:


  (i)If X^(i)∼^i.i.d.𝒩(0,1) for i∈ [k], then STT declares “Signal" with probability at most ε /T.

  (ii)For any j∈[k], if the X^(i)∼^i.i.d.𝒩(μ ,1) for i∈ [j] with

    μ≥√(c(2ε /T )/jlog2T/ε) + √(2 log4/ε) ,

then STT declares “No Signal" with probability at most ε/3.



Note that, for (ii) it suffices for the first j observations to have elevated mean to guarantee the good performance of the STT.


For the first part suppose note that the STT declares “Signal" if at any time step j∈ [k] the running average X_j exceeds the threshold t_j.

    ( ∃ j ∈ [k]: X^(j)≥ t_j )    ≤∑_j=1^k (X^(j)≥ t_j) 
       ≤∑_j=1^k1/2exp( - j t_j^2/2) 
        = ∑_j=1^⌊log (T/2) ⌋1/2exp( -c(2ε /T)/2logT/2ε) 
       ≤1/2log (T/2) ·( 2ε/T)^c(2ε /T)/2 ,

where the first inequality follows by a union bound, and the second inequality is follows by a tail bound on Gaussian random variables noting that X_j∼𝒩(0,1/j).  The last expression above is at most ε /T, which can be checked by taking the logarithm:

    log( 1/2log (T/2) ·( 2ε/T)^c(2ε /T)/2)    = loglog (T/2) + ( 1- loglog (T/(2ε))/log (2ε/T)) log (2ε /T) -log 2
        = loglog (T/2) + log (2ε/T) - loglog (T/(2ε)) -log 2
       ≤logε/T .


For the second part assume the conditions in (ii) hold for μ as given in the lemma.  Define the event

    Ω = {∃ i∈ [j-1]: X^(i)≤ t_k } .

Note that if this event happens, we stop and declare “No signal" in one of the first j-1 steps.

    (Declare “No signal")     =  (Ω ) +  (Declare “No signal")|Ω) ( Ω ) 
       ≤ (Ω ) +  ( X^(j)≤ t_j|Ω) ( Ω ) 
       ≤ (Ω ) + (X^(j)≤ t_j )  .

Using a union bound and the same Gaussian tail bound as before, the last expression can be upper bounded by

    ∑_i=1^j-11/2exp( -i (μ -t_k)^2/2) + 1/2exp( - j(μ -t_j)^2/2)  .


Considering the first term above, note that

    μ - t_k ≥ t_j + √(2 log4/ε) -t_k ≥√(2 log4/ε) ,

since t_j ≥ t_k (recall that j≤ k).  Hence the first term can be upper bounded as

    ∑_i=1^j-11/2exp( -i (μ -t_k)^2/2) ≤1/2∑_i=1^j-1 (ε /4)^i ≤ε/21/4-ε≤ε /6  .

On the other hand, when μ satisfies the inequality above, the second term is simply upper bounded by (ε /4)^j, and so the left-hand-side of (<ref>) is less than ε/6+ε/8<ε/3.


Using Lemma <ref>, we can establish a performance guarantee for our detection algorithm.  Though it is possible to derive a result for fixed n and s it is more transparent to state a result for large n instead, better highlighting the impact of parameter p.  Keeping this comment in mind, note that 2 ≤ c(x) ≤ 2(1+1/e)≤ 2√(2) and c(x)→ 2 as x → 0.  Thus, keeping ε fixed and letting T→∞, we see that if there exists a τ >1 for which

    μ≥τ√(2/jlog T) + √(2 log4/ε) ,

then for T large enough the condition on μ in Lemma <ref> is satisfied.  Furthermore, recall that our main interest is how the algorithm performs when the time horizon (number of measurements) is only slightly larger than n/s.























Fix ε∈ (0,1/3) and assume s≡ s_n=o(n/(log n)^2) as n→∞.  The parameter p≡ p_n is also allowed to depend on n.  Set T= 9n2slog_2 3ε and the parameters of STT according to Lemma <ref>.  If the measurement budget is m≥ 2T the detection algorithm satisfies

    R(Ψ)=max_i=0,1_i (Ψ≠ i) ≤ε ,

whenever

    μ≥τ√(2 max{ 2p,1log (n/s)}log (n/s)) + √(2 log4/ε) ,

for n large enough and τ>1 fixed (but arbitrary).













Before we move on to the proof of this result, let us discuss its message.  First note that the detection algorithm is agnostic about the speed of change p and the signal strength μ, though it does require knowledge of the sparsity s to set the parameter T.  




The number of measurements that we require is a multiple of n/s, which is the minimum amount necessary to be able to solve the problem (see Section <ref>).  Furthermore, when p < 1/(2log (n/s)) the signal strength needs to scale as √(log (1/ε )), and when p≥ 2/log (n/s) it needs to scale as √(p log (n/s)).  This matches the intuition that the speed of change p affects the problem difficulty in a monotonic fashion.  We will show in Section <ref> that in the regime m ≈ n/s this scaling of μ is necessary to reliably solve this detection problem.

In Figure <ref> we present an illustration of the above detection algorithm.  We can clearly see the “random” exploration (in red) and the “tracking” of active components (in green).  Note that in this case the algorithm missed that an active component was hit at time 8, so more exploration was needed.




As we have mentioned in Section <ref>, for now we are interested in the case where the number of observations we can make is roughly n/s.  Note that Theorem <ref> claims the same performance guarantee for every m that is at least of order n/s.  

In fact, it is not hard to see that the performance of this algorithm does not improve as m increases, hinting that it is suboptimal for large m.  Actually this algorithm completely ignores the fact that a component might have multiple periods of activity over time, and that activity evidence from multiple components might be combined for detection, in a more global fashion.  

Consider the following simple algorithm: sample components uniformly at random in each step t∈ [m].  Then in each step we hit an active component with probability s/n.  We then roughly have ms/n active components in our sample under the alternative.  Consider the standardized sum of our observations.  Under the null this follows a standard normal distribution, whereas under the alternative it is distributed as N(√(m) s μ/n,1).  

Thus reliable detection using this simple global algorithm is possible when μ is of the order n/(√(m) s).  Hence this algorithm clearly outperforms the one above when m is large enough (compared to n/s).  This phenomena is not unlike that present in sparse mixture detection problems (e.g.  as in <cit.>) where depending on the sparsity a global test might be optimal.



In light of Lemma <ref>, the type I error probability is at most ε by a union bound.  Hence we are left with studying the alternative.

There are two ways that our algorithm can make a type II error.  Either the measurement budget is exhausted, or we fail to identify an active component in T runs of STT.  We bound the probability of the first event by ε/3, and of the second event by 2ε/3 ensuring that under the alternative the probability of error is bounded by ε.

We start with upper bounding the probability of exhausting our measurement budget.  Let N_j denote the number of measurements that STT makes when called for the jth time, for j∈ [T].  Note that these random variables are independent and identically distributed, because the components to query are selected uniformly at random independently from the past, the dynamic evolution of the model is memoryless, and the observation noise is independent.  First we upper bound _1 (N_1).  Note that 1 ≤ N_1 ≤ k, where k=⌊log (T/2) ⌋ by Lemma <ref>.  Let Ω denote the event that a non-zero mean observation appears at location A_1 in any of the first k steps.  By the law of total expectation we have

    _1 (N_1) ≤ k _1 (Ω ) + _1 (N_1 |Ω )  .

Note that

    _1 (Ω )     = _1 (∃ t∈[k]: A_1 ∈ S^(t) ) ≤∑_t=1^k _1 (A_1 ∈ S^(t) ) 
       ≤s/n + (k-1)s/n-s≤ks/n-s ,

since the choice of A_1 (and S^(1)) is random, and in each subsequent step the probability that a signal component moves to location A_1 is at most s/(n-s) regardless of p.  On the other hand, recalling that t_k = √(c(2ε /T)klogT2ε)≥√(2) is the lower stopping boundary of STT,

    _1 (N_1|Ω)     = 1+∑_t=2^k _0 (N_1 ≥ t)
       ≤ 1+∑_t=2^k _0 (X_t-1 > t_k) ≤ 1+∑_t=2^k _0 (X_t-1 > √(2)) 
       ≤ 1+ 1/2∑_t=1^k-1 e^-t≤ 1+ 1/2(e-1) < 3/2  .

Hence

    _1 (N_1) ≤ 1+ 1/2(e-1) + k^2s/n-s < 3/2  ,

for large enough n, since the last term can be made arbitrarily small by the definition of T, and the assumption on s.  Since N_1 is also a bounded random variable, an easy (but crude) way of proceeding is to use Hoeffding's inequality to get

    _1 ( ∑_j=1^T N_j > m )     = _1 ( ∑_j=1^T N_j - _1 ( ∑_j=1^T N_j ) > m - _1 ( ∑_j=1^T N_j ) ) 
       ≤_1 ( ∑_i=1^T N_i - _1 ( ∑_i=1^T N_i ) > T/2 ) 
       ≤exp( - T/2k^2)=exp( - T/2⌊log(T/2)⌋^2)≤ε/3  ,

provided T is large enough, which is the case if n is large enough.  This shows that the probability that the measurement budget is exhausted is bounded by ε/3.

The final step in the proof is to guarantee that the algorithm identifies an active component in one of the T tests with high probability.  To show this, we first guarantee that there will be an instance in the repeated application of STT where the first 1/(2p) observations that the procedure has access to have elevated mean (when p=0 we only need that the STT probes an active component at least once).  Then we can apply Lemma <ref> together with a union bound to conclude the proof.

Let T_j = 1+∑_i=1^j-1 N_i denote the time when STT starts for the jth time.  Let N = ∑_j=1^T { Q_j ∈ S^(T_j)} denote the number of times an active component is sampled at the start of an STT.  Note that N ∼ (T,s/n).  In these situations the STT has access to a sequence of active measurements (of random length).  Denote the number of consecutive active observations these STTs have access to by {η_i }_i∈ [N], and for now assume p>0.  Note that η_i ∼ (p) and {η_i }_i∈ [N] are independent.  We have

    (∀ i ∈ [N]: η_i < 1/(2p) )    ≤( ∀ i∈ [N]: η_i <1/(2p) | N≥log_2 3ε) 
            + ( N < log_2 3ε)  .

On one hand, note that the median of η_i is ⌈ -1/log_2 (1-p) ⌉ which is greater than 1/(2p).  This can be easily checked by considering the cases p≥ 1/2 and p<1/2 separately.  Hence the first term above can be upper bounded as

    ( ∀ i∈ [N]: η_i <⌈ -1/log_2 (1-p) ⌉ | N≥log3ε) ≤ 2^-log_2 3ε = ε /3  .


On the other hand, N ∼ (T,s/n) and so by Bernstein's inequality,

    ( N < (1-δ ) Ts/n) ≤exp( -3 δ^2/8Ts/n)  ,

for any δ∈ (0,1).  However, note that plugging in the value of T together with δ = 2/3 yields

    ( N<log_2 3ε) = ( N < (1-δ)Ts/n)≤exp( -49/48log_2 3ε) < ε /3  ,

since log_2 x > log x for x>1.  So we conclude that the probability that there is no block (out of T) with the first 1/(2p) observations active is bounded by 2ε/3.  When p=0, we only need to control (N=0), for which we can simply use the inequality above since log_2 3ε >0.  

Finally, if such a block is present the probability STT will not detect it is bounded by ε/3 via part (ii) of Lemma <ref>, provided

    μ≥√(c(2ε/T)/min{ 1/(2p),⌊log (T/2) ⌋}log(T/2ε))+√(2log4/ε) ,

where one should note that the blocks sampled by the STT are never larger than ⌊log (T/2) ⌋.  It is easily checked that the above condition is met for the choices in the theorem, provided n is large enough, concluding the proof.








§ LOWER BOUNDS
 

In this section we identify conditions for the signal strength that are necessary for the existence of a sensing procedure to have small risk, namely

    R(Ψ)=max_i=0,1_i (Ψ≠ i) ≤ε .

We consider first the non-adaptive sensing setting.  This is done both for comparison purposes (to highlight the gains of sensing adaptivity) but also illustrates some of the interesting features of this problem.  In this case the sensing procedure is simply the choice of when and where to measure a component, before any data is collected.  Then we consider the adaptive sensing setting to show the near-optimality of the algorithm proposed in Section <ref>.  In both cases our primary interests in on the regime m ≈ n/s, as highlighted in Section <ref>.





 §.§ Non-adaptive sensing
 

In the non-adaptive sensing setting, the sampling strategy { A_t }_t∈ [m] needs to be specified before any observations are made.  Note that this does not exclude the possibility of having a random design of the sensing actions.

Common sense tells us that supports that are changing fast are harder to detect than those that are changing slowly, provided all other parameters are fixed.  In other words, the problem difficulty should be increasing in the parameter p, meaning the signal magnitude μ needed to ensure (<ref>) should grow monotonically in p.  Formalizing this heuristic in general turns out to be technically challenging with the methodologies we are aware of.  Because of this we focus on the two extreme cases: when the signal is static (p=0), and when the entire signal resets at each time instance (p=1).


Note that in the case s=1 it is relatively easy to formalize that the problem difficulty is non-decreasing in p.

Suppose there exists an algorithm (denoted by Alg) that performs accurate detection for some p>0, and suppose we need to perform the detection task of a static signal.  The idea is to transform the signal into one that has the same distribution as if it were generated according to the model of Section <ref> with parameter p, and apply Alg to the modified signal.  If such a transformation is possible than the existence of Alg implies the existence of an accurate detection procedure – in other words, the problem difficulty is non-decreasing in p.

Such a transformation is easy to construct for s=1, in fact one can almost follow the description of the signal model of Section <ref> word-by-word.  Let {θ_t }_t∈ [m-1] be i.i.d.  (p) variables and w.l.o.g.  θ_m =1 — these represent the coin flips in the description of Section <ref>.  Let N=∑_t∈ [m]{θ_t =1 } be the number of times the coin came up heads and τ_0 =0 and τ_j = inf{ t> τ_j-1: θ_t =1 }, j∈ [N] be the instances when the coin came up heads.  Finally, let {π_i }_i∈ [N] be permutations of [n] drawn independently and uniformly at random (from the set of possible permutations).

It is clear that a static support that is permuted by π_i on the time intervals [τ_i-1+1,τ_i ] will "look" like a support sequence evolving with parameter p.  Formally, one can show that if ≡{ S^(t)}_t∈ [m] is a static support sequence (chosen uniformly at random) then ≡{S̃^(t)}_t∈ [m] defined as

    S̃^(t) = ∑_i∈ [N]{ t∈ [τ_i-1+1 ,τ_i ] π_i (S^(t))

is distributed as a support sequence generated according to the model described in Section <ref> with parameter p.  Hence for s=1 the problem difficulty is indeed non-decreasing in p.

Nonetheless the authors did not find an obvious way to extend this argument to general sparsities, because the signal components change their locations at possibly different times.  We note at this point that if one considered a more restrictive model where the entire support of the signal would reset simultaneously (a setting perhaps not vastly different to the one we are considering) would enable an argument similar to the above.


We have the following result for these two extreme cases, which we prove at the end of the section.  Note that these are not asymptotic, and hold for any n,m and s satisfying the assumptions in the statement.

 Let n,s,m ∈ be fixed (with s≤ n), consider a setup described in Section <ref>, and suppose there is a non-adaptive sensing design and a test Ψ satisfying

    R(Ψ)=max_i=0,1_i (Ψ≠ i) ≤ε .



  (i)If p=0, s≤ n/2, n/s≤ m and ε≤ 1/(2e) then necessarily

    μ≥√(n/2mslog( 2 n/s^2log( 1e-4ε)  +1 )) .



  (ii)If p=1 and ε <1/2 then necessarily

    μ≥√(log( n^2/s^2 mlog( 4(1-2ε )^2 +1 ) +1 )) .





Considering the case p=1, the result above tells us that when m scales like n/s, the signal strength needs to scale as √(log (n/s)) for detection to be possible.  This is the same scaling that is guaranteed by Theorem <ref>.  This should come as no surprise, since when p=1 we have { A_t ∈ S^(t)}∼ (s/n) independently for every t∈ [m], regardless of the choice of A_t.  Hence the resulting measurements { Y_t }_t∈ [m] follow the same mixture distribution under the alternative, no matter what sampling strategy we use.  Although settings like these have been studied extensively (see <cit.> and references therein), those works consider asymptotic results.  As such we find it useful to prove a non-asymptotic result for our particular problem, though we point out that this can be simply established by following the steps of the referenced proofs.

Contrasting with this one has the (arguably) more interesting case when the signal is static (p=0).  Although the problem of detecting static signals have been the focus of much work (see for instance <cit.>), a key difference in our setting is that the sensing actions of the experimenter are not fixed, but are free to choose.  This results in a qualitatively different statement, as the following remark attests.


In particular, the first part of the theorem above is interesting in its own right.  It tells us that, for static signals, if the experimenter is free to choose the sensing actions, the signal magnitude needs to scale at least as √(nsmlogns^2) for detection to be possible.  It is easy to see that this rate can (almost) be achieved using a sub-sampling scheme: select roughly n/s components at random and collect an equal number of samples of each.  Average the observations for each component separately, and declare a signal if any of these averages is above the threshold √(nsmlogns).  Basic calculations show that this procedure has low probability of error.

Contrasting this, the lower bounds of <cit.>, which pertain the situation where we measure each component of the vector exactly once, scale as √(logns^2).  Hence, the additional flexibility of where to sample buys us a multiplicative factor of √(nsm), even though no feedback from the observations is used.  If we can use this feedback, we can also get rid of the log-factor, as shown in <cit.>.



In light of the previous remark, the authors suspect the lower bound in part (i) of the Theorem is slightly loose.  Namely, the term s^2 appears to be due to slack in the second moment method in Equation <ref>, and it might be possible to replace it by s via a more sophisticated truncation argument.


The result above tells us that in the regime m ≈ n/s, the signal strength needs to scale as √(log (n/s^2)) for detection to be possible — approximately the same magnitude as required for p=1.  On the other hand Theorem <ref> guarantees the existence of an adaptive sensing procedure that reliably detects static signals of constant magnitude (in terms of the parameters n and s) using roughly n/s measurements.  This shows that adaptive sensing gains over non-adaptive sensing become more pronounced as the speed of change decreases.

Finally we point out once more that the requirements for the signal strength of Theorem <ref> are essentially the same for p=0 and p=1.  Although we did not succeed in proving a result that holds for any value of p due to technical difficulties, we conjecture that the lower bound or general values of p should interpolate between these two extremes.  In other words, we suspect that the problem difficulty is essentially independent of p in the non-adaptive case when m is of the order (or slightly larger than) n/s.  This conjecture is further supported by numerical simulations of testing error probability presented in Section <ref>.


(i): To prove the claim above for p=0 we use the truncated second moment method, an approach suggested by <cit.> to address problems in the regular second moment method when the distribution of the likelihood ratio under the null has tails that are too heavy (and therefore too large of a second moment).  First, note that

    max_i=0,1_i (Ψ≠ i) ≥1/2∑_i=0^1 _i (Ψ≠ i) = 1/2( 1-1/2_0 ( |L(Y⃗)-1|) )  ,

where L(Y⃗) denotes the likelihood-ratio of the observations Y⃗=(Y_1,…,Y_m), and _0 is the expectation taken with respect to the distribution of the observations Y⃗ under the null.  The second equality is well known (see for instance <cit.>), and can be easily checked using simple algebraic manipulations.

A common way to proceed is to use either Cauchy-Schwarz's or Jensen's inequality to get

    _0 ( |L(Y⃗)-1|) ≤√(_0 ( (L(Y⃗)-1)^2 )) = √(_0 (L(Y⃗))) .

Therefore, to get a lower bound on the risk we need to get a good upper bound on the variance of the likelihood ratio.  This is often referred to as the second moment method.  However, in some cases there is a lot of slack in the bound and the variance is too large to yield interesting results — so a modification of the above argument is needed.

Let 𝒴 denote the sample space, and let L̃(y⃗): 𝒴→ be an arbitrary function.  Instead of using the Cauchy-Schwarz inequality right away, let us continue the first chain of inequalities as

    _0 ( |L(Y⃗)-1|)     = _0 ( |L(Y⃗) -L̃(Y⃗) + L̃(Y⃗) -1| ) 
       ≤_0 ( |L̃(Y⃗) -1| ) + _0 ( |L(Y⃗) -L̃(Y⃗)| ) 
       ≤√(_0 ( L̃(Y⃗)^2 ) -2_0 ( L̃(Y⃗)) +1) + _0 ( |L(Y⃗) -L̃(Y⃗)| )  .

Furthermore, if L̃(y⃗)≤ L(y⃗) for every y⃗∈𝒴, then we have

    _0 ( |L(Y⃗)-1|) ≤√(_0 ( L̃(Y⃗)^2 ) -2_0 ( L̃(Y⃗)) +1) +1 -_0 ( L̃(Y⃗) )  .

In order to proceed, we need to lower bound _0 (L̃(Y⃗)) and upper bound _0 (L̃(Y⃗)^2).  To get a sharp lower bound with this method, we need a good choice for L̃(y⃗).  This is often achieved by truncating the original likelihood-ratio by multiplying with the indicator of a well chosen event.

In our setting the likelihood-ratio can be expressed in a convenient way.  Note that under the null the observations are independent standard normal regardless of the sensing actions, hence

    _0 (y⃗) = ∏_t∈ [m] f_0(y_t)  ,

where f_μ (· ) is the density of a normal random variable with mean μ and variance 1.  Under the alternative, the density of the observations is a mixture.  Recall that we are considering the case p=0 therefore the signal support S^(t) does not change over time, namely S^(t)=S for all t∈[m].  The conditional density of the observations given the sensing actions A=(A_1 ,… ,A_m ) and the support S can be written as

    _1 (y⃗|A,S) = ∏_t∈ [m]( { A_t ∈ S} f_μ (y_t) + { A_t ∉ S} f_0 (y_t) )  .

Hence the likelihood-ratio can be expressed as

    L(y⃗) = ( exp( ∑_t∈ [m]{ A_t ∈ S}logf_μ (y_t)/f_0 (y_t)) )  .


Using the second moment method without truncation, one would need to upper bound the second moment of the likelihood ratio above.  Unfortunately, this yields a loose bound on μ.  The reason is that the second moment will be extremely large when the signal is sampled often, even if this event is relatively rare.  In other words, if ∑_t∈ [m]{ A_t ∈ S} is large one will face problems.  Note that, since the support is chosen uniformly at random,

    ( ∑_t∈ [m]{ A_t ∈ S }) = ms/n  .

However, for certain choices of design ∑_t∈ [m]{ A_t ∈ S} can be very far from the mean (e.g., if A_1=⋯=A_m then ∑_t∈ [m]{ A_t ∈ S} is equal to m with probability s/n and zero otherwise).  This causes the second moment of the likelihood ratio to be extremely large.  To resolve this issue we truncate the likelihood-ratio to exclude these somewhat troublesome instances.

Begin by defining the sets

    A_ big = { i: ∑_t∈ [m]{ A_t =i } > 2ms/n }   and    A_ small = [n] ∖ A_ big .

In words, for a given sensing design the signal components are divided in two disjoint subsets: one subset contains signal components that are sampled often, whereas the other contains the remaining components.  A simple pigeon hole principle shows that |A_ big|≤ n/(2s).  Now define

    L̃(Y⃗) = [.  {S⊆ A_ small}exp( ∑_t∈ [m]{ A_t ∈ S}logf_μ (Y_t)/f_0 (Y_t))| Y⃗]  .

Clearly L̃(y⃗) ≤ L(y⃗) for all y⃗∈𝒴, and so we can apply (<ref>) by controlling the first and second moments of L̃(Y⃗).

First note that, since the event S⊆ A_ small does not involve the observations Y⃗ we can easily conclude that

    _0 ( L̃(Y⃗) ) =  (S⊆ A_ small) = ( (S⊆ A_ small|A⃗) )  ,

where A⃗≡ (A_1 ,… ,A_m ).  The conditional probability on the right can be lower bounded as

    (S⊆ A_ small|A⃗)     = |A_ small|  s/n  s = |A_ small| (|A_ small|-1)… (|A_ small|-s+1)/n(n-1)… (n-s+1)
       ≥( |A_ small|-s+1/n-s+1)^s ≥( n(1-12s)-s+1/n-s+1)^s 
        = ( 1-n/2s(n-s+1))^s ≥( 1-1/s)^s
       ≥1/e ,

where we used |A_ small|≥ n(1-1/2s) and 1≤ s≤ n/2.

We are left with upper bounding the second moment of L̃(Y⃗).  First, note that in the non-adaptive sensing setting A=(A_1,… ,A_m) and S are independent.  The proof proceeds by careful conditioning on these random quantities.  We use Jensen's inequality to write

    _0 (L̃(Y)^2)     = _0 [ ([{S⊆ A_ small}exp( ∑_t∈ [m]{ A_t ∈ S}logf_μ (Y_t)/f_0 (Y_t))| Y⃗] )^2]
    
       ≤_0[[([{S⊆ A_ small}exp( ∑_t∈ [m]{ A_t ∈ S}logf_μ (Y_t)/f_0 (Y_t))_h(S,Y⃗,A⃗)| Y⃗,A⃗])^2|Y⃗]] .

At this point it is convenient to introduce an extra random variable S', independent from S and identically distributed.  Then

    ([.  h(S,Y⃗,A⃗)| Y⃗,A⃗])^2    = [.  h(S,Y⃗,A⃗)| Y⃗,A⃗] [.  h(S',Y⃗,A⃗)| Y⃗,A⃗]
       = [.  h(S,Y⃗,A⃗)h(S',Y⃗,A⃗)| Y⃗,A⃗] .

Therefore we conclude that

    _0[L̃(Y⃗)^2]    ≤_0 [{S⊆ A_ small}{S'⊆ A_ small}exp( ∑_t∈ [m]({ A_t ∈ S}+{ A_t ∈ S'}) logf_μ (Y_t)/f_0 (Y_t))]
       = [ _0[.  {S,S'⊆ A_ small}exp( ∑_t∈ [m]({ A_t ∈ S}+{ A_t ∈ S'}) logf_μ (Y_t)/f_0 (Y_t))|A⃗,S,S']]
       = [{S,S'⊆ A_ small}∏_t∈ [m]_0[.  exp(({ A_t ∈ S}+{ A_t ∈ S'}) logf_μ (Y_t)/f_0 (Y_t))|A⃗,S,S']]
       = [{S,S'⊆ A_ small}exp(μ^2 ∑_t∈ [m]{A_t∈ S∩ S'})] .

We are now in a good position to finish the bound.  Note that, when S,S'⊆ A_ small we have ∑_t∈[m]{A_t=i}≤ 2ms/n.  It follows that

    _0[L̃(Y⃗)^2]    ≤[[.{S,S'⊆ A_ small}exp(μ^2 ∑_i∈[n]{i∈ S∩ S'}∑_t∈[m]{A_t=i}) |A⃗]]
       ≤[[.  exp(2msμ^2/n∑_i∈[n]{i∈ S∩ S'}) |A⃗]]
       = [ exp( λ∑_i∈[n]{i∈ S∩ S'}) ] ,

where λ=2msμ^2/n.  The beauty of the last expression is that it no longer involves the sensing actions or the observations, and depends only on the support.  Using the negative association property of { i∈ S∩ S'} as introduced in <cit.> we can finally bound the second moment of the truncated likelihood as

    _0 (L̃(Y⃗)^2)    ≤[exp(λ∑_i∈[n]{i∈ S∩ S'}])]
        = [∏_i∈[n] e^λ{i∈ S∩ S'}] ≤∏_i∈[n][ e^λ{i∈ S∩ S'}]
        = ( 1+ s^2/n^2( e^λ -1 ) )^n = ( 1+ s^2/n^2( e^2μ^2 ms/n -1 ) )^n  .

We have now all the ingredients needed to complete the proof.  Note that, on one hand, if max_i=0,1_i (Ψ≠ i) ≤ε then necessarily _0[|L(Y⃗)-1|]≥ 2-4ε.  On the other hand, from (<ref>) we know that

    _0[|L(Y⃗)-1|]    ≤√(_0 ( L̃(Y⃗)^2 ) -2_0 ( L̃(Y⃗)) +1) +1 -_0 ( L̃(Y⃗) )
       < (1+ s^2/n^2( e^2μ^2 ms/n -1) )^n/2 +1/2 .

This means that

    s^2/n^2(e^2μ^2 ms/n -1) > (3/2-4ε)^2/n-1≥2/nlog(3/2-4ε) ,

where the last inequality uses the fact that x-1 ≥log x.  The final result ensues by simple algebraic manipulation.



(ii): Proving the claim for p=1 requires considerably less technical effort.  In particular we can use the original second moment method, without truncation.  Therefore, we simply need to upper bound the second moment of the likelihood-ratio.

Using essentially the same calculations as before, we get

    _0 ( L(Y)^2 ) = [ exp( μ^2 ∑_t∈ [m]{ A_t ∈ S^(t)∩ S'^(t)}) ]  .

When p=1 we have that { A_t ∈ S^(t)∩ S'^(t)}∼ (s^2 /n^2 ) and these random variables are independent, so we can simply evaluate the above expression and get 

    _0 ( L(Y)^2 ) = ( 1+ s^2/n^2( e^μ^2 -1 ) )^m  .


Plugging this into the inequalities above (not using the truncation), we get

    μ≥√(log( n^2/s^2( √(4(1-2ε )^2)-1 ) +1 )) .

The desired result follows by using x-1 ≥log x.







 §.§ Adaptive sensing
 

In the adaptive sensing setting, the decision where to sample at time t can depend on information gleaned up to that point.  For the static case (p=0) the fundamental limits of the detection problem using adaptive sensing have been studied in <cit.>.  Those lower bounds are derived for a slightly more general setting than the one considered here, in that the total precision of the measurements is constrained, but not the total number of measurements.  Nevertheless, this bound is still valid in our setting, and states that for any adaptive sensing and testing procedure Ψ if

    max{_0 (Ψ≠ 0 ), _1 (Ψ≠ 1) }≤ε

then necessarily

    μ≥√(2 n/smlog1/2ε) .


In the regime m ≈ n/s the bound states that the signal strength needs scale as √(log (1/ε )).  This coincides (up to constants) with the bound of Theorem <ref> when p≤ 2/log (n/s).  This tells us that when the signal changes slowly enough, the problem is essentially non-dynamic in nature.

On the other extreme end of the spectrum is the case p=1.  We have seen previously that in this case the non-adaptive and adaptive sensing settings are identical, by virtue of the fact that { A_t∈ S^(t)}∼ (s/n) for every t∈ [m] and independent, regardless of the choice of A_t.

What remains to be understood are the fundamental limits for the intermediate regime.






  §.§.§ Non-extreme dynamics (p∈ (0,1))


For general values of p we start by considering the case s=1, which we call the 1-sparse case.  This case is considerably simpler to analyze than the general s-sparse setting, as now whenever the active component changes the entire signal resets.  This effectively creates a number of independent static signals on the time horizon.


Consider the setup in Section <ref> and suppose there exists a test Ψ such that

    max_i=0,1_i (Ψ≠ i) ≤ε .



  (i)The signal strength must satisfy

    μ≥√(2n/smlog1/4ε) .



  (ii)
When s=1 and p≥ 8/m, then necessarily

    μ≥√(p/2clog( log( ( 54 -4ε)^2 +12) p^2 n^2/4 c^2 m +1 )) ,

with c=6+3log 2.





We provide the proof of Theorem <ref> at the end of the section.  Part (i) holds regardless of the values of p and s, so it is necessarily loose when p is large.  On the other hand part (ii) already captures the role of the rate of change p, and it is the main contribution in this result.

Let us compare the above bound on μ with the guarantees for Algorithm <ref> proved in Theorem <ref>.  Note that c and ε are constants.  Thus the bound on the signal strength in the above result scales as √(p log(p^2 n^2/m)).  Recall that we are interested in the regime m≈ n/s and that s=1, as we are considering the 1-sparse case.  In that setting the bound above scales as √(p log (p^2 n)).  Also note that the scaling of the performance guarantee of Theorem <ref> matches that of the lower bound from <cit.> when p<1/log n.  Hence we only need to assess the result of Theorem <ref> when p≥ 1/log n.  In this case, the scaling of that bound is at least as big as √(p(log n - 2loglog n))≈√(p log n).  This shows near-optimality of the algorithm proposed in Section <ref>, in terms of its scaling in the parameters n and p.

Due to technical reasons we were unable to generalize the result for signals of sparsity greater than one.  As noted above, a key feature of the 1-sparse case is that the signal decouples into independent static signals over time.  This key property is lost when we consider signals with sparsity greater than one, and this proves to be a major obstacle to obtain a rigorous formal proof.  However, we conjecture that a similar result to the one above holds for s-sparse signals, with n replaced by n/s.  The heuristic behind this is that a general s-sparse signal of dimension n should behave very much like an s-fold concatenation of an 1-sparse signal of dimension n/s, when viewed through the lens of one measurement per time-index (one expects this to actually be a statistical reduction, and this problem should be statistically easier than the original one).  For such a signal the result above would follow directly with the signal dimension n replaced by n/s.


When p≥ 8/m, if the risk of an adaptive sensing and test procedure is less or equal to ε then necessarily

    μ≥√(p/2clog( log( ( 54 -4ε)^2 +12) p^2 n^2/4 c^2 s^2 m +1 )) ,

with c=6+3log 2.



We prove the two parts of the statement separately.



(i): The proof is very similar to that of Theorem 3.1 in <cit.>, with small modifications to be able to deal with dynamically evolving signals (which actually simplify the argument).  By Theorem 2.2 of <cit.> we have

    inf_Ψmax_i=0,1_i (Ψ≠ i) ≥1/4 e^-  (_0 _1 ) ,

where (_0 _1 ) denotes the Kullback-Leibler divergence between the distribution of the data  under the null and alternative respectively.  This divergence can be simply upper bounded using Jensen's inequality as

    (_0 _1 )     = _0 [ -log L( ) ] 
       ≤_0 [ [ .  -∑_t∈ [m]{ A_t ∈ S^(t)}logf_μ (Y_t)/f_0 (Y_t)| ] ]  .


Changing the order of integration and expanding the densities f_μ (· ) and f_0 (· ) we get

    (_0 _1 ) ≤μ^2/2[ ∑_t∈ [m]{ A_t ∈ S^(t)}] = μ^2/2sm/n ,

where the last step follows from the symmetry of the supports.  In particular note that [ { A_t ∈ S^(t)} | A_t ] = s/n for every t∈ [m].  Plugging this bound into the right side of (<ref>), using that the left side of (<ref>) is at most ε due to our assumption, and rearranging concludes the proof of the first claim.



(ii): We use the truncated second moment method, as in the proof of Theorem <ref>.  Recall that, from (<ref>) and (<ref>) , we have

    2 max_i=0,1_i (Ψ≠ i) ≥ 1- 1/2( √(_0 ( L̃(Y)^2 ) -2_0 ( L̃(Y)) +1) +1 -_0 ( L̃(Y) ) )  ,

for any function L̃(· ) satisfying L̃( ) ≤ L( ), ∀∈𝒴, where L(· ) is the likelihood function.



To aid the presentation we begin by introducing some convenient notation, illustrated in Figure <ref>.  Recall that the variables θ^(t)_i∼^i.i.d.  (p), t∈ [m], i∈ [s] identify the change points of the signal.  Since now we are dealing with the 1-sparse case we have one variable per time index, so in what follows we drop the subscript from the previous notation.  Furthermore, note that our time horizon is m, so we enforce θ^(m) =1 as this does not change the model and it is convenient for the presentation.

Let the total number of change points over the time horizon be N = ∑_t∈ [m]{θ^(t) =1}.  Note that N-1 ∼ (m-1,p).  Let τ_0 = 0 and for j∈ N let τ_j = min{ t>τ_j-1: θ^(t) =1 } denote the time instances when the signal changes (so τ_N =m), as illustrated in Figure <ref>.  Note that on the time intervals [ τ_j +1,τ_j+1 ] the signal is static.  Let l_j=τ_j+1-τ_j denote the length of these intervals, and S_j, j∈ [N] denote the correspoding signal support.  Finally, for any t∈ [m] let the number of change points up to time t be N(t) = max{ j: τ_j ≤ t }.  It is important to note that the random variables θ^(t) completely determine the variables τ_j, N(t) and N.

Let us first explicitly write the likelihood of the observations in the model under consideration.  We use the shorthand notation = { y_t }_t∈ [m],  ={ A_t }_t∈ [m],  ={ S^(t)}_t∈[m],  ={θ_t }_t∈ [m].  As before, the density of  under the alternative is a mixture.  In particular, denoting the density of N(μ ,1) by f_μ, the conditional density of  can be written as

    _1 ( | , )     = ∏_t∈ [m]( { A_t ∈ S^(t)} f_μ (y_t) + { A_t ∉ S^(t)} f_0 (y_t) ) 
        = ∏_j∈ [N]∏_t= τ_j-1+1^τ_j( { A_t ∈ S_j } f_μ (y_t) + { A_t ∉ S_j } f_0 (y_t) )  .

Hence, the likelihood ratio is

    L( ) = [ [ .  exp( ∑_j∈ [N]∑_t=τ_j-1+1^τ_j{ A_t∈ S_j }logf_μ (y_t)/f_0 (y_t)) |  ,] ]  ,

where conditioning on  and  is done in order to conveniently define L̃().  Consider the event

    Ω_c = {∀ j: l_j ≤ 2c/p } ,

with some fixed c>0.  This event says that the signal is never static for a time longer than 2c/p.  Note that this event is determined exclusively by the variables {θ_t }_t∈ [m].  We define the truncated likelihood as

    L̃( ) = [ {Ω_c}[ .  exp( ∑_j∈ [N]∑_t=τ_j-1+1^τ_j{ A_t∈ S_j }logf_μ (y_t)/f_0 (y_t)) |  ,] ]  .


As in the proof of Theorem <ref>, we need to upper bound _0 ( L̃()^2 ) and lower bound _0 ( L̃()).  We start with the latter.  Since the event Ω_c only involves the variables , we have

    _0 ( L̃()) =  (Ω_c )  .

We have the following result, the proof of which is presented in the Appendix.


Consider the event

    Ω_c = {∀ j: l_j ≤ 2c/p } .

In the model described above (Ω_c ) >1/4 whenever c≥ 6 + 3 log 2 and p ≥ 8/m.


According to Lemma <ref>, we have an appropriate bound for _0 ( L̃(Y)) when c≥ 6 + 3 log 2.  All that remains is to derive an upper bound on the truncated second moment.  This can be done much the same way as in the proof of Theorem <ref>.  Using Jensen's inequality, we have

    _0 [ L̃( )^2 ] ≤_0 [ [ {Ω_c}[ .  exp( ∑_j∈ [N]∑_t=τ_j-1+1^τ_j{ A_t∈ S_j }logf_μ (y_t)/f_0 (y_t)) |  ,]^2 ] ]  .

Note that given , the S_j ∼ ([n]) and independent for j∈ [N].  Let { S'_j }_j∈ [N] be an independent copy of { S_j }_j∈ [N].  Following the same reasoning as in Theorem <ref> we can write the square of the conditional expectation above as the product of two expectations using the random variables {S_j, S'_j }_j∈ [N], and change the order of the expectations to get

    _0 [ L̃( )^2 ] ≤[ {Ω_c}[ .  exp( μ^2 ∑_j∈ [N]∑_t=τ_j-1+1^τ_j{A_t ∈ S_j ∩ S'_j }) |  ,] ]  .


So far we have not taken into account the fact that we are allowed an adaptive design.  This is captured by the crude bound below.

    ∑_t=τ_j-1+1^τ_j{A_t ∈ S_j ∩ S'_j }≤ l_j {∃ t∈ [τ_j-1+1,τ_j ]: A_t ∈ S_j ∩ S'_j } .

Informally this means that, if the used design “hits” the signal at any place in the interval [τ_j-1+1,τ_j ] it is assumed the design hit the signal in the entire interval (capturing more information).  Furthermore

    (.  ∃ t∈ [τ_j-1+1,τ_j ]: A_t ∈ S_j ∩ S'_j|,) = (.  S_j ∈{ A_t : t∈ [τ_j-1+1,τ_j ] }|,)^2  .

However, |{ A_t: τ_j-1 +1 ≤ t ≤τ_j }| ≤τ_j-τ_j-1 := l_j thus the probability above is bounded from above by l_j^2 /n^2.

Using all this yields

    _0 [ L̃( )^2 ]    ≤[ {Ω_c}∏_j∈ [N][ .  exp( l_j μ^2 {∃ t∈ [τ_j-1+1,τ_j ]: A_t ∈ S_j ∩ S'_j }μ^2 ) |  ,] ] 
       ≤[ {Ω_c}∏_j∈ [N]( 1+ l_j^2/n^2( e^l_j μ^2 -1 ) ) ]  .


The last expression is readily upper bounded by the fact that N≤ m.  Although this is a crude bound[In principle one can recall that N-1∼(m-1,p) and proceed from there, although it will overcomplicate the derivation.  In any case, this will at most allow us to replace the term p^2 by p inside the logarithm in the statement of the theorem, which is not very relevant.] it is enough for our purposes.  Also, on the event Ω_c we have the upper bound l_j ≤ 2c/p for every j∈ [N].  We conclude that

    _0 ( L̃( )^2 ) ≤( 1+ 4c^2/p^2 n^2( e^2cμ^2 /p -1 ) )^m  .























Combining our results yields that if there exists a test for which max_i=0,1 (Ψ≠ i) ≤ε, we must have

    √(( 1+ 4c^2/p^2 n^2( e^2cμ^2 /p-1 ) )^m -1/2) +3/4≥ 2-4ε .

Rearranging gives

    4c^2/p^2 n^2( e^2cμ^2 /p-1 ) ≥√(( 5/4 - 4ε)^2 + 1/2)-1  .

Using the inequality log x ≤ x-1 on the right hand side, and rearranging concludes the proof.







§ NUMERICAL EVALUATION OF THE NON-ADAPTIVE LOWER BOUND


Although the lower bound in Theorem <ref> only deals with the extreme cases p∈{ 0,1 }, we conjecture that in the regime m≈ n/s the same scaling of μ is necessary for reliable detection, regardless of the value of p.  To corroborate this conjecture we provide a brief section of numerical experiments.  We numerically estimate the right hand side of (<ref>), which is a lower bound on the maximal probability of error.  We do so for several values of p∈ [0,1], and for each p we plot the value of the lower bound as a function of μ.

Note that the sampling strategy has a large impact on the value in question.  We know that when p=0 a sub-sampling scheme is near-optimal (see Remark <ref>), and so it should also be reasonable for small values of p.  On the other hand, the sampling strategy is irrelevant for p=1, and probably essentially irrelevant for large p.  This motivates using a sub-sampling scheme in all the experiments.

Furthermore, note that unless we sample c· n/s different components, the probability _1 (∀ t∈ [m]: A_t ∉ S^(t)) can not be small.  To ensure an upper bound of ε on the previous probability, we need to choose c ≡ c(ε ) = log (1/ε ).

Considering all the above, we set up our experiment as follows.  We set n=5000, s=⌈ n^1/4⌉ =9 and m=c(ε )n/s with ε =0.05.  In this case, sub-sampling reduces to measuring m randomly selected components (one measurement each).  We note that we experimented using multiple values of s across a wide range of sparsity levels, but found qualitatively the same result in all cases.

Based on previous work concerning the sparse-mixture model (e.g.  <cit.>) we expect the lower bound to reach the value ε when μ≈√(2log (n/s)).  Hence, we set μ_t ≈ t·√(2log (n/s)), and plot the r.h.s.  of (<ref>) as a function of t.

The left panel of Figure <ref> seems to support our conjecture that the problem difficulty is independent of p in the regime m≈ n/s, as all the curves are on top of each other.  Furthermore, since there is always a non-negligible chance of not sampling a signal component, the lower bound is bounded away from zero, even as μ_t grows large.



To contrast this, we present another simulation with the same setup, except that the number of measurements m ≫ n/s.  In particular, we set m=n, but otherwise use the same parameters.  Note that in this case, sub-sampling amounts to sampling c(ε ) n/s randomly chosen components, but now we sample each of these m/(c(ε ) n/s) consecutive times.

To keep the two plots on the same horizontal scale, we set μ_t = t·√( (2c(ε )n /sm) log (n/s)) in the right panel of Figure <ref>.  It seems that in this case, the curves are no longer on top of each other, suggesting that the value of p has an impact on the problem difficulty.  Surprisingly, the curve corresponding to p=1 is the one that descends the fastest, though the difference is only marginal.  Though the cause of this is unclear, a possible reason might be that for faster signals the chance of not sampling active components at all is diminished, an effect that is more pronounced when m is large.

In any case, this shows that in the regime m≫ n/s the speed of change might have a non-trivial effect on the problem difficulty.  Exploring this is out of the scope of this work, but might be an interesting topic of future research.






§ FINAL REMARKS
 

In this paper we studied the problem of the detection of signals that evolve dynamically over time.  We introduced a simple model for the evolution of the signal that allowed us to explicitly characterize the difficulty of the problem with a special regard to the effect of the speed of change.  We also showed the potential advantages that adaptively collecting the observations bring to the table and showed that these are more and more pronounced as the speed of change decreases, which is in line with previous results dealing with signal detection using adaptive sensing.  The lower bounds derived in this paper provide a clear picture of the role of the rate of change parameter p, but unfortunately still do not span the entire range of problems we would like to consider (e.g.  Theorem <ref> applies only to p=0,1 and part (ii) of Theorem <ref> applies only to s=1).  The latter difficulties appear to be mostly technical and the authors suspect these might be possible to address with carefully chosen reductions.  Our contributions merely scratch the surface of this interesting problem, and below we highlight a few interesting directions for future work in this regard.


Large vs.  small sample regimes: in this work we focus primarily on the case m≈ n/s, which may be deemed as the small sample regime.  When the number of measurements m is significantly larger the type of tests and performance tradeoffs will likely be different, even under the non-adaptive sensing paradigm.  For instance, we expect the signal dynamics to have an effect on performance, meaning that it is easier to detect signals non-adaptively when p is smaller.  Other interesting questions arise in that setting as well — what is the optimal non-adaptive sensing design?  These questions become even more intriguing when one considers adaptive sensing.


Restricted dynamics: in the model considered in this paper when signal components change they can move to any unoccupied location in the signal vector.  This assumption simplifies the setup, but in some applications might be too unrestrictive.  For instance, if signal components can only move to adjacent locations at each time step the effect of the speed of change will likely be less pronounced in the difficulty of detection (at least for adaptive sensing).  Understanding the effect of such restrictions could prove valuable in certain applications, such as detection of a disease outbreak in a network, besides being interesting from a theoretical point of view.


Structures: in certain situations the signal support can be assumed to have structure to it, for instance all anomalous items might be consecutive or have some other pattern.  In some cases the structure of the support has a huge effect on the difficulty of the problems of detection and recovery (see for instance <cit.>).  How structural restrictions affect these tasks for dynamically evolving signals could be a fruitful avenue of research.


Support recovery: another common question in such settings is how well can we estimate the support of a signal.  That is, instead of deciding only if there are anomalous items or not, we need to determine which of the items are anomalous.  This is also an interesting problem to study for dynamically evolving signals, although a precise formulation of the objective and performance metric for such estimators is less immediate than for static signals.




§ ACKNOWLEDGEMENTS


This work was partially supported by a grant from the Nederlandse organisatie voor Wetenschappelijk Onderzoek (NWO 613.001.114). We are very grateful for the comments of the two anonymous referees, which helped improving the presentation.



§ APPENDIX



We write

    (Ω_c )    ≥( { N-1 >mp/2}∩{∀ j: l_j ≤ cm/N }) 
        = [ { N-1 > mp/2 }[ {∀ j: l_j≤ cm/N } | N ] ]  ,


We first lower bound the inner conditional probability.  Note that if N≤ c this probability is one (since cm/N≥ m and l_j ≤ m by definition).  When N>c, we will upper bound the probability of the complementary event.

Note that given N the distribution of  is uniform from the set of 0-1 sequences of length m containing exactly N ones, and for which also θ_m =1.  Hence, to upper bound (∃ j: l_j > cm/N), we simply need to count the number of sequences described above for which we have a long block.

We can get an upper bound on this count in the following way.  First note that since the last element of the sequence is always one, we can simply think of sequences of length [m-1] containing N-1 ones.  Consider an interval of length cm/N in the set [m-1].  Now consider the sequences containing N-1 ones, and for which there are no ones in the aforementioned interval.  Note that for all such sequences the existence of at least one long interval is guaranteed.  We can simply count how many 0-1 sequences can be generated like this.  This number is an upper bound on the number of 0-1 sequences that have N ones, the last element of the sequence is one and for which ∃ j: l_j > cm/N.

We thus have

    (∃ j: l_j> cm/N |N)    ≤ (m-cm/N) m-cm/N  N-1/m-1  N-1
        = (m-cm/N) (m-cm/N)(m-cm/N -1)… (m-cm/N -N+2)/(m-1)(m-2)… (m-N+1)
       ≤m/m-1(1-c/N) ( m-cm/N/m-2)^N-2
        < ( m-cm/N/m-2)^N-2 .

Now consider the logarithm of the expression above.  Using log (1+x) ≤ x, we get

    log (∃ j: l_j> cm/N |N)     < (N-2) ( logm/m-2 + log (1-c/N) ) 
       ≤ (N-2) ( 2/m-2 - c/N) 
       ≤ -log2 ,

whenever c≥ 6+3log 2, using the fact that 3≤ c≤ N≤ m.

Hence (Ω_c ) ≥ (N-1 >mp/2)/2.  All that remains is to use the fact that N-1 ∼ (m-1,p).  For instance Chebyshev's inequality yields

    (N-1 ≤ mp/2) ≤4(m-1)p(1-p)/(mp)^2≤ 1/2  ,

when p≥ 8/m and so the claim is proved.


chicago


