1
Exact minimum number of bits
to stabilize a linear system
Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke
Abstract
—We consider an unstable scalar linear stochastic
system,
X
n
+1
=
aX
n
+
Z
n
−
U
n
, where
a
≥
1
is the system
gain,
Z
n
’s are independent random variables with bounded
α
-
th moments, and
U
n
’s are the control actions that are chosen
by a controller who receives a single element of a finite set
{
1
,...,M
}
as its only information about system state
X
i
. We
show new proofs that
M > a
is necessary and sufficient for
β
-moment stability, for any
β < α
. Our achievable scheme
is a uniform quantizer of the zoom-in / zoom-out type that
codes over multiple time instants for data rate efficiency; the
controller uses its memory of the past to correctly interpret the
received bits. We analyze its performance using probabilistic
arguments. We show a simple proof of a matching converse
using information-theoretic techniques. Our results generalize
to vector systems, to systems with dependent Gaussian noise,
and to the scenario in which a small fraction of transmitted
messages is lost.
Index Terms
—Linear stochastic control, source coding, data
rate theorem.
I. I
NTRODUCTION
We study the tradeoff between stabilizability of a linear
stochastic system and the coarseness of the quantizer used to
represent the state. The evolution of the system is described
by
X
n
+1
=
aX
n
+
Z
n
−
U
n
,
(1)
where constant
a
≥
1
;
X
1
and
Z
1
,Z
2
,...
are independent
random variables with bounded
α
-th moments, and
U
n
is
the control action chosen based on the history of quantized
observations. More precisely, an
M
-bin causal quantizer-
controller
for
X
1
,X
2
,...
is a sequence
{
f
n
,
g
n
}
∞
n
=1
, where
f
n
:
R
n
7→
[
M
]
is the encoding (quantizing) function, and
g
n
: [
M
]
7→
R
n
is the decoding (controlling) function, and
[
M
]
,
{
1
,
2
,...,M
}
. At time
i
, the controller outputs
U
n
=
g
n
(
f
1
(
X
1
)
,
f
2
(
X
2
)
,...,
f
n
(
X
n
))
.
(2)
V. Kostina (vkostina@caltech.edu) is with California Institute of Tech-
nology, Pasadena, CA. Y. Peres (yuval@yuvalperes.com) is an independent
researcher. G. Ranade (ranade@eecs.berkeley.edu) is with the University of
California, Berkeley, CA. M. Sellke (msellke@stanford.edu) is with Stanford
University, CA. This work was supported in part by the National Science
Foundation (NSF) under Grant CCF-1751356, and by the Simons Institute
for the Theory of Computing. Research of Y. Peres was partially supported
by NSF grant DMS-1900008. G. Ranade acknowledges the Siebel Energy
Institute Seed Funding.
The fundamental operational limit of quantized control of
interest in this paper is the minimum number of quantization
bins to achieve
β
-moment stability:
M
?
β
,
min
{
M
:
∃
M
-bin causal quantizer-controller
s.t.
lim sup
n
E
[
|
X
n
|
β
]
<
∞
}
,
(3)
where
0
< β < α
is fixed.
The main results of the paper are new proofs of the
following achievability and converse theorems, whose various
special cases have been previously shown in literature.
Theorem 1
(achievability)
.
Let
X
1
, Z
n
in
(1)
be independent
random variables with bounded
α
-moments. Then for any
0
< β < α
M
?
β
≤b
a
c
+ 1
.
(4)
Theorem 2
(converse)
.
Let
X
1
,
Z
n
in
(1)
be independent
random variables. Let
h
(
X
1
)
>
−∞
, where
h
(
X
)
,
−
∫
R
f
X
(
x
) log
f
X
(
x
)
dx
is the differential entropy. Then, for
all
β >
0
,
M
?
β
≥b
a
c
+ 1
.
(5)
The first achievability results [1], [2] focused on unstable
scalar systems with bounded disturbances, i.e.
|
Z
n
| ≤
B
a.s., and showed that a simple uniform quantizer with the
number of quantization bins in
(4)
stabilizes such systems.
That corresponds to the special case
α
=
β
=
∞
. Nair and
Evans [3] showed that time-invariant fixed-rate quantizers are
unable to attain bounded cost if the noise is unbounded [3],
regardless of their rate. The reason is that since the noise is
unbounded, over time, a large magnitude noise realization
will inevitably be encountered, and the dynamic range of the
quantizer will be exceeded by a large margin, not permitting
recovery. This necessitates the use of adaptive quantizers of
zooming type [4]–[6]. Such quantizers “zoom out” (i.e. expand
their quantization intervals) when the system is far from the
target and “zoom in” when the system is close to the target.
Nair and Evans [3] constructed such an adaptive fixed-length
quantizer with nonuniform quantization levels and showed
second-moment stability via a recursive bound on its mean-
squared error, under the assumption that the system noise
has bounded
2 +
moment, for some
>
0
. Under the same
assumption, Y
̈
uksel [7] (see [8], [9] for generalizations to
vector systems and to
β
= 1
,
2
,...
) showed second-moment
stabilizability using a uniform scalar quantizer that enters its
arXiv:1807.07686v3 [cs.SY] 23 Nov 2021
2
zoom-out mode whenever its input falls outside its dynamic
range. When applied to encode each
k
-th system state over
the following
k
time instances, the schemes in [3], [7] attain
(4)
for a large enough
k
. See also [10], which explores the
use of constrained quantizers to encode the overflow event
over multiple time instances.
The converse in the special case of
β
= 2
was proved
in [3], where it was shown that it is impossible to achieve
second moment stability in the system in
(1)
using a quantizer-
controller with the number of bins
<
b
a
c
+ 1
. This implies
the validity of Theorem 2 for
β
≥
2
. Variants of the necessity
result in Theorem 2 are known for vector systems with
bounded disturbances [11] and model uncertainty [12]; for
noiseless vector systems under different stability criteria [13];
for vector linear stochastic systems under second moment
constraint stabilized over rate-constrained noiseless [3] and
packet-drop [14] channels; for vector linear stochastic systems
stabilized in probability over noisy channels [15]; and for
nonlinear systems with additive noise stabilized in probability
over noisy channels [16, Th. 3.1].
In this paper, we construct a new zoom-in zoom-out scheme
that most of the time operates as if the noise were bounded,
and relies on a periodic magnitude test to determine whether
the state has left the quantized region. Similar to an application
of the schemes in [3], [7] to an undersampled system with
the transmission of a codeword over multiple time slots
mentioned above, our strategy uses coding over multiple time
instants, and the controller uses its memory of the past to
correctly interpret the received bits. While the controller in the
above modification of the known schemes is almost always
silent, producing a large signal once in
k
time instances, our
controller is almost always active, producing a control signal
optimized for bounded noise. Thus it introduces less delay. If
the periodic magnitude test is failed, the quantizer-controller
enters the zoom-out mode, which is essentially the same as
in [7]: the controller looks for the
X
n
in exponentially larger
intervals until it is located, at which point it returns to the
zoom-in mode. We provide an elementary analysis of our
scheme with an explicit bound on
k
leading to Theorem 1.
We also present a short proof of the converse result in
Theorem 2 that uses information-theoretic arguments. We
also provide an elementary converse proof for stabilizability
in probability that is tight for non-integer
a
.
In Section II, we describe our achievable scheme and give
its analysis. In Section III, we give a proof of the converse
in Theorem 2. Our results generalize to constant-length time
delays, to control over communication channels that drop a
small fraction of packets, to systems with dependent Gaussian
noise, and to vector systems. These extensions are presented
in Section IV. This is a full version of the conference paper
[17]. This paper presents full proofs (the proofs in [17]
are either omitted or replaced with proof outlines), and a
much more comprehensive discussion of our results and
their relationship to past and future research. In addition,
Theorem 3, which presents a converse using an elementary
+
0
−
X
n
(a) Sign test
+
−
C
n
−
C
n
−
X
n
(b) Magnitude test
Fig. 1. The binary quantizer uses two kinds of tests on a schedule determined
by the previous
±
’s to produce the next
+
or
−
.
probabilistic argument, is not contained in [17].
II. A
CHIEVABLE SCHEME
A. The idea
Here we explain the idea of our achievable scheme. For
readability we focus on the case
a
∈
[1
,
2)
and show that
the system can be controlled with 1 bit. In this case we will
be able to restrict to two types of tests, a
sign test
and a
magnitude test
(see Fig. 1), which simplifies our procedure.
The straightforward extension to an arbitrary
a
≥
1
, in which
the sign test is replaced by a uniform quantizer, is found in
Section II-E below.
In the case of bounded noise a uniform time-invariant
quantizer deterministically keeps
X
n
bounded [1], [2]. Indeed,
when
|
Z
n
|≤
B
,
n
= 1
,
2
,...
and
|
X
1
|≤
C
1
, if
C
1
≥
B
1
−
a/
2
one can put
C
2
,
(
a/
2)
C
1
+
B
≤
C
1
,
(6)
and putting further
C
n
+1
,
(
a/
2)
C
n
+
B
, we obtain
a monotonically decreasing to
B
1
−
a/
2
sequence numbers
{
C
n
}
∞
n
=1
. Setting
U
n
= (
a/
2)
C
n
sgn(
X
n
)
(7)
requires only 1 bit of knowledge about
X
n
(i.e., its sign). If
|
X
n
|≤
C
n
then
|
X
n
+1
|≤
(
a/
2)
C
n
+
B
=
C
n
+1
,
(8)
and
lim sup
n
→∞
|
X
n
|≤
B
1
−
a/
2
.
(9)
Actually, this is the best achievable bound on the uncertainty
about the location of
X
n
, as a simple volume-division
argument shows [11], [18].
When
Z
n
merely have bounded
α
-moments the above
does not work because a single large value of
Z
n
will cause
the system to explode. However we can use the idea of the
bounded case with the following modification. Most of the
time, in
normal
, or
zoom-in
, mode, the controller assumes
the
X
n
are bounded by constants
C
n
and forms the control
3
actions according to the above procedure, but occasionally,
on a schedule, the quantizer performs a
magnitude test
and
sends a bit whose sole purpose is to inform the controller
whether the
X
n
is staying within desired bounds. If the test
is passed, the controller continues in the normal mode, and
otherwise, it enters the
emergency
, or
zoom-out
, mode, whose
purpose is to look for the
X
n
in exponentially larger intervals
until it is located, at which point it returns to the zoom-in
mode while still occasionally checking for anomalies. We
will show that all this can be accomplished with only 1 bit
per controller action.
The intuition behind our scheme is the following. At any
given time, with high probability
X
n
is not too large. Thus,
the emergencies are rare, and when they do occur, the size of
the uncertainty region tends to decrease exponentially. The
zoom-in mode operates almost exactly as in the bounded
case, except that we choose
B
large enough to diminish the
probability that the noise exceeds it. We now proceed to
making these intuitions precise in Section II-B.
B. The Algorithm
Here we describe the algorithm precisely and then prove
that it works. Specifically, we consider the setting of The-
orem 1 with
a
∈
[1
,
2)
and
Z
n
with bounded
α
-moments.
We find
U
n
- a function only of the sequence bits received
from the quantizer - that achieves
β
-moment stability, for
0
< β < α
.
First we prepare some constants. We fix
B
≥
1
large
enough. We set the
probing factor
P
=
P
(
α,β
)
- a large
positive constant (how large will be explained below, but
roughly
P
blows up as
β
↑
α
). Fix a small
δ >
0
and a large
enough
k
=
k
(
a
)
so that
(
a/
2)
k
−
1
a
≤
1
−
3
δ.
(10)
We proceed in “rounds” of at least
k
+ 1
moves,
k
moves in
normal (zoom-in) mode and
k
+ 1
’th move to test whether
X
n
escaped the desired bounds. If that magnitude test comes
back normal, the round ends; otherwise the controller enters
the emergency (zoom-out) mode, whose duration is variable
and which ends once the controller learns a new (larger)
bound on
X
n
. In normal mode, we use the update rule in
(7)
,
where
C
n
≥
B
is positive. In the emergency mode,
U
n
≡
0
while
C
n
grows exponentially. A precise description of the
operation of the algorithm is given below.
1)
At the start of a round at time-step
m
,
|
X
m
|≤
C
m
, the
controller is silent,
U
m
= 0
, and
X
m
+1
=
aX
m
+
Z
m
.
Set
C
m
+1
=
aC
m
+
B,
(11)
and for each
i
∈{
2
,...,k
}
,
C
m
+
i
=
a
2
C
m
+
i
−
1
+
B
(12)
= (
a/
2)
i
−
1
C
m
+1
+
1
−
(
a/
2)
i
−
1
1
−
a/
2
B.
(13)
In this normal mode operation, the quantizer sends
a sequence of signs of
X
n
(see Fig. 1(a)), while
the controller applies the controls
(7)
successively to
X
m
,...,X
m
+
k
−
1
. This normal mode operation will
keep
X
m
+
i
bounded by
C
m
+
i
unless some
Z
m
+
i
is
atypically large.
2)
The quantizer applies the magnitude test to check whether
|
X
m
+
k
| ≤
C
m
+
k
(see Fig. 1(b)). If
|
X
m
+
k
| ≤
C
m
+
k
,
we return to step 1. If
|
X
m
+
k
|
> C
m
+
k
, this means
some
Z
m
+
i
was abnormally large; the system has blown
up and we must do damage control. In this case we enter
emergency (zoom-out) mode
in Step 3 below.
3)
In emergency mode, we repeatedly perform silent
(
U
m
+
k
+
j
≡
0
) magnitude tests via
C
m
+
k
+
j
=
P C
m
+
k
+
j
−
1
=
P
j
C
m
+
k
j
≥
0
(14)
until the first time
τ
that the magnitude test is passed,
i.e.
τ
,
inf
{
j
≥
0 :
|
X
m
+
k
+
j
|≤
C
m
+
k
+
j
}
.
(15)
We then set
m
←
m
+
k
+
τ
and return to Step 1.
The controller is silent at the start of a round because it does
not know the sign of
X
m
. Each round thus includes one silent
step at the start, and
τ
≥
0
silent steps of the emergency
mode.
C. Overview of the Analysis
We analyze the result of each round. At the start of each
round
m
we know that
X
m
is contained within interval
[
−
C
m
,C
m
]
. We will show that when
C
m
is large, the
uncertainty interval tends to decrease by a constant factor
each round.
At the start of the round,
|
X
m
| ≤
C
m
. Assume that for
each
i
∈{
0
,
1
,...,k
}
, we have
|
Z
m
+
i
|≤
B.
(16)
and thus
|
X
m
+
i
|≤
C
m
+
i
.
(17)
In particular, applying
(10)
,
(11)
and
(12)
, we bound the state
at the end of the round as
|
X
m
+
k
|≤
C
m
+
k
(18)
≤
(1
−
3
δ
)
C
m
+
B
1
−
a/
2
,
(19)
which means that
C
m
+
k
≤
C
m
, provided that
C
m
≥
B
3
δ
(1
−
a/
2)
. Thus, even starting with the silent step we have
successfully decreased
C
m
, provided that it was large enough.
What if
(16)
fails to hold? Because the
Z
i
have bounded
α
-moments, by the union bound and Markov’s inequality, the
chance (16) fails is at most
P
[
∪
k
i
=0
{|
Z
m
+
i
|
> B
}
]
≤
(
k
+ 1)
E
[
|
Z
|
α
]
B
−
α
.
(20)
In this case, we show that we can control the blow-up
to avert a catastrophe. Recall that in emergency mode our
4
procedure will take exponentially growing
C
n
(see
(14)
) so
that we will soon observe that
|
X
n
|≤
C
n
. The controller then
exits emergency mode and returns to the normal mode, starting
a new round at time step
n
. Using boundedness of
α
-moments
of
Z
i
, we will show in Section
II-D
below that the chance that
on step
n
=
m
+
k
+
j
this
fails
is exponentially small in
j
.
We will see that in each round starting at
X
m
∈
[
−
C
m
,C
m
]
,
there is a high chance to shrink the magnitude of the state
and a small chance to grow larger. In the next section we
explain how to obtain precise moment control.
D. Precise Analysis
Here we give details of the analysis outlined in Section
II-C
,
demonstrating that when the
Z
n
are i.i.d. with bounded
α
-
moments, our strategy in Section II-B yields
lim sup
n
E
[
|
X
n
|
β
]
<
∞
(21)
for all
0
< β < α
.
The following tools will be instrumental in controlling the
tails of the accumulated noise.
Proposition 1.
If the random variable
Z
has finite
α
-moment,
then
t
α
P
[
|
Z
|
> t
]
(22)
are bounded in
t
. Conversely, if
(22)
are bounded in
t
then
Z
has a finite
β
-moment for any
0
< β < α
.
Proof.
The first part is the Markov inequality. The second is
a standard use of the tail-sum formula.
Lemma 1.
Suppose
a >
1
is fixed and
Z
i
are (arbitrarily
coupled) random variables with uniformly bounded absolute
α
moments. Then the random variables
̃
Z
j
,
j
∑
i
=0
a
−
i
Z
i
(23)
also have uniformly bounded absolute
α
-moments.
Proof.
It is easy to see that for any
α >
0
, ε >
0
there is
c
=
c
α,ε
such that for all
(
x
+
y
)
α
≤
c
α,ε
x
α
+ (1 +
ε
)
y
α
(24)
holds for all
x,y
≥
0
. Indeed, to see this, assume without loss
of generality that
x
= 1
, and note that when
y
is sufficiently
large we already have
(1 +
y
)
α
≤
(1 +
ε
)
y
α
.
(25)
The set of
y
for which
(25)
does not hold is bounded, hence
so is the value of
(1 +
y
)
α
; take
c
to be an upper bound for
this expression. The equation will now hold for any value of
y
.
Applying (24) repeatedly yields
|
̃
Z
k
|
α
≤
(26)
c
|
Z
0
|
α
+
c
k
−
1
∑
i
=1
(1 +
)
i
a
−
αi
|
Z
i
|
α
+ (1 +
ε
)
k
a
−
αk
|
Z
k
|
α
.
Since
E
[
|
Z
i
|
α
]
are uniformly bounded and for
1 +
ε < a
α
the geometric series
∑
j
−
1
i
=1
(1 +
)
i
a
−
αi
converges,
E
[
|
̃
Z
j
|
α
]
is bounded uniformly in
j
, as desired.
Remark
1
.
The mild assumptions of Lemma 1 will make
it easy to generalize our results to dependent noise in
Section IV-C below.
The bound in Lemma 2 below considers the evolution of
the system over
k
+ 1 +
τ
steps, where
τ
(15)
determines
the end of the round. Note that
τ
is a stopping time of the
filtration generated by
{
X
n
}
.
Lemma 2.
Fix
B,P >
0
and consider our algorithm
described in Section
II-B
with these parameters. Suppose
that time-step
m
is the start of a round, so that the round
ends on time-step
m
+
k
+
τ
. For all
1
< a <
2
and for all
0
≤
j
≤
τ
, it holds that
max
{|
X
m
+1
|
,...,
|
X
m
+
k
+
j
|
,C
m
+
k
+
j
}
(27)
≤
Pa
k
+
j
(
2
C
m
+
aB
(2
−
a
)(
a
−
1)
+
k
+
j
−
1
∑
`
=0
a
−
`
−
1
|
Z
m
+
`
|
)
,
Proof.
Appendix.
Proof of Theorem 1 for the case
a
∈
[1
,
2)
.
To avoid a spe-
cial treatment of the case
a
= 1
, we assume that
a >
1
. This
is without loss because showing stability for
a
implies stability
for all
a
′
≤
a
. First we prepare some constants. Recall the
choices of
k
and
δ
in (10).
•
Fix
∆
< α
−
β
an arbitrary fixed constant, e.g.
∆ =
α
−
β
3
,
so that
β
=
α
−
3∆
.
(28)
•
Fix
P
large enough so that
P/a
≥
max
{
(
a
1
−
δ
)
α
−
∆
,
2
k
,
a
k
+1
2(
a
−
1)
}
.
(29)
Suppose that time-step
m
is the start of a round, so that
the round ends on time-step
m
+
k
+
τ
, with stopping time
τ
= 0
usually.
We define a modified sequence
1
̃
X
n
through, for
1
≤
i
≤
k
+
τ
,
̃
X
m
+
i
,
(
1
1
−
δ
)
τ
−|
i
−
k
|
+
(30)
max
{|
X
m
+
k
|
,...,
|
X
m
+
k
+
τ
|
,C
m
+
k
+
τ
}
,
1
̃
X
n
serves as a Lyapunov function that stochastically controls the growth
of the state process
X
n
. See [9, Th. 2.1], [19] for a general approach to
proving stability using Lyapunov functions for general Markov chains.
5
where
|·|
+
,
max
{
0
,
·}
. Clearly this definition ensures that
|
X
m
+
k
+
j
|≤
̃
X
m
+
k
+
j
0
≤
j
≤
τ.
(31)
Furthermore, for all
1
≤
i
≤
k
−
1
, there exists universal
constants
K
1
,K
2
,K
3
that depend on
a
,
k
and
B
such that
(Appendix A)
E
[
|
X
m
+
i
|
β
]
≤
K
1
E
[
̃
X
β
m
+
k
]
+
K
2
E
[
̃
X
β
m
]
+
K
3
.
(32)
Inequalities
(31)
and
(32)
together mean that to establish
(21)
,
it is sufficient to prove
lim sup
n
E
[
̃
X
β
n
]
<
∞
.
(33)
The rest of the proof is focused in establishing (33).
By definition (30),
̃
X
m
+
i
≤
̃
X
m
+1
i
= 2
,...,k
+
τ,
(34)
with equality for
i
≤
k
.
We will show that
E
[
̃
X
β
m
+1
]
≤
(1
−
δ
)
β
E
[
̃
X
β
m
] +
K,
(35)
where
K
=
K
(
P,k,δ
)
is a constant that may depend on
P,k,δ
(but is independent of
m
). Together, inequalities
(34)
and
(35)
ensure that
lim sup
n
E
[
̃
X
β
n
]
is bounded above by
K
1
−
(1
−
δ
)
β
.
The intuition behind the definition for
̃
X
n
is as follows.
We want to construct a dominating sequence
̃
X
n
with the
expected decrease property in
(35)
. During emergency mode,
the original sequence
X
n
may increase on average during
rounds. The sequence
̃
X
n
in
(30)
takes the potential increase
during each round up front, achieving the desired expected
decrease property. We will see that
P
in
(29)
is chosen so
that the constant-factor decrease of the system is preserved
when switching between rounds.
To show
(35)
, we define the filtration
F
n
as follows:
F
n
is
the
σ
-algebra generated by the sequences
Z
1
,Z
2
,...,Z
n
−
1
and
̃
X
1
,
̃
X
2
,...,
̃
X
n
. Unless
n
is the end of a round,
knowledge of
̃
X
n
involves a peek into the future, so
F
n
encompasses slightly more information than the naive notion
of “information up to time
n
”. The inequality we will show,
clearly stronger than (35), is
E
[
̃
X
β
m
+1
|F
m
]
≤
(1
−
δ
)
β
E
[
̃
X
β
m
|F
m
] +
K.
(36)
Define
Y
n
,
̃
X
n
+1
̃
X
n
+
B
(1
−
a/
2)(1
−
3
δ
)
.
(37)
We will show
(36)
by the means of the following two
statements, where
m
is the transition between rounds:
(a)
For sufficiently large
k
and
P
in
(10)
and
(29)
, respec-
tively, it holds that
2
P
[
Y
m
≥
t
|F
m
] =
O
(
t
−
(
α
−
∆)
)
,
(38)
2
Throughout this section, the implicit constants
O
(
·
)
may depend on
P,k,δ
(but are independent of
n
and
B
≥
1
).
(b) As
B
→∞
,
P
[
Y
m
≤
1
−
3
δ
|F
m
]
→
1
.
(39)
We use
(38)
and
(39)
to show
(36)
as follows. First,
observe that by
(38)
and Proposition 1,
{
Y
m
|F
m
}
has bounded
β
+ ∆
- moment since we assumed
(28)
when choosing
∆
.
Furthermore, since the right side of
(38)
is independent of
F
m
, the
β
+ ∆
- moment of
Y
m
is bounded uniformly in
m
. Now, pick
p >
1
so that
βp
≤
β
+ ∆
, and let
q
satisfy
1
p
+
1
q
= 1
. Write
E
[
Y
β
m
|F
m
]
≤
(1
−
3
δ
)
β
+
E
[
Y
β
m
1
{
Y
m
>
1
−
3
δ
}|F
m
]
(40)
≤
(1
−
3
δ
)
β
+
(
E
[
Y
βp
m
|F
m
])
1
p
(
P
[
Y
m
>
1
−
3
δ
|F
m
])
1
q
(41)
→
(1
−
3
δ
)
β
, B
→∞
,
(42)
where
(41)
is by H
̈
older’s inequality, and the second term
in
(41)
vanishes as
B
→ ∞
due to
(39)
and uniform
boundedness of the
β
+ ∆
- moment of
{
Y
m
| F
m
}
. Note
that convergence in
(42)
is uniform in
m
. It follows that for a
large enough
B
(how large depends on the values of
P,k,δ
),
E
[
Y
β
m
|F
m
]
≤
(1
−
2
δ
)
β
.
(43)
Rewriting (43) using (37) yields
E
[
̃
X
β
m
+1
|F
m
]
≤
(1
−
2
δ
)
β
(
̃
X
m
+
B
(1
−
a/
2)(1
−
3
δ
)
)
β
(44)
≤
(1
−
δ
)
β
̃
X
β
m
+
K,
(45)
where to write
(45)
we used
(24)
. This establishes the
inequality (36).
To complete the proof of Theorem 1, it remains to establish
(38) and (39).
To show
(38)
, recall that the round ends at stopping time
m
+
k
+
τ
. Since the events
{
τ
=
j
}
are disjoint, we have
P
[
Y
m
≥
t
|F
m
] =
∞
∑
j
=0
P
[
Y
m
≥
t,τ
=
j
|F
m
]
+
P
[
Y
m
≥
t,τ
=
∞|F
m
]
(46)
Note that since
m
is the end of the previous round,
F
m
does not contain any information about the future.
We estimate the probability of the event in
P
[
Y
m
≥
t,τ
=
j
|F
m
]
in two ways, and use the better estimate on each term
individually.
We express the system state at time
m
+
i
in terms of the
system state at time
m
:
X
m
+
i
=
a
i
(
X
m
+
i
−
1
∑
`
=0
a
−
`
−
1
U
m
+
`
+
i
−
1
∑
`
=0
a
−
`
−
1
Z
m
+
`
)
.
(47)
6
Using
(7)
,
(11)
,
(12)
and recalling that
U
m
= 0
, we can
crudely bound the cumulative effect of controls on
X
m
+
i
as
a
i
∣
∣
∣
∣
∣
k
−
1
∑
`
=0
a
−
`
−
1
U
m
+
`
∣
∣
∣
∣
∣
≤
a
i
(
a/
2)
∞
∑
`
=1
a
−
`
−
1
(48)
(
(
a/
2)
`
−
1
C
m
+1
+
1
−
(
a/
2)
`
−
1
1
−
a/
2
B
)
=
a
i
(
C
m
+
B
a
−
1
)
.
(49)
Recalling the definitions of
̃
X
n
,
Y
n
in
(30)
,
(37)
, respec-
tively, and invoking Lemma 2, we see that if
{
Y
m
≥
t,τ
=
j
}
holds, then
t
(1
−
δ
)
k
+
j
−
1
(
̃
X
m
+
B
(1
−
a/
2)(1
−
3
δ
)
)
(50)
≤
Pa
k
+
j
(
2
C
m
+
aB
(2
−
a
)(
a
−
1)
+
k
+
j
−
1
∑
`
=0
a
−
`
−
1
|
Z
m
+
`
|
)
.
Noting that both
C
m
and
aB
2
−
a
are dominated by
̃
X
m
+
B
(1
−
a/
2)(1
−
3
δ
)
≥
1
, we can weaken (50) as
t
(1
−
δ
)
k
+
j
−
1
≤
Pa
k
+
j
(
2 +
1
a
−
1
+
k
+
j
−
1
∑
`
=0
a
−
`
−
1
|
Z
m
+
`
|
)
.
(51)
Applying Lemma 1 and Proposition 1, we deduce that the
probability of the event in (51) is
O
(
(
a
1
−
δ
)
αj
t
−
α
)
.
(52)
The bound in
(52)
works well for small
j
/ large
t
. For
large
j
/ small
t
, we observe that
{
Y
m
≥
t,τ
=
j
}⊆{
τ
≥
j
}
and apply the following reasoning. The event
{
τ
≥
j
}
means
that the emergency did not end at time
j
; in other words,
|
X
m
+
k
+
j
−
1
|
> C
m
+
k
+
j
−
1
(53)
=
P
j
(
2 (
a/
2)
k
C
m
+
B
1
−
a/
2
)
,
(54)
where to write
(54)
we used
(11)
,
(13)
, and
(14)
. Substituting
i
←
k
+
j
into
(47)
and recalling
(49)
and
|
X
m
|≤
C
m
, we
weaken (53)–(54) as
a
k
+
j
(
2
C
m
+
aB
(2
−
a
)(
a
−
1)
+
k
+
j
−
1
∑
`
=0
a
−
`
−
1
|
Z
m
+
`
|
)
> P
j
(
2 (
a/
2)
k
C
m
+
B
1
−
a/
2
)
,
(55)
the event equivalent to
(
a/P
)
j
k
+
j
−
1
∑
`
=0
a
−
`
−
1
|
Z
m
+
`
|≥
2
(
(1
/
2)
k
−
(
a/P
)
j
)
C
m
+
(
(1
/a
)
k
−
a
(
a/P
)
j
2(
a
−
1)
)
B
1
−
a/
2
.
(56)
Due to the choice of
P
in
(29)
, the coefficients in front of
C
m
and
B
in the right side of
(56)
are nonnegative for all
j
≥
1
. Bounding the probability of the event in
(56)
using
Lemma 1 and Proposition 1, we conclude that
3
P
[
τ
≥
j
] =
O
(
(
P/a
)
−
jα
)
.
(57)
Furthermore,
(57)
means that
P
[
τ
=
∞
] = 0
. Indeed,
1
{
τ
=
∞}
=
∏
∞
j
=0
1
{
τ
≥
j
}
= lim
j
→∞
1
{
τ
≥
j
}
and by Fatou’s
lemma,
P
[
τ
=
∞
]
≤
lim
j
→∞
P
[
τ
≥
j
] = 0
,
(58)
thus the corresponding term can be eliminated from (46).
Juxtaposing
(52)
and
(57)
, we conclude that the probability
P
[
Y
m
≥
t,τ
=
j
|F
m
]
is bounded by
O
(
min
{
(
a
1
−
δ
)
αj
t
−
α
,
(
P/a
)
−
jα
})
.
(59)
Since
(29)
ensures that
(
P/a
)
∆
≥
(
a
1
−
δ
)
α
, we weaken
(59)
as
O
(
(
P/a
)
j
∆
min
{
t
−
α
,
(
P/a
)
−
jα
})
.
(60)
Recall that we have fixed
t
and are varying
j
; this upper
bound peaks at
j
such that
(
P/a
)
j
=
t
at the value
t
−
(
α
−
∆)
and decays geometrically on each side at rates
(
P/a
)
∆
and
(
P/a
)
α
−
∆
. Hence the sum of all
P
[
Y
m
≥
t,τ
=
j
|F
m
]
terms
in
(46)
is bounded by the maximum up to a constant factor
and therefore (38) holds.
To complete the proof of Theorem 1, it remains to establish
(39)
. By Markov’s inequality
(20)
, with probability converging
to
1
as
B
→∞
, all terms
Z
m
,...,Z
m
+
k
are within
[
−
B,B
]
,
and
τ
= 0
. In such a case, applying
(19)
and recalling
(30)
,
we get
̃
X
m
+1
= max
{|
X
m
+
k
|
,C
m
+
k
}
(61)
≤
(1
−
3
δ
)
̃
X
m
+
B
1
−
a/
2
,
(62)
which implies that
Y
m
≤
1
−
3
δ
, establishing (39).
E. Finer Quantization
For
a
≥
2
, the controller receives an element of an
b
a
c
+ 1
-
element set instead of a single bit. In this case we restrict
our attention to
order-statistic
tests, meaning that we split the
real line into
b
a
c
+ 1
intervals
(
−∞
,w
1
,n
)
,
[
w
1
,n
,w
2
,n
)
,...,
[
w
b
a
c
,n
,
∞
)
,
(63)
and the controller receives the index
b
n
∈ {
0
,
1
,...,
b
a
c}
of the interval containing
X
n
. The only real issue is for
the quantizer and the controller to agree upon a rule for
updating the values of
w
i
. However, this is easy; in the
obvious generalization of our algorithm to higher
a
, the
3
Similar exponential bounds to the event
P
[
τ
≥
j
]
are provided in [9,
Lem. 5.2] and in [16, Lem. 5.2].
7
(uniform) quantizer simply breaks up the interval
[
−
C
n
, C
n
]
into
b
a
c
+ 1
equal parts, where
C
n
is the same bound on
the state magnitude as before. Both quantizer and controller
follow the rules in
(12)
(with
a/
2
replaced by
a/
(
b
a
c
+1)
and
in
(14)
to update
C
n
. During the normal mode, the controller
applies the control
U
n
=
−
C
n
+
C
n
2
b
n
+ 1
b
a
c
+ 1
(64)
which reduces to (7) when
b
a
c
= 1
.
In the case
a <
1
, the controller does nothing, which by
Lemma 1 achieves
β
-moment stability.
III. C
ONVERSE
In this section, we prove the converse result in Theorem 2
using information-theoretic arguments similar to those em-
ployed in [3], [20]. Then, we use elementary probability to
show an alternative converse result, which implies Theorem 2
unless
a
is an integer.
Proof of Theorem 2.
Conditional entropy power is defined as
N
(
X
|
U
)
,
1
2
πe
exp (2
h
(
X
|
U
))
(65)
where
h
(
X
|
U
) =
−
∫
R
f
X,U
(
x,u
) log
f
X
|
U
=
u
(
x
)
dx
is the
conditional differential entropy of
X
.
Conditional entropy power is bounded above in terms of
moments (e.g. [21, Appendix 2]):
N
(
X
)
≤
κ
β
E
[
|
X
|
β
]
2
β
(66)
κ
β
,
2
πe
(
e
1
β
Γ
(
1 +
1
β
)
β
1
β
)
2
,
(67)
Thus,
κ
β
E
[
|
X
n
|
β
]
2
β
≥
N
(
X
n
)
(68)
≥
N
(
X
n
|
U
n
−
1
)
,
(69)
where
(69)
holds because conditioning reduces entropy. Next,
we show a recursion on
N
(
X
n
|
U
n
−
1
)
:
N
(
X
n
|
U
n
−
1
)
=
N
(
A
X
n
−
1
+
Z
n
−
1
|
U
n
−
1
)
(70)
≥
a
2
N
(
X
n
−
1
|
U
n
−
1
) +
N
(
Z
n
−
1
)
(71)
≥
a
2
N
(
X
n
−
1
|
U
n
−
2
) exp (
−
2
r
) +
N
(
Z
n
−
1
)
,
(72)
where
(71)
is due to the conditional entropy power inequality:
4
N
(
X
+
Y
|
U
)
≥
N
(
X
|
U
) +
N
(
Y
|
U
)
,
(73)
which holds as long as
X
and
Y
are conditionally inde-
pendent given
U
, and
(72)
is obtained by weakening the
constraint
|
U
n
−
1
| ≤
M
to a mutual information constraint
I
(
X
n
−
1
;
U
n
−
1
|
U
n
−
2
)
≤
log
M
=
r
and observing that
min
P
U
|
X
:
I
(
X
;
U
)
≤
r
h
(
X
|
U
)
≥
h
(
X
)
−
r.
(74)
4
Conditional EPI follows by convexity from the unconditional EPI first
stated by Shannon [22] and proved by Stam [23].
It follows from
(72)
that
r >
log
a
is necessary to keep
N
(
X
n
|
U
n
−
1
)
bounded. Due to
(69)
, it is also necessary to
keep
β
-th moment of
X
n
bounded.
Consider the following notion of stability.
5
Definition 1.
The system is stabilizable in probability if there
exists a control strategy such that for some bounded interval
I
,
lim sup
n
→∞
P
[
X
n
∈I
]
>
0
.
(75)
As a simple consequence of Markov’s inequality, if the
system is moment-stable, it is also stable in probability.
Therefore the following converse for stability in probability
implies a converse for moment stability.
Theorem 3.
Assume that
X
1
has a density. To achieve
stability in probability,
M
≥d
a
e
is necessary.
Proof.
We want to show that for any bounded interval
I
, if
r <
log
a
then
lim sup
n
→∞
P
[
X
n
∈I
] = 0
.
(76)
At first we assume that the density of
X
1
is bounded, that is,
|
f
X
1
(
x
)
|≤
f
max
and that
X
1
is supported on a finite interval,
i.e.
|
X
1
|≤
x
max
, for some constants
f
max
,x
max
.
Since we are showing a converse (impossibility) result,
we may relax the operational constraints by revealing the
noises
Z
n
, n
= 1
,
2
,...
noncausally to both encoder and
decoder. Since then the controller can simply subtract the
effect of the noise, we may put
Z
n
≡
0
in
(1)
. Then,
X
n
+1
=
a
n
X
1
+
̃
U
n
, where
̃
U
n
,
∑
n
i
=0
a
n
−
i
U
i
is the combined
effect of
t
controls, which can take one of
M
n
values, i.e.
U
n
=
u
(
m
)
if
X
1
∈I
m
,
m
= 1
,...,M
n
. Regardless of the
particular choice of control actions
u
(
m
)
and quantization
intervals
I
m
, for any bounded interval
I
,
P
[
X
n
+1
∈I
] =
P
[
a
n
X
1
+
̃
U
n
∈I
]
(77)
=
M
n
∑
m
=1
P
[
a
n
X
1
+
u
(
m
)
∈I
,X
1
∈I
m
]
(78)
≤
M
n
a
−
n
f
max
|I|
,
(79)
and
(76)
follows for any
M < a
, confirming the necessity of
M
≥d
a
e
to achieve weak stability.
6
Finally, if the density of
X
1
is unbounded, consider
the set
S
b
,
{
x
∈
R
:
f
X
1
(
x
)
≤
b
}
and notice that since
5
A more stringent to Definition 1 notion of stability in probability, in
which
>
0
in the right side of
(75)
is replaced by
= 1
, was considered in
[15, Def. 2.1], and in [16, Th. 3.1].
6
An argument similar to
(77)
–
(79)
showing that the Lebesgue measure
of
I
cannot be sustained is the key to the data-rate theorems for invariance
entropy [24]–[27].
8
1
{
f
X
1
(
x
)
> b
} →
0
pointwise as
b
→ ∞
, by dominated
convergence theorem,
P
[
X
1
∈S
b
] =
∫
R
f
X
1
(
x
)1
{
f
X
1
(
x
)
> b
}
d
x
→
0
as
b
→∞
.
(80)
Therefore for any
>
0
, one can pick
b >
0
such that
P
[
X
1
∈S
b
]
≤
. Then, since we already proved that
(76)
holds for bounded
f
X
1
, we conclude
lim sup
n
→∞
P
[
X
n
∈I
]
≤
+ lim sup
n
→∞
P
[
X
n
∈I|
X
1
∈S
b
] =
,
(81)
which implies that
(76)
continues to hold for unbounded
f
X
1
.
The quantities
d
a
e
and
b
a
c
+ 1
coincide unless
a
is an
integer, thus Theorem 3 shows that for non-integer
a
, the
converse (impossibility) part of Theorem 1 continues to hold
in the sense of weak stability. Note that the proof of Theorem 3
relaxes the causality requirement. We conjecture that
d
a
e
can
be replaced by
b
a
c
+ 1
in its statement, but proving that will
require bringing causality back in the picture, and the simple
argument in the proof of Theorem 3 will not work.
We conclude Section III with a technical remark.
Remark
2
.
The assumptions in Theorem 3 are weaker than
those in Theorem 2, because the differential entropy of
X
1
not being
−∞
implies that
X
1
must have a density. The
assumption that
X
1
must have a density is not superficial.
For example, consider
Z
i
≡
0
and
X
1
uniformly distributed
on the Cantor set, and
a
= 2
.
9
. Clearly this system can be
stabilized with 1 bit, by telling the controller at each step the
undeleted third of the interval the state is at. This is lower
than the result of Theorem 1, which states that
M
?
β
would be
3
if
X
1
had a density. Beyond distributions with densities, we
conjecture that
M
?
β
will depend on the Hausdorff dimension
of the probability measure of
X
1
.
IV. G
ENERALIZATIONS
In this section, we generalize our results in several direc-
tions. In most cases we only outline the mild differences in
the proof.
A. Constant-Length Time Delays
Many systems have a finite delay in feedback. To model
this, we can force
U
n
to depend on only the feedback up to
round
n
−
`
, i.e.
U
n
=
g
n
(
f
1
(
X
1
)
,
f
2
(
X
2
)
,...,
f
n
−
`
(
X
n
−
`
))
,
(82)
where
f
n
(
X
n
)
is the quantizer’s output at time
n
, as before.
We argue here that this makes no difference in terms of
the minimum number of bits required for stability. We state
the modified result next.
Theorem 4.
Let
X
1
,
Z
n
in
(1)
be independent random vari-
ables with bounded
α
-moments. Assume that
h
(
X
1
)
>
−∞
.
The minimum number of quantization points to achieve
β
-
moment stability, for any
0
< β < α
and with any constant
delay
`
is given by
b
a
c
+ 1
.
Proof.
The problem here is that the encoder sees the system
before the controller can act on it. However, if we also delay
the encoder seeing the system by
`
time steps, then we
can directly use the algorithm we have already constructed.
Specifically, if our artificially delayed sequence of system
states is
{
̃
X
n
}
, then the real sequence is given by
X
n
=
a
`
̃
X
n
+
a
`
−
1
Z
n
+1
+
...
+
Z
n
+
`
.
(83)
By Theorem 1, we can keep
E
[
|
̃
X
n
|
β
]
bounded for any
β < α
by applying to
̃
X
n
the control in
(64)
in normal mode
and
U
n
= 0
in the emergency mode. Since with delay, the
controller acts on
X
n
rather than on
̃
X
n
, we multiply the
control action
(64)
by
a
`
to achieve the same effect on
̃
X
n
as
without delay. Furthermore, each
Z
i
has bounded
β
moment,
so by Lemma 1 their sum will have bounded
β
-moment, as
desired.
The converse is obvious as even with
`
= 0
, Theorem 2
asserts that the system cannot be stabilized with fewer than
b
a
c
+ 1
bits.
B. Packet drops
Suppose that the encoder cannot send information to the
controller at all time-steps. Instead, the encoder can only send
information at a deterministic set
T ⊆
N
of times. Formally,
U
n
=
g
n
(
{
f
n
(
X
n
) :
n
∈T}
)
.
(84)
As long as the density of
T
is high enough on all large,
constant-sized scales, the same results go through.
Definition 2.
A set
T ⊆
N
is
strongly
p
-dense
if there exists
N
such that for all
n
we have
|
n
+
i
:
n
+
i
∈T
, i
= 0
,...,N
−
1
|
N
> p.
(85)
Note that the constant delay scenario in Section
IV-A
amounts to control on a strongly
p
-dense set, with
p
∈
[0
,
1)
as close to
1
as desired.
Theorem 5.
Let
X
1
,
Z
n
in
(1)
be independent random vari-
ables with bounded
α
-moments. Assume that
h
(
X
1
)
>
−∞
.
The minimum number of quantization points to achieve
β
-
moment stability is
b
a
c
+ 1
, for any
0
< β < α
and on any
strongly
p
-dense set with some
p
∈
[0
,
1]
large enough so
that
(
b
a
c
+ 1)
p
> a.
(86)
Proof.
The requirement
(86)
ensures that the bounded case
works; indeed, it is equivalent to
(
a
b
a
c
+ 1
)
p
a
1
−
p
<
1
,
(87)
9
which means that the logarithm of the range of
X
n
decreases
on average each time-step.
In the unbounded noise case, we perform the same basic
algorithm, but ensuring that the normal mode has enough times
in
T
, so the duration of the normal mode gets longer if
N
is
large. Likewise, in the emergency mode, it will take longer
to catch blow-ups. However, a much weaker condition on
T
suffices for the emergency mode to end: even if
T
contains
only
1
element out of every
N
, we make the probe factor
P
large enough depending on
N
. The difference between
probing every
N
time steps vs. every time step at most a
factor of
a
N
which is a constant.
C. Dependent Noise
Here we address a modification in which the noise is
correlated rather than independent.
Proposition 2.
Suppose
{
Z
n
}
is a Gaussian process whose
covariance matrix
M
(for any number of samples) has
spectrum bounded by
λ
. Then there is an independent
Gaussian process
{
Z
′
n
}
such that the random variables
{
Z
n
+
Z
′
n
}
are i.i.d. Gaussians with variances
λ
2
.
Proof.
Just make the covariances matrices of
{
Z
n
}
and
{
Z
′
n
}
add to
λI
; the assumption means both are positive
semidefinite, hence define Gaussian processes.
If the rows of
M
have
`
1
norm at most
λ
, the assumption
of Proposition 2 that
M
has spectrum bounded by
λ
will be
satisfied. Indeed, we can add a positive semidefinite matrix
to such an
M
to obtain a diagonal matrix with each entry at
most
λ
: if
M
has an entry of
x
at positions
(
i,j
)
and
(
j,i
)
then we add
|
x
|
to the
(
i,i
)
and
(
j,j
)
entries; it is easy to
see that the symmetric matrix
(
|
x
| −
x
−
x
|
x
|
)
(88)
is always positive semidefinite. Therefore doing this for all
non-diagonal entries adds a positive semidefinite matrix to
M
and still results in a spectrum contained in
[0
,λ
]
, meaning
M
also had spectrum contained in
[0
,λ
]
.
Theorem 6.
The results in Theorems 1, 4, 5 extend to the case
when
{
Z
n
}
is correlated Gaussian noise whose covariance
matrix has bounded spectrum.
Proof.
As a result of Proposition 2, for any Gaussian noise
with known covariance matrix
M
of bounded spectrum, the
controller can simply add extra noise to the system via
U
n
to effectively make the noise i.i.d. Gaussian, reducing this
scenario to the i.i.d. case.
D. Vector systems
The results generalize to higher dimensional systems
X
n
+1
=
A
X
n
+
Z
n
−
B
U
n
,
(89)
where
A
is a
d
×
d
matrix and
Z
n
, U
n
are vectors. The
dimensionality of control signals
U
n
can be less than
d
, in
which case
B
is a tall matrix.
For the controls to potentially span the whole space
R
d
when combined with the multiplication-by-
A
amplification,
the range of
[
B
,
AB
,
A
2
B
, ...,
A
d
−
1
B
]
(90)
needs to span
R
d
. Such a pair
(
A
,
B
)
of matrices is commonly
referred to as
controllable
. (The
0
,...,d
−
1
powers of
A
are
sufficient in
(90)
, because by the Cayley-Hamilton theorem
any higher power of
A
is a linear combination of those lower
powers). For our results to hold, a weaker condition suffices,
namely, we need
stabilizability
of
(
A
,
B
)
, which is to say that
only unstable modes need be controllable. More precisely, in
the
canonical
representation of a linear system,
[
X
u
n
+1
X
s
n
+1
]
=
[
A
u
A
′
0 A
s
][
X
u
n
X
s
n
]
+
Z
n
−
[
B
u
0
]
U
n
,
(91)
where the matrix
A
s
has all stable eigenvalues, the state
coordinates
X
s
n
+1
cannot be reached by the control
U
n
.
Stabilizability means that the pair
(
A
u
,
B
u
)
is controllable,
which ensures that unstable modes can be controlled.
The idea behind our generalization to the vector case,
previously explored in e.g. [3], is that we can decompose
R
d
into eigenspaces of
A
and rotate attention between these
parts.
Theorem 7.
Consider the stochastic vector linear system in
(89)
with
(
A
,
B
)
stabilizable. Let
X
1
, Z
n
be independent
random
R
d
-valued random vectors with bounded
α
-moments.
Assume that
h
(
X
1
)
>
−∞
. Let
(
λ
1
,...,λ
d
)
be the eigenvalues
of
A
, and set
a
,
d
∏
j
=1
max(1
,
|
λ
j
|
)
.
(92)
Then for any
0
< β < α
, the minimum number of quantization
points to achieve
β
-moment stability is
M
?
β
=
b
a
c
+ 1
.
(93)
Proof.
We first consider the case
U
n
∈
R
d
,
B
=
I
:
X
n
+1
=
A
X
n
+
Z
n
−
U
n
,
(94)
and then explain how to deal with the general stabilizable
system in (89).
By using a real Jordan decomposition, we can block-
diagonalize
A
into
A
=
⊕
j
A
j
(95)
where
A
j
:
V
j
→V
j
with
⊕
j
V
j
=
R
d
(96)
such that: