Distributed Change Detection Based on Average Consensus
Qinghua Liu∗and Yao Xie†

arXiv:1710.10378v2 [eess.SP] 20 Nov 2017

November, 2017

Abstract
Distributed change-point detection has been a fundamental problem when performing real-time monitoring using sensor-networks. Most existing algorithms require local
sensors to exchange information with a global fusion center. We present a distributed
detection algorithm, where each sensor only exchanges CUSUM statistic with their
neighbors based on average consensus, and an alarm is fired when local statistic exceeds
a pre-specified global threshold. We provide theoretical performance bounds showing
that the performance of the fully distributed scheme can match the centralized algorithms under some mild conditions. Numerical experiments demonstrate the good
performance of the algorithm.
Keywords: Change-point sequential detection, local communication, distributed
network, CUSUM decision

1

Introduction

Detecting an abrupt change from data collected by sensor-networks has been a fundamental
problem in various applications, such as cybersecurity [1, 2] and environmental monitoring
[3]. The goal is to detect the change as quickly as possible while the false alarm is under
control.
Various distributed change-point detection methods have been developed based on the
classic CUSUM and Shiryaev-Roberts procedures [4, 5]. Most of the existing approaches
[2, 6–8] require a fusion center that gathers information (raw data or statistics) from all
sensors to perform decision centrally. For instance, [8] requires a global center to collect all
the local CUSUM statistics from all the sensors and utilizes their sum to make decision.
This may be difficult to implement with limited communication bandwidth: for instance,
when some nodes are too far from the central hub. On the other hand, there are approaches
where each sensor makes decision using its own data and only transmits a one-bit signal to
central hub once a local alarm has been trigged (e.g., [7, 9]). However, this approach can
be improved if neighboring sensors can exchange information, which has become practical
in sensor networks with the ever developing technology.
In this paper, we study a new distributed multi-sensor change-point detection procedure
based on the so-called average consensus scheme [10], by allowing sensors to exchange
their local CUSUM statistics. This scheme does not involve explicit point-to-point message
passing or routing; instead, it diffuses information across the network by updating their
∗

Department of Electronic Engineering,
Tsinghua University,
China;
qh14@mails.tsinghua.edu.cn
†
ISYE, Georgia Institute of Technology, USA; Email: yao.xie@isye.gatech.edu.

1

Email:

liu-

Center

(a) with fusion center

(b) w/o fusion center

Figure 1: Distributed change-point detection (a) with a fusion center in [7], where all
sensors send data to central hub, and (b) without fusion center, where sensors perform
local consensus average.
own statistics by performing a weighted average of neighbors’ statistics [11]. Therefore,
each sensor performs detection locally using only the consensus result available to itself. An
alarm is fired whenever any sensor detects a change. Hence, our scheme requires no global
fusion center and allows each sensor to utilize neighboring data. Figure 1 demonstrates the
different graph topologies of our approach and the conventional scheme with a fusion center.
We demonstrate the good performance of our proposed method via numerical examples.
The main theoretical contributions of the paper are the analysis of our detection procedure in terms of the two fundamental performance metrics: the average run length (the
reciprocal of false alarm rate) and the expected detection delay. We show that for a system
consisting of N sensors, using the average consensus scheme, the expected detecting delay
can nearly be reduced by a factor of N compared to a system without communication,
under the same false alarm rate.
Some recent works [12–14] study a related but different problem, the distributed sequential hypothesis test based on average consensus, which aims to resolve two hypotheses.
It can be viewed as a case when the change-point happens at the first moment. There
exists a major difference in our analysis from the analysis for this problem. In sequential
hypothesis test, the local log-likelihood statistic accumulates linearly, while in sequential
change-point detection, the local detection statistic is recursively computed using CUSUM,
and the local likelihood statistic accumulates nonlinearly due to a non-linear transformation
in the CUSUM procedure. This results in a more challenging case for analysis and requires
significantly different techniques.

2

Preliminary

We first introduce some necessary notations and background.
Definition 1. Log-likelihood ratio (LLR) Suppose we have two distinct distributions P1
and P2 . Define the probability density function of P1 and P2 as f1 (x) and f2 (x), respectively.
Then the log-likelihood radio function (LLR) between distribution P2 and P1 is defined as
L(x) = log

f2 (x)
.
f1 (x)

(1)

Assume a sequence of observations {xt }+∞
t=1 . There exists a change-point τ , and two
i.i.d.

i.i.d.

