1

Sampling Constrained Asynchronous
Communication: How to Sleep Efficiently

arXiv:1501.05930v5 [] 24 Oct 2017

Venkat Chandar and Aslan Tchamkerten

Abstract—The minimum energy, and, more generally,
the minimum cost, to transmit one bit of information
has been recently derived for bursty communication when
information is available infrequently at random times at
the transmitter. Furthermore, it has been shown that even
if the receiver is constrained to sample only a fraction
ρ ∈ (0, 1] of the channel outputs, there is no capacity
penalty. That is, for any strictly positive sampling rate ρ,
the asynchronous capacity per unit cost is the same as
under full sampling, i.e.,, when ρ = 1. Moreover, there is
no penalty in terms of decoding delay.
The above results are asymptotic in nature, considering
the limit as the number B of bits to be transmitted
tends to infinity, while the sampling rate ρ remains fixed.
A natural question is then whether the sampling rate
ρ(B) can drop to zero without introducing a capacity (or
delay) penalty compared to full sampling. We answer this
question affirmatively. The main result of this paper is an
essentially tight characterization of the minimum sampling
rate. We show that any sampling rate that grows at least
as fast as ω(1/B) is achievable, while any sampling rate
smaller than o(1/B) yields unreliable communication. The
key ingredient in our improved achievability result is a
new, multi-phase adaptive sampling scheme for locating
transient changes, which we believe may be of independent
interest for certain change-point detection problems.
Index Terms—Asynchronous communication; bursty
communication; capacity per unit cost; energy; change detection; hypothesis testing; sequential analysis; sparse communication; sampling; synchronization; transient change

I. I NTRODUCTION

I

N many emerging technologies, communication is
sparse and asynchronous, but it is essential that
This work was supported in part by a grant and in part by a Chair of
Excellence both from the French National Research Agency (ANRBSC and ANR-ACE, respectively). This work was presented in part
at the 2015 International Symposium on Information Theory and at
the 2016 Asilomar Conference on Signals, Systems, and Computers.
V. Chandar is with D. E. Shaw and Co., New York, NY 10036,
USA. Email: chandarvenkat@verizon.net.
A. Tchamkerten is with the Department of Communications and
Electronics, Telecom ParisTech, 75634 Paris Cedex 13, France.
Email: aslan.tchamkerten@telecom-paristech.fr.

when data is available, it is delivered to the destination as timely and reliably as possible.
In [3] the authors characterized capacity per unit
cost as a function of the level of asynchronism for
the following model. There are B bits of information that are made available to the transmitter at
some random time ν, and need to be communicated to the receiver. The B bits are encoded into
a codeword of length n, and transmitted over a
memoryless channel using a sequence of symbols
that have costs associated with them. The rate R per
unit cost is B divided by the cost of the transmitted
sequence. Asynchronism is captured here by the fact
that the random time ν is not known a priori to
the receiver. However, both transmitter and receiver
know that ν is distributed uniformly over a time
horizon {1, 2, . . . , A}. At all times before and after
the actual transmission, the receiver observes pure
noise.
The goal of the receiver is to reliably decode the
information bits by sequentially observing the outputs of the channel. A main result in [3] is a singleletter characterization of the asynchronous capacity
per unit cost C(β), where β = (log A)/B denotes
the timing uncertainty per information bit. While
this result holds for arbitrary discrete memoryless
channels and arbitrary input costs, the underlying
model assumes that the receiver is always in the
listening mode: every channel output is observed
until the decoding instant.
In [8] it is shown that even if the receiver is
constrained to observe at most a fraction ρ ∈ (0, 1]
of the channel outputs the asynchronous capacity
per unit cost C(β, ρ) is not impacted by a sparse
output sampling, that is
C(β, ρ) = C(β)
for any asynchronism level β > 0 and sampling
frequency ρ ∈ (0, 1]. Moreover, the decoding delay
is minimal: the elapsed time between when information is available sent and when it is decoded

2

is asymptotically the same as under full sampling.
This result uses the possibility for the receiver to
sample adaptively: the next sample can be chosen as
a function of past observed samples. In fact, under
non-adaptive sampling, it is still possible to achieve
the full sampling asynchronous capacity per unit
cost, but the decoding delay gets multiplied by a
factor 1/ρ. Therefore, adaptive sampling strategies
are of particular interest in the very sparse regime.
The results of [8] provide an achievability scheme
when the sampling frequency ρ is a strictly positive
constant. This suggests the question whether ρ =
ρ(B) can tend to zero as B tends to infinity while
still incurring no capacity or delay penalty. The
main result of this paper resolves this question. We
introduce a novel, multi-phase adaptive sampling
algorithm for message detection, and use it to prove
an essentially tight asymptotic characterization of
the minimum sampling rate needed in order to communicate as efficiently as under full sampling. Informally, we exhibit a communication scheme utilizing
this multi-phase sampling method at the receiver
that asymptotically achieves vanishing probability
of error and possesses the following properties:
1. The scheme achieves the capacity per unit cost
under full sampling, that is, there is no rate
penalty even though the sampling rate tends to
zero;
2. The receiver detects the codeword with minimal delay;
3. The receiver detects changes with minimal
sampling rate, in the sense that any scheme that
achieves the same order of delay but operates
at a lower sampling rate will completely miss
the codeword transmission period, regardless
of false-alarm probability. The sampling rate
converges to 0 in the limit of large B, and our
main result characterizes the best possible rate
of convergence.
In other words, our communication scheme achieves
essentially the minimal sampling rate possible, and
incurs no delay or capacity penalty relative to full
sampling. A formal statement of the main result is
given in Section II.

of asynchronism under which it is still possible
to communicate reliably. In [9], [10] capacity is
defined as the message length divided by the mean
elapsed time between when information is available
and when it is decoded. For this definition, capacity
upper and lower bounds are established and shown
to be tight for certain channels. In [9] it is also
shown that so called training-based schemes, where
synchronization and information transmission are
performed separately, need not be optimal in particular in the high rate regime. In [3] capacity is
defined with respect to codeword length and is characterized as a function of the level of asynchronism.
For the same setup Polyanskiy in [5] investigated
the finite length regime and showed that in certain
cases dispersion is unaffected by asynchronism even
when β > 0.
In [11], [12] the authors investigated the slotted
version of the problem (i.e., the decoder is revealed
ν mod n) and established error exponent tradeoffs
between between decoding error, false-alarm, and
miss-detection.
In [3], [6] the above bursty communication setup
is investigated in a random access configuration and
tradeoffs between communication rate and number
of users are derived as a function of the level of
asynchronism. Finally, in [7] a diamond network is
considered and the authors provided bounds on the
minimum energy needed to convey one bit across
the network.
Paper organization
This paper is organized as follows. In Section II,
we recall the asynchronous communication model
and related prior results. Then, we state our main
result, Theorem 3, which is a stronger version
of the results in [8]. Section III states auxiliary
results, Theorems 4 and 5, characterizing the performance of our multi-phase sampling algorithm.
In Section IV we first prove Theorems 4 and 5,
then prove Theorem 3. The achievability part of
Theorem 3 uses the multi-phase sampling algorithm
for message detection at the receiver, and the converse is essentially an immediate consequence of
the converse of Theorem 5.

Related works
II. M AIN RESULT: THE SAMPLING RATE
REQUIRED
IN ASYNCHRONOUS COMMUNICATION
The above sparse communication model was first
Our main result, Theorem 3 below, is a strengthintroduced in [2], [10]. These works characterize
the synchronization threshold, i.e.,the largest level ening of the results of [8]. We recall the model and

3

results (Theorems 1 and 2) of that paper below to receiver observes “pure noise.” Specifically, conditioned on ν and on the message to be conveyed m,
keep the paper self-contained.
Communication is discrete-time and carried over the receiver observes independent channel outputs
a discrete memoryless channel characterized by its
Y1 , Y2 , . . . , YA+n−1
finite input and output alphabets
X and

Y,

distributed as follows. For
1≤t≤σ−1

respectively, and transition probability matrix
Q(y|x),

or

σ +n ≤ t ≤ A+n −1,
for all y ∈ Y and x ∈ X. Without loss of generality,
we assume that for all y ∈ Y there is some x ∈ X the Yt ’s are “pure noise” symbols, i.e.,
for which Q(y|x) > 0.
Yt ∼ Q(·|⋆)
Given B ≥ 1 information bits to be transmitted,
a codebook C consists of
where ⋆ represents the “idle” symbol. For σ ≤ t ≤
M = 2B
σ+n−1
Yt ∼ Q(·|ct−σ+1 (m))
codewords of length n ≥ 1 composed of symbols
from X.
where ci (m) denotes the ith symbol of the codeword
A randomly and uniformly chosen message m cn (m).
is available at the transmitter at a random time ν,
Decoding involves three components:
independent of m, and uniformly distributed over
• a sampling strategy,
{1, . . . , AB }, where the integer
• a stopping (decoding) time defined on the sampled process,
A = 2βB
• a decoding function defined on the stopped
characterizes the asynchronism level between the
sampled process.
transmitter and the receiver, and where the constant A sampling strategy consists of “sampling times”
which are defined as an ordered collection of ranβ≥0
dom time indices
denotes the timing uncertainty per information bit.
S = {(S1 , . . . , Sℓ ) ⊆ {1, . . . , A+n−1} : Si < Sj , i < j}
While ν is unknown to the receiver, A is known by
both the transmitter and the receiver.
where Sj is interpreted as the jth sampling time.
We consider one-shot communication, i.e.,only The sampling strategy is either non-adaptive or
one message arrives over the period {1, 2, . . . , A} . adaptive. It is non-adaptive when the sampling times
If A = 1, the channel is said to be synchronous.
in S are independent of Y1A+n−1 . The strategy is
Given ν and m, the transmitter chooses a time adaptive when the sampling times are functions of
σ(ν, m) to start sending codeword cn (m) ∈ C past observations. This means that S1 is an arbitrary
assigned to message m. Transmission cannot start value in {1, . . . , A + n − 1}, possibly random but
before the message arrives or after the end of the independent of Y A+n−1 , and for j ≥ 2
1
uncertainty window, hence σ(ν, m) must satisfy
Sj = gj ({YSi }i<j )
ν ≤ σ(ν, m) ≤ A almost surely.
for some (possibly randomized) function
In the rest of the paper, we suppress the arguments
ν and m of σ when these arguments are clear from
gj : Yj−1 → {Sj−1 + 1, . . . , A + n − 1} .
context.
Given a sampling strategy, the receiver decodes
Before and after the codeword transmission,
i.e.,before time σ and after time σ + n − 1, the by means of a sequential test (τ, φτ ) where τ

4

denotes a stopping (decision) time with respect to Definition 2 (Cost of a code). The (maximum) cost
the sampled output process1
of a code C with respect to a cost function k : X →
[0, ∞] is defined as
Y S1 , Y S2 , . . .
n
X
def
and where φτ denotes a decoding function based on
k(ci (m)).
K(C) = max
m
the stopped sampled output process. Let
i=1
def

St = {Si ∈ S : Si ≤ t}.

(1)

denote the set of sampling times taken up to time t
and let
def

Ot = {YSi : Si ∈ St }

(2)

Definition 3 (Sampling frequency of a code). Given
ε > 0, the sampling frequency of a code C, denoted
by ρ(C, ε), is the relative number of channel outputs that are observed until a message is declared.
Specifically, it is defined as the minimum r ≥ 0
such that

denote the corresponding set of channel outputs.
The decoding function φτ is a map

min Pm (|Sτ |/τ ≤ r) ≥ 1 − ε .

φτ : Y|Oτ | → {1, 2, . . . , M}
Oτ 7→ φτ (Oτ ).

Definition 4 (Delay of a code). Given ε > 0, the
(maximum) delay of a code C, denoted by d(C, ε),
is defined as the minimum integer l such that

A code (C, (S, τ, φτ )) is defined as a codebook
and a decoder composed of a sampling strategy, a
decision time, and a decoding function. Throughout
the paper, whenever clear from context, we often
refer to a code using the codebook symbol C only,
leaving out an explicit reference to the decoder.
Note that a pair (S, τ ) allows only to do message
detection but does not provide a message estimate.
Such a restricted decoder will later (Section III) be
referred simply as a “detector.”

m

min Pm (τ − ν ≤ l − 1) ≥ 1 − ε .
m

We now define capacity per unit cost under the
constraint that the receiver has access to a limited
number of channel outputs:

Definition 5 (Asynchronous capacity per unit cost
under sampling constraint). Given β ≥ 0 and a
non-increasing sequence of numbers {ρB }, with
0 ≤ ρB ≤ 1, rate per unit cost R is said to
be achievable if there exists a sequence of codes
Definition 1 (Error probability). The maximum
{CB } and a sequence of positive numbers εB with
(over messages) decoding error probability of a code
B→∞
εB −→ 0 such that for all B large enough
C is defined as
1) CB operates at timing uncertainty per informax Pm (Em |C),
(3)
mation bit β;
m
2) the maximum error probability P(E|CB ) is at
where
most εB ;
A
X
3)
the rate per unit cost
def 1
Pm (Em |C) =
Pm,t (Em |C),
A t=1
B
K(CB )
where the subscripts “m, t” denote conditioning on
the event that message m arrives at time ν = t, and
where Em denotes the error event that the decoded
message does not correspond to m, i.e.,
def

Em = {φτ (Oτ ) 6= m} .

(4)

1
Recall that a (deterministic or randomized) stopping time τ
with respect to a sequence of random variables Y1 , Y2 , . . . is a
positive, integer-valued, random variable such that the event {τ = t},
conditioned on the realization of Y1 , Y2 , . . . , Yt , is independent of the
realization of Yt+1 , Yt+2 , . . . for all t ≥ 1.

is at least R − εB ;
4) the sampling frequency satisfies
ρ(CB , εB ) ≤ ρB ;
5) the delay satisfies2
1
log(d(CB , εB )) ≤ εB .
B
2
Throughout the paper logarithms are always intended to be to the
base 2.

5

Given β and {ρB }, the asynchronous capacity per where maxX denotes maximization with respect to
unit cost, denoted by C(β, {ρB }), is the supremum the channel input distribution PX , where (X, Y ) ∼
PX (·)Q(·|·), where Y⋆ denotes the random output
of achievable rates per unit cost.
of the channel when the idle symbol ⋆ is transTwo comments are in order. First note that sammitted (i.e.,Y⋆ ∼ Q(·|⋆)), where I(X; Y ) denotes
ples occurring after time τ play no role in our perthe mutual information between X and Y , and
formance metrics since error probability, delay, and
where
D(Y ||Y⋆) denotes the divergence between the
sampling rate are are all functions of Oτ (defined
distributions of Y and Y⋆ .
in (2)). Hence, without loss of generality, for the
rest of the paper we assume that the last sample
Theorem 1 characterizes capacity per unit cost
is taken at time τ , i.e.,that the sampled process is under full output sampling, and over codes whose
truncated at time τ . The truncated sampled process delay grow sub-exponentially with B. As it turns
is thus given by the collection of sampling times out, the full sampling capacity per unit cost can
Sτ (defined in (1)). In particular, we have (almost also be achieved with linear delay and sparse output
surely)
sampling.
Define3
S1 ⊆ S2 ⊆ · · · ⊆ Sτ = Sτ +1 = · · · = SAB +n−1 . (5)
B
The second comment concerns the delay con- n∗B (β, R) def
=
= Θ(B)
R max{E[k(X)] : X ∈ P(R)}
straint 4). The delay constraint is meant to capture
(7)
the fact that the receiver is able to locate νB with
high accuracy. More precisely, with high probabil- where P(R) is defined as the set
ity, τB should be at most sub-exponentially larger 



I(X; Y ) I(X; Y ) + D(Y ||Y⋆ )
than νB . This already represents a decent level of
≥R .
,
X : min
accuracy, given that νB itself is uniform over an
E[k(X)]
E[k(X)](1 + β)
(8)
exponentially large interval. However, allowing a
sub-exponential delay still seems like a very loose
∗
constraint. As Theorem 3 claims, however, we can The quantity nB (β, R) quantifies the minimum deachieve much greater accuracy. Specifically, if a tection delay as a function of the asynchronism level
sampling rate is achievable, it can be achieved with and rate per unit cost, under full sampling:
delay linear in B, and if a sampling rate cannot be Theorem 2 (Minimum delay, constant sampling
achieved with linear delay, it cannot be achieved rate, Theorem 3 [8]). Fix β ≥ 0, R ∈ (0, C(β)],
even if we allow a sub-exponential delay.
and ρ ∈ (0, 1]. For any codes {CB } that achieve
Notational conventions: We shall use dB and ρB rate per unit cost R at timing uncertainty β, and
instead of d(CB , εB ) and ρ(CB , εB ), respectively, operating at constant sampling rate 0 < ρB = ρ,
leaving out any explicit reference to CB and the we have
dB
sequence of non-negative numbers {εB }, which we
≥ 1.
lim inf ∗
B→∞ n (β, R)
assume satisfies εB → 0. Under full sampling,
B
i.e.,when ρB = 1 for all B, capacity is simply
denoted by C(β), and when the sampling rate is Furthermore, there exist codes {CB } that achieve
constant, i.e.,when ρB = ρ ≤ 1 for all B, capacity rate R with (a) timing uncertainty β, (b) sampling
rate ρB = ρ, and (c) delay
is denoted by C(β, ρ).
The main, previously known, results regarding cadB
lim sup ∗
≤ 1.
pacity for this asynchronous communication model
B→∞ nB (β, R)
are the following. First, capacity per unit cost under
Theorem 2 says that the minimum delay achieved
full sampling is given by the following theorem:
by rate R ∈ (0, C(β)] codes is n∗B (β, R) for any
Theorem 1 (Full sampling, Theorem 1 [1] ). For constant sampling rate ρ ∈ (0, 1]. This naturally
any β ≥ 0

 3
Throughout the paper we use the standard “big-O” Landau
I(X; Y ) I(X; Y ) + D(Y ||Y⋆)
C(β) = max min
,
notation to characterize growth rates (see, e.g., [4, Chapter 3]). These
X
E[k(X)]
E[k(X)](1 + β)
growth rates, e.g., Θ(B) or o(B), are intended in the limit B → ∞,
(6) unless stated otherwise.

6

suggests the question “What is the minimum sampling rate of codes that achieve rate R and minimum
delay n∗B (β, R)?” Our main result is the following
theorem, which states that the minimum sampling
rate essentially decreases as 1/B:
Theorem 3 (Minimum delay, minimum sampling
rate). Consider a sequence of codes {CB } that
operate under timing uncertainty per information
bit β > 0. If
ρB dB = o(1),

(9)

the receiver does not even sample a single component of the sent codeword with probability tending to one. Hence, the average error probability
tends to one whenever R > 0, dB = O(B), and
ρB = o(1/B).
Moreover, for any R ∈ (0, C(β)] and any sequence of sampling rates satisfying ρB = ω(1/B),
there exist codes {CB } that achieve rate R at (a)
timing uncertainty β, (b) sampling rate ρB , and (c)
delay
dB
lim sup ∗
≤ 1.
B→∞ nB (β, R)
If R > 0, the minimum delay n∗B (β, R) is O(B)
by Theorem 2 and (7), so Theorem 3 gives an
essentially tight characterization of the minimum
sampling rate; a necessary condition for achieving
the minimum delay is that ρB be at least Ω(1/B),
and any ρB = ω(1/B) is sufficient.
That sampling rates of order o(1/dB ) are not
achievable is certainly intuitively plausible and even
essentially trivial to prove when restricted to nonadaptive sampling. To see this note that by the
definition of delay, with high probability decoding
happens no later than instant ν + dB . Therefore,
without essential loss of generality, we may assume
that information is being transmitted only within
period {ν, ν + 1, . . . , ν + dB }. Hence, if sampling is
non-adaptive and its rate is of order o(1/dB ) then
with high probability (over ν) information transmission will occur during one unsampled period
of duration dB . This in turn implies a high error
probability. The main contribution in the converse
argument is that it also handles adaptive sampling.
Achievability rests on a new multi-phase procedure to efficiently detect the sent message. This
detector, whose performance is the focus of Section III, is a much more fine grained procedure than
the one used to establish Theorem 2. To establish

achievability of Theorem 2, a two-mode detector is
considered, consisting of a baseline mode operating
at low sampling rate, and a high rate mode. The
detector starts in the baseline mode and, if past
observed samples suggest the presence of a change
in distribution, the detector changes to the high rate
mode which acts as a confirmation phase. At the end
of the confirmation phase the detector either decides
to stop, or decides to reverse to the baseline mode
in case the change is unconfirmed.
The detector proposed in this paper (see Section III for the setup and Section IV-C for the
description of the procedure) has multiple confirmation phases, each operating at a higher sampling
rate than the previous phase. Whenever a confirmation phase is passed, the detector switches to
the next confirmation phase. As soon as a change
is unconfirmed, the procedure is aborted and the
detector returns to the low rate baseline mode. The
detector only stops if the change is confirmed by all
confirmation phases. Having multiple confirmation
phases instead of just one, as for Theorem 2, is key
to reducing the rate from a constant to essentially
1/B, as it allows us to aggressively reject falsealarms whithout impacting the ability to detect the
message.
III. S AMPLING

CONSTRAINED TRANSIENT
CHANGE - DETECTION

This section focuses on one key aspect of asynchronous communication, namely, that we need to
quickly detect the presence of a message with a
sampling constrained detector. As there is only one
possible message, the problem amounts to a pure
(transient) change-point detection problem. Related
results are stated in Theorems 4 and 5. These results
and their proofs are the key ingredients for proving
Theorem 3.
A. Model
The transient change-detection setup we consider
in this section is essentially a simpler version of
the asynchronous communication problem stated
in Section II. Specifically, rather than having a
codebook of 2B messages, we consider a binary
hypothesis testing version of the problem. There
is a single codeword, so no information is being
conveyed, and our goal is simply to detect when
the codeword was transmitted.

7

the tail event where τ is much larger than ν, say
because we missed the transient change completely.
We are able to characterize optimal performance
tightly with the above definition, but expected delay
would also be of interest, and an analysis of the
y
optimal performance under this metric is an open
There is no parameter B in our problem, but in problem for future research.
analogy with Section II, let n denote the length of
Definition 8 (Sampling rate). For a given detector
the transient change. Let ν be uniformly distributed
(S, τ ) and ε > 0, the sampling rate, denoted by
over
ρ((S, τ ), ε), is defined as the minimum r ≥ 0 such
{1, 2, . . . , A = 2αn }.
that
P(|Sτ |/τ ≤ r) ≥ 1 − ε.
where the integer A denotes the uncertainty level
and where α the corresponding uncertainty expoAchievable sampling rates are defined analonent, respectively.
gously to Section II, but we include a formal defiGiven P0 and P1 , process {Yt } is defined simi- nition for completeness.
larly as in Section II. Conditioned on the value of
Definition 9 (Achievable sampling rate). Fix α ≥ 0,
ν, the Yt ’s are i.i.d. according to P0 for
and fix a sequence of non-increasing values {ρn }
1≤t<ν
with 0 ≤ ρn ≤ 1. Sampling rates {ρn } are said
to be achievable at uncertainty exponent α if there
or
exists a sequence of detectors {(Sn , τn )} such that
νn + n ≤ t ≤ A + n − 1
for all n large enough
and i.i.d. according to P1 for ν ≤ t ≤ ν + n −
1) (Sn , τn ) operates under uncertainty level An =
1. Process {Yt } is thus i.i.d. P0 except for a brief
2αn ,
period of duration n where it is i.i.d. P1 .
2) the false-alarm probability P(τn < νn ) is at
Sampling strategies are defined as in Section II,
most εn ,
but since we now only have a single message, we
3) the sampling rate satisfies ρ((Sn , τn ), εn ) ≤
formally define the relevant performance metrics
ρn ,
below.
4) the delay satisfies
Definition 6 (False-alarm probability). For a given
1
log(d((Sn , τn ), εn )) ≤ εn
detector (S, τ ) the probability of false-alarm is den
fined as
for some sequence of non-negative numbers {εn }
P(τ < ν) = P0 (τ < ν)
n→∞
such that εn −→ 0.
where P0 denotes the joint distribution over τ and
Notational conventions: We shall use dn and ρn
ν when the observations are drawn from the P0 instead of d((Sn , τn ), εn ) and ρ((Sn , τn ), εn ), reproduct distribution. In other words, the false-alarm
spectively, leaving out any explicit reference to the
probability is the probability that the detector stops
detectors and the sequence of non-negative numbers
before the transient change has started.
{εn }, which we assume satisfies εn → 0.
Definition 7 (Detection delay). For a given detector
(S, τ ) and ε > 0, the delay, denoted by d((S, τ ), ε), B. Results
is defined as the minimum l ≥ 0 such that
Define
nα
P(τ − ν ≤ l − 1) ≥ 1 − ε .
def
= Θ(n).
(10)
n∗ (α) =
D(P1 ||P0 )
Remark: The reader might wonder why we chose
the above definition of delay, as opposed to, for Theorem 4 (Detection, full sampling). Under full
example, measuring delay by E[max(0, τ − ν)]. sampling (ρn = 1):
The above definition corresponds to capturing the
1) the supremum of the set of achievable uncer“typical” delay, without incurring a large penalty in
tainty exponents is D(P1 ||P0);
Proceeding more formally, let P0 and P1 be
distributions defined over some finite alphabet Y and
with finite divergence
X
def
D(P1 ||P0) =
P1 (y) log[P1 (y)/P0(y)].

8

IV. P ROOFS
2) any detector that achieves uncertainty exponent α ∈ (0, D(P1 ||P0 )) has a delay that
Typicality convention
satisfies
A length q ≥ 1 sequence v q over Vq is said to be
dn
lim inf ∗
≥ 1;
typical with respect to some distribution P over V
n→∞ n (α)
if5
3) any uncertainty exponent α ∈ (0, D(P1 ||P0))
||P̂vq − P || ≤ q −1/3
is achievable with delay satisfying
where P̂vq denotes the empirical distribution (or
dn
type) of v q .
lim sup ∗
≤ 1.
n→∞ n (α)
Typical sets have large probability. Quantitatively,
Hence, the shortest detectable4 change is of size a simple consequence of Chebyshev’s inequality is
that
log An
(1 ± o(1))
(11) P q (||P̂V q − P || ≤ q −1/3 ) = 1 − O q −1/3  (q → ∞)
nmin (An ) =
D(P1 ||P0 )
(12)
by Claim 1) of Theorem 4, assuming An ≫ 1. In
q
this regime, change duration and minimum detec- where P denotes the q-fold product distribution of
tion delay are essentially the same by Claims 2)-3) P . Also, for any distribution P̃ over V we have
and (10), i.e.,
P q (||P̂V q − P̃ || ≤ q −1/3 ) ≤ 2−q(D(P̃ ||P )−o(1)) . (13)
n∗ (α = (log An )/nmin (An )) = nmin (An )(1 ± o(1))
whereas in general minimum detection delay could
be smaller than change duration.
The next theorem says that the minimum sampling rate needed to achieve the same detection
delay as under full sampling decreases essentially
as 1/n. Moreover, any detector that tries to operate
below this sampling limit will have a huge delay.

About rounding
Throughout computations, we ignore issues related to the rounding of non-integer quantities, as
they play no role asymptotically.
A. Proof of Theorem 4

The proof of Theorem 4 is essentially a Corollary
of [2, Theorem]. We sketch the main arguments.
1) : To establish achievability of D(P1 ||P0) one
uses the same sequential typicality detection proρn = ω(1/n)
cedure as in the achievability of [2, Theorem]. For
is achievable with delay satisfying
the converse argument, we use similar arguments
as for the converse of [2, Theorem]. For this latter
dn
setting, achieving α means that we can drive the
≤ 1.
lim sup ∗
n→∞ n (α)
probability of the event {τn 6= νn + n − 1} to
zero. Although this performance metric differs from
Conversely, if
ours—vanishing probability of false-alarm and subρn = o(1/n)
exponential delay—a closer look at the converse
the detector samples only from distribution P0 (i.e.,it argument of [2, Theorem] reveals that if α >
completely misses the change) with probability tend- D(P1 ||P0) there are exponentially many sequences
ing to one. This implies that the delay is Θ(An = of length n that are “typical” with respect to the
2αn ) whenever the probability of false-alarm tends posterior distribution. This, in turn, implies that
either the probability of false-alarm is bounded
to zero.
away from zero, or the delay is exponential.
Theorem 5 (Detection, sparse sampling). Fix α ∈
(0, D(P1||P0 )). Any sampling rate

4
By detectable we mean with vanishing false-alarm probability and
subexponential delay.

5

|| · || refers to the L1 -norm.

9

2) : Consider stopping times {τn } that achieve
delay {dn }, and vanishing false-alarm probability
(recall the notational conventions for dn at the end
of Section III-A). We define the “effective process”
{Ỹi } as the process whose change has duration
min{dn , n} (instead of n).
Effective output process: The effective process {Ỹi }
is defined as follows. Random variable Ỹi is equal
to Yi for any index i such that
1 ≤ i ≤ νn + min{dn , n} − 1
and
{Ỹi : νn + min{dn , n} ≤ i ≤ An + n − 1}
is an i.i.d. P0 process independent of {Yi }. Hence,
the effective process differs from the true process
over the period {1, 2, . . . , τn } only when {τn ≥ νn +
dn } with dn < n.
Genie aided statistician: A genie aided statistician
observes the entire effective process (of duration
An +n−1) and is informed that the change occurred
over one of


def An + n − 1 − (νn mod dn )
rn =
(14)
dn

