1

Event-Triggered Control over Unreliable Networks
Subject to Jamming Attacks

arXiv:1503.06980v2 [] 15 Mar 2016

Ahmet Cetinkaya, Hideaki Ishii, and Tomohisa Hayakawa

Abstract— Event-triggered networked control of a linear
dynamical system is investigated. Specifically, the dynamical
system and the controller are assumed to be connected through
a communication channel. State and control input information
packets between the system and the controller are attempted
to be exchanged over the network only at time instants
when certain triggering conditions are satisfied. We provide
a probabilistic characterization for the link failures which
allows us to model random packet losses due to unreliability
in transmissions as well as those caused by malicious jamming
attacks. We obtain conditions for the almost sure stability of
the closed-loop system, and we illustrate the efficacy of our
approach with a numerical example.

I. I NTRODUCTION
One of the main challenges in networked control systems
is that communication between plant and controller may
not always be reliable. State measurement and control input
packets may fail to be transmitted at times due to network
congestion or errors in communication. In the literature,
unreliability of a network is often characterized through
random models for packet loss events [1]. For instance, in
[2], [3], Bernoulli processes are used for modeling packet
losses in a network. Furthermore, in [4], [5], packet loss
events are characterized in a more general way by employing
Markov chains. In these studies, a variety of control methods
are proposed to ensure stability of networked control systems
that face random packet losses.
More recently, cyber security has become a critical issue
in networked control systems since the channels are nowadays connected via the Internet or wireless communications
[6], [7]. Here, in addition to random losses, we consider
communication effects due to jamming attacks initiated by
malicious agents. Such attacks may block the communication
link and effectively prevent transmission of packets between
the plant and the controller. In a few recent works [8]–
[11], networked control problems under malicious jamming
attacks were investigated.
In this paper we explore feedback control of a discretetime linear system over a network that is subject to both
random packet losses due to unreliability of the communication channel and jamming attacks coming from an intelligent
A. Cetinkaya and T. Hayakawa are with the Department of Mechanical and Environmental Informatics, Tokyo Institute of Technology, Tokyo 152-8552, Japan. ahmet@dsl.mei.titech.ac.jp,

hayakawa@mei.titech.ac.jp
H. Ishii is with the Department of Computational Intelligence and Systems Science, Tokyo Insitute of Technology, Yokohama, 226-8502, Japan.

ishii@dis.titech.ac.jp
This work was supported in part by Japan Science and Technology
Agency under the CREST program.

attacker. We employ an event-triggered control framework,
where the plant and the controller attempt to exchange
state and control input information packets only at times
that correspond to event-triggering instants. Following the
approach in [12], [13], we utilize Lyapunov-like functions
to characterize the triggering conditions. The triggering
conditions that we propose in this paper ensure that the
value of a Lyapunov-like function of the state stays within
certain limits. Packet exchanges are attempted only before
the value of the Lyapunov-like function is predicted to exceed
a certain level. In a successful packet exchange scenario,
state measurements are sent from the plant to the controller,
which computes a control input and sends it back to the
plant. However, state measurement or control input packets
may fail to be transmitted due to random packet losses and
jamming attacks. We model random losses using a binaryvalued time-inhomogeneous Markov chain. To characterize
jamming attacks, we follow the approach of [10]. Rather than
specifying predetermined patterns or distributions for the
occurrences of jamming attacks, we allow jamming attacks
to happen arbitrarily as long as the total number of packet
exchange attempts that face jamming attacks are almost
surely bounded by a certain ratio of the number of total
packet exchange attempts.
We consider both the case where random packet losses
and jamming attacks are independent and the case where
the attacker may use information of past random packet
losses in generating a jamming attack strategy. The main
theoretical challenge in dealing with both of these cases
stems from the fact that random losses and jamming attacks
are of different nature and hence have different models.
By utilizing a tail probability inequality for the sum of
processes that represent random losses and jamming attacks,
we show that a probabilistic characterization for the evolution
of the total number of packet exchange failures allows us
to deal with both cases. Based on this characterization, we
obtain conditions for almost sure asymptotic stability of
the closed-loop event-triggered networked control system.
Furthermore, we present a numerical method for finding
stabilizing feedback gains as well as parameters for the
event-triggering mechanism.
The paper is organized as follows. In Section II, we
describe the event-triggered networked control system under random and jamming-related packet losses. We provide
sufficient conditions for almost sure asymptotic stability of
the closed-loop control system in Section III and present
an illustrative numerical example in Section IV. Finally, in
Section V, we conclude the paper.

2

We use a fairly standard notation in the paper. Specifically,
we denote positive and nonnegative integers by N and N0 ,
respectively. We write R for the set of real numbers, Rn for
the set of n × 1 real column vectors, and Rn×m for the set
of n × m real matrices. Moreover, (·)T denotes transpose,
k · k denotes the Euclidean vector norm, and ⌊·⌋ denotes the
largest integer that is less than or equal to its real argument.
The notation P[·] denotes the probability on a probability
space (Ω, F , P) with filtration {Fi }i∈N0 .
II. E VENT-T RIGGERED N ETWORKED C ONTROL
In this section we provide the mathematical model for the
event-triggered networked control system. We then present a
characterization of a network that faces random packet losses
and packet losses caused by jamming attacks.
A. Event-Triggered Control System
Consider the linear dynamical system
x(t + 1) = Ax(t) + Bu(t),

x(0) = x0 ,

t ∈ N0 ,

(1)

where x(t) ∈ Rn and u(t) ∈ Rm denote the state and the
control input; furthermore, A ∈ Rn×n and B n×m are the
state and input matrices, respectively.
In this paper, we use the event-triggering framework (see
[13] and the references therein), where the control input is
only updated when a certain triggering condition is satisfied.
The triggering condition is checked at each time step at the
plant side.
In the networked operation setting, the plant and the
controller are connected through a communication channel and attempt to exchange information packets at times
corresponding to event-triggering instants. We consider the
case where packets are transmitted without delay, but they
may get lost. In a successful packet exchange scenario, at
a certain time instant, measured plant states are transmitted
to the controller, which generates a control input based on
the received state information and sends a packet containing
the control input information to the plant. The transmitted
control input is applied at the plant side. In the case of an
unsuccessful packet exchange attempt, either the measured
state packet or the control input packet may get dropped, and
in such cases control input at the plant side is set to 0.
We use τi ∈ N0 , i ∈ N0 , to denote the time instants at
which packet exchanges between the plant and the controller
are attempted. To characterize these time instants we utilize a
quadratic Lyapunov-like function V : Rn → [0, ∞) given by
V (x) , xT P x, where P > 0. Letting τ0 = 0, we describe
τi , i ∈ N, and control input u(t) applied to the plant by
n
τi+1 , min t ∈ {τi + 1, τi + 2, . . .} : t ≥ τi + θ
o
or V (Ax(t) + Bu(τi )) > βV (x(τi )) , (2)
u(t) , (1 − l(i)) Kx(τi ), t ∈ {τi , . . . , τi+1 − 1},

(3)

for i ∈ N0 , where β ∈ (0, 1), θ ∈ N, and {l(i) ∈ {0, 1}}i∈N0
is a binary-valued process that characterizes success or
failure of packet exchange attempts. When l(i) = 0, packet

Fig. 1.

Networked control system operation

exchange attempt at time τi is successful and the piecewiseconstant control input at the plant side is set to u(τi ) =
Kx(τi ), where K ∈ Rm×n denotes the feedback gain.
On the other hand, the case l(i) = 1 indicates that either
the packet sent from the plant or the packet sent from the
controller is lost at time τi . Again, in such cases, control
input at the plant side is set to 0.
The triggering condition (2) involves two parts. The part
characterized by V (Ax(t) + Bu(τi )) > βV (x(τi )) ensures
that after a successful packet exchange attempt at τi , the
value of the Lyapunov-like function V (·) stays below the
level βV (x(τi )) until the next packet exchange attempt.
Furthermore, the triggering condition t ≥ τi + θ ensures
that two consecutive packet exchange attempt instants are at
most θ steps apart, that is, τi+1 − τi ≤ θ, i ∈ N0 . Although
the specific value of θ does not affect the results developed
below, the boundedness of packet exchange attempt intervals
guarantees that τi (and hence V (x(τi ))) are well-defined for
each i ∈ N. In practice, the value of θ can be selected
considering how frequent the plant state is desired to be
monitored by the controller side.
Operation of the event-triggered networked control system
is illustrated in Fig. 1. The triggering condition (2) is checked
at the plant side at each step t ∈ N0 . At times t = τi , i ∈ N,
the triggering condition is satisfied and packet exchanges
between the plant and the controller are attempted. For this
example, packet exchange is attempted at time t = τ1 , since
V (Ax(t) + Bu(τ0 )) > βV (x(τ0 )). At this time instant,
the plant and the controller successfully exchange state and
control input packets over the network, and as a result,
control input on the plant side is updated to Kx(τ1 ). Note
that packet exchange attempts are not always successful, and
may fail due to loss of packets in the network. For instance,
the packet exchange attempt at time τ2 fails for the case of
Fig. 1. In this case, the control input at the plant side is set to
0 at time τ2 , which results in an unstable behavior. A packet
exchange is attempted again at the very next time step τ3 ,
since the triggering condition is also satisfied at that instant.
Remark 2.1: The event-triggering framework we describe
above requires a plant-side mechanism for checking the
triggering condition (2) at each time step. If the overall
practical setup of the process does not allow placing such
a mechanism at the plant side, following the self-triggering

3

control approach described in [14], we can use a decision
mechanism at the controller side. In this case, packet exchange times are decided at the controller side based on the
state information obtained at previously successful packet
exchange attempts.
B. Characterization of a Network with Random Packet
Losses and Packet Losses Caused by Jamming Attacks
Packet transmission failures in a network may have different reasons. Packet losses caused by network congestion
may be accurately described using stochastic models [15].
However, only stochastic models would not be enough to
characterize packet losses if the communication channel is
subject to jamming attacks of a malicious agent. In what
follows we characterize the effects of certain stochastic and
jamming-related packet loss models in a unified manner by
investigating dynamical evolution of the total number of
packet exchange failures.
First, we define a nonnegative integer-valued process
{L(k) ∈ N0 }k∈N by
L(k) ,

k−1
X

l(i),

i=0

k ∈ N.

(4)

Note that L(k) denotes the total number of failed packet
exchange attempts during the time interval [0, τk−1 ].
Assumption 2.1: There exist scalars ρ ∈ [0, 1], γk ∈
[0, ∞), k ∈ N, such that
P[L(k) > ρk] ≤ γk ,
X
γk < ∞.

k ∈ N,

(5)
(6)

k∈N

Note that conditions (5) and (6) provide a probabilistic
characterization of the evolution of the total number of packet
exchange failures through scalars ρ ∈ [0, 1], γk ∈ [0, ∞),
k ∈ N. A closely related characterization for packet dropouts
in a communication link is presented in [3]; the scalar ρ in
(5) corresponds to the notion dropout rate discussed there.
The following result is a direct consequence of BorelCantelli lemma (see [16]) and it shows that under Assumption 2.1, the long run average of the total number of failed
packet exchanges is upper bounded by ρ.
Lemma 2.2: If there exist scalars ρ ∈ [0, 1], γk ∈ [0, ∞),
k ∈ N, such that (5), (6) hold, then lim supk→∞ L(k)
≤ ρ,
k
almost surely.
It is important to note that for any packet loss model,
Assumption 2.1 is trivially satisfied with ρ = 1, and γk =
0, k ∈ N, since L(k) ≤ k. On the other hand, as illustrated
in the following, for certain random and jamming-related
packet loss models, ρ can be obtained to be strictly smaller
than 1.
1) Random Losses: To characterize random packet
losses in the communication channel, we utilize timeinhomogeneous Markov chains. Specifically, let {lR (i) ∈
{0, 1}}i∈N0 be an Fi -adapted time-inhomogeneous Markov
chain characterized by initial distributions ϑq ∈ [0, 1], q ∈

{0, 1}, and time-varying transition probabilities pq,r : N0 →
[0, 1], q, r ∈ {0, 1}, such that
P[lR (0) = q] = ϑq , q ∈ {0, 1},

P[lR (i + 1) = r|lR (i) = q] = pq,r (i), q, r ∈ {0, 1}, i ∈ N0 .
The state lR (i) = 1 indicates that the network faces
random packet losses at time τi , and hence the packet
exchange attempt at τi results in failure. Note that in this
characterization, the event that a packet exchange attempt
fails depends on the states of previous packet exchange attempts. Furthermore, transition probabilities between success
(lR (i) = 0) and failure (lR (i) = 1) states of packet exchange
attempts are time-dependent. For instance, the probability of
packet exchange failure at time τi+1 is given by plR (i),1 (i).
It is important to note that the time-inhomogeneous
Markov chain characterization of random packet losses generalizes the Bernoulli and time-homogeneous Markov chain
models that are often used in the literature.
2) Jamming Attacks : For jamming attacks coming from
an intelligent attacker, a model capturing the attack strategy
of a malicious agent has been proposed in [10]. In that study,
the sum of the length of attack durations is assumed to be
bounded by a certain ratio of total time.
We follow the approach of [10] for modeling packet
exchange failures due to a jamming attack. Specifically, let
{lJ (i) ∈ {0, 1}}i∈N0 denote the state of jamming attacks.
The state lJ (i) = 1 indicates that the network is subject to
a jamming attack at time τi . We consider the case where
the number of packet exchange attempts that face jamming
attacks are upper bounded almost surely by a certain ratio
of the total number of packet exchange attempts, that is,
{lJ (i) ∈ {0, 1}}i∈N0 satisfies
P

X
 k−1
i=0

lJ (i) ≤ κ +

k
= 1,
τ

k ∈ N,

(7)