different distributions P1 , P2 such that for t < τ , xt ∼ P1 and for t ≥ τ , xt ∼ P2 . The
classical CUSUM procedure is based on the likelihood ratio to detect the change of the data
distribution.
2

Definition 2. (CUSUM Procedure) The CUSUM procedure is a stopping time that
stops the first time the likelihood based statistic exceeds a threshold b:


Ts = inf t > 0 : max

1≤i≤t

t
X

L(xk ) ≥ b .

(2)

k=i

Under normal circumstances, the larger b is, the larger the detection delay and the smaller
the false alarm rate. The stopping time Ts has a recursive implemention as below

y t+1 = max{y t + L(xt+1 ), 0}, Ts = inf t > 0 : y t ≥ b .

3

Consensus based detection procedure

We represent an N -sensor network using a graph G = (V, E), where V and E are the sensor
set and edge set, respectively. There exists an edge between sensor i and sensor j if and
only if they can communicate with each other. Without loss of generality, we assume that
the graph is connected; since if there is more than one connected component, we can apply
our algorithm to each of them separately. Assume the topology of the sensor network is
known (e.g., by system design).
Denote data observed by the sensor v at time t as xtv . There exists a change time τ
i.i.d.

i.i.d.

such that for t < τ , xtv ∼ Pv1 and for t ≥ τ , xtv ∼ Pv2 . The data observed at different
sensors are mutually independent of each other. We also assume the change occurs to all
sensors at the same time.
Assume the nodes exchange information via a weighted consensus matrix W ∈ RN ×N .
We assume consensus matrix W ∈ RN ×N satisfying the following conditions (by design):
• Wij > 0 if sensor i and sensor j are connected and Wij = 0 if sensor i and sensor j
are not connected.
• W1 = 1 and WT = W.
• The second largest eigenvalue modulus of W, defined as λ2 (W), is smaller than 1.
As long as the graph is connected, the consensus matrix W satisfying the above conditions
always exists. We will present a method to design W satisfying the above conditions in
Section 5.3.
Our algorithm contains three steps at each sensor, as summarized in Algorithm 1, which
we present below:
Step 1: Form a local CUSUM statistic at each sensor:
yvt+1 = max{yvt + Lv (xt+1
v ), 0}, v ∈ V,
where Lv (·) is the LLR between Pv2 and Pv1 .
Step 2: Sensors exchange information with their neighbors according to the pre-determined
topology and weights, as follows
X

zvt+1 =
Wvu zut + yut+1 − yut , v ∈ V,
u∈N (v)

where N (v) contains sensor v and its neighbor sensors. To update the auxiliary variable
zvt at sensor v in this process, we only need the information from sensor v’s neighbors due
to the first property of the consensus matrix. Therefore, the communication process is
completely local and the detection is fully distributed.
3

Algorithm 1: Distributed Change-point Detection.
Parameter: {ov }v∈V , {yv }v∈V , {zv }v∈V and b.
Initialization: ov = yv = zv = 0 for all v ∈ V.
For t = 1, 2 · · ·
1) Sample xtv , v ∈ V.
2) Compute CUSUM statistic at each sensor:
ov = yv , v∈ V.
yv = max yv + Lv (xtv ), 0 , v ∈ V.
3) Communicate
with neighbors:
P
zv = u∈N (v) Wvu (zu + yu − ou ), v ∈ V.
4) Detect change if there exits a zv ≥ b, v ∈ V.
End
Remark 1. Since W1 = 1 and WT = W, it is not difficult to verify that
X
X
zvt =
yvt holds for all t.
v∈V

v∈V

Step 3: Perform detection by comparing zvt with a predetermined threshold b at each sensor
v ∈ V. As long as there exists one v ∈ V such that zvt ≥ b, a global alarm is fired.
In summary, our detection procedure corresponds to the following stopping time

Ts = inf t > 0 : max zvt ≥ b .
(3)
v∈V

4

Theoretical analysis of ARL and EDD

In this section, we present the main theoretical results. First, we define necessary performance metrics: the average run length (ARL) and the expected detection delay (EDD) [5]:
Definition 3. (ARL and EDD)
EDD = E[Ts |τ = 1],

(4)

ARL = E[Ts |τ = ∞].

(5)

In the definition above, τ = ∞ means that the change-point never occurs. Intuitively,
EDD can be interpreted as the delay time before detecting the change and ARL can be
interpreted as the expected duration between two false alarms, which is the reciprocal of
false alarm rate.
In addition, we make the following assumptions
Assumption 1.
1. All the sensors share the same distribution P1 and P2 , and thus the
same log-likelihood radio function L(·).
2. For x ∼ P1 and x ∼ P2 , random variable L(x) obeys sub-Gaussian distribution.
The sub-Gaussian distribution includes many important cases such as Student’s tdistribution, Gaussian distribution and Beta Distribution, and it is a commonly seen property for the LLR. For instance, [13] studied distributed sequential hypothesis test such that
all the sensors share the same P1 = N (0, I), P2 = N (u, I) and L(x) = uT x−kuk2 /2. Hence,
when x ∼ P1 , L(x) ∼ N (−kuk2 /2, kuk2 ) and when x ∼ P2 , L(x) ∼ N (kuk2 /2, kuk2 ).
4

Remark 2. The above assumption is made purely to simplify theoretical analysis. The
detection procedure can still be implemented without this assumption.

4.1

Theoretical Analysis of ARL

First we present an asymptotic lower bound for the ARL defined in (4). Assume that the
mean and variance of L(x) when x ∼ P1 are given by µ1 and σ1 , respectively. Note that
since −µ1 corresponds to the Kullback-Leibler (KL)-divergence from P2 to P1 , µ1 is always
nonpositive (can be shown using Jensen’s inequality).
The following theorem establishes a lower bound for ARL and shows that it increases
at least exponentially as N increases.
Theorem 1 (Lower-bound for ARL). When the detection threshold b tends to infinity,
we have
"

2 #

µ1 b
N
ARL ≥ exp − 2 2N − 2
N +1
σ1
"√
# 
2 !

√
−µ1 µ1 λ2 (W)
N
+
+ o(1)
b .
2N − 2
2
N +1
σ1 [1 − λ2 (W)]
The main ingredient of the proof is concentration inequality, which is used to find p ∈ R
as large as possible such that
lim P (Ts ≤ p) = 0.
b→+∞

Then we can obtain ARL≥ p. The detailed proof is delegated to appendix.
Remark 3. Intuitively, as the number of sensors increases, the false alarm rate increases
because we take the one-shot scheme similar to [9]. The situation in our algorithm, however, is different due to local communications. Moreover, Theorem 1 demonstrates that the
lower bound of ARL is related with the second largest eigenvalue modulus of the consensus
matrix. The smaller the second largest eigenvalue modulus, the larger the lower bound of
ARL. This is similar to observation made for the original average consensus paper [10] and
mixing Markov chain problem [15], where smaller second largest eigenvalue modulus can
lead to faster convergence speed. Previous works [10, 15, 16] have studied how to design the
consensus matrix to get the smallest second largest eigenvalue modulus. Their results can
be adapted to design the consensus matrix in this paper, as we shown in numerical examples
in Section 5.3.

4.2

Theoretical Analysis of EDD

In this section, we analyze the EDD, i.e. the expected detection delay, assuming that the
distribution of samples changes at time 0 (which provides an upper bound to EDD [17]).
Denote the mean and the variance of L(x) for x ∼ P2 as µ2 and σ2 , respectively. Note that
µ2 corresponds to the KL-divergence from P1 to P2 , so µ2 is nonnegative.
Lemma 1 (Upper-bound for EDD). When the detection threshold b tends to infinity,
we have
EDD ≤

b
(1 + o(1)) .
µ2
5

The main ingredient of the proof is again concentration inequality, which shows
lim

b→+∞

+∞
X

P (Ts = t) t = 0,

∀ε > 0.

b(1+ε)
t=[ µ ]+1
2

The proof can be found in the appendix.
By combining Theorem 1 with Lemma 1, we explicitly characterizes the relationship to
ARL.
Theorem 2. When the detection threshold b tends to infinity, under the constraint ARL ≥
γ, we have
EDD ≤

log γ (1 + o(1))
σ12
×
.
N µ2
−2µ1 (1 − N 2 /(N + 1)2 )

Theorem 2 shows that EDD can be reduced by roughly a factor of N by using local
communications compared to the scheme with no communication [9]. Moreover, by comparing Theorem 2 with the results in [6, 8], one can find that the theoretical performance
of our decentralized algorithm is nearly as optimal as the existing centralized algorithms.

5

Numerical Experiments

In this section, we present several numerical experiments to verify the performance of our
algorithm. Assume P1 is N (0, 1) and P2 is N (1, 1). Thus, µ1 = −0.5, µ2 = 0.5 and
σ1 = σ2 = 1.

5.1

Comparison with one-shot scheme

First consider a simple four-node network. We compare a line topology with a network
of isolated nodes (i.e., no communication) to show the effect of communication. Here the
isolated case corresponds to the one-shot detection scheme in [9], where each sensor performs
a CUSUM procedure separately and does not communicate with their neighbors; as long as
there is one CUSUM statistic exceeding the threshold, a change is detected. In our case,
sensors cooperate with each other. The consensus matrix used for communication is as
below (here the diagonal entries are non-zero meaning that a sensor incorporates its own
data when computing the local statistic):


1/3
2/3
0
0

W=

2/3
1/6
1/6
0

0
1/6
1/2
1/3

0
0 
1/3 .
2/3

The detection performance shown in Figure 2 demonstrates that the change can be detected
approximately four times faster under the same ARL with our scheme, which is consistent
with the theoretical prediction in Theorem 2.

5.2

The impact of network topology

In the second example, we compare the performance of our algorithm on two different topologies, a line network consisting of four nodes and K4, which is a complete graph consisting
of four mutually connected nodes [18]. The line is the worst topology for communication
6

EDD−ARL

50
Four Isolated Nodes
Four Cooperating Nodes

45
40

EDD

35
30
25
20
15
10
5
4

5

10

6

10

10

ARL

Figure 2: Communication versus No communication [9] in fully distributed network.

14
13

Line
K4

12

EDD

11
10
9
8
7
6

4

5

10

10
ARL

(a) Line

(b) K4

(c) Line Versus K4

Figure 3: Two different topology consisting of four nodes.

7

6

10

EDD−ARL

10
Maximum degree chain matrix
Best weighted adjacency matrix

9
8

EDD

7
6
5
4
3

5

6

10

7

10

10

ARL

Figure 4: Optimized consensus matrix [15] versus Maximum degree chain matrix
because the information at one end needs to travel all edges before it reaches another end
while K4 is the best because the information at one sensor can be directly passed to other
sensors via only one edge. We use the following consensus matrices for the two networks,
respectively




1/3

Line:

2/3
1/6
1/6
0

2/3
0
0

0
1/6
1/2
1/3

0
0 
1/3
2/3

1/4

K4:

1/4
1/4
1/4

1/4
1/4
1/4
1/4

1/4
1/4
1/4
1/4

1/4
1/4
1/4
1/4

Their second largest eigenvalue modulus are 0.86 and 0, respectively. According to our
previous analysis, the graph with smaller second largest eigenvalue modulus should have
smaller EDD under the same ARL, which is consistent with the experiment results shown
in Figure 3(c).

5.3

Optimized weights versus maximum degree chain

In the last example, we compare two networks with the same topology: the first network
is the maximum degree chain network [15], which uses unity weights on all edges, and the
second network uses optimized weights using the algorithm in [15]. The optimized weights
are obtained for a fixed topology by minimizing the second largest eigenvalue modulus to
achieve faster convergence. The optimal consensus matrix obtained using the algorithm
in [15], which is solved numerically from an optimization problem and the resulted weight
matrix given as below
 0 0 0.34 0 0.34 0.08 0 0.09 0.15 0 
0

0

0.13

0

0.13 0.13

0

0.26

0

0.35

0.13 0.27 0.13 0.13 0
0
0
0
0
 0.34
0
0 0.13 0 0.13 0.13 0.26 0
0 0.35 
 0.34
0.13 0.13 0.13 0
0 0.16 0.11 0
0 
W =  0.08 0.13
0.13 0 0.26 0 0.14 0.26 0  .
 0 0 00 0.26
0.16 0 0.13 0.1 0.34 0 
0.09 0.26
0.15 0
0 0.35

0
0
0

0 0.11 0.14 0.1 0.04 0.25 0
0
0 0.26 0.34 0.25 0
0
0.35 0
0
0
0
0
0.3

The maximum degree chain network has the following weights (with the same topology as
the network above):

Wij =


i∈V di ,
1/ max
P
1−
0,



i 6= j and (i, j) ∈ E
j∈N (i) Wij , i = j
otherwise,

8

(6)

where di is the number of neighbors of sensor i. Their second largest eigenvalue modulus are
0.5722 (optimized weights) and 0.7332 (maximum degree network), respectively. Figure 4
shows that the optimized consensus matrix achieves certain performance gain by optimizing
weights for the same network topology, which is consistent with Theorem 1. This example
shows that when fixing the network topology (which corresponds to fixing the support of W,
i.e., the location of the non-zeros), there are still certain benefits of optimizing the weights
on the consensus schemes to achieve better performance for the change-point detection
procedures.