B. Proof of Theorem 5: Converse
As alluded to earlier (see discussion after Theorem 3), it is essentially trivial to prove that sampling
rates of order o(1/n) are not achievable when we
restrict to non-adaptive sampling, that is when all
sampling times are independent of {Yt }. The main
contribution of the converse, and the reason why it
is somewhat convoluted, is that it handles adaptive
sampling as well.
Consider a sequence of detectors {(Sn , τn )} that
achieves, for some false-alarm probability εn → 0,
sampling rate {ρn } and communication delay dn
(recall the notational conventions for dn and ρn at
the end of Section III-A).
We show first that if
ρn = o(1/n)

(15)

then any detector, irrespective of delay, will take
only P0 -generated samples with probability asymptotically tending to one. This, in turn, will imply
that the delay is exponential, since by assumption
the false-alarm probability vanishes.
In the sequel, we use P(·) to denote the (unconditional) joint distribution of the output process
Y1 , Y2 , . . . and ν, and we use P0 (·) to denote the
consecutive (disjoint) blocks of duration dn . The
distribution of the output process Y1 , Y2 , . . . , YA+n−1
genie aided statistician produces a time interval of
when no change occurs, that is a P0 -product distrisize dn which corresponds to an estimate of the
bution.
change in distribution and is declared to be correct
By definition of achievable sampling rates {ρn }
only if this interval corresponds to the change in
we have
distribution.
Observe that since τn achieves false-alarm proba1 − o(1) ≤ P(|Sτn | ≤ τn ρn ).
(16)
bility εn and delay dn on the true process {Yi }, the
genie aided statistician achieves error probability at The following lemma, proved thereafter, says if
most 2εn . The extra εn comes from the fact τn stops (15) holds then with probability tending to one the
after time νn + dn − 1 (on {Yi }) with probability at detector samples only P0 -distributed samples with
most εn . Therefore, with probability at most εn the probability tending to one:
genie aided statistician observes a process that may Lemma 1. For any α > 0, if ρn = o(1/n) then
differ from the true process.
P({νn , νn + 1, . . . , νn + n − 1} ∩ Sτn = ∅)
By using the same arguments as for the converse
of [2, Theorem], but on the process {Ỹi } parsed into
≥ 1 − o(1). (17)
consecutive slots of size dn , we can conclude that
This, as we now show, implies that the delay is
if
dn
exponential.
lim inf ∗
<1
n→∞ n (α)
On the one hand, since the probability of falsethen the error probability of the genie aided decoder alarm vanishes, we have
tends to one.
3) : To establish achievability apply the same
sequential typicality test as in the achievability part
of [2, Theorem].


o(1) ≥ P(τn < νn )
≥ P(τn < An /2|νn ≥ An /2)/2
= P0 (τn < An /2)/2.

10

for any k ∈ {1, 2, . . . , An }, where we defined the
set of indices

This implies
P0 (τn < An /2) ≤ o(1),

def

Js = {j : {j, j + 1, . . . , j + n − 1} ∩ s = ∅}}.

and, therefore,
P(τn ≥ An /2) ≥ P(τn ≥ An /2|νn > An /2)/2
= P0 (τn ≥ An /2)/2
= 1/2 − o(1).
(18)

The first equality in (20) holds by the definition
of St (see (1)) and by (5). The third equality
holds because event {Sν+n−1 = s} involves random
variables whose indices are not in Js . Hence samples
in s are all distributed according to the nominal
distribution P0 (P0 -product distribution). The last
inequality holds by the property

Now, define events
def
A1 = {τn ≥ An /2},
def
|Sa+b | ≤ |Sa | + b
A2 = {|Sτn | ≤ τn ρn },
def
A3 = {{νn , νn + 1, . . . , νn + n − 1} ∩ Sτn = ∅}, which follows from the definition of St .
def
Since τn ≤ An + n − 1 from (16) we get
and let A = A1 ∩ A2 ∩ A3 .
From (16), (17), and (18), we get
1 − o(1) ≤ P(|Sτn | ≤ (An + n − 1)ρn )
P(A) = 1/2 − o(1).
(19)
≤ P(|Sνn −1 | ≤ (An + n − 1)ρn )

(21)

(22)

We now argue that when event A happens, the de- where the second inequality holds by (5).
Now,
tector misses the change which might have occurred,
say, before time An /4, thereby implying a delay P(|Sνn−1 | ≤ (A + n − 1)ρ )
n
n
Θ(An ) since τn ≥ An /2 on A.
A
n
X
When event A happens, the detector takes
P(|St−1 | ≤ (An + n − 1)ρn , νn = t)
=
o(An /n) samples (this follows from event A2 since
t=1
by assumption ρn = o(1/n)). Therefore, within
An
X
{1, 2, . . . , An /4} there are at least An /4 − o(An ))
P0 (|St−1 | ≤ (An + n − 1)ρn )P(νn = t)
=
time intervals of length n that are unsampled. Each
t=1
of these corresponds to a possible change. ThereAnX
+n−1
fore, conditioned on event A, with probability at
≤
P0 (|St−1 | ≤ (An + n − 1)ρn )P(νn = t)
least 1/4 − o(1) the change happens before time
t=n
An /4, whereas τn ≥ An /2. Hence the delay is
n−1
X
Θ(An ), since the probability of A is asymptotically
+
P(νn = t)
bounded away from zero by (19).

t=1
Proof of Lemma 1: We have
≤ P0 (|Sνn +n−1 | ≤ (An + n − 1)ρn )
+ n/An
P({νn , νn + 1, . . . , νn + n − 1} ∩ Sτn = ∅)
νn +n−1
| ≤ (An + n − 1)ρn )
= P({{νn , νn + 1, . . . , νn + n − 1} ∩ Sνn +n−1 = ∅}) ≤ P0 (|S
+ o(1)
(23)
≥ P({{ν , ν + 1, . . . , ν + n − 1} ∩ Sν+n−1 = ∅}
n

n

n
νn +n−1

∩ {|S
=

X X

where the last equality holds since An = 2αn .
From (23) and (22) we have

| ≤ k})

P(Sνn +n−1 = s, νn = j)

1 − o(1) ≤ P0 (|Sνn +n−1 | ≤ (An + n − 1)ρn ).
(24)

s:|s|≤k j∈Js

=

X X

P0 (Sνn +n−1 = s)P(νn = j)

Letting

s:|s|≤k j∈Js

An − k · n X
≥
P0 (Sνn +n−1 = s)
An

def

s:|s|≤k

An − k · n
=
P0 (|Sνn+n−1 | ≤ k)
An

def

k = kn = (An + n − 1)ρn ,
and assuming that ρn = o(1/n) we get
(20)

kn · n = o(An )

(25)

11

and hence from (20) and (24)
P({νn , νn + 1, . . . , νn + n − 1} ∩ Sτn = ∅)
≥ 1 − o(1)
which concludes the proof.
C. Proof of Theorem 5: Achievability
We describe a detection procedure that asymptotically achieves minimum delay n∗ (α) and any
sampling rate that is ω(1/n) whenever α ∈
(0, D(P0||P1 )).
Fix α ∈ (0, D(P1||P0 )) and pick ε > 0 small
enough so that

typical with respect to P1 . If the test is negative,
skip samples until the next s-instant and repeat
Phase zero (that is, test ∆0 (n) samples). If the
test is positive, perform a second confirmation
phase with ∆1 (n) replaced with ∆2 (n), and
so forth. Note that each confirmation phase is
performed on a new set of samples. If ℓ − 1
consecutive confirmation phases (with respect
to the same s-instant) are positive, the receiver
moves to the full block sampling phase.
3 Full block sampling (ℓ-th phase): Take
another
∆ℓ (n) = n∗ (α)(1 + ε)

samples and check if they are typical with respect to P1 . If they are typical, stop. Otherwise,
Suppose we want to achieve some sampling rate
skip samples until the next s-instant and repeat
ρn = f (n)/n where f (n) = ω(1) is some arPhase zero. If by time An + n − 1 no sequence
bitrary increasing function (upper bounded by n
is found to be typical, stop.
without loss of generality). For concreteness, it Note that with our f (n) = log log log log(n) exmight be helpful for the reader to take f (n) = ample, we have two preamble confirmation phases
log log log log(n). Define
followed by the last full block sampling phase.
def
1/3
For the probability of false-alarm we have
¯
∆(n)
= n/f (n)
n∗ (α)(1 + 2ε) ≤ n.

(26)

def

¯
s-instants = {t = j ∆(n),
j ∈ N∗ },
and recursively define
def

∆0 (n) = f (n)
def

∆i (n) = min{2

c∆i−1 (n)

P(τn < νn ) ≤ 2αn · 2−n

∗ (α)(1+ε)(D(P

1 ||P0 )−o(1))

= 2−nαΘ(ε)
= o(1)

(27)

1/3

because whenever the detector stops, the previous
∗

, n (α)(1 + ε)}

for i ∈ 1, 2, . . . , ℓ where ℓ denotes the smallest
integer such that ∆ℓ (n) = n∗ (α)(1 + ε). The
constant c in the definition of ∆i (n) can be any
fixed value such that
0 < c < D(P1 ||P0 ).
The detector starts sampling in phases at the first
¯
s-instant (i.e.,, at time t = ∆(n))
as follows:
1 Preamble detection (phase zero): Take ∆0 (n)
consecutive samples and check if they are
typical with respect to P1 . If the test is negative,
meaning that ∆0 (n) samples are not typical,
skip samples until the next s-instant and repeat the procedure i.e.,sample and test ∆0 (n)
observations. If the test is positive, proceed to
confirmation phases.
2 Preamble confirmations (variable duration,
ℓ − 1 phases at most): Take another ∆1 (n)
consecutive samples and check if they are

n∗ (α)(1 + ε)
samples are necessarily typical with respect to P1 .
Therefore, the inequality (27) follows from (13) and
a union bound over time indices. The equality in
(27) follows directly from the definition of n∗ (α)
(see (10)).
Next, we analyze the delay of the proposed
scheme. We show that
P(τn ≤ νn + (1 + 2ε)n∗ (α)) = 1 − o(1).

(28)

¯
To see this, note that by the definition of ∆(n)
and
because each ∆i (n) is exponentially larger than the
previous ∆i−1 (n),
¯
∆(n)
+

ℓ
X

∆i (n) ≤ (1 + 2ε)n∗ (α)

i=0

for n large enough. Applying (12) and taking a
union bound, we see that when the samples are
distributed according to P1 , the series of ℓ + 1

12

hypothesis tests will all be positive with probability Therefore, the expected number of samples taken
by the detector up to any given time t can be upper
1 − o(1). Specifically,
bounded
as
ℓ
X
1
t
P(any test fails) ≤
O (∆i (n))− 3 = o(1). (29)
E0 |St | ≤ ¯
∆0 (n)(1 + o(1))
∆(n)
i=0
f (n)2/3
Since ε can be made arbitrarily small, from (27) and
=t
(1 + o(1)).
(33)
n
(28) we deduce that the detector achieves minimum
delay (see Theorem 4, Claim 2)) .
This, as we now show, implies that the detector has
Finally, to show that the above detection proce- the desired sampling rate. We have
dure achieves sampling rate
P(|Sτn |/τn ≥ ρn )
ρn = f (n)/n
≤ P(|Sτn |/τn ≥ ρn , νn ≤ τn ≤ νn + (1 + 2ε)n∗ (α))
+ 1 − P(νn ≤ τn ≤ νn + (1 + 2ε)n∗ (α))
we need to establish that
n→∞
≤ P(|Sτn |/τn ≥ ρn , νn ≤ τn ≤ νn + n)
P(|Sτn |/τn ≥ ρn ) −→ 0.
(30)
+ 1 − P(νn ≤ τn ≤ νn + (1 + 2ε)n∗ (α))
(34)
To prove this, we first compute the sampling rate of
the detector when run over an i.i.d.-P0 sequence, where the second inequality holds for ε small
∗
that is, a sequence with no transient change. As enough by the definition of n (α).
The fact that
should be intuitively clear, this will essentially give
us the desired result, since in the true model, the
1 − P(νn ≤ τn < νn + (1 + 2ε)n∗ (α)) = o(1)
duration of the transient change, n, is negligible
(35)
with respect to An anyway.
To get a handle on the sampling rate of the detec- follows from (27) and (28). For the first term on the
tor over an i.i.d.-P0 sequence, we start by computing right-hand side of the second inequality in (34), we
the expected number of samples N taken by the have
detector at any given s-instant, when the detector is
P(|Sτn |/τn ≥ ρn , νn ≤ τn ≤ νn + n)
started at that specific s-instant and the observations
≤ P(|Sνn+n | ≥ νn ρn )
are all i.i.d. P0 . Clearly, this expectation does not
≤ P(|Sνn−1 | ≥ νn ρn − n − 1).
(36)
depend on the s-instant.6 We have
E0 N ≤ ∆0 (n) +

ℓ−1
X
i=0

pi · ∆i+1 (n)

(31)

Since Sνn −1 represents sampling times before the
transient change, the underlying process is i.i.d. P0 ,
so we can use our previous bound on the sampling
rate to analyze Sνn −1 . Conditioned on reasonably
large values of νn , in particular, all νn satisfying
p
νn ≥ An = 2αn
(37)

where pi denotes the probability that the i-th confirmation phase is positive given that the detector
actually reaches the i-th confirmation phase, and
E0 denotes expectation with respect to an i.i.d.-P0
sequence. Since each phase uses new, and therefore, we have
independent, observations, from (13) we conclude
E0 |Sνn |
P(|Sνn −1 | ≥ νn ρn − n − 1|νn ) ≤
that
νn ρn − n − 1
pi ≤ 2−∆i (n)(D(P1 ||P0 )−o(1)) .
2/3
f (n) (1 + o(1))
≤
Using the definition of ∆i (n), and recalling that 0 <
n(ρn − (n + 1)/νn )
c < D(P1 ||P0 ), this implies that the sum in the
f (n)2/3 (1 + o(1))
≤
second term of (31) is negligible, and
nρn (1 − o(1))
(1 + o(1))
E0 Ns = ∆0 (n)(1 + o(1)).
(32)
=
f (n)1/3 (1 − o(1))
6
Boundary effects due to the fact that An need not be a multiple
= o(1)
(38)
¯ n play no role asymptotically and thus are ignored.
of ∆

13

where the second inequality holds by (33); where
the third inequality holds by (37) and because ρn =
ω(1/n); and where the last two equalities hold by
the definitions of ρn and f (n).
Removing the conditioning on νn ,
P(|Sνn−1 | ≥ νn ρn − n − 1)
≤ P(|Sνn−1 | ≥ νn ρn − n − 1, νn ≥
p
+ P(νn < An )
= o(1)

p
An )
(39)