where κ ≥ 0 and τ > 1. In this characterization, among k
packet exchange attempts, at most κ+ τk of them are affected
by jamming attacks. The ratio τ1 corresponds to the notion
jamming rate discussed in [17]. Note that when κ = 0, (7)
implies lJ (i) = 0, i ∈ {0, . . . , ⌊τ ⌋}, almost surely. Scenarios
that involve possible jamming attacks during the first few
packet exchange attempts can be modeled by setting κ > 0.
Note that the characterization in (7) does not require lJ (i),
i ∈ N0 , to follow a particular distribution. In fact, lJ (·) may
be generated in a deterministic fashion, or it may involve
randomness.
3) Combination of Random and Jamming-Related Losses:
In order to model the case where the network is subject
to both random losses and malicious jamming attacks, we
define {l(i) ∈ {0, 1}}i∈N0 by
(
1,
lR (i) = 1 or lJ (i) = 1,
l(i) =
i ∈ N0 , (8)
0,
otherwise,
where {lR (i) ∈ {0, 1}}i∈N0 is a time-inhomogeneous
Markov chain characterizing random packet losses (see Section II-B.1) and {lJ (i) ∈ {0, 1}}i∈N0 satisfying (7) is a

4

binary-valued process that characterizes jamming attacks (see
Section II-B.2).
Proposition 2.3 below provides a range of values for
ρ ∈ (0, 1) that satisfy Assumption 2.1 in the case that the
network under consideration faces both random packet losses
and jamming attacks. In the proof of this result, we utilize
Lemma A.1
for obtaining P
upper bounds on tail probabilities
Pk−1
k−1
of sums i=0 lR (i) and i=0 (1 − lR (i))lJ (i).

Proposition 2.3: Consider the packet loss indicator process {l(i) ∈ {0, 1}}i∈N0 given by (8) where {lR (i) ∈
{0, 1}}i∈N0 and {lJ (i) ∈ {0, 1}}i∈N0 are mutually independent. If there exist scalars p0 , p1 ∈ (0, 1) such that
pq,1 (i) ≤ p1 ,

(9)

pq,0 (i) ≤ p0 , q ∈ {0, 1}, i ∈ N0 ,
(10)
p0
p1 +
< 1,
(11)
τ
hold, then for all ρ ∈ (p1 + pτ0 , 1), there exist γk ∈ [0, ∞),
k ∈ N, that satisfy (5), (6).
Proof: It follows from (8) that
l(i) = lR (i) + (1 − lR (i))lJ (i),

i ∈ N0 ,

and hence, by (4),
L(k) =

k−1
X
i=0

lR (i) +

k−1
X
i=0

(1 − lR (i))lJ (i),

k ∈ N.

(12)

0
Now, let ǫ , ρ − p1 − pτ0 , ǫ2 , min{ 2ǫ , 1−p
2τ }, ǫ1 , ǫ − ǫ2 ,
p0
and define ρ1 , p1 +ǫ1 , ρ2 , τ +ǫ2 . Note that ρ1 ∈ (p1 , 1)
Pk−1
and ρ2 ∈ ( pτ0 , τ1 ). Furthermore, let L1 (k) , i=0 lR (i) and
Pk−1
L2 (k) , i=0 (1 − lR (i))lJ (i). It then follows that

P[L(k) > ρk] = P[L1 (k) + L2 (k) > ρ1 k + ρ2 k]
= 1 − P[L1 (k) + L2 (k) ≤ ρ1 k + ρ2 k]

≤ 1 − P[{L1 (k) ≤ ρ1 k} ∩ {L2 (k) ≤ ρ2 k}]
= P[{L1 (k) > ρ1 k} ∪ {L2 (k) > ρ2 k}]

≤ P[L1 (k) > ρ1 k] + P[L2 (k) > ρ2 k]. (13)
In the following we obtain upper bounds for the two
probability terms on the far right-hand side of (13) using
Lemma A.1.
First, to apply the lemma for the term P[L1 (k) > ρ1 k],
let p̃ = p1 , c̃ = 0, w̃ = 1, and define processes {ξ(i) ∈
{0, 1}}i∈N0 and {χ(i) ∈ {0, 1}}i∈N0 by setting ξ(i) , lR (i),
χ(i) = 1, i ∈ N0 . Then, the conditions
Pk−1 in (41) and (42)
are satisfied. Now, since L1 (k) = i=0
ξ(i)χ(i), it follows
from Lemma A.1 that
(1)

P[L1 (k) > ρ1 k] ≤ γk ,
X (1)
γk < ∞,

k ∈ N,

(14)

(1)

(2)

P[L2 (k) > ρ2 k] ≤ γk ,
X (2)
γk < ∞,

(1−p1 )
1 k+1 ((φ1 −1)p1 +1) −1
.
and φ1 , pρ11 (1−ρ
where γk , φ−ρ
1
(φ−1)p1
1)
Next, we use Lemma A.1 to find an upper bound for
P[L2 (k) > ρ2 k]. Specifically, as a consequence of (7),
conditions (41), (42) hold with p̃ = p0 , c̃ = κ, and w̃ = τ1
together with processes {ξ(i) ∈ {0, 1}}i∈N0 and {χ(i) ∈

k ∈ N,

(16)
(17)

k∈N

(2)

where γk

τ ρ2 (1−p0 )
p0 (1−τ ρ2 ) .

κ+ k
τ

2 k+1 ((φ2 −1)p0 +1)
, φ−ρ
2
(φ2 −1)p0

(1)

−1

and φ2

,

(2)

Now, let γk , γk + γk , k ∈ N. By using (13), (14),
and (16), we obtain (5). Furthermore, as a consequence of
(15) and (17), we have (6) as
X
X (1) X (2)
γk =
γk +
γk < ∞,
k∈N

k∈N

k∈N

which completes the proof.
Note that in Proposition 2.3, {lR (i) ∈ {0, 1}}i∈N0 and
{lJ (i) ∈ {0, 1}}i∈N0 are assumed to be mutually independent
processes. In other words, packet exchange attempt failures
due to jamming attacks are assumed to be independent
of packet exchange attempt failures due to random packet
losses. This assumption would not be satisfied in the case
that the malicious jamming attacker has information of the
past random packet losses in the communication channel and
utilizes this information in the attack strategy. Proposition 2.4
below deals with such cases.
Proposition 2.4: Consider the packet loss indicator process {l(i) ∈ {0, 1}}i∈N0 . Suppose there exists a scalar
p1 ∈ (0, 1) such that (9) and
p1 +

1
< 1,
τ

(18)

hold. Then for all ρ ∈ (p1 + τ1 , 1), there exist γk ∈ [0, ∞),
k ∈ N, that satisfy (5), (6).
Proof: It follows from (8) that
L(k) ≤

k−1
X

lR (i) +

k−1
X

lJ (i),

i=0

i=0

k ∈ N.

Let ǫ , ρ − p1 − τ1 , and define ρ1 , p1 + 2ǫ , ρ2 , τ1 + 2ǫ .
Using arguments similar to the ones used for obtaining (13)
in the proof of Proposition 2.3, we obtain
P[L(k) > ρk] ≤ P[

(15)

k∈N

k

{0, 1}}i∈N0 defined by setting ξ(i) , 1−lR(i), χ(i) = lJ (i),
i ∈ N0 . Now, since
ξ(i) , 1 − lR (i) and χ(i) = lJ (i),
Pk−1
we have L2 (k) = i=0 ξ(i)χ(i); and hence, Lemma A.1
implies that

≤ P[

k−1
X
i=0

k−1
X

lR (i) +

i=0

lR (i) > ρ1 k] + P[

k−1
X

lJ (i) > ρk]

i=0
k−1
X
i=0

lJ (i) > ρ2 k], k ∈ N. (19)

Pk−1
Pk−1
The terms P[ i=0 lR (i) > ρ1 k] and P[ i=0 lJ (i) > ρ2 k]
in (19) respectively correspond to random packet losses and
packet losses due to jamming attacks. First, it is shown in the
Pk−1
(1)
proof of Proposition 2.3 that P[ i=0 lR (i) > ρ1 k] ≤ γk ,

5
k

(1)

1 k+1 ((φ1 −1)p1 +1) −1
where γk , φ−ρ
and φ1 ,
1
(φ−1)p1
Moreover, using Markov’s inequality we obtain

P[

k−1
X
i=0

lJ (i) > ρ2 k] ≤ P[

= P[e

Pk−1
i=0

lJ (i)

k−1
X
i=0

ρ1 (1−p1 )
p1 (1−ρ1 ) .

lJ (i) ≥ ρ2 k]

≥ eρ2 k ] ≤ e−ρ2 k E[e

Pk−1
i=0

lJ (i)

Pk−1

],

(20)

In comparison with Proposition 2.3, Proposition 2.4 provides a more restricted range of values for ρ that satisfy
Assumption 2.1. The interpretation may be that the malicious jamming attacker is more knowledgeable and may use
information of the past random packet losses in the attack
strategy.
III. C ONDITIONS FOR A LMOST-S URE A SYMPTOTIC
S TABILITY OF THE N ETWORKED C ONTROL S YSTEM
In this section, we investigate stability of the closed-loop
event-triggered networked control system (1)–(3), which is
a stochastic dynamical system due to probabilistic characterization of packet losses. Below we define almost sure
asymptotic stability for stochastic dynamical systems.
Definition 3.1: The zero solution x(t) ≡ 0 of a stochastic
system is almost surely stable if, for all ǫ > 0 and p̄ > 0,
there exists δ = δ(ǫ, p̄) > 0 such that if kx(0)k < δ, then
(21)

t∈N0

Moreover, the zero solution x(t) ≡ 0 is asymptotically stable
almost surely if it is almost surely stable and
P[ lim kx(t)k = 0] = 1.
t→∞

T

T

ϕP − A P A ≥ 0,
(1 − ρ) ln β + ρ ln ϕ < 0,

· (A + (1 − l(i)) BK) x(τi ), i ∈ N0 . (26)

Now, for the case l(i) = 0, (23) and (26) imply
V (x(τi + 1)) = xT (τi ) (A + BK)T P (A + BK) x(τi )
≤ βxT (τi )P x(τi ).

(23)
(24)
(25)

then the event-triggered control law (2), (3) guarantees
almost sure asymptotic stability of the zero solution x(t) ≡ 0
of the closed-loop system dynamics.
Proof: The proof is composed of three steps. In the
initial step, we obtain an inequality concerning the evolution

(27)

Since τi+1 ≥ τi + 1, it follows from (2) and (27) that
V (x(t)) ≤ βxT (τi )P x(τi )

t ∈ {τi + 1, . . . , τi+1 }.

= βV (x(τi )),

(28)

On the other hand, for the case l(i) = 1, it follows from
(24) and (26) that
V (x(τi + 1)) = xT (τi )AT P Ax(τi ) ≤ ϕxT (τi )P x(τi ).
(29)
Now if τi+1 = τi +1, we have V (x(τi+1 )) ≤ ϕV (x(τi )) due
to (29). If, on the other hand, τi+1 > τi + 1, it means that
V (x(t)) ≤ βV (x(τi )) for t ∈ {τi + 2, . . . , τi+1 }. Therefore,
since β ≤ ϕ,
V (x(t)) ≤ ϕV (x(τi )),

t ∈ {τi + 1, . . . , τi+1 }.

(30)

Using (28) and (30) we obtain
V (x(τi+1 )) ≤ (1 − l(i))βV (x(τi )) + l(i)ϕV (x(τi )), (31)
for i ∈ N0 . Note that the inequality given in (31) characterizes an upper bound on the growth of the Lyapunov function
candidate V (·).
Qk−1
Now, let η(k) , i=0 ((1 − l(i))β + l(i)ϕ). It follows
from (31) that
V (x(τk )) ≤ η(k)V (x(0)),

(22)

In Theorem 3.2 below, we present sufficient conditions for
almost sure asymptotic stability of the zero solution of the
dynamical system (1)–(3).
Theorem 3.2: Consider the linear dynamical system (1).
Suppose that the process {l(i) ∈ {0, 1}}i∈N0 characterizing
packet exchange failures in the network satisfies Assumption 2.1 with scalar ρ ∈ [0, 1]. If there exist a matrix
K ∈ Rm×n , a positive-definite matrix P ∈ Rn×n , and
scalars β ∈ (0, 1), ϕ ∈ [1, ∞) such that
βP − (A + BK) P (A + BK) ≥ 0,

T

V (x(τi + 1)) = xT (τi ) (A + (1 − l(i)) BK) P

k

κ+ τ
for k ∈ N. By (7), we have E[e i=0 lJ (i) ] ≤
] =
PE[e
k−1
κ+ τk
. Therefore, it follows from (20) that P[ i=0 lJ (i) >
e
1
(2)
(2)
ρ2 k] ≤ γk , where γk , eκ−(ρ2 − τ )k , k ∈ N.
(1)
(2)
Now, let γk , γk + γk , k ∈ N. Using (19), we
P
(1)
< ∞,
obtain (5). Moreover, (6) holds since
k∈N γk
P
(2)
γ
<
∞.
k∈N k

P[ sup kx(t)k > ǫ] < p̄.

of the Lyapunov-like function V (·) defined by V (x) ,
xT P x, x ∈ Rn . Then, by utilizing this inequality, we will
establish almost sure stability, and then finally we show
almost sure asymptotic stability of the closed-loop system.
First, we use (1) and (3) together with V (·) to obtain

(32)

for k ∈ N. Furthermore, since ln ((1 − q)β + qϕ) = (1 −
q) ln β + q ln ϕ for q ∈ {0, 1}, we have
ln η(k) =
=

k−1
X

i=0
k−1
X
i=0

ln ((1 − l(i))β + l(i)ϕ)

(1 − l(i)) ln β +

k−1
X

l(i) ln ϕ

i=0

= (k − L(k)) ln β + L(k) ln ϕ,
Pk−1
where L(k) = i=0 l(i) by (4). Now since β ∈ (0, 1), and
ϕ ∈ [1, ∞), it follows from Lemma 2.2 that
lim sup
k→∞

1
ln η(k)
= lim sup ((k − L(k)) ln β + L(k) ln ϕ)
k
k→∞ k
≤ (1 − ρ) ln β + ρ ln ϕ,

almost surely. Therefore, it follows from (25) that
P[lim sup
k→∞

ln η(k)
< 0] = 1.
k

6

As a consequence, limk→∞ ln η(k) = −∞, and hence,
limk→∞ η(k) = 0, almost surely. Thus, for all ǫ > 0,
lim P[sup η(k) > ǫ2 ] = 0,

j→∞

It follows from (35) and (36) that for all ǫ > 0, p̄ > 0,
P[ sup kx(t)k > ǫ] = P[ sup max kx(t)k > ǫ]
= P[{

and therefore, for all ǫ > 0 and p̄ > 0, there exists a positive
integer N (ǫ, p̄) such that
P[sup η(j) > ǫ2 ] < p̄,
k≥j

j ≥ N (ǫ, p̄).

(33)

In what follows, we will employ (32) and (33) to show
almost sure stability of the closed-loop system. Note that
(28), (30), and ϕ ≥ 1 > β imply that
V (x(t + 1)) ≤ ϕV (x(t)), t ∈ {τi , . . . , τi+1 − 1},
2

1
λmin (P ) V

for i ∈ N0 . Since, kxk ≤
λmax (P )kxk2 , x ∈ Rn , we have

(x) and V (x) ≤

kx(t)k2 ≤ ϕνkx(τi )k2 , t ∈ {τi , . . . , τi+1 − 1},

(34)

(P )
for i ∈ N0 , where ν , λλmax
.
min (P )
Now, let Tk , {τk , . . . , τk+1 − 1}, k ∈ N0 . Then
k ))
by using (32) and (34), we obtain η(k) ≥ VV(x(τ
(x(0)) ≥
2
λmin (P ) kx(τk )k2
1 kx(t)k
λmax (P ) kx(0)k2 ≥ ν 2 ϕ kx(0)k2 , for all t ∈ Tk ,
maxt∈Tk kx(t)k2
, k ∈ N. By (33),
η(k) ≥ ν 21ϕ
kx(0)k2

k ∈ N. Hence,
it follows that

for all ǫ > 0 and p̄ > 0,

√
P[sup max kx(t)k > ǫν ϕkx(0)k]
k≥j t∈Tk

= P[sup max kx(t)k2 > ǫ2 ν 2 ϕkx(0)k2 ]
k≥j t∈Tk

1 maxt∈Tk kx(t)k2
> ǫ2 ]
ν2ϕ
kx(0)k2

= P[sup
k≥j

≤ P[sup η(k) > ǫ2 ]
k≥j

< p̄,

j ≥ N (ǫ, p̄).

We now define δ1 , ν √1 ϕ . Note that if kx(0)k ≤ δ1 , then
√
(since ν ϕkx(0)k ≤ 1) we have
P[sup max kx(t)k > ǫ]
k≥j t∈Tk

√
≤ P[sup max kx(t)k > ǫν ϕkx(0)k]
k≥j t∈Tk

< p̄,

j ≥ N (ǫ, p̄).

(35)

On the other hand, since ϕ ≥ 1 > β, it follows from
(31) that V (x(τk )) ≤ ϕk V (x(0)) ≤ ϕN (ǫ,p̄)−1 V (x(0)) for
all k ∈ {0, 1, . . . , N (ǫ, p̄) − 1}. Therefore, kx(τk )k2 ≤
(P )
ϕN (ǫ,p̄)−1 λλmax
kx(0)k2 = ϕN (ǫ,p̄)−1 νkx(0)k2 . Furthermin (P )
more, as a result of (34),
max kx(t)k2 ≤ ϕνkx(τk )k2 ≤ ν 2 ϕN (ǫ,p̄) kx(0)k2 ,
t∈Tk

p
and hence, maxt∈Tk kx(t)k ≤ ν ϕN (ǫ,p̄) kx(0)k
p for all
k ∈ {0, 1, . . . , N (ǫ, p̄) − 1}. Let δ2 , ǫν −1 ϕ−N (ǫ,p̄) .
Now, if kx(0)k ≤ δ2 , then maxt∈Tk kx(t)k ≤ ǫ, k ∈
{0, 1, . . . , N (ǫ, p̄) − 1}, which implies
P[

max

max kx(t)k > ǫ] = 0.

k∈{0,1,...,N (ǫ,p̄)} t∈Tk

k∈N0 t∈Tk

t∈N0

k≥j

(36)

max

max kx(t)k > ǫ}

k∈{0,1,...,N (ǫ,p̄)−1} t∈Tk

∪ { sup

max kx(t)k > ǫ}]

k≥N (ǫ,p̄) t∈Tk

≤ P[

max

max kx(t)k > ǫ]

k∈{0,1,...,N (ǫ,p̄)−1} t∈Tk

+ P[ sup

max kx(t)k > ǫ]

k≥N (ǫ,p̄) t∈Tk

< p̄,
whenever kx(0)k < δ , min(δ1 , δ2 ), which implies almost
sure stability.
Now in order to establish almost sure asymptotic stability
of the zero solution, it remains to show (22). To this end,
note that P[limk→∞ η(τk ) = 0] = 1. It follows from (32) that
P[limk→∞ V (x(τk )) = 0] = 1, which implies (22). Hence
the zero solution of the closed-loop system (1), (2), (3) is
asymptotically stable almost surely.
Theorem 3.2 provides a sufficient condition under which
the event-triggered control law (2), (3) guarantees almost
sure asymptotic stability of the linear dynamical system (1)
for the case packet losses satisfy Assumption 2.1. Note that
the scalars β ∈ (0, 1) and ϕ ∈ [1, ∞) in conditions (23) and
(24) characterize upper bounds on the growth of a Lyapunovlike function. Specifically, when a packet exchange attempt
between the plant and the controller is successful at time
τi , the condition (23) together with (2) guarantees that
V (x(τi+1 )) ≤ βV (x(τi )). On the other hand, if a packet
exchange attempt between the plant and the controller is
unsuccessful at time τi , it follows from (24) and (2) that
V (x(τi+1 )) ≤ ϕV (x(τi )). If unsuccessful packet exchange
attempts are sufficiently statistically rare (successful packet
exchanges happen statistically frequently) such that condition
(25) is satisfied, then the closed-loop system stability is
guaranteed.
Note that the analysis for the closed-loop system stability is technically involved partly due to the general characterization in Assumption 2.1, which captures not only
random packet losses but jamming attacks as well. If we
consider only the case of random packet losses, we may
employ methods from discrete-time Markov jump systems
theory [18] for obtaining conditions of stability. On the
other hand packet losses due to malicious jamming attacks
(Section II-B.2) cannot be described using Markov processes.
Stability of a system under jamming attacks is explored in
[10], where the analysis relies on a deterministic approach
for obtaining an exponentially decreasing upper bound for
the norm of the state. In contrast, in our analysis, after
establishing that both random losses and jamming attacks
allow a probabilistic characterization, we use tools from
probability theory. Specifically, we find a stochastic upper
bound for a Lyapunov-like function and show that this
stochastic upper bound tends to zero even though it may
increase at certain times.

7

Fig. 2. Region for β ∈ (0, 1) and ϕ ∈ [1, ∞) that satisfy (25) for ρ = 0.4

A. Feedback Gain Design for Event-Triggered Control
In the following, we outline a numerical method for
designing the feedback gain K ∈ Rm×n , as well as the
positive-definite matrix P ∈ Rn×n and the scalar β ∈ (0, 1)
used in the event-triggered control law (2), (3).
Corollary 3.3: Consider the linear dynamical system (1).
Suppose that the process {l(i) ∈ {0, 1}}i∈N0 characterizing
packet exchange failures in the network satisfies Assumption 2.1 with scalar ρ ∈ [0, 1]. If there exist a matrix
M ∈ Rm×n , a positive-definite matrix Q ∈ Rn×n , and
scalars β ∈ (0, 1), ϕ ∈ [1, ∞) such that (25),


T
βQ
(AQ + BM )
≥ 0,
(37)
AQ + BM
Q


ϕQ (AQ)T
≥ 0,
(38)
AQ
Q
hold, then the event-triggered control law (2), (3) with P ,
Q−1 and K , M Q−1 guarantees almost sure asymptotic
stability of the zero solution x(t) ≡ 0 of the closed-loop
system dynamics.
Proof: Using Schur complements (see [19]), we transform (37) and (38), respectively, into
T

βQ − (AQ + BM ) Q−1 (AQ + BM ) ≥ 0,
T

ϕQ − (AQ) Q

−1

AQ ≥ 0.

(39)
(40)

Now by multiplying both sides of inequalities (39) and (40)
from left and right by Q−1 , we obtain (23) and (24) with
P = Q−1 and K = M Q−1 . Thus, the result follows from
Theorem 3.2.
Note that inequalities (37) and (38) are linear in M ∈
Rm×n and Q ∈ Rn×n for fixed β ∈ (0, 1) and ϕ ∈ [1, ∞).
In our method we seek feasible solutions M and Q for
linear matrix inequalities (37) and (38) by iterating over a
set of values for β ∈ (0, 1) and ϕ ∈ [1, ∞) that satisfy
(25). We do not need to search β and ϕ in the entire space
characterized by (25). We restrict the search space and only
check feasibility of (37) and (38) for larger values of β and ϕ
that are close to the boundary of the search space identified
by (1 − ρ) ln β + ρ ln ϕ = 0. Specifically, we set ∆ > 0
as a small positive real number, and then we iterate over
∆
a set of values for β in the range (0, e− 1−p ] to look for
feasible solutions M and Q for linear matrix inequalities
(1−ρ) ln β+∆
ρ
(37) and (38) with ϕ = e−
. In this approach,
feasibility of (37) and (38) is checked only for β ∈ (0, 1),
ϕ ∈ [1, ∞) that are on the curve (1 − ρ) ln β + ρ ln ϕ = −∆.
We illustrate the curve (1 − ρ) ln β + ρ ln ϕ = −∆ with solid

red line in Fig. 2, where the dark shaded region corresponds
to β ∈ (0, 1) and ϕ ∈ [1, ∞) that satisfy (25). Note that
picking smaller values for ∆ > 0 moves the curve towards
the boundary identified by (1 − ρ) ln β + ρ ln ϕ = 0. Also,
there is no conservatism in not considering β ∈ (0, 1),
ϕ ∈ [1, ∞) such that (1 − ρ) ln β + ρ ln ϕ < −∆. This
is due to the fact that if there exist M and Q that satisfy
(37) and (38) for values β = β̃ and ϕ = ϕ̃, then the same
M and Q satisfy (37) and (38) also for larger values β > β̃
and ϕ > ϕ̃; moreover, for all β̃ ∈ (0, 1), ϕ̃ ∈ [1, ∞) such
that (1−ρ) ln β̃ +ρ ln ϕ̃ < −∆, there exist β ≥ β̃ and ϕ ≥ ϕ̃
such that (1 − ρ) ln β + ρ ln ϕ = −∆.
IV. N UMERICAL E XAMPLE
In this section we present a numerical example to illustrate
our results. Specifically, we consider (1) with




1
0.1
0.1
A,
, B,
.
−0.5 1.1
1.2
We use the event-triggering control law (2), (3) for stabilization of (1) over a network. We consider the case where
the random packet losses in the network are characterized
by the discrete-time Markov chain {lR (i) ∈ {0, 1}}i∈N0
with initial distribution ϑ0 = 0, ϑ1 = 1, and transition
probabilities p0,1 (i) , 0.2 + 0.03 sin2 (0.1i), p1,1 (i) ,
0.2 + 0.03 cos2 (0.1i), and pq,0 (i) = 1 − pq,1 (i), q ∈ {0, 1},
i ∈ N0 . Note that {lR (i) ∈ {0, 1}}i∈N0 satisfies (9) and (10)
with p1 = 0.23 and p0 = 0.8. Furthermore, the network
is assumed to be subject to jamming attacks characterized
with {lJ (i) ∈ {0, 1}}i∈N0 that is independent of {lR (i) ∈
{0, 1}}i∈N0 and satisfies (7) with κ = 2 and τ = 5.
Note that p1 + pτ0 < 0.4. It follows from Proposition 2.3
that for ρ = 0.4, there exist γk ∈ [0, ∞), k ∈ N, such that
(5) and (6) of Assumption 2.1 hold. Furthermore, matrices




0.618 −2.119
Q=
, M = 0.202 −20.405 ,
−2.119 28.214

and scalars β = 0.55, ϕ = 2.4516 satisfy (25), (37), (38).
Hence, it follows from Corollary 3.3 that the event-triggered
control law (2), (3) with P = Q−1 and K = M Q−1 ,
guarantees almost sure asymptotic stabilization.
Fig. 3 shows 250 sample trajectories of the state norm
T
kx(t)k obtained with the same initial condition x0 = [1, 1]
and the event-triggering mechanism parameter θ = 1000,
but with different sample paths for {lR (i) ∈ {0, 1}}i∈N0
and {lJ (i) ∈ {0, 1}}i∈N0 . Furthermore, in Fig. 4 we show
a single sample trajectory of the Lyapunov-like function
V (x(t)), and in Fig. 5 we show the corresponding sample trajectories for l(·), lR (·), and lJ (·), indicating packet exchange
attempt failures due to random packet losses and jamming
attacks. Note that when packet exchange attempts fail due to
a random loss or a jamming attack, the control input is set to
0. As a result, due to unstable dynamics of the uncontrolled
system, the Lyapunov-like function V (·) may grow and take
a larger value at the next packet exchange attempt instant.
On the other hand, when a packet exchange attempt between
the plant and the controller is successful, the control input
at the plant side is updated. In this case V (·) is guaranteed

lR (i)

8
6
4
2
0
0

5

10

15

20

25

30

35

0

2

4

6

8

10

12

14

0

2

4

6

8

10

12

14

0

2

4

6

8

10

12

14

1
0

Time [t]

Sample paths of the state norm
l(i)

Fig. 3.

1
0

lJ (i)

kx(t)k

8

1

V (x(t))

0
3.0
2.5
2.0
1.5
1.0
0.5
0.0

Successful packet exchange attempts
Failed packet exchange attempts

Fig. 5.
0

5

10

15

Sample paths of lR (·), lJ (·), and l(·)

20

Time [t]

Fig. 4.

Packet exchange attempt index [i]

A sample path of Lyapunov-like function V (·)

to take a smaller value at the next packet exchange attempt
instant, although it may not be monotonically decreasing. As
implied by Corollary 3.3, the Lyapunov-like function V (·)
eventually converges to zero (see Fig. 4).
V. C ONCLUSION
In this paper, we explored event-triggered networked control of linear dynamical systems. We described a probabilistic
characterization of the evolution of the total number of packet
exchange failures in a network that faces random packet
losses and jamming attacks. Based on this characterization,
we obtained sufficient conditions for almost sure asymptotic
stabilization of the zero solution and presented a method for
finding a stabilizing feedback gain and parameters for our
proposed event-triggered control framework. In the framework that we describe in the paper, the controller does not
need the information whether the control input packets are
successfully transmitted or lost. This type of acknowledgment messages would be useful to detect anomalies such as
jamming attacks in the network. Future extensions include
incorporating acknowledgement messages in the framework.

[9] H. Shisheh-Foroush and S. Martínez, “On single-input controllable
linear systems under periodic DoS jamming attacks,” in Proc. SIAM
Conf. Contr. Appl., 2013.
[10] C. De Persis and P. Tesi, “Resilient control under Denial-of-Service,”
in Proc. 19th IFAC World Congress, pp. 134–139, 2014.
[11] S. Liu, P. X. Liu, and A. El Saddik, “A stochastic game approach to the
security issue of networked control systems under jamming attacks,”
J. Franklin Inst., vol. 351, no. 9, pp. 4570–4583, 2014.
[12] M. Velasco, P. Martí, and E. Bini, “On Lyapunov sampling for eventdriven controllers,” in Proc. Conf. Dec. Contr., (Shanghai, P. R. China),
pp. 6238–6243, 2009.
[13] W. P. M. H. Heemels, M. C. F. Donkers, and A. R. Teel, “Periodic
event-triggered control for linear systems,” IEEE Trans. Autom. Control, vol. 58, no. 4, pp. 847–861, 2013.
[14] W. P. M. H. Heemels, K. H. Johansson, and P. Tabuada, “An introduction to event-triggered and self-triggered control,” in Proc. IEEE
Conf. Dec. Contr., (Maui, HI), pp. 3270–3285, 2012.
[15] E. Altman, K. Avrachenkov, and C. Barakat, “A stochastic model of
TCP/IP with stationary random losses,” IEEE/ACM Trans. Networking,
vol. 13, no. 2, 2005.
[16] A. Klenke, Probability Theory: A Comprehensive Course. SpringerVerlag: London, 2008.
[17] L. Anantharamu, B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki,
“Medium access control for adversarial channels with jamming,” in
Proc. 18th Int. Col. SIROCCO, (Gdansk, Poland), pp. 89–100, 2011.
[18] O. L. V. Costa, M. D. Fragoso, and R. P. Marques, Discrete-Time
Markov Jump Linear Systems. Springer, 2004.
[19] D. Bernstein, Matrix Mathematics: Theory, Facts, and Formulas.
Princeton University Press: Princeton, 2009.
[20] P. Billingsley, Probability and Measure. John Wiley and Sons:New
Jersey, 2012.

A PPENDIX
R EFERENCES
[1] J. P. Hespanha, P. Naghshtabrizi, and Y. Xu, “A survey of recent results
in networked control systems,” Proc. IEEE, vol. 95, no. 1, pp. 138–
172, 2007.
[2] H. Ishii, “Limitations in remote stabilization over unreliable channels
without acknowledgements,” Automatica, vol. 45, no. 10, pp. 2278–
2285, 2009.
[3] M. Lemmon and X. S. Hu, “Almost sure stability of networked control
systems under exponentially bounded bursts of dropouts,” in Proc. 14th
HSCC, pp. 301–310, 2011.
[4] V. Gupta, N. C. Martins, and J. S. Baras, “Optimal output feedback
control using two remote sensors over erasure channels,” IEEE Trans.
Autom. Control, vol. 54, no. 7, pp. 1463–1476, 2009.
[5] K. Okano and H. Ishii, “Stabilization of uncertain systems with finite
data rates and Markovian packet losses,” IEEE Trans. Control Netw.
Syst., vol. 1, pp. 298–307, 2014.
[6] H. Fawzi, P. Tabuada, and S. Diggavi, “Secure estimation and control
for cyber-physical systems under adversarial attacks,” IEEE Trans.
Autom. Control, vol. 59, no. 6, pp. 1454–1467, 2014.
[7] H. Sandberg, S. Amin, and K. H. Johansson, “Special issue on
cyberphysical security in networked control systems,” IEEE Control
Syst. Mag., vol. 35, no. 1, 2015.
[8] S. Amin, A. A. Cardenas, and S. S. Sastry, “Safe and secure networked
control systems under Denial-of-Service attacks,” in Proc. 12th HSCC,
pp. 31–45, 2009.

Lemma A.1 below provides upper bounds on the tail
probabilities of sums involving a binary-valued timeinhomogeneous Markov chain.
Lemma A.1: Let {ξ(i) ∈ {0, 1}}i∈N0 be a timeinhomogeneous Markov chain with transition probabilities
pq,r : N0 → [0, 1], q, r ∈ {0, 1}. Furthermore, let {χ(i) ∈
{0, 1}}i∈N0 be a binary-valued process that is independent
of {ξ(i) ∈ {0, 1}}i∈N0 . Assume

P[

k−1
X
i=0

pq,1 (i) ≤ p̃, q ∈ {0, 1}, i ∈ N0 ,
χ(i) ≤ c̃ + w̃k] = 1, k ∈ N,

(41)
(42)

where p̃ ∈ (0, 1), w̃ ∈ (0, 1], and c̃ ∈ [0, ∞). It then follows
that for all ρ ∈ (p̃w̃, w̃),
P[

k−1
X
i=0

ξ(i)χ(i) > ρk] ≤ ψk ,

k ∈ N,

(43)

9
c̃+w̃k

p̃+1)
where ψk , φ−ρk+1 ((φ−1)(φ−1)
p̃
P∞
Moreover, k=1 ψk < ∞.

−1

with φ ,

ρ
w̃ (1−p̃)
ρ .
p̃(1− w̃
)

In the proof of Lemma A.1, by following the approach
used for obtaining Chernoff-type tail distribution inequalities
for sums of Bernoulli random variables (see [20]), we use
Markov’s inequality. Some additional key steps (including
Lemma A.2 below) are also required due to the fact that in
Lemma A.1 we consider sums of (not necessarily independent) random variables composed of the product of states
of a time-inhomogeneous Markov chain and a binary-valued
process that satisfy (42).
Lemma A.2: Let {ξ(i) ∈ {0, 1}}i∈N0 be an Fi -adapted
binary-valued Markov chain with transition probability functions pq,r : N0 → [0, 1], q, r ∈ {0, 1}. Then for all φ > 1,
s ∈ N, and p̃ ∈ [0, 1] such that
pq,1 (i) ≤ p̃, q ∈ {0, 1}, i ∈ N0 ,

We now show that (45) holds for s = s̃ + 1. Using similar
arguments that we used for obtaining (47)–(49), we obtain
Ps̃+1

E[φ

j=1

E[φ

j=1 ξ(ij )

s−1

] ≤ φ ((φ − 1)p̃ + 1)

Ps

j=1

ξ(ij )

E[φ

j=1

ξ(ij )

,

] = E[φξ(i1 ) ] ≤ φ.

= E[E[φ

φ

| Fi2 −1 ]]

= E[φξ(i1 ) E[φξ(i2 ) | Fi2 −1 ]].
Ps

(45)

= E[φξ(i1 ) ]((φ − 1)p̃ + 1)
≤ φ((φ − 1)p̃ + 1).

ξ(ij )

= E[φ
≤ E[φ

j=1

ξ(ij )

ξ(is̃+1 )

E[φ

ξ(is̃+1 )

E[φ

] ≤ φ ((φ − 1)p̃ + 1)s̃−1 .

| Fis̃+1 −1 ]]
| Fis̃+1 −1 ]]

| ξ(is̃+1 − 1)]]

]((φ − 1)p̃ + 1).