6

Conclusion

In this paper, we present a new distributed change-point detection algorithm based on
average consensus, where sensors can exchange CUSUM statistic with their neighbors and
perform local detection, and thus no fusion center is needed. We show by allowing sensors
to communicate and share information with their neighbors, the expected detection delay
can be reduced by a factor of N for a network consisting of N sensors, while the ARL is
kept constant.

References
[1] A. Lakhina, M. Crovella, and C. Diot, “Diagnosing network-wide traffic anomalies,” in
ACM SIGCOMM Computer Communication Review, vol. 34, no. 4. ACM, 2004, pp.
219–230.
[2] A. G. Tartakovsky and V. V. Veeravalli, “An efficient sequential procedure for detecting changes in multichannel and distributed systems,” in Information Fusion, 2002.
Proceedings of the Fifth International Conference on, vol. 1. IEEE, 2002, pp. 41–48.
[3] J. Chen, S.-H. Kim, and Y. Xie, “S3 T : An efficient score-statistic for spatio-temporal
surveillance,” arXiv preprint arXiv:1706.05331, 2017.
[4] E. S. Page, “Continuous inspection schemes,” Biometrika, vol. 41, no. 1/2, pp. 100–115,
1954.
[5] G. Lorden, “Procedures for reacting to a change in distribution,” The Annals of Mathematical Statistics, pp. 1897–1908, 1971.
[6] A. G. Tartakovsky and V. V. Veeravalli, “Quickest change detection in distributed
sensor systems,” in Proceedings of the 6th International Conference on Information
Fusion, 2003, pp. 756–763.
[7] ——, “Asymptotically optimal quickest change detection in distributed sensor systems,” Sequential Analysis, vol. 27, no. 4, pp. 441–475, 2008.
[8] Y. Mei, “Efficient scalable schemes for monitoring a large number of data streams,”
Biometrika, vol. 97, no. 2, pp. 419–433, 2010.
[9] O. Hadjiliadis, H. Zhang, and H. V. Poor, “One shot schemes for decentralized quickest
change detection,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3346–
3359, 2009.

9

[10] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Systems &
Control Letters, vol. 53, no. 1, pp. 65–78, 2004.
[11] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor fusion based on
average consensus,” in Proceedings of the 4th international symposium on Information
processing in sensor networks. IEEE Press, 2005, p. 9.
[12] S. Li and X. Wang, “Order-2 asymptotic optimality of the fully distributed sequential
hypothesis test,” arXiv preprint arXiv:1606.04203, 2016.
[13] A. K. Sahu and S. Kar, “Distributed sequential detection for Gaussian shift-in-mean
hypothesis testing,” IEEE Transactions on Signal Processing, vol. 64, no. 1, pp. 89–103,
2016.
[14] K. Liu and Y. Mei, “Improved performance properties of the CISPRT algorithm for
distributed sequential detection,” Submitted, 2017.
[15] S. Boyd, P. Diaconis, and L. Xiao, “Fastest mixing markov chain on a graph,” SIAM
review, vol. 46, no. 4, pp. 667–689, 2004.
[16] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed average consensus with least-meansquare deviation,” Journal of Parallel and Distributed Computing, vol. 67, no. 1, pp.
33–46, 2007.
[17] Y. Xie and D. Siegmund, “Sequential multi-sensor change-point detection,” Annals of
Statistics, vol. 41, no. 2, pp. 670–692, 2013.
[18] J. A. Bondy, U. S. R. Murty et al., Graph theory with applications.
vol. 290.

10

Citeseer, 1976,

7

Appendix

For the simplicity of proof, we first number the sensors from 1 to N . Then, we use vector
T

t T and vector zt
Lt to respresent L(xt1 ), · · · , L(xtN ) , vector yt to represent y1t , · · · , yN

t T . Now, our algorithm can be rewritten in the following form
to represent z1t , · · · , zN
yt+1 = (yt + Lt+1 )+ ,
zt+1 = W(zt + yt+1 − yt ),

Ts = inf t > 0 : kzt k∞ ≥ b .

(7)

Firstly, we prove some useful lemmas before reaching the main results.
Lemma 2. (Hoeffding Inequality) Let Xi be independent, mean-zero, σi2 -sub-Gaussian
random variables. Then for K > 0,


n
X
K2
.
P(
Xn ≥ K) ≤ exp − Pn
2 i=1 σi2
i=1
i.i.d.

Lemma 3. Consider a sequence of random variables Xk ∼ P, for k = 1, 2, . . . , t. P
is a sub-Gaussian distribution and its mean and variance are defined as µ1 < 0 and σ1 ,
respectively. Given K > 0 large enough, we have




t
k
X
X
2K
2Kµ1


P
Xq > K < −
exp
.
µ1
σ12
q=1
k=1

Proof.
Case 1. For 0 < t ≤ [− 2K
µ1 ], by Hoeffding Inequality, we have




k
t
t
X
X
X
1
K
−
kµ
1
2
exp − ( √
P
Xq > K  <
) .
2
kσ1
q=1

k=1

Using

K−kµ
√ 1
k

k=1

√
≥ 2 −Kµ1 and t ≤ − 2K
µ1 , we get
t
X
k=1


P

k
X
q=1


2K
exp
Xq > K  < −
µ1

Case 2. For [− 2K
µ1 ] + 1 ≤ t, by (9), we have




t
k
X
X
2Kµ1
2K
P
Xq > K  < −
exp
+
µ1
σ12
k=1

(8)

q=1



2Kµ1
σ12

t
X
k=[− 2K
]+1
µ1




P

.

k
X

(9)


Xq > K  .

q=1

Utilizing Hoeffding Inequality and k ≥ [− 2K
µ1 ] + 1, we get






k
X
1
K
−
kµ
9Kµ
1
1
2
P
Xq > K  < exp − ( √
) ≤ exp
.
2
4σ12
kσ1
q=1

11

(10)

(11)

Besides, for k ≥ [− 2K
µ1 ] + 1 ,we have


1 2




√
exp − 12 ( K−(k+1)µ
)
3µ21
K2
µ2
k+1σ1

 = exp − 12 +
< exp − 2 .
1 2
2σ1
2k(k + 1)σ12
8σ1
√
exp − 12 ( K−kµ
)
kσ

(12)

1

Then, utilizing Hoeffding Inequality , (11) and (12), we get


t
k
X
X
P
Xq > K 
q=1

k=[− 2K
]+1
µ
1

<

t
X
]+1
k=[− 2K
µ



1 K − kµ1 2
exp − ( √
)
2
kσ1

1

<

t
X


exp

]+1
k=[− 2K
µ1

exp
<



9Kµ1
4σ12

9Kµ1
4σ12



3µ2
× exp − 12
8σ1




2K
]−1
k − [−
µ1



.

3µ2
1 − exp − 8σ12

(13)

1

From (13), we know that the second term on the RHS of (10) is a small quantity compared
with the first term provided K large enough, so we just neglect it and get


t
k
X
X
2K
2Kµ1 
P
Xq > K  < −
exp
.
(14)
µ1
σ12
k=1

q=1

Given ε > 0 and p > 0, we define event
B(ε, p) = {|L(xti )| < εb, for i = 1, . . . , N and t = 1, . . . , p},
where b is the pre-specified threshold in detection. Besides, we use {Ts = p} to represent
the event that our algorithm detects the change at t = p.
Lemma 4. For any t ≤ p, we have
√

PN
{Ts = t} ∧ B(ε, p) ⊂



t
j=1 yj

N

> (1 −

N ελ2
)b ∧ B(ε, p).
1 − λ2

Proof. Throughout the proof of this lemma, we assume B(ε, p) happens. First, by the
recursive form of our algorithm in (7) and the definition of B(ε, p), for any sensor j, we

12

have
|zjt

PN
−

≤kzt −
=k

t
X

t
i=1 yi

N
PN

|=

t
i=1 zi

N

≤

≤

k=1
t
X

PN
−

t
i=1 zi

N

|

1k2
1 T k
11 )(y − yk−1 )k2
N

(Wt−k+1 −

k=1
t
X

|zjt

λt−k+1
kyk − yk−1 k2
2
λt−k+1
kLk k2
2

k=1

≤

t
X

√
N εb
λt−k+1
2

k=1

√
≤

N ελ2 b
,
1 − λ2

where λ2 is the second largest eigenvalue modulus of W. If {Ts = t} happens, then zjt > b
holds for some j, which, together with the inequality above, leads to
PN t
√
N ελ2
j=1 yj
> (1 −
)b.
N
1 − λ2

Lemma 5. Suppose we have a sequence of independent random variables Y1 , · · · , YN . Take
any integer M > N and let C(M, N ) to be the set below,
N
X

(i1 , · · · , iN ) : ij ∈ N and M − N ≤
ij ≤ M .
j=1

Then we have

P

N
X





N
X Y
ij K
P Yj >
.
M

Yj > K  ≤

j=1

C(M,N ) j=1

P
Proof. ∀(y1 , · · · , yN ) ∈ {(Y1 , · · · , YN ) : N
j=1 Yj > K}, take
"
#
yj M
ij = PN
for j = 1, . . . , N.
j=1 yj
We can easily verify that M − N ≤
N
X

Yj > K ⊂
(Y1 , · · · , YN ) :
j=1

PN

j=1 ij

[
C(M,N )



≤ M and yj > ij K/M . Therefore, we have

ij K
(Y1 , · · · , YN ) : Yj >
for j = 1, . . . , N
M

13


.

Because Yj is independent with each other, together with the property of probability measure, we get




N
N
X
X Y
ij K


.
P
Yj > K ≤
P Yj >
M
j=1

7.1

C(M,N ) j=1

Proof of Theorem 1

First, we calculate the probability that our algorithm stops within time p. The value of p
is to be specified later.
p
X

=
≤
≤

t=1
p
X
t=1
p
X

P(Ts = t)

P ({Ts = t} ∧ B(ε, p)) + P {Ts = t} ∧ B̄(ε, p)

P ({Ts = t} ∧ B(ε, p)) + P B̄(ε, p)

t=1
p
X



(εb + µ1 )2
P ({Ts = t} ∧ B(ε, p)) + 2N p × exp −
,
2
2σ
1
t=1

where the last inequality is from Hoeffding Inequality and Assumption 1. The value of ε is
to be specified later. √
N ελ2
Denote b̄ = N (1− 1−λ
)b, then b̄ will also tend to infinity as b tends to infinity provided
2
ε small enough. By Lemma 4, we have




p
p
N
X
X
X
(εb + µ1 )2
P(Ts = t) ≤
P {
yjt > b̄} ∧ B(ε, p)  + 2N p × exp −
.
(15)
2
2σ
1
t=1
t=1
j=1
By Lemma 5, we have


N
X
P {
yjt > b̄} ∧ B(ε, p)  ≤
j=1



N
X Y
ij b̄
t
P {yj >
} ∧ B(ε, p) ,
M

(16)

C(M,N ) j=1

where the value of M is to be specified later. If yjt > ij b̄/M , then there must exist 1 ≤ k ≤ t
P
such that yjt = tq=k L(xqj ) ≥ ij b̄/M . So, we have



 X
t
t
X
ij b̄
ij b̄
P {yjt >
} ∧ B(ε, p) ≤
P {
L(xqj ) >
} ∧ B(ε, p) .
M
M
k=1

(17)

q=k

The influence of B(ε, p) in (17) can be interpreted as truncating the original distribution
of L(·). It’s obvious that the new distribution is still sub-Gaussian. Besides, the mean and
variance almost keep unchanged provided εb large enough.
14

If ij = 0, we just set the upper bound of the probability in (17) to be 1. If ij 6= 0, by
Lemma 3, we have




t
t
X
X
i
b̄
2i
b̄µ
2i
b̄
j
j
1
j
q
P {
L(xj ) >
exp
} ∧ B(ε, p) < −
.
(18)
M
M µ1
M σ12
k=1

q=k

Plugging (18) into (16), we get


N
X Y
ij b̄
t
} ∧ B(ε, p)
P {yj >
M
C(M,N ) j=1


X Y 2ij b̄
2ij b̄µ1
exp
<
−M µ1
M σ12
C(M,N ) ij 6=0



X  2b̄ N
2b̄µ1
N
≤
exp
(1 −
)
−µ1
M
σ12
C(M,N )


=|C(M, N )|

2b̄
−µ1

N


exp


N
2b̄µ1
(1 −
) .
M
σ12

(19)

Plugging (19) and (16) into (15), we get
p
X
t=1
p
X

P(Ts = t)

N




2b̄
2b̄µ1
N
(εb + µ1 )2
<
|C(M, N )|
exp
(1 −
) + 2N p × exp −
−µ1
M
σ12
2σ12
t=1




N

2b̄
N
(εb + µ1 )2
2b̄µ1
=p |C(M, N )|
(1 −
) + 2N p × exp −
.
exp
−µ1
M
σ12
2σ12


(20)

Next, we will show that as b tends to infinity, the second term on the RHS of (20) is a small
quantity in comparison with the first term if we choose the value of M and ε properly. Note
N
that 2N p is a small quantity in comparison with p |C(M, N )| −2b̄/µ1 , so we only require
N
(εb + µ1 )2
2b̄µ1
(1
−
)
≥
−
.
M
σ12
2σ12

(21)

√

Choosing M = (N + 1)2 and recalling that b̄ = N (1 −

N ελ2
1−λ2 )b,

(21) can be rewritten as
!
√
N ελ2
1−
.
(22)
1 − λ2

(εb + µ1 )2
2(N 3 + N 2 + N )µ1 b
≥−
2
2σ1
(N + 1)2 σ12
p
To ensure that (22) holds as b tends to infinity, ε = 2 −N µ1 /b is sufficient. Plugging the
value of M and ε into (20) and neglecting the second term, we get

N
2b̄
2
P (Ts ≤ p) ≤|C((N + 1) , N )|
−µ1
√
√
3
2

2(N + N + N )µ1 b 4(N 3 + N 2 + N ) −µ1 µ1 λ2 b
× exp
−
+ ln(p) .
2
2
2
2
(N + 1) σ1
(N + 1) (1 − λ2 )σ1
15

3

2

√

+N +N ) −µ1 µ1 λ2
So ∀l > − 4(N (N
, if we take
+1)2 (1−λ )σ 2
2

1



√
2(N 3 + N 2 + N )µ1 b
−
l
p = exp −
b
.
(N + 1)2 σ12
Then we have
lim P (Ts ≤ p)

b→+∞



2

≤ lim |C((N + 1) , N )|
b→+∞

2b̄
−µ1

N

 
 
√
4(N 3 + N 2 + N ) −µ1 µ1 λ2 √
exp − l +
b
(N + 1)2 (1 − λ2 )σ12

=0,
which together with the definition of ARL leads to


√
√
2(N 3 + N 2 + N )µ1 b
4(N 3 + N 2 + N ) −µ1 µ1 λ2
ARL ≥ p = exp −
− l b , ∀l > −
,
(N + 1)2 σ12
(N + 1)2 (1 − λ2 )σ12
which is identical to


 
√
2(N 3 + N 2 + N )µ1 b
4(N 3 + N 2 + N ) −µ1 µ1 λ2 √
ARL ≥ exp −
b ,
+ o(1) +
(N + 1)2 σ12
(N + 1)2 (1 − λ2 )σ12
when b tends to infinity.

7.2

Proof of Lemma 1

First of all, note that P (Ts = +∞) = 0, so given ε > 0, we have
EDD ≤

b(1 + ε)
+
µ2

+∞
X

P (Ts = t) t.

If Ts = t, then we have that zjt−1 < b holds for all j. Since
must exist some yjt−1 < b. Therefore, we have
+∞
X

Note that yjt−1 ≥

b(1+ε)
t=[ µ ]+1
2

q
q=1 L(xj ),

Pt−1



P yjt−1

+∞
X

P (Ts = t) t ≤

b(1+ε)
t=[ µ ]+1
2

(23)

b(1+ε)
t=[ µ ]+1
2

PN

t−1
j=1 zj

=

N


X
P yjt−1 < b t.

PN

t−1
j=1 yj ,

there

(24)

j=1

together with Hoeffding Inequality, we get



t−1

X
< b t ≤P 
L(xqj ) < b
q=1

1
=exp −
2

16



b − (t − 1)µ2
√
t − 1σ2

2 !
t.

(25)

When b is large enough, for any t > [ b(1+ε)
µ2 ], utilizing the similar technique in (12), we get




√ 2 )2
exp − 21 ( b−tµ
b
1
t+1
tσ2

×
) .
≤ exp − (1 −
2 2
t
2
(1 + ε)2
√
exp − 12 ( b−(t−1)µ
)
t−1σ

(26)

2

Plugging (25) and (26) into (24), utilizing the similar technique in (13), we get
+∞
X

P (Ts = t) t

b(1+ε)
t=[ µ ]+1
2

+∞
X

≤

b(1+ε)
t=[ µ ]+1
2


≤N

1
N × exp −
2

b(1 + ε)
+1
µ2





b − (t − 1)µ2
√
t − 1σ2

2 !



ε2 b
exp − 2(1+ε)σ
2
2

.
b
1
1 − exp − 2 (1 − (1+ε)
2)

t

(27)

Note that ∀ε > 0, as b tends to infinity, the RHS of (27) would converge to zero. Therefore,
by (23), we get

b 1 + o(1)
.
EDD ≤
µ2

17