by (38) and the fact that νn is uniformly distributed
over {1, 2, . . . , An }. Hence, from (36), the first term
on the right-hand side of the second inequality in
(34) vanishes.
This yields (30).
D. Discussion
There is obviously a lot of flexibility around
the quickest detection procedure described in Section IV-C. Its main feature is the sequence of
binary hypothesis tests, which manages to reject
the hypothesis that a change occurred with as few
samples as possible when the samples are drawn
from P0 , while maintaining a high probability of
detecting the transient change.
It may be tempting to simplify the detection
procedure by considering, say, only two phases,
a preamble phase and the full block phase. Such
a scheme, which is similar in spirit to the one
proposed in [8], would not work, as it would produce either a much higher level of false-alarm, or a
much higher sampling rate. We provide an intuitive
justification for this below, thereby highlighting the
role of the multiphase procedure.
Consider a two phase procedure, a preamble
phase followed by a full block phase. Each time
we switch to the second phase, we take Θ(n)
samples. Therefore, if we want to achieve a vanishing sampling rate, then necessarily the probability
of switching from the preamble phase to the full
block phase under P0 should be o(1/n). By Sanov’s
theorem, such a probability can be achieved only
if the preamble phase makes it decision to switch
to the full block phase based on at least ω(log n)
samples, taken over time windows of size Θ(n).
This translates into a sampling rate of ω((log n)/n)
at best, and we know that this is suboptimal, since
any sampling rate ω(1/n) is achievable.

The reason a two-phase scheme does not yield a
sampling rate lower than ω((log n)/n) is that it is
too coarse. To guarantee a vanishing sampling rate,
the decision to switch to the full block phase should
be based on at least log(n) samples, which in turn
yields a suboptimal sampling rate. The important
observation is that the (average) sampling rate of
the two-phase procedure essentially corresponds to
the sampling rate of the first phase, but the first
phase also controls the decision to switch to the
full block phase and sample continuously for a long
period of order n. In the multiphase procedure,
however, we can separate these two functions. The
first phase controls the sampling rate, but passing
the first phase only leads us to a second phase, a
much less costly decision than immediately switching to full block sampling. By allowing multiple
phases, we can ensure that when the decision to
ultimately switch to full sampling occurs, it only
occurs because we have accumulated a significant
amount of evidence that we are in the middle of the
transient change. In particular, note that many other
choices would work for the length and probability
thresholds used in each phase of our sampling
scheme. The main property we rely on is that the
lengths and probability thresholds be chosen so that
the sampling rate is dominated by the first phase.
E. Proof of Theorem 3
In this section, we prove Theorem 3. A reader
familiar with the proofs presented in [8] will recognize Theorem 3 as a corollary of Theorem 5, but we
include a detailed proof below for interested readers
unfamiliar with the prior work [8].
1) Converse of Theorem 3: By using the same
arguments as for Lemma 1, and simply replacing
replacing n with dB , one readily sees that if
ρB dB = o(1)

(40)

then
P({νB ,νB + 1, . . . , νB + dB − 1} ∩ SτB = ∅)
≥ (1 − o(1)).
(41)
Since the decoder samples no codeword symbol
with probability approaching one, the decoding error probability will tend to one whenever the rate is
positive (so that (M − 1)/M tends to one).

14

2) Achievability of Theorem 3: Fix β > 0.
We show that any R ∈ (0, C(β)] is achievable
with codes {CB } whose delays satisfy d(CB , εB ) ≤
n∗B (β, R)(1 + o(1)) whenever the sampling rate ρB
is such that
f (B)
ρB =
B
for some f (B) = ω(1).
Let X ∼ P be some channel input and let
Y denote the corresponding output, i.e.,(X, Y ) ∼
P (·)Q(·|·). For the moment we only assume that X
is such that I(X; Y ) > 0. Further, we suppose that
the codeword length n is linearly related to B, i.e.,
B
=q
n

¯

according to P until when xn−∆(n) is typical with
respect to P . In this case we let
def

¯

cn∆(n)+1
(1) = xn−∆(n) ,
¯
move to message 2, and repeat the procedure until
when a codeword has been assigned to each message.
From (12), for any fixed m no repetition will
be required to generate cn∆(n)+1
(m) with probability
¯
tending to one as n → ∞. Moreover, by construction the codewords are essentially of constant
composition, i.e.,each symbol appears roughly the
same number of times in all codewords, and all
codewords have cost

nE[k(X)](1 + o(1))
for some fixed constant q > 0. We shall specify this
linear dependency later to accommodate the desired as n → ∞.
Codeword transmission time. Define the set of
rate R. Further, let
start instants
def
f˜(n) = f (q · n)/q
def
¯
s-instants = {t = j ∆(n),
j ∈ N∗ }.
and
˜
Codeword transmission start time σ(m, νn ) corredef f (n)
.
ρ̃n =
sponds to the first s-instant ≥ νn (regardless of m).
n
Sampling and decoding procedures. The deHence, by definition we have
coder first tries to detect the preamble by using a
similar detection procedure as in the achievability
ρ̃n = ρB .
of Theorem 5, then applies a standard message
Let a be some arbitrary fixed input symbol such decoding isolation map.
that
Starting at the first s-instant (i.e.,at time t =
¯
∆(n)),
the decoder samples in phases as follows.
Q(·|a) 6= Q(·|⋆).
1 Preamble test (phase zero): Take ∆0 (n) con¯
Below we introduce the quantities ∆(n)
and ∆i (n),
secutive samples and check if they are typical
1 ≤ i ≤ ℓ, which are defined as in Section IV-C
with respect to Q(·|a). If the test turns negative,
but with P0 replaced with Q(·|⋆), P1 replaced with
the decoder skips samples until the next sQ(·|a), f (n) replaced with f˜(n), and n∗ (α) replaced
instant when it repeats the procedure. If the
with n.
test turns positive, the decoder moves to the
Codewords: preamble followed by constant
confirmation phases.
composition information symbols. Each codeword
2
Preamble confirmations (variable duration,
cn (m) starts with a common preamble that consists
ℓ − 1 phases at most): The decoder takes
¯
of ∆(n)
repetitions of symbol a. The remaining
another ∆1 (n) consecutive samples and checks
if they are typical with respect to Q(·|a). If
¯
n − ∆(n)
the test turns negative the decoder skips samples until the next s-instant when it repeats
components
n
Phase
zero (and tests ∆0 (n) samples). If the
c∆(n)+1
(m)
¯
test turns positive, the decoder performs a
second confirmation phase based on new ∆2 (n)
of cn (m) of each message m carry information and
samples, and so forth. If ℓ − 1 consecutive
are generated as follows. For message 1, randomly
¯
¯
confirmation phases (with respect to the same
generate length n − ∆(n)
sequences xn−∆(n) i.i.d.

15

s-instant) turn positive, the decoder moves to
the message sampling phase.
3 Message sampling and isolation (ℓ-th phase):
Take another n samples and check if among
¯
these samples there are n − ∆(n)
consecutive samples that are jointly typical with the
¯
n − ∆(n)
information symbols of one of the
codewords. If one codeword is typical, stop
and declare the corresponding message. If more
than one codeword is typical declare one message at random. If no codeword is typical, the
decoder stops sampling until the next s-instant
and repeats Phase zero. If by time AB + n − 1
no codeword is found to be typical, the decoder
declares a random message.
Error probability. Error probability and delay
are evaluated in the limit B → ∞ with AB = 2βB
and with


B
I(X; Y ) + D(Y ||Y⋆)
q=
.
< min I(X; Y ),
n
1+β
(42)