(51)

j=1

ξ(ij )

] ≤ φ ((φ − 1)p̃ + 1)s̃ ,

which completes the proof.
Proof of Lemma A.1: First, let
ξ(k) , [ξ(0), ξ(1), . . . , ξ(k − 1)]T ,

k ∈ N.

Now let
Fs,k , {χ ∈ {0, 1}k : χT χ = s}, s ∈ {0, 1, . . . , k}, k ∈ N.
It is important to note that Fs1 ,k ∩ Fs2 ,k = ∅, s1 6= s2 ;
moreover, due to (42)
⌊c̃+w̃k⌋

P[χ(k) ∈ ∪s=0

k ∈ N.

Fs,k ] = 1,

It then follows that for all ρ ∈ (p̃w̃, 1) and k ∈ N,
k−1
X

T

ξ(i)χ(i) > ρk] = P[ξ (k)χ(k) > ρk]

i=0

(47)

=

⌊c̃+w̃k⌋

X
s=0

X

χ∈Fs,k

T

P[ξ (k)χ(k) > ρk | χ(k) = χ]

· P[χ(k) = χ].

(52)

Due to the mutual independence of ξ(·) and χ(·),
T

T

P[ξ (k)χ(k) > ρk | χ(k) = χ] = P[ξ (k)χ > ρk]. (53)
As a result, it follows from (52) and (53) that for k ∈ N,
P[

k−1
X

ξ(i)χ(i) > ρk]

i=0
⌊c̃+w̃k⌋

=

X
s=0

X

T

P[ξ (k)χ > ρk]P[χ(k) = χ].

χ∈Fs,k
T

(49)

Hence, by (46) and (49), (45) is satisfied for s ∈ {1, 2}.
Now, suppose that (45) holds for s = s̃ > 2, that is,
j=1

φ

j=1 ξ(ij )

Ps̃+1

P[

Then by using (44) and (46), we arrive at

i
h
Ps
E[φ j=1 ξ(ij ) ] ≤ E φξ(i1 ) (φ − 1)p̃ + 1

Ps̃

ξ(ij ) ξ(is̃+1 )

= E[φ

E[φ

ξ(ij )

E[φ

]

Using (50) and (51), we arrive at

(46)

] = E[φξ(i1 ) E[φξ(i2 ) | ξ(i2 − 1)]]

h
= E φξ(i1 ) φP[ξ(i2 ) = 1 | ξ(i2 − 1)]
i
+ P[ξ(i2 ) = 0 | ξ(i2 − 1)]

h
= E φξ(i1 ) φP[ξ(i2 ) = 1 | ξ(i2 − 1)]
i
+ 1 − P[ξ(i2 ) = 1 | ξ(i2 − 1)]
h

i
= E φξ(i1 ) (φ − 1)P[ξ(i2 ) = 1 | ξ(i2 − 1)] + 1 . (48)
j=1

j=1

j=1 ξ(ij )

Ps̃

Noting that {ξ(i) ∈ {0, 1}}i∈N0 is a Markov chain, we obtain
E[φξ(i2 ) | Fi2 −1 ] = E[φξ(i2 ) | ξ(i2 − 1)]. Consequently,
E[φ

φ

Ps̃

] = E[φξ(i1 ) φξ(i2 ) ]
ξ(i1 ) ξ(i2 )

ξ(ij ) ξ(is̃+1 )

Ps̃

χ(k) , [χ(0), χ(1), . . . , χ(k − 1)]T ,

For the case s = 2, the random variable ξ(i1 ) is Fi2 −1 measurable (since i1 ≤ i2 − 1), and thus we have
Ps

j=1

Ps̃

(44)

where i1 , i2 , . . . , is ∈ N0 denote indices such that 0 ≤ i1 <
i2 < . . . < is .
Proof: The proof is based on induction. First, note that
for the case s = 1,
E[φ

Ps̃

] = E[φ

= E[E[φ

we have
Ps

ξ(ij )

(50)

Next, note that P[ξ (k)χ > ρk] = 0 for χ ∈ F0,k . Hence,
for all k ∈ N such that ⌊c̃ + w̃k⌋ = 0, we have
⌊w̃k⌋

X X

T

P[ξ (k)χ > ρk]P[χ(k) = χ]

s=0 χ∈Fs,k

= 0.

(54)

10

Furthermore, for all k ∈ N such that ⌊c̃ + w̃k⌋ ≥ 1, we have
⌊c̃+w̃k⌋

X
s=0

⌊c̃+w̃k⌋

T

X

P[ξ (k)χ > ρk]P[χ(k) = χ]

X

χ∈Fs,k

⌊c̃+w̃k⌋

X

=

Hence, (58) and (59) imply

s=1

s=0

T

X

P[ξ (k)χ > ρk]P[χ(k) = χ].

(55)

T

P[ξ (k)χ > ρk] = P[
= P[

s
X

j=1
s
X
j=1

ξ ij (χ̄) (k) > ρk]

T

P[ξ (k)χ > ρk] ≤ P[

s
X

ξ(ij (χ) − 1) ≥ ρk]

j=1
Ps

= P[φ

j=1 ξ(ij (χ)−1)

Ps

≤ φ−ρk E[φ

j=1

ρk

≥φ ]

ξ(ij (χ)−1)

].

X

(56)

for χ ∈ Fs,k , s ∈ {1, 2, . . . , ⌊c̃ + w̃k⌋}, and k ∈ N such that
⌊w̃k⌋ ≥ 1.
Now note that φ > 1, since ρ ∈ (p̃w̃, w̃). We use Markov’s
inequality to obtain

s=0

X
s=0

≤

X

∞
X

ψk =

X
s=1

X

χ∈Fs,k

−ρk+1

=φ

s−1

φ−ρk φ ((φ − 1)p̃ + 1)

⌊c̃+w̃k⌋

≤ φ−ρk+1

s−1

X

((φ − 1)p̃ + 1)

X

((φ − 1)p̃ + 1)

X

((φ − 1)p̃ + 1)

s=1

= φ−ρk+1

∞
X

⌊c̃+w̃k⌋
s=1
⌊c̃+w̃k⌋
s=1

s−1

s−1

P[χk = χ]

X

=

X
s=1

=
≤

(60)

T

c̃+w̃k

((φ − 1)p̃ + 1)
(φ − 1)p̃

−1

,

k ∈ N.

(61)

c̃+w̃k

φ−ρk+1

((φ − 1)p̃ + 1)
(φ − 1)p̃

−1

∞
φ ((φ − 1)p̃ + 1)c̃ X −ρk
φ
((φ − 1)p̃ + 1)w̃k
(φ − 1)p̃
k=1

−

φ
(φ − 1)p̃

∞
X

φ−ρk .

(62)

k=1

We will show that the series on the far right hand side of (62)
are both convergent. First of all, since
1, we have φ−ρ <
P∞ φ >−ρk
1, and thus, the geometric series k=1 φ
converges, that
is,
∞
X

P[χk = χ]

k=1

χ∈Fs,k

φ−ρk < ∞.

(63)

w̃

Next, we show φ−ρ ((φ − 1)p̃ + 1) < 1. We obtain

P[χk ∈ Fs,k ]
,

(58)

where we also used the fact that P[χk ∈ Fs,k ] ≤ 1 to obtain
the last inequality. Here, we have
⌊c̃+w̃k⌋

,

P[ξ (k)χ > ρk]P[χ(k) = χ]

k=1

T

P[ξ (k)χ > ρk]P[χ(k) = χ]

−1

Hence (58) and (59) imply (43).
P∞
Our next goal is to show that k=1 ψk < ∞. To this end,
first note that

Ps

χ∈Fs,k

⌊c̃+w̃k⌋

X

≤ φ−ρk+1

Now it follows from Lemma A.2 that E[φ j=1 ξ(ij (χ)−1) ] ≤
s−1
φ ((φ − 1)p̃ + 1) . Using this inequality together with (55)
and (57), for all k ∈ N such that ⌊c̃ + w̃k⌋ ≥ 1, we obtain
⌊c̃+w̃k⌋

c̃+w̃k

((φ − 1)p̃ + 1)
(φ − 1)p̃

χ∈Fs,k

k=1

(57)

χ∈Fs,k

for all k ∈ N such that ⌊c̃ + w̃k⌋ ≥ 1. Note that since
P⌊c̃+w̃k⌋ P
T
s=0
χ∈Fs,k P[ξ (k)χ > ρk]P[χ(k) = χ] = 0 for all
k ∈ N such that ⌊c̃ + w̃k⌋ = 0, (60) holds for all k ∈ N, that
is,
⌊c̃+w̃k⌋

ξ(ij (χ) − 1) > ρk],

P[ξ (k)χ > ρk]P[χ(k) = χ]

≤ φ−ρk+1

χ∈Fs,k

Now, for s ∈ {1, 2, . . . , ⌊c̃+ w̃k⌋}, let i1 (χ), i2 (χ), . . . , is (χ)
denote the indices of the nonzero entries of χ ∈ Fs,k such
that i1 (χ) < i2 (χ) < · · · < is (χ). Consequently,

T

X

s−1

((φ − 1)p̃ + 1)

((φ − 1)p̃ + 1)⌊c̃+w̃k⌋ − 1
((φ − 1)p̃ + 1) − 1

((φ − 1)p̃ + 1)c̃+w̃k − 1
.
(φ − 1)p̃

(59)

w̃
 ρ
w̃
φ−ρ ((φ − 1)p̃ + 1) = φ− w̃ ((φ − 1)p̃ + 1) .

(64)

Furthermore,
ρ

φ− w̃ ((φ − 1)p̃ + 1)
ρ
− w̃ρ  ρ


w̃ (1 − p̃)
w̃ (1 − p̃)
=
−
1
p̃
+
1
p̃(1 − w̃ρ )
p̃(1 − w̃ρ )
− w̃ρ 

  w̃ρ 
1 − p̃
1 − p̃
p̃w̃
=
ρ
1 − w̃ρ
1 − w̃ρ
  w̃ρ 
1− w̃ρ
1 − p̃
p̃w̃
=
.
(65)
ρ
1 − w̃ρ

11

1−p̃
Note that p̃ρw̃ , 1−
ρ ∈ (0, 1) ∪ (1, ∞). Since ln v < v − 1 for
w̃
any v ∈ (0, 1) ∪ (1, ∞), we have
 ρ

ln φ− w̃ ((φ − 1)p̃ + 1)

 

ρ
ρ
p̃w̃
1 − p̃
+ (1 − ) ln
= ln
w̃
ρ
w̃
1 − w̃ρ




ρ
1 − p̃
ρ p̃w̃
− 1 + (1 − )
<
−
1
w̃
ρ
w̃
1 − w̃ρ
p
ρ
= p̃ − + − p̃
w̃ w̃
= 0,
ρ

which implies that φ− w̃ ((φ − 1)p̃ + 1) < 1, and hence by
(64), φ−ρ ((φ − 1)p̃ + 1)w̃ < 1. Therefore,
∞
X

k=1

φ−ρk ((φ − 1)p̃ + 1)w̃k < ∞.

Finally, (62), (63), and (66) imply

P∞

k=1

ψk < ∞.

(66)