as n → ∞.
Using analogous arguments as in the achievability
of [1, Proof of Theorem 1], we obtain the upper
bounds
Pm (E1,m′ ) ≤ 2βB · 2−n(I(X;Y )+D(Y ||Y⋆ )−o(1))
and
Pm (E2,m′ ) ≤ 2−n(I(X;Y )−o(1))
which are both valid for any fixed ε > 0 provided
that B is large enough. Hence from the union bound
Pm (E1,m′ ∪ E2,m′ ) ≤2−n(I(X;Y )−o(1))
+ 2βB · 2−n(I(X;Y )+D(Y ||Y⋆ )−o(1)) .
Taking a second union bound over all possible
wrong messages, we get

B
′
′
′
Pm (∪m 6=m (E1,m ∪ E2,m )) ≤ 2 2−n(I(X;Y )−o(1))

+2βB · 2−n(I(X;Y )+D(Y ||Y⋆ )−o(1))
def

= ε2 (B)
(46)
We first compute the error probability averaged
over codebooks and messages. Suppose message m where ε2 (B) = o(1) because of (42).
Combining (43), (44), (46), we get from the union
is transmitted and denote by Em the error event that
′
the decoder stops and outputs a message m 6= m. bound
Then we have
Pm (Em ) ≤ ε1 (B) + ε2 (B)
(43)
Em ⊆ E0,m ∪m′ 6=m (E1,m′ ∪ E2,m′ ),
= o(1)
(47)
where events E0,m , E1,m′ , and E2,m′ are defined as for any m.
• E0,m : at the s-instant corresponding to σ, the
Delay. We now show that the delay of our coding
preamble test phase or one of the pream- scheme is at most n(1 + o(1)). Suppose codeword
ble confirmation phases turns negative, or cn (m) is sent. If
cn∆(n)+1
(m) is not found to be typical by time
¯
τB > σ + n
σ + n − 1;
• E1,m′ : the decoder stops at a time t < σ and
then necessarily cn∆+1
(m) is not typical with the
¯
declares m′ ;
corresponding channel outputs. Hence
• E2,m′ : the decoder stops at a time t between σ
and σ + n − 1 (including σ and σ + n − 1) and
Pm (τB − σ ≤ n) ≥ 1 − Pm (E0,m )
declares m′ .
= 1 − ε1 (B)
(48)
From Sanov’s theorem,
¯
¯
by (44). Since σ ≤ νB + ∆(n)
and ∆(n)
= o(n) we
Pm (E0,m ) = ε1 (B)
(44)
7
get
where ε1 (B) = o(1). Note that this equality holds
Pm (τB − νB ≤ n(1 + o(1))) ≥ 1 − ε1 (B) .
pointwise (and not only on average over codebooks)
for any specific (non-random) codeword cn (m) Since this inequality holds for any codeword cn (m)
since, by construction, they all satisfy the constant that satisfies (45), the delay is no more than n(1 +
composition property
o(1)). Furthermore, from (47) there exists a specific
−1/3
¯
||P̂cn (m) − P || ≤ (n − ∆)
= o(1)
(45)
7
¯
∆+1

Recall that B/n is kept fixed and B → ∞.

16

non-random code C whose error probability, averaged over messages, is less than ε1 (n) + ε2 (n) =
o(1) whenever condition (42) is satisfied. Removing
the half of the codewords with the highest error
probability, we end up with a set C′ of 2B−1 codewords whose maximum error probability satisfies
max Pm (Em ) ≤ o(1)
m

(49)

whenever condition (42) is satisfied.
Since any codeword has cost nE[k(X)](1+o(1)),
condition (42) is equivalent to

I(X; Y )
R < min
,
E[k(X)](1 + o(1))

I(X; Y ) + D(Y ||Y⋆ )
(50)
E[k(X)](1 + o(1))(1 + β)
where
def

R=

B
K(C′ )

denotes the rate per unit cost of C′ .
Thus, to achieve a given R ∈ (0, C(β)) it suffices
to choose the input distribution and the codeword
length as
X = arg max{E[k(X ′ )] : X ′ ∈ P(R)}
and
n = n∗B (β, R)
(see (7) and (8)). By a previous argument the corresponding delay is no larger than n∗B (β, R)(1+o(1)).
Sampling rate. For the sampling rate, a very
similar analysis to the achievability proof of Theorem 5 (see from equation (30) onwards with f (n),
ρn , n∗ (α), and An replaced with f˜(n), ρ̃n , n∗ (β, R),
and AB , respectively) shows that
B→∞

Pm (|SτB |/τB ≥ ρB ) −→ 0.

(51)

Note that the arguments that establish (51) rely
only on the preamble detection procedure. In particular, they do not use (50) and hold for any codeword
length nB as long as nB = Θ(B).
V. C ONCLUSION
We have proved an essentially tight characterization of the sampling rate required to have no
capacity or delay penalty for the asynchronous
communication model of [8]. The key ingredient in
our results is a new, multi-phase, adaptive sampling
scheme used to detect when the received signal’s

distribution switches from the pure noise distribution to the codeword distribution. As noted above,
there is a lot of flexibility around the quickest
detection procedure described in Section IV-C, but
a simple, two level generalization of the sampling
algorithm from [8] is insufficient to achieve the
optimal sampling rate. Instead, a fine-grained, multilevel scheme is needed.
R EFERENCES
[1] V. Chandar, A. Tchamkerten, and D. Tse. Asynchronous
capacity per unit cost. Information Theory, IEEE Transactions
on, 59(3):1213 –1226, march 2013.
[2] V. Chandar, A. Tchamkerten, and G. Wornell. Optimal sequential frame synchronization. Information Theory, IEEE
Transactions on, 54(8):3725–3728, 2008.
[3] Venkat Chandar, Aslan Tchamkerten, and David Tse. Asynchronous capacity per unit cost. Information Theory, IEEE
Transactions on, 59(3):1213–1226, 2013.
[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
Introduction to Algorithms, 2nd edition. MIT Press, McGrawHill Book Company, 2000.
[5] Yury Polyanskiy. Asynchronous communication: Exact synchronization, universality, and dispersion. Information Theory,
IEEE Transactions on, 59(3):1256–1270, 2013.
[6] Sara Shahi, Daniela Tuninetti, and Natasha Devroye. On the
capacity of strong asynchronous multiple access channels with
a large number of users. In Information Theory (ISIT), 2016
IEEE International Symposium on, pages 1486–1490. IEEE,
2016.
[7] I. Shomorony, R. Etkin, F. Parvaresh, and A.S. Avestimehr.
Bounds on the minimum energy-per-bit for bursty traffic in
diamond networks. In Information Theory Proceedings (ISIT),
2012 IEEE International Symposium on, pages 801–805. IEEE,
2012.
[8] A. Tchamkerten, V. Chandar, and G. Caire. Energy and sampling constrained asynchronous communication. Information
Theory, IEEE Transactions on, 60(12):7686–7697, Dec 2014.
[9] A. Tchamkerten, V. Chandar, and G. W. Wornell. Asynchronous
communication: Capacity bounds and suboptimality of training.
Information Theory, IEEE Transactions on, 59(3):1227 –1255,
march 2013.
[10] A. Tchamkerten, V. Chandar, and G.W. Wornell. Communication under strong asynchronism. Information Theory, IEEE
Transactions on, 55(10):4508–4528, 2009.
[11] Da Wang. Distinguishing codes from noise: fundamental limits
and applications to sparse communication. Master’s thesis,
Massachusetts Institute of Technology, 2010.
[12] N. Weinberger and N. Merhav. Codeword or noise? exact
random coding exponents for joint detection and decoding.
Information Theory, IEEE Transactions on, 60(9):5077–5094,
Sept 2014.

