# Information Velocity of Cascaded
Gaussian Channels with Feedback

Elad Domanovitz, Anatoly Khina, Tal Philosof, and Yuval Kochman E. Domanovitz
and A. Khina are with the School of Electrical Engineering, Tel Aviv
University, Tel Aviv 6997801, Israel (e-mail:
{domanovi,anatolyk}@eng.tau.ac.il).T. Philosof is with Samsung Research, Tel
Aviv 6492103, Israel (e-mail: tal.philosof@gmail.com).Yuval Kochman is with
the The Rachel and Salim Benin School of Computer Science and Engineering, the
Hebrew University of Jerusalem, Jerusalem 9190401, Israel (email:
yuvalko@cs.huji.ac.il).

###### Abstract

We consider a line network of nodes, connected by additive white Gaussian
noise channels, equipped with local feedback. We study the velocity at which
information spreads over this network. For transmission of a data packet, we
give an explicit positive lower bound on the velocity, for any packet size.
Furthermore, we consider streaming, that is, transmission of data packets
generated at a given average arrival rate. We show that a positive velocity
exists as long as the arrival rate is below the individual Gaussian channel
capacity, and provide an explicit lower bound. Our analysis involves applying
pulse-amplitude modulation to the data (successively in the streaming case),
and using linear mean-squared error estimation at the network nodes. Due to
the analog linear nature of the scheme, the results extend to any additive
noise. For general noise, we derive exponential error-probability bounds.
Moreover, for (sub-)Gaussian noise we show a doubly-exponential behavior,
which reduces to the celebrated Schalkwijk–Kailath scheme when considering a
single node. Viewing the constellation as an “analog source”, we also provide
bounds on the exponential decay of the mean-squared error of source
transmission over the network.

##  I Introduction

Large-scale, ubiquitous wireless networks are evolving, the Internet of Things
being a technology that implements part of the vision. A central problem of
interest in this context, is transmission over a cascade of channels
interconnected by relaying nodes. Beyond serving as a building block for more
complex networks, such line networks are found, for example, in saltatory
conduction in the brain, where action potentials propagate along myelinated
axons with the nodes of Ranvier serving as relays [1, 2, 3, 4], as well as in
vehicle platooning, where wireless communication between geographically
distant vehicles that travel together in a coordinated fashion is carried over
intermediate vehicles which act as relays [5, 6].

From an information-theoretic perspective, without delay constraints, assuming
that each channel may be used the same number of times, the maximal reliable
communication rate is equal to the minimum of the individual channel
capacities. In a more practical scenario, the end-to-end delay of the network
is constrained. Since it is wasteful for a node to wait to decode a long block
code, the nodes should opt to apply causal operations to their measurements
instead. However, determining the maximal rate of reliable communication over
such networks, let alone determining the error probability behavior, turns out
to be very challenging.

If we fix the message size and number of channels and let the number of time
steps grow, decoding with high probability is guaranteed, and one seeks the
optimal error exponent. Determining the optimal error exponent turned out to
be difficult even for the simple case of single-bit transmission over a tandem
of binary symmetric channels [7, 8], and was eventually proved by Ling and
Scarlett [9] to equal to that of a single channel. They further extended the
scope to any finite number of messages in [10].

The behavior of large networks is better expressed by taking the number of
channels to grow linearly with the number of time steps. The minimum ratio
between the two such that the error probability may be arbitrarily small, was
termed Information Velocity (IV) by Polyanskiy (see [7, 11]) in the single-bit
context. The same term was used earlier by Iyer and Vaze [12] in a related
setting of spatial wireless networks.111Similar concepts also exist in other
disciplines, e.g., in physics, in neuroscience, epidemic spread in networks,
and in marketing and finance.

It is not a priori clear whether such a positive IV exists at all for a given
network. Rajagopalan and Schulman [11], while considering simulating protocols
over binary symmetric channels (BSCs), answered this in the affirmative for a
finite number of bits transmitted over BSCs (and hence also for any binary-
input output symmetric channels via slicing). Improving upon this work, Ling
and Scarlett [13] gave tighter upper and lower bounds in the limits of
crossover probabilities that go to 0 or $1/2$.

Analyzing the IV of the transmission of a single message does not capture the
entire behavior of the network. As the IV is meaningful when both the time and
number of relays go to infinity, it might suggest that when another message
arrives, the network is still occupied with processing the previous message.
Hence, analyzing the IV while transmitting an infinite stream of messages is
of interest. For transmission of a stream of messages over a cascade of
packet-erasure channels (with instantaneous ACK/NACK feedback), the existence
of a positive IV can be derived from stochastic network calculus [14, 15, 16,
17] (these results also hold for a single packet without feedback). However,
only recently, in [18], the explicit IV was derived for streaming over packet-
erasure channels with such feedback. This work also derived the IV of
transmitting a single packet and determined the explicit error decay rate for
velocities below the IV for both single-packet and streaming settings.

Despite these efforts, no explicit expressions for the IV for non-erasure
channels are available even for a single bit, let alone for streaming or error
probability decay rate guarantees.

Causal
---
source
Transmitter
---
(Node 0)
+Node 1+$\bullet\bullet\bullet$ Node $r$
---
$\bullet\bullet\bullet$$\bullet\bullet\bullet$${Z_{0}\left(t\right)}$${Z_{1}\left(t\right)}$
Stream of
---
packets
$W\left(\cdot\right)$
Decoded packets
---
${\hat{W}}_{r}\left(\cdot\middle|t\right)$
Decoded packets
---
${\hat{W}}_{1}\left(\cdot\middle|t\right)$
${X_{0}\left(t\right)}$${Y_{0}\left(t\right)}$${X_{1}\left(t\right)}$${Y_{1}\left(t\right)}$${Y_{r-1}\left(t\right)}$${X_{r}\left(t\right)}$

Figure 1: Block diagram of the system. ${X_{r}\left(t\right)}$,
${Y_{r}\left(t\right)}$, and ${Z_{r}\left(t\right)}$ are the channel input,
output, and noise, respectively, at node $r$ at time $t$. Each $T$ time steps,
a new packet is generated. At every time step, all the nodes decode all the
hitherto arrived packets.

In this work, we consider a cascade of additive white-noise (say Gaussian)
channels with the same signal-to-noise ratio (SNR) $P>0$, equipped with
perfect and local feedback. That is, each node is aware of the measurements of
the next node in a causal manner; see Figure 1. For this setting, we derive a
lower bound on both the single-packet and the streaming IVs:222These results
are stated for delayed hops, that is, a relay may only use its input in the
subsequent time step. In the body of the paper we consider instantenous hops
for ease of presentation; the results for both dealyed and instantaneous hops
are summarized in Table I in Section VII. We prove that the single-packet IV
is bounded from below as

$\displaystyle\mathrm{V}\geq 1-{\operatorname{exp}\left\\{-2C\right\\}},$ (1)

where $C\triangleq\frac{1}{2}\log(1+P)$ denotes the channel capacity of an
individual additive white-Gaussian noise channel with SNR $P$; the same bound
(1) has been independently derived by Inovan and Telatar [19]. The streaming
IV $\mathrm{V}(R)$ at data-generation rate $R$ is bounded from below as

$\displaystyle\mathrm{V}(R)\geq
1-{\operatorname{exp}\left\\{-2(C-R)\right\\}}$ (2)

for $R<C$; in particular, the streaming IV is positive for any $R<C$, and the
bound on the streaming IV (2) reduces to that on the single-packet IV (1) in
the limit of $R\to 0$.

Reminiscent of [20], our approach is based on the source node translating the
incremental message history into a real number. Subsequently, this number is
handled by the network in an analog linear manner. Namely, each node keeps the
best linear estimator of that number based on its past measurements, as well
as the estimate of the next node (known thanks to the feedback), and transmits
a scaled version of the difference. Indeed, for a single data packet, the
communication between the source node and the first relay reduces to the
celebrated Schalkwijk–Kailath scheme for feedback communication over an
additive-noise channel [21, 22], which can be viewed [23] as an application of
the joint source–channel coding scheme with feedback of Elias [24]. On the
other hand, the first transmission of each of the nodes reduces to scalar
amplify-and-forward relaying [25].

Treating a representation of a data message as an analog source is a concept
that has proved useful in relaying schemes [25, 26, 27]. Using that concept,
techniques from source coding and joint source–channel coding find their way
into digital communication settings. In the context of our work, the
estimation at the relays are reminiscent of the Gaussian CEO problem [28, 29,
30], and in particular its sequential variant [31, 32, 33]. From the point of
view of our relay network, the way that the source node builds its scalar
representation of the data stream, is as if an analog source were revealed to
it using successive refinement [34, 35].

Due to the amount of concepts involved, we present our results gradually. We
first address a single source to be transmitted, and then streaming. Within
each of the above, we start with an analog source and consider the estimation
mean-squared error (MSE), and in particular its decay rate, before advancing
to data packets and considering error probabilities. For error probabilities,
we show that for velocities lower than our achievable bound on the IV, the
error probabilities decay at least exponentially fast, while if the noise is
assumed to be Gaussian (or, more generally, sub-Gaussian), the error
probabilities are shown to decay at least double exponentially, extending the
known behavior of the Schalkwijk–Kailath scheme [21, 22] to multiple relays.

The rest of the paper is organized as follows. In Section II, we formally
define the problem. In Section IV, we address the MSE when communicating a
single analog source sample. In Section V, we replace that source sample by a
data packet, possibly of unbounded size. In Section VI, we advance to a source
sample being successively revealed to the first node, and then to a stream of
data packets. Finally, in Section VII we conclude with a summary of the main
results, and discussion of future reserach directions.

### Notation

Denote by $\mathbb{Z}$, $\mathbb{Z}_{\geq 0}$, $\mathbb{R}$, $\mathbb{R}_{\geq
0}$, and $\mathbb{N}$ the sets of integer, non-negative integer, real, non-
negative real, and natural numbers, respectively. Throughout, all logarithms
and exponents are taken to the natural base. We make use of small $o$
notation: $f(x)=o_{x}\left(g(x)\right)$ if $\lim_{x\to\infty}{f(x)}/{g(x)}=0$;
if the argument is clear, we write $o(\cdot)$. For a scalar
$a\in\mathbb{R}_{\geq 0}$, we denote

$\displaystyle\bar{a}=\frac{a}{1+a}.$ (3)

We denote time sequences of a signal $a_{k}$ between times
$t_{1},t_{2}\in\mathbb{Z}_{\geq 0}$ ($t_{1}\leq t_{2}$) by

$\displaystyle a_{k}\left(t_{1}:t_{2}\right)$
$\displaystyle\triangleq\begin{bmatrix}a_{k}(t_{1}),&a_{k}(t_{1}+1),&\ldots,&a_{k}(t_{2})\end{bmatrix}.$
(4)

We denote Markov chains by $X_{1}\leftrightarrow X_{2}\leftrightarrow X_{3}$,
namely, given $X_{2}$, $X_{1}$ is independent of $X_{3}$. $\exp$ and $\log$
denote the natural exponential and logarithm functions, respectively. We use
the binary entropy and divergence functions: for $0<p,q<1$,

$\displaystyle\begin{aligned} h(p)&\triangleq
p\log\frac{1}{p}+(1-p)\log\frac{1}{1-p},\\\
{\mathbb{D}\left(p\middle\|q\right)}&\triangleq
p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}.\end{aligned}$ (5)

##  II Problem Statement

###  II-A Communication Model

The communication model that is considered in this work is depicted in Figure
1.

Causal source. Every $T$ time steps, a source generates a new message that
comprises $\ell$ bits, namely, at time $t=T\tau$ for $\tau\in\mathbb{Z}_{\geq
0}$, the source generates packet

$\displaystyle
W\left(\tau\right)=\begin{bmatrix}B\left(\tau\ell\right),&B\left(\tau\ell+1\right),&\ldots,&B\left((\tau+1)\ell-1\right)\end{bmatrix}$
(6)

comprising bits. The bits of the entire message sequence,
$\left\\{B\left(i\right)\middle|i\in\mathbb{Z}_{\geq 0}\right\\}$, are assumed
i.i.d. uniform. Define the average rate of this source, measured in nats per
time instant, as

$\displaystyle R=\frac{\ell}{T}\log(2).$ (7)

Channels. The network is composed of a cascade of channels; channel
$r\in\mathbb{Z}_{\geq 0}$ is an additive noise channel:

$\displaystyle{Y_{r}\left(t\right)}={X_{r}\left(t\right)}+{Z_{r}\left(t\right)},$
(8)

where ${X_{r}\left(t\right)}$, ${Y_{r}\left(t\right)}$, and
${Z_{r}\left(t\right)}$ are the channel input, output, and noise,
respectively, at time $t\in\mathbb{Z}_{\geq 0}$. The entries of all the noise
sequences $\left\\{{Z_{r}\left(t\right)}\middle|r,t\in\mathbb{Z}_{\geq
0}\right\\}$ are i.i.d. zero-mean, unit variance, and independent of all
channel inputs. All channel inputs are subject to a mean power constraint:

$\displaystyle\mathbb{E}\left[{X^{2}_{r}\left(t\right)}\right]$
$\displaystyle\leq P$ $\displaystyle\forall r,t\in\mathbb{Z}_{\geq 0}.$ (9)

The following channel quantities will be useds in the sequel:

$\displaystyle C=\frac{1}{2}\log(1+P)$ (10)

is the Gaussian capacity and (recalling the bar notation (3))

$\displaystyle\begin{aligned}
\eta\triangleq(1-\bar{P})\cdot{\operatorname{exp}\left\\{2R\right\\}}={\operatorname{exp}\left\\{-2(C-R)\right\\}}.\end{aligned}$
(11)

As will be formally defined in the node functions below, perfect feedback is
available in each channel, from the channel output to the terminal feeding it,
in the subsequent time step.

Originating transmitter (node 0). At each time $t\in\mathbb{Z}_{\geq 0}$,
generates a channel input ${X_{0}\left(t\right)}$ as a function of all the
packet history $W\left(0:\left\lfloor{\frac{t}{T}}\right\rfloor\right)$, and
of all past outputs of channel 0, ${Y_{0}\left(0:t-1\right)}$, which are
available via feedback. The input is subject to the power constraint (9).

Node $r$ ($r\in\mathbb{N}$). At each time $t\in\mathbb{Z}_{\geq 0}$, generates
the channel input ${X_{r}\left(t\right)}$ as a function of all its measurement
history333The current measurement is included, that is, we assume
_instantaneous_ hops. See Remark 3 in the sequel. ${Y_{r-1}\left(0:t\right)}$
from its feeding channel (channel $r-1$), and of all its feedback history from
the subsequent channel (channel $r$), ${Y_{r}\left(0:t-1\right)}$. The input
is subject to the power constraint (9). The relays also produce estimates of
the message.444We consider decoding at a general node $r\in\mathbb{N}$. This
decoding does not affect the creation of subsequent channel inputs in any way.
As a special case, one can think of a specific node where the network
terminates and information is needed. See Remark 2 in the sequel. Let
${\hat{B}}_{r}\left(n\middle|t\right)$,
${\hat{B}}_{r}\left(0:n\middle|t\right)$,
${\hat{W}}_{r}\left(n\middle|t\right)$, and
${\hat{W}}_{r}\left(0:n\middle|t\right)$ denote the estimates of
$B\left(n\right)$, $B\left(0:n\right)$, $W\left(n\right)$, and
$W\left(0:n\right)$, respectively, at node $r\in\mathbb{N}$ at time $t$ based
on the measurement history ${Y_{r-1}\left(0:t\right)}$ and feedback history
${Y_{r}\left(0:t-1\right)}$.

Scheme. We refer to the collection of maps of nodes $0$ to $r\in\mathbb{N}$ at
times $0$ to $t\in\mathbb{Z}_{\geq 0}$ as an $(r,t)$-scheme. A scheme is
defined as a nested set collection of $(r,t)$-schemes with respect to
$t\in\mathbb{Z}_{\geq 0}$ for a fixed $r\in\mathbb{N}$, and with respect to
$r\in\mathbb{N}$ for a fixed $t\in\mathbb{Z}_{\geq 0}$, to wit, an
$(r,t)$-scheme equals to the union of all the $(\tilde{r},\tilde{t})$-schemes
over $\tilde{r}\leq r,\tilde{t}\leq t$.

###  II-B Performance Measures

Error Probability. We define the bit error probability for bit $n$ at relay
$r$ at time $t$ as

$\displaystyle{\epsilon}_{r}\left(n\middle|t\right)$
$\displaystyle\triangleq\Pr\left({\hat{B}}_{r}\left(n\middle|t\right)\neq
B\left(n\right)\right).$ (12)

We define the maximal bit error probability as a function of the detection
delay $\Delta$ (the number of time steps elapsed since the generation of the
bit) [18] as

$\displaystyle P_{e}\left(r,\Delta\right)$
$\displaystyle\triangleq\sup_{\tau\in\mathbb{Z}_{\geq 0}}\max_{\tau\ell\leq
n\leq(\tau+1)\ell-1}{\epsilon}_{r}\left(n\middle|\tau T+\Delta\right).$ (13)

The outer maximization (supremum) is carried over all the packets, whereas the
inner maximization is carried over all the bits inside a packet. $\Delta$ is
the elapsed time (delay) after a generated bit is decoded. Thus,
$P_{e}\left(r,\Delta\right)$ is the worst-case error probability across all
the bits recovered $\Delta$ time steps after their generation.

Achievable streaming velocity. A streaming velocity $v\in\mathbb{R}_{\geq 0}$
of a source of average rate $R$ is said to be achievable if there exists a
scheme, such that,

$\displaystyle\lim_{r\rightarrow\infty}P_{e}\left(r,\left\lfloor{\frac{r}{v}}\right\rfloor\right)=0,$
(14)

namely, $\Delta=\left\lfloor{r/v}\right\rfloor$ in $P_{e}$.

Streaming information velocity. The streaming IV of a source of average rate
$R$, denoted by $\mathrm{V}(R)$, is defined as the supremum of all achievable
streaming velocities of that source.

Figure 2 demonstrates schematically the propagation of packets along the
network nodes versus time. The example in Figure 2 consists of a transmitter
(node $0$) and two relay nodes (nodes $1$ and $2$). The packet length is
$\ell=4$ bits and $T=4$, meaning that the average rate is $R=\log 2$. The top
graph indicates generation times of packets (when they arrive at node $0$).
Packets $W(0),W(1),W(2)$ arrive at node $0$ at times $0$, $4$ and $8$,
respectively. The middle and bottom graphs depict the estimations of the
hitherto generated packet at each time step at nodes 1 and 2, respectively:
for $t\in[0,3]$, packet $W(0)$ is estimated, namely, $\hat{W}(0|t)$; for
$t\in[4,7]$, packets $W(0:1)$ are estimated, namely $\hat{W}(0:1|t)$; for
$t\in[8,11]$, packets $W(0:2)$ are estimated, namely $\hat{W}(0:2|t)$; etc.

We also mark in Figure 2 a few instances of the error probability, e.g.,
${\epsilon}_{1}\left(6\middle|5\right)$ is the error probability at node $1$
of bit $B\left(6\right)$ at time $t=5$, and
${\epsilon}_{2}\left(0:6\middle|11\right)$ is the error probability at node
$2$ of bits $B\left(0:6\right)$ at time $t=11$.

Figure 2: Data packet streaming: visualization packet estimations at nodes
$r=0,1,2$ across time, for time period $T=4$, and four bits per packet
$\ell=4$. The packets at the transmitter (node $0$) indicate arrival time to
transmitter, while the packets at nodes $1$ and $2$ indicate decoded packets.

######  Remark 1 (average rate).

The streaming IV is set by the average rate $R$ (7) rather than by the source
parameters $\ell$ and $T$ individually. To see why this is true, notice that
the generation time of the bit $n$, which is $\tau T$ where $\tau$ is the
index of the packet containing $n$, equals $n\log(2)/R$ up to a bounded
difference. This difference does not affect the IV as it is absorbed in
$\Delta\rightarrow\infty$ in the definition (13).

It will become evident that we could use other transmission patterns with the
same average rate without changing our results. We keep the periodic pattern
for simplicity, noticing that it can approximate any desired positive rate.

######  Remark 2 (finite horizon).

In this work, we consider a setting of an infinite number of cascaded nodes
and analyze the velocity at which information can propagate over this network
with a decaying error probability. This setting is more stringent than
previous IV definitions [7, 18, 13] in which the number of nodes was a
prescribed finite number with a target final recevier, which was then taken to
infinity. In particular, in the previously-considered settings, all nodes were
designed to attain the best possible error probability at a particular final
receiver (“horizon”), whereas in our (“horizon-free”) setting, tension may
arise between attaining the best possible performance at different nodes.
Clearly, any achievable IV or error probability guarantees carry over to the
finite-horizon setting, but not necessarily the other way around.

######  Remark 3 (delayed hops).

The described model above assumes instantaneous hops, namely, node $r$ at time
$t$ transmits ${X_{r}\left(t\right)}$ that may dependent on its measurement
history ${Y_{r-1}\left(1:t\right)}$ until and including time $t$ (and its
feedback history ${Y_{r}\left(1:t-1\right)}$). The exposition of this scenario
is simpler to follow and we therefore present it in detail. That said, we also
present results for the parallel scenario of delayed hops, in which, node $r$
at time $t$ transmits ${X_{r}\left(t\right)}$ that can depend only on its
purely causal history ${Y_{r-1}\left(1:t-1\right)}$ (and its feedback history
${Y_{r}\left(1:t-1\right)}$).

##  III Detailed Work Overview

The setting described in Section II is the ultimate goal of this work. As
mentioned in the introduction, we tackle this goal by first considering
somewhat simpler settings, namely a single packet (no streaming) and source
transmission (the data bits are replaced by a continuous source). Beyond
setting the ground for the main result, these settings yield auxiliary results
that may be of interest in their own right.

Let $S$ denote a source sample that we want to convey to the nodes with
minimal mean-squared error (MSE), and ${{{\hat{S}}}_{r}\left(t\right)}$ denote
its estimate at node $r$ at time $t$. We will analyze the estimation MSE of
${{{\hat{S}}}_{r}\left(t\right)}$:

$\displaystyle{\mathrm{MSE}_{r}\left(t\right)}\triangleq
E\left[\left(S-{{{\hat{S}}}_{r}\left(t\right)}\right)^{2}\right].$ (15)

Besides being interesting in and of itself, as a joint source–channel coding
(JSCC) problem, the transmission of an analog source over the same network
constitutes an essential component in our proposed communication schemes.
Specifically, in Section IV, the sample $S$ is revealed to the transmitter
before transmission begins.

In Section V, the error probability of transmitting a single packet over the
network is derived. Transmitting a single packet may be viewed as a limiting
streaming setting in which the packet inter-generation time $T$ is infinite
[and the average rate (7) goes to 0]. Therefore, all the definitions of
Section II carry over to the single-packet transmission setting, except for
the maximal bit error probability (13). Since the (only) packet comprises
$\ell$ bits, $B\left(0:\ell-1\right)$, that are generated together at time 0,
their detection delay $\Delta$ equals simply the elapsed time since the
beginning of transmission $t$, the maximal bit error probability reduces, in
this case, to

$\displaystyle P_{e}\left(r,t\right)$ $\displaystyle\triangleq\max_{0\leq
n\leq\ell-1}{\epsilon}_{r}\left(n\middle|t\right).$ (16)

The IV is defined with respect to this error probability. Since our bounds on
the single-packet IV do not depend on $\ell$ (and correspond to $R=0$), we
denote the single-packet IV by $\mathrm{V}$ without an argument.

To bound the maximal error probability of a transmission of a single packet,
we will treat the packet as a source sample and use the bounds on the MSE of
transmitting a single source sample. We will subsequently analyze the packet
error probability [decoding error probability of $B\left(0:\ell-1\right)$]:

$\displaystyle{\epsilon}_{r}\left(0:\ell-1\middle|t\right)$
$\displaystyle=\Pr\left({\hat{B}}_{r}\left(0:\ell-1\middle|t\right)\neq
B\left(0:\ell-1\right)\right).$ (17)

Clearly, the packet error probability bounds from above the corresponding
individual bit error probabilities since

$\displaystyle{\epsilon}_{r}\left(0:\ell-1\middle|t\right)$
$\displaystyle=\Pr\left(\bigcup_{i\in\left\\{0,\ldots,\ell-1\right\\}}\left\\{{\hat{B}}_{r}\left(i\middle|t\right)\neq
B\left(i\right)\right\\}\right)$ (18)
$\displaystyle\geq\max_{i\in\\{1,\ldots,\ell-1\\}}\Pr\left({\hat{B}}_{r}\left(i\middle|t\right)\neq
B\left(i\right)\right)$ (19)
$\displaystyle=\max_{i\in\\{1,\ldots,\ell-1\\}}{\epsilon}_{r}\left(i\middle|t\right).$
(20)

We then move to analyze streaming settings in Section VI. In Section VI-A, we
consider a streaming JSCC setting in which the sample $S$ is gradually
revealed (a la successive refinement) to the transmitter with quality that
improves with time and derive bounds on the MSE (15) as a function of the node
index $r$ and the time $t$. In Section VI-B, we use the JSCC streaming
solution and results of Section VI to derive bounds on the error probability
for data-packet streaming by constructing a virtual source comprising the
infinite concatenation of the entire data-packet sequence, where the hitherto
generated data packets correspond to partial knowledge of the source $S$.
Similar to (18), to bound the maximal bit error probability (13), we bound the
more stringent prefix error probability

$\displaystyle{\epsilon}_{r}\left(0:n\middle|t\right)$
$\displaystyle=\Pr\left({\hat{B}}_{r}\left(0:n\middle|t\right)\neq
B\left(0:n\right)\right)$ (21)

for $n\in\mathbb{N}$, by

$\displaystyle\begin{aligned}
P_{e}\left(r,\Delta\right)&\triangleq\sup_{\tau\in\mathbb{Z}_{\geq
0}}\max_{\tau\ell\leq n\leq(\tau+1)\ell-1}{\epsilon}_{r}\left(n\middle|\tau
T+\Delta\right)\\\ &\leq\sup_{\tau\in\mathbb{Z}_{\geq
0}}{\epsilon}_{r}\left(0:(\tau+1)\ell-1\middle|\tau
T+\Delta\right).\end{aligned}$ (22)

##  IV Transmission of a Single Source Sample

In this section, we consider the problem of transmitting a single zero-mean
unit-variance source sample over the network under a minimum MSE criterion.

We propose the following simple _linear_ scheme, which is a natural extension
of the single-channel scheme of Elias [24] to our network setting.

######  Scheme 1.

Initialization.

  * •

Since the transmitter (node 0) knows $S$ perfectly, it sets
${{{\hat{S}}}_{0}\left(t\right)}=S$ for all $t\in\mathbb{Z}_{\geq 0}$.

  * •

Each node $r\in\mathbb{N}$ initializes its estimate before transmission begins
to the mean: ${{{\hat{S}}}_{r}\left(-1\right)}=0$.

Estimation at node $r\in\mathbb{N}$. At each time $t\in\mathbb{Z}_{\geq 0}$,
constructs an estimate of $S$:

$\displaystyle{{{\hat{S}}}_{r}\left(t\right)}={{{\hat{S}}}_{r}\left(t-1\right)}+{{\gamma}_{r}\left(t\right)}{Y_{r-1}\left(t\right)},$
(23)

where ${{\gamma}_{r}\left(t\right)}$ is a linear MSE (LMMSE) constant, to be
specified in the sequel.

Transmission by node $r\in\mathbb{Z}_{\geq 0}$. At each time
$t\in\mathbb{Z}_{\geq 0}$, transmits

$\displaystyle{X_{r}\left(t\right)}={{\beta}_{r}\left(t\right)}\left[{{{\hat{S}}}_{r}\left(t\right)}-{{{\hat{S}}}_{r+1}\left(t-1\right)}\right],$
(24)

where ${{\beta}_{r}\left(t\right)}$ is a power-normalization constant, to be
specified in the sequel.

Since node $r\in\mathbb{N}$ at time $t$ knows ${Y_{r+1}\left(0:t-1\right)}$
via feedback, it can construct ${{{\hat{S}}}_{r+1}\left(t-1\right)}$ which is
used to generate the transmit signal (24) of node $r$ at time $t$.

Using Scheme 1, the estimates satisfy the following properties.

######  Lemma 1.

In Scheme 1, all channel inputs and outputs and all estimates have zero mean.
Setting

$\displaystyle{{\gamma}_{r}\left(t\right)}=\frac{{\mathrm{Cov}\left(S,{X_{r-1}\left(t\right)}\right)}}{1+{\mathrm{Var}\left({X_{r-1}\left(t\right)}\right)}},$
(25)

we have the following.

  1. 1.

${{{\hat{S}}}_{r}\left(t\right)}$ is the LMMSE estimate of $S$ from
${Y_{r-1}\left(0:t\right)}$.

  2. 2.

The outputs of the same channel at different times are uncorrelated, viz.

$\displaystyle{\mathrm{Cov}\left({Y_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}$
$\displaystyle=0$ $\displaystyle t\neq\tau.$ (26)

  3. 3.

The covariance between $S$ and ${X_{r}\left(t\right)}$, for
$r,t\in\mathbb{Z}_{\geq 0}$, equals

$\displaystyle{\mathrm{Cov}\left(S,{X_{r}\left(t\right)}\right)}={{\beta}_{r}\left(t\right)}\cdot\left[{\mathrm{MSE}_{r+1}\left(t-1\right)}-{\mathrm{MSE}_{r}\left(t\right)}\right].$
(27)

  4. 4.

The variance of the channel input ${X_{r}\left(t\right)}$, for
$r,t\in\mathbb{Z}_{\geq 0}$, equals

$\displaystyle{\mathrm{Var}\left({X_{r}\left(t\right)}\right)}=\beta^{2}_{r}\left(t\right)\cdot\left[{\mathrm{MSE}_{r+1}\left(t-1\right)}-{\mathrm{MSE}_{r}\left(t\right)}\right].$
(28)

The proof is based on properties of LMMSE estimation, primarily the
orthogonality principle [36, Ch. 7-3]; it appears in Appendix A. Notice that
the uncorrelatedness of the channel outputs means that indeed each node
receives “novel” information at each time step, and thus the channels are
utilized well.

Using the properties of Lemma 1, and choosing ${{\beta}_{r}\left(t\right)}$ to
satisfy the power constraint with equality, we find that the constants
satisfy,

$\displaystyle{{\beta}_{r}\left(t\right)}$
$\displaystyle=\sqrt{\frac{P}{{\mathrm{MSE}_{r+1}\left(t-1\right)}-{\mathrm{MSE}_{r}\left(t\right)}}}$
$\displaystyle\forall r,t\in\mathbb{Z}_{\geq 0}\,;$ (29a)
$\displaystyle{{\gamma}_{r}\left(t\right)}$
$\displaystyle=\frac{\sqrt{P({\mathrm{MSE}_{r}\left(t-1\right)}-{\mathrm{MSE}_{r-1}\left(t\right)})}}{P+1}$
$\displaystyle\forall r\in\mathbb{N},t\in\mathbb{Z}_{\geq 0}\,.$ (29b)

Using these values in Scheme 1 yields the relation [notice that
$\beta_{r-1}(t)\gamma_{r}(t)=\bar{P}$ for all $r\in\mathbb{N}$ where $\bar{P}$
is defined according to the notation (3)]:

$\displaystyle{{{\hat{S}}}_{r}\left(t\right)}=\bar{P}\cdot{{{\hat{S}}}_{r-1}\left(t\right)}+(1-\bar{P})\cdot{{{\hat{S}}}_{r}\left(t-1\right)}+{{\gamma}_{r}\left(t\right)}{Z_{r-1}\left(t\right)},\
\forall r\in\mathbb{N},t\in\mathbb{Z}_{\geq 0}.$ (30)

Further, the resulting MSE of the scheme is given in the following lemma,
whose proof appears in Appendix A.

######  Lemma 2.

Scheme 1 with the parameters of (29) satisfies the recursion

$\displaystyle{\mathrm{MSE}_{r}\left(t\right)}=\bar{P}\cdot{\mathrm{MSE}_{r-1}\left(t\right)}+(1-\bar{P})\cdot{\mathrm{MSE}_{r}\left(t-1\right)}\
\forall r\in\mathbb{N},t\in\mathbb{Z}_{\geq 0},$ (31)

with the initial conditions ${\mathrm{MSE}_{r}\left(-1\right)}=1$ for all
$r\in\mathbb{Z}_{\geq 0}$, and the boundary conditions
${\mathrm{MSE}_{0}\left(t\right)}=0$ for all $t\in\mathbb{Z}_{\geq 0}$.
Furthermore, the solution of this recursion is

$\displaystyle{\mathrm{MSE}_{r}\left(t\right)}$
$\displaystyle=\left(1-\bar{P}\right)^{t+1}\sum_{k=1}^{r}\binom{t+r-k}{r-k}\bar{P}^{r-k}$
$\displaystyle\forall r,t\in\mathbb{N}.$ (32)

In order to study the asymptotic behavior of (32), we fix some velocity $v>0$
such that $t=\left\lfloor{r/v}\right\rfloor$, and consider the MSE sequence as
a function of the relay index.

######  Theorem 1.

Let $v>0$ be some fixed velocity. Then, the MSE of Scheme 1 satisfies

$\displaystyle{\mathrm{MSE}_{r}\left(\left\lfloor{\frac{r}{v}}\right\rfloor\right)}\leq{\operatorname{exp}\left\\{-rE_{1}(v)+o(r)\right\\}},$
(33)

where the $o(r)$ correction is independent of $v$, $E_{1}(\cdot)$ is defined
via $\bar{P}=\frac{P}{1+P}$ (3) as

$\displaystyle
E_{1}(v)\triangleq\begin{cases}\frac{1}{\bar{v}}{\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)},&v<P;\\\
0,&v\geq P.\end{cases}$ (34)

The proof appears in Appendix A. It is based on the entropy-based bounds on
the binomial coefficients. In fact, It can be shown (although it is not needed
for our purposes) that the bound of (33) is exponentially tight.

Theorem 1 implies that, for any $v<P$, the MSE goes to zero with $t$ (and
$r\propto t$). That is, the source is reconstructed with arbitrarily good
precision asymptotically. Indeed we can interpret this result as a lower bound
on the source “reconstruction velocity”.

In the next section, we will use the JSCC results of this section for the
problem of transmitting a single data packet. This is achieved by mapping the
data packet to a pulse amplitude modulation (PAM) symbol $S$, applying 1 to
$S$ by treating the latter as a source samples, and finally decoding the data
packet from the resulting LMMSE estimate of $S$. This scheme will allow
translating the JSCC results of this section to parallel results for data-
packet transmission: a lower bound on the single-packet IV of $\mathrm{V}\geq
P$, and an exponential decay rate of $E_{1}$ (34) for velocity $v<P$.

##  V Transmission of a Single Data Packet

In this section, we consider the problem of transmitting a single data packet
of $\ell$ i.i.d. uniform bits $B\left(0:\ell-1\right)$ over the network. We
bound the block error probability
${\epsilon}_{r}\left(0:\ell-1\middle|t\right)$ (21), which, as explained in
Section III, serves as an upper bound on the worst-case individual bit error
probability $P_{e}\left(r,t\right)$ (16). The error-probability bounds yield
an achievable single-packet IV.

To that end, we map the the bits $B\left(0:\ell-1\right)$, which comprise the
data packet, to a PAM constellation point using natural labeling:

$\displaystyle
S^{\ell}=\sqrt{3}\sum_{i=0}^{\ell-1}(-1)^{B\left(i\right)}2^{-(i+1)},$ (35)

and apply Scheme 1 by viewing $S^{\ell}$ as source sample. Since the bits
$B\left(0:\ell-1\right)$ are uniformly distributed, $S^{\ell}$ is uniformly
distributed over a discrete symmetric finite grid of size $2^{\ell}$ with the
spacing between two adjacent constellation points being

$\displaystyle d_{\ell}=\sqrt{3}\cdot 2^{-\ell+1};$ (36)

in particular, $S^{\ell}$ has zero mean. In the limit of an infinite message
length $\ell$, $S^{\ell}$ converges to

$\displaystyle
S=\lim_{\ell\rightarrow\infty}S^{\ell}=\sqrt{3}\sum_{i=0}^{\infty}(-1)^{B\left(i\right)}2^{-(i+1)}.$
(37)

Since the bits $\left\\{B\left(i\right)\right\\}$ are i.i.d. uniform, $S$ is
uniformly distributed over $[-\sqrt{3},\sqrt{3})$, meaning that it has zero
mean and unit variance. For any $\ell$, the variance of $S^{\ell}$ is smaller
than $1$. This allows us to construct the following transmission scheme for a
single packet, which satisfies the power constraints (9).

######  Scheme 2.

  1. 1.

The transmitter (node 0) maps $B\left(0:\ell-1\right)$ to $S^{\ell}$ according
to (35).

  2. 2.

All nodes apply Scheme 1 with $S^{\ell}$ taking the role of the source $S$.

  3. 3.

At each time step $t\in\mathbb{Z}_{\geq 0}$, each relay (node $r$ for
$r\in\mathbb{N}$) estimates $B\left(0:\ell-1\right)$ from
${{\hat{S}}^{\ell}_{r}\left(t\right)}$—the estimate of $S^{\ell}$ at relay $r$
at time $t$.

######  Remark 4.

Since the variance of $S^{\ell}$ is strictly lower than $1$ (converges to $1$
in the limit of $\ell\to\infty$), Scheme 2 can be improved by adjusting the
power of $S^{\ell}$ to 1 by multiplying it by a factor that is greater than 1.
However, the gain of such an improvement is negligible in the limit of large
$t$.

We denote the error of ${{\hat{S}}^{\ell}_{r}\left(t\right)}$ in estimating
$S^{\ell}$ by

$\displaystyle{\mathcal{E}^{\ell}_{r}\left(t\right)}\triangleq
S^{\ell}-{{\hat{S}}^{\ell}_{r}\left(t\right)}.$ (38)

Since ${\mathrm{Var}\left(S^{\ell}\right)}\leq 1$,

$\displaystyle\mathbb{E}\left[\left\\{{\mathcal{E}^{\ell}_{r}\left(t\right)}\right\\}^{2}\right]\leq{\mathrm{MSE}_{r}\left(t\right)}.$
(39)

######  Lemma 3.

The packet error probability of Scheme 2 is bounded from above as

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|t\right)\leq\frac{1}{3}\cdot
2^{2\ell}\cdot{\mathrm{MSE}_{r}\left(t\right)}$ (40)

with ${\mathrm{MSE}_{r}\left(t\right)}$ of Lemma 2.

###### Proof:

Feeding ${{\hat{S}}^{\ell}_{r}\left(t\right)}$ to a nearest-neighbor decoder
(slicer) of the constellation point $S^{\ell}$ results in an error probability
that is bounded from above as

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|t\right)$
$\displaystyle\leq\Pr\left(\left|{\mathcal{E}^{\ell}_{r}\left(t\right)}\right|>\frac{d_{\ell}}{2}\right)$
(41a)
$\displaystyle\leq\frac{\mathbb{E}\left[\left\\{{\mathcal{E}^{\ell}_{r}\left(t\right)}\right\\}^{2}\right]}{d_{\ell}^{2}/4}$
(41b) $\displaystyle\leq\frac{1}{3}2^{2\ell}{\mathrm{MSE}_{r}\left(t\right)},$
(41c)

where (41a) follows from the nearest-neighbor decision rule and the PAM
constellation points being distant by $d_{\ell}$, (41b) follows from
Chebyshev’s inequality, and (41c) follows from (36) and (39). ∎

Substituting the result of Theorem 1 in Lemma 3, and recalling the definition
of single-packet IV (1), yields immediately the following.

######  Theorem 2.

Let $\ell\in\mathbb{N}$ be the packet size, however large. Then, the single-
packet IV (1) is bounded from below as $V\geq P$.

Moreover, for velocity $v<P$, the achievable prefix-free error probability is
bounded as

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|\left\lfloor{\frac{v}{r}}\right\rfloor\right)={\operatorname{exp}\left\\{-E_{1}(v)r+o(r)\right\\}},$
(42)

where $E_{1}(v)$ was defined in (34).

For a single channel ($r=1$) and Gaussian noise, Schalkwijk and Kailath [22]
(see also [21, 23], [37, pp. 481–482], [38, Ch. 17.1.1]) showed that the error
probability of transmitting a single message decays double exponentially with
$t$:

$\displaystyle{\epsilon}_{1}\left(0:\ell\middle|t\right)$
$\displaystyle\leq\exp\big{\\{}-\exp\left\\{2Ct+o(t)\right\\}\big{\\}}.$ (43)

We next show that the doubly-exponential behavior extends also to our setting
of multiple AWGN channels. To that end, we tighten the bound of Lemma 5 for
AWGN channels as follows.

######  Lemma 4.

The packet error probability of Scheme 2 over AWGN channels is bounded as

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|t\right)\leq
2{\operatorname{exp}\left\\{-\frac{3}{2^{2\ell+1}\cdot{\mathrm{MSE}_{r}\left(t\right)}}\right\\}}$
(44)

with ${\mathrm{MSE}_{r}\left(t\right)}$ of Lemma 2.

The proof appears in Appendix B and relies on replacing the Chebyshev
inequality with respect to the estimation error
${\mathcal{E}^{\ell}_{r}\left(t\right)}$ in (41b) with a Chernoff–Hoeffding
bound with respect to a (sub-)Gaussian
${\mathcal{E}^{\ell}_{r}\left(t\right)}$ in this case.

Substituting the result of Theorem 1 in Lemma 4 yields immediately the
following.

######  Theorem 3.

Assume AWGN channels and let $\ell\in\mathbb{N}$ be the packet size, however
large. Then, for velocity $v<P$, the achievable prefix-free error probability
is bounded from above as

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|\left\lfloor{\frac{r}{v}}\right\rfloor\right)=\exp\big{\\{}-\exp\left\\{{E_{1}(v)}r+o(r)\right\\}\big{\\}},$
(45)

where $E_{1}(v)$ was defined in (34).

######  Remark 5.

The result of Theorem 3 extends to sub-Gaussian noises, since the proof of
Lemma 4 relies on the sub-Gaussianity of the noise.

The result of Theorem 3 may be rewritten in terms of time $t$ as

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|\left\lfloor{\frac{r}{v}}\right\rfloor\right)=\exp\big{\\{}-\exp\left\\{E_{1}(v)\cdot
vt+o(t)\right\\}\big{\\}}.$ (46)

This expression means that the doubly-exponential behavior (43) of the
celebrated scheme of Schalkwijk and Kailath [22, 21] extends also to
communication at a fixed velocity across multiple relays as long as the
velocity is below $P$. Indeed, since the error propbability for $r=o(t)$ (and
$r=1$ in particular) can only be better than the limit of Theorem 3 as
$v\rightarrow 0$, the result of Theorem 3 reduces exactly to (43) in this
case, by noticing that $\lim\limits_{v\to 0}E_{1}(v)v=2C$ with $C$ of (10).

######  Remark 6.

Gallager [37, pp. 481–482] (see also [23]) rederived the doubly-exponentil
decay rate of Schalkwijk and Kailath by introducing a variant of their scheme
that sends in the first time step a PAM constellation point, extracts the
first Gaussian noise sample via feedback, and then applies over the following
time steps the JSCC scheme of Elias [24] for conveying this Gaussian sample.
In the analysis of Scheme 2 in Appendix B, we show that in fact the JSCC
scheme can be used from the start to describe the constellation point
directly; the analysis of Gallager extends to this case by identifying that
the noise is sub-Gaussian with variance proxy that equals the variance.

######  Remark 7.

The superexponential behavior of the Schalkwijk–Kailath scheme was shown by
Gallager and Nakiboğlu [23] to extend beyond a second-order exponential decay,
where the order of the exponential decay is commensurate with the blocklength
$n$, namely, a tetration-like decay. This behavior seems to extend also to the
network setting with a constant velocity $v<P$, but it is beyond the scope of
this work.

The bound of Lemma 3 deteriorate exponentially with an increase in $\ell$. We
next derive a bound on the prefix error probability
${\epsilon}_{r}\left(0:n\middle|t\right)$, that hold uniformly for all $\ell$
(assuming $n\leq\ell$), and hence serves as a stepping stone for the
derivation of similar bounds for streaming in Section VI.

######  Lemma 5.

The prefix error probability of Scheme 2, for any $n\leq\ell$, is bounded from
above as

$\displaystyle{\epsilon}_{r}\left(0:n\middle|t\right)\leq\frac{2}{\sqrt{3}}\cdot
2^{n}\cdot\sqrt{{\mathrm{MSE}_{r}\left(t\right)}}$ (47)

with ${\mathrm{MSE}_{r}\left(t\right)}$ of Lemma 2.

This result is proven in Appendix C. In conjunction with Theorem 1, it allows
to prove that any velocity below $P$ is achievable in agreement with Theorem
2. However, as the bound of Lemma 5 is proportional to the square-root of the
bound of of Lemma 3, it attains only half the error exponent $E_{1}(v)$. This
factor two in the exponent is thus the price of decoding in the presence of
“interference” from an unbounded number of bits that are not decoded.

##  VI Streaming

In this Section, we consider the packet streaming transmission problem as
introduced in Section II. Like in single packet transmission, we start with
the counterpart JSCC problem, namely, conveying, over the network, a source
that is only gradually revealed to the transmitter, and then apply the MSE
results to packet streaming.

###  VI-A Successively Refined Source

Suppose that the transmitter node does not have full knowledge of the source
at the start ($t=0$), but rather it is given an estimate
${{{\hat{S}}}_{0}\left(t\right)}$ at time $t$, such that these estimates form
a Markov chain
${{{\hat{S}}}_{0}\left(0\right)}\leftrightarrow{{{\hat{S}}}_{0}\left(1\right)}\leftrightarrow\ldots\leftrightarrow
S$. Thus, we can think of them as being the reconstructions obtained from a
successive refinement scheme feeding the network. In particular, we will
assume that these transmitter inputs have MSE

$\displaystyle{\mathrm{MSE}_{0}\left(t-1\right)}$
$\displaystyle=\exp\\{-2Rt\\}$ $\displaystyle\forall t\in\mathbb{N}$ (48)

for some $R>0$. We can think of this as a digital message that arrives at $R$
nats per sample (neglecting rounding issues), or as a source that is gradually
revealed to the transmitter via a fixed-rate successive refinement
scheme.555This is the MSE that is attained by a sequence of greedy optimal
quantizers of rate $R$ (neglecting rounding issues) that are applied to a
uniformly distributed source sample. Moreover, for continuous sources, this
decay is exponentially optimal in $t$ as it matches the exponent of the
distortion–rate function by the Shannon’s lower bound and the Gaussian source
being the “least compressable” [39, Prob. 10.8 and Th. 10.4.1], [38, Prob.
3.18, Ch. 3.9].

The scheme that we use is almost identical to Scheme 1, except the boundary
condition which is not 0 for all $t$ but rather improves according to (48).

######  Scheme 3.

Transmitter initialization. The transmitter (node 0) sets the given
${{{\hat{S}}}_{0}\left(t\right)}$ for all $t\in\mathbb{Z}_{\geq 0}$.

The rest of the scheme (initialization of nodes $r\in\mathbb{N}$, estimation
at nodes $r\in\mathbb{N}$, transmission by nodes $r\in\mathbb{Z}_{\geq 0}$) is
exactly as Scheme 1.

The power-normalization constant ${{\beta}_{r}\left(t\right)}$ and the LMMSE
constant ${{\gamma}_{r}\left(t\right)}$ are set according to (29).

######  Remark 8.

One may wonder, why the transmitter does not apply preprocessing, estimating
the source from its inputs. Indeed, due to the Markov structure, the best
estimate of $S$ from ${{{\hat{S}}}_{0}\left(0:t\right)}$ only depends on
${{{\hat{S}}}_{0}\left(t\right)}$. There may still be a scalar function, e.g.,
scaling by a factor, that would improve the estimate; we assume that it is
already applied before the estimate is given to the transmitter.

In the following theorem, we evaluate the asymptotic behavior of the MSE for a
fixed velocity. Namely, we fix some velocity $v>0$, set time
$t=\left\lfloor{t/v}\right\rfloor$, and consider the MSE sequence as a
function of relay $r$.

######  Theorem 4.

Let $v>0$ be some fixed velocity. Then, the MSE of Scheme 3 satisfies

$\displaystyle{\mathrm{MSE}_{r}\left(\left\lfloor{\frac{r}{v}}\right\rfloor\right)}\leq{\operatorname{exp}\left\\{-rE_{S}(v)+o(r)\right\\}},$
(49)

where the correction term is independent of $v$,

$\displaystyle
E_{S}(v)=\begin{cases}\frac{1}{1-\eta}{\mathbb{D}\left(1-\eta\middle\|\bar{P}\right)}+2R\left(\frac{1}{v}-\frac{\eta}{1-\eta}\right),&0\leq
v\leq\frac{1-\eta}{\eta};\\\
\frac{1}{\bar{v}}{\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)},&\frac{1-\eta}{\eta}<v\leq
P;\\\ 0,&P<v;\end{cases}$ (50)

and
$\eta\triangleq(1-\bar{P})\cdot{\operatorname{exp}\left\\{2R\right\\}}={\operatorname{exp}\left\\{-2(C-R)\right\\}}$
as in (11).

The proof appears in Appendix D. It is similar to the proofs of Lemma 2 and
Theorem 1, as the MSE recursion is the same. However, the initial conditions
for the MSE are different. In the first region of (50), the initial error at
the transmitter node is (exponentially) dominant, while, in the second region,
the lack of any source knowledge at the relay nodes at $t=0$ is dominant and
the exponent is identical to $E_{1}(v)$ (34).

The result in Theorem 4 means that, for any $v<P$, the MSE of the source
sample goes to zero for an exponentially decaying boundary condition (48).
That is, the “reconstruction velocity” is the same as it were with full a
priori source knowledge (Section IV).

Figure 3: Successively refined source: The achievable MSE exponent. The plot
depicts the exponent as a function of velocity, at fixed SNR $P=10$, as a
function of the refinement rate $R$. The upper curve is $E_{1}(v)$, which is
$E_{S}(v)$ for any rate above the capacity $C=\log(11)/2\cong 1.2$ nats. Below
one sees the first region of the exponent at rates $1$, $0.5$ and $0.1$ nats
(from upper to lower curves); in the second region ($\frac{1-\eta}{\eta}\leq
v\leq P$) the exponent equals $E_{1}(v)$.

As the rate grows, the exponent $E_{S}(v)$ becomes the exponent with full
source knowledge at the transmitter at $t=0$, $E_{1}(v)$ (34). This is to be
expected, as, in the limit $R\to\infty$, the initial MSE drops immediately.
Moreover, for all $R\geq C$, the exponents are already equal, as the first
region of (50) is empty in that limit. See Figure 3.

Another way to consider $E_{S}(v)$, evident in Figure 3, is the following.
Clearly, even at zero velocity, any exponent above $2R$ is not achievable, as
this is the exponent at which the transmitter node learns the source. Then,
the exponent in the first region is the tangent to $E_{1}(v)$ at
$v=\frac{1-\eta}{\eta}$, originating at $E_{S}(0)=2R$.

###  VI-B Packet Streaming

We now finally reach our target scenario as described in Section II. We
combine the PAM mapping with the successively-refined source scheme, as
follows. Recall that at time $t=\tau T$ for $\tau\in\mathbb{Z}_{\geq 0}$ the
packet $\tau$ is made available at the transmitter. Thus, at time $t=\tau T$
it has access to bits $B\left(0:\tau\ell-1\right)$. By (35), the transmitter
can then map these bits to the corresponding MAP constellation point

$\displaystyle
S^{\tau\ell}=\sqrt{3}\sum_{i=0}^{\tau\ell-1}(-1)^{B\left(i\right)}2^{-(i+1)}.$
(51)

As in Section V, we define $S$ to be the infinite-constellation limit:

$\displaystyle S$
$\displaystyle=\lim_{\ell\rightarrow\infty}S^{\ell}=\lim_{\tau\rightarrow\infty}S^{\tau\ell};$
(52)

recall that $S$ has zero mean and unit variance. Clearly, the nested
constellations have all zero mean, and they form a Markov chain
$S^{0}\leftrightarrow S^{\ell}\leftrightarrow S^{2\ell}\leftrightarrow
S^{3\ell}\leftrightarrow\ldots\leftrightarrow S$. Furthermore, they form the
LMMSE (even MMSE) estimates of $S$ given the available bits, since the
resulting estimation error $S-S^{\tau\ell}$ is independent of
$B\left(0:\tau\ell-1\right)$. Thus, we can use Scheme 3 for the successively
refined source $S$, with $S^{k\ell}$ taking the role of
${{{\hat{S}}}_{0}\left(\ell\right)}$, as follows.

######  Scheme 4.

  1. 1.

At instants $t=\tau T$ for $\tau\in\mathbb{Z}_{\geq 0}$, the transmitter maps
$B\left(0:\tau\ell-1\right)$ to $S^{\tau\ell}$ according to (51) and updates
${{{\hat{S}}}_{0}\left(\tau T\right)}={{{\hat{S}}}_{0}\left(\tau
T+1\right)}={{{\hat{S}}}_{0}\left(\tau
T+2\right)}=\cdots={{{\hat{S}}}_{0}\left((\tau+1)T-1\right)}$.

  2. 2.

The transmitter and relays apply Scheme 3 with respect to the (virtual) source
$S$ (52).

  3. 3.

At each time step $t\in\mathbb{Z}_{\geq 0}$, each relay (node $r$ for
$r\in\mathbb{N}$) estimates the hitherto generated bits
$B\left(0:\left(\left\lfloor{\frac{t}{T}}\right\rfloor+1\right)\ell-1\right)$
from ${{{\hat{S}}}_{r}\left(t\right)}$.

######  Remark 9.

${{{\hat{S}}}_{0}\left(t\right)}$ follow an MSE profile in $t$ that is
strictly better (smaller) than (48) for $t\neq\tau T$ with
$\tau\in\mathbb{Z}_{\geq 0}$, and satisfies (48) with equality for $t=\tau T$.
Thus, Scheme 4 can be improved. However, the gain from such an improvement
becomes negligible in the limit of large $t$.

We can now invoke the MSE of Theorem 4 and the bound on the error probability
of Lemma 5, which holds uniformly for all packet sizes, to obtain the
following.

######  Lemma 6.

In Scheme 3 above, for any average rate $R>0$ and for all $v<P$,

$\displaystyle
P_{e}\left(r,\left\lfloor{\frac{r}{v}}\right\rfloor\right)\leq{\operatorname{exp}\left\\{-\inf_{t_{0}\in\mathbb{Z}_{\geq
0}}\left[\frac{t_{0}+\Delta}{2v}E_{S}\left(\frac{v\Delta}{t_{0}+\Delta}\right)-t_{0}R\right]+o(r)\right\\}},$
(53)

where the worst-bit error probability $P_{e}\left(r,\Delta\right)$ was defined
in (13), and $E_{S}(\cdot)$ is given by (50).

The proof appears in Appendix E. It is based upon combining the MSE bound of
Theorem 4 with the error-probability bound of Lemma 5. We note that, in
Theorem 4, the velocity is measured from time $0$, while in the definition of
$P_{e}\left(r,\Delta\right)$ in (13), the velocity of a particular packet is
measured with respect to the elapsed time since its generation. Since each
packet is generated at a different time, at a particular node $r$ at a
particular time $t$, each packet has a different velocity for the purpose of
$P_{e}\left(r,\Delta\right)$. Hence, the key step in the proof of Lemma 6 is
translating the bound of Theorem 4 using an affine transformation of the
velocity.

Having proved this, we are ready to state our main result.

######  Theorem 5.

Let $R<C$ be some average rate (7) where $C\triangleq\frac{1}{2}\log(1+P)$ as
in (10). Then, the streaming IV is bounded from below as

$\displaystyle\mathrm{V}(R)\geq{\operatorname{exp}\left\\{2(C-R)\right\\}}-1.$
(54)

The proof appears in Appendix E. It is based upon substituting $E_{S}(v)$ (50)
in the result of Lemma 6. Noticing that the argument of $E_{S}(\cdot)$ in (50)
is at most $v$, for $v$ below the claimed bound we always take the first
region in (50) which gives the desired positive error exponent (it becomes
independent of $t_{0}$ after the substitution, making the minimization
redundant).

######  Remark 10.

For $v>{\operatorname{exp}\left\\{2(C-R)\right\\}}-1$ and large enough
$\Delta$, the argument of $E_{S}(\cdot)$ in (50) falls inside the second
region of (50) and the error exponent becomes negative; we do not provide a
proof of this fact, as it is not required for our achievability result. Hence,
we believe that the IV bound of Theorem 5 is tight for our Scheme 4.

Figure 4: Lower bound on the streaming IV as a function of the rate average
rate $R$ (7) for SNRs $P=0.1,1,10,100$ and the linear limit $P\to 0$. Relative
coordinates are used: the lower bound on the streaming IV of Theorem 5 is
normalized by the lower bound on the single-packet IV $P$ of Theorem 2,
whereas the average rate $R$ is normalized by $C$ (10).

As expected, the IV bound goes to the single-packet IV bound $P$ as the rate
goes to zero, and—to zero as the rate goes to $C$. It is also worth noting
that, for any fixed $P$, the achievable velocity is a convex function of $R$.
In the low-SNR limit $P\rightarrow 0$, the curve approaches the linear
function (See Figure 4):

$\displaystyle V(R)\cong\left(1-\frac{R}{C}\right)P.$ (55)

In the high-SNR limit, on the other hand, for any fixed $R$, our bound grows
linearly with $P$:

$\displaystyle V(R)\cong P\exp\\{-2R\\}.$ (56)

##  VII Conclusion and Extensions

We have derived achievable IV and error-probability bounds for both single-
packet and streaming communications, and exponential MSE bounds for conveying
a source sample, both when it is available upfront and when it is revealed
successively to the transmitter.

In Table I, we summarize our main results, and translate them to the setting
of delayed hops, which may be more familiar to some of the readers. The
translation is immediate, by a linear transformation of the velocity: if the
velocity with instantaneous hops is $v$, then with delayed hops it becomes
$\bar{v}=v/(1+v)$, and in particular it is at most $1$. We have not included
the results on decoding error probability which are longer, but they may be
translated in the same way.

Setting | Reference | Quantity | Instantaneous Hops | Delayed Hops
---|---|---|---|---
| Single source
---
sample
Thm. 1 | MSE exponent | $\begin{array}[]{l}\text{For }v\in\left[0,P\right):\\\ \quad\frac{1}{\bar{v}}{\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)}\end{array}$ | $\begin{array}[]{l}\text{For }v\in\left[0,\bar{P}\right):\\\ \quad\frac{1}{v}{\mathbb{D}\left(v\middle\|\bar{P}\right)}\end{array}$
| Single data
---
packet
Thm. 2 |  | single-packet
---
IV
$P$ | $\bar{P}$
| Successively-refined
---
source
Thm. 4 | MSE exponent | $\begin{array}[]{l}\text{For }v\in\left[0,\frac{1-\eta}{\eta}\right):\\\ \quad\frac{1}{1-\eta}{\mathbb{D}\left(1-\eta\middle\|\bar{P}\right)}\\\ \hfill+2\left(\frac{1}{v}-\frac{\eta}{1-\eta}\right)R\\\ \text{For }v\in\left[\frac{1-\eta}{\eta},P\right):\\\ \qquad\frac{1}{\bar{v}}{\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)}\end{array}$ | $\begin{array}[]{l}\text{For }v\in\left[0,\eta\right):\\\ \quad\frac{1}{1-\eta}{\mathbb{D}\left(1-\eta\middle\|\bar{P}\right)}\\\ \hfill+2\left(\frac{\bar{v}}{1-\bar{v}}-\frac{\eta}{1-\eta}\right)R\\\ \text{For }v\in\left[\eta,\bar{P}\right):\\\ \qquad\frac{1}{v}{\mathbb{D}\left(v\middle\|\bar{P}\right)}\end{array}$
Packet streaming | Thm. 5 | Streaming IV | $\frac{1-\eta}{\eta}$ | $1-\eta$
TABLE I: Summmary of main results, and their translation to delayed hops.
Recall that $\bar{P}=P/(1+P)$, $\bar{v}=v/(1+v)$ and
$\eta=(1-\bar{P})\exp\\{2R\\}={\operatorname{exp}\left\\{-2(C-R)\right\\}}$.

This work raises many interesting directions for further research. First, we
have only presented achievability results. We believe that our analysis is
tight for linear schemes, but is it possible to improve them using a different
approach? Specifically, it seems plausible that no positive IV is possible for
rates $R>C$, but we are less certain about the IV at lower rates.

Secondly, our analysis presents a rather wide framework that allows for
variations. For conveying a source, we considered one that is either known
from the start or conveyed at a constant refinement rate; the MSE recursion
was the same, and only the initial conditions differed. Other scenarios,
including variable-rate refinement and side information of various types in
relays along the way may be treated under the same framework. The same holds
for data packet settings.

Lastly, in this work we have assumed perfect feedback. Such feedback is not
practical. In particular, in a line network it does not make sense that, all
along a line network, the backward channels enjoy much better conditions than
the forward ones. Extending our results to settings with noisy feedback is of
major interest. The feedback scheme may be linear, or using modulo-lattice
modulation as Ben-Yishai and Shayevitz suggested for a single channel [40].

##  Appendix A Proofs for Section IV

We start with two auxiliary lemmas that will be used in the sequel. They refer
to an generalized Scheme 1, in which the estimator
${{{\hat{S}}}_{r}\left(t\right)}$ at node $r\in\mathbb{N}$ at time
$t\in\mathbb{N}$ is taken to be the LMMSE estimator of $S$ from its entire
measurement history ${Y_{r-1}\left(0:t\right)}$; we will prove that
${{{\hat{S}}}_{r}\left(t\right)}$ is of the form of (23) (part 1 of Lemma 1).
We denote the estimation error by

$\displaystyle{\mathcal{E}_{r}\left(\tau\right)}\triangleq
S-{{{\hat{S}}}_{r}\left(\tau\right)}.$ (57)

######  Lemma 7.

In the generalized Scheme 1, the outputs of the same channel at different
times are uncorrelated, viz.
${\mathrm{Cov}\left({Y_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}=0$
for $t\neq\tau$.

Proof: Assume without loss of generality that $0\leq\tau<t$. Then,

$\displaystyle\\!{\mathrm{Cov}\left({Y_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}\stackrel{{\scriptstyle(a)}}{{=}}{\mathrm{Cov}\left({X_{r}\left(t\right)}+{Z_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}\stackrel{{\scriptstyle(b)}}{{=}}{\mathrm{Cov}\left({X_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}$
(58a) $\displaystyle\ \
\stackrel{{\scriptstyle(c)}}{{=}}{\mathrm{Cov}\left(\beta_{r}(t)\left[{{{\hat{S}}}_{r}\left(t\right)}-{{{\hat{S}}}_{r+1}\left(t-1\right)}\right],{Y_{r}\left(\tau\right)}\right)}\stackrel{{\scriptstyle(d)}}{{=}}{\mathrm{Cov}\left(\beta_{r}(t)\left[{\mathcal{E}_{r+1}\left(t-1\right)}-{\mathcal{E}_{r}\left(t\right)}\right],{Y_{r}\left(\tau\right)}\right)}$
$\displaystyle\ \
\stackrel{{\scriptstyle(e)}}{{=}}\beta_{r}(t)\left[{\mathrm{Cov}\left({\mathcal{E}_{r+1}\left(t-1\right)},{Y_{r}\left(\tau\right)}\right)}-{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}\right],$
(58b)

where $(a)$ follows from (8), $(b)$ holds since ${Z_{r}\left(t\right)}$ is
independent of ${Y_{r}\left(0:t-1\right)}$ and hence uncorrelated with its
entries, $(c)$ follows from (24), $(d)$ follows from adding and subtracting
$S$ and (57), and $(e)$ follows from the bilinearity of the covariance.

Now, to complete the proof, we prove that both of the resulting elements equal
zero as follows.

  1. 1.

Since ${\mathcal{E}_{r+1}\left(t-1\right)}$ is the LMMSE estimation error
given ${Y_{r}\left(0:t-1\right)}$, by the orthogonality principle [36, Ch.
7-3],
${\mathrm{Cov}\left({\mathcal{E}_{r+1}\left(t-1\right)},{Y_{r}\left(0:t-1\right)}\right)}=0$.
In particular, since $\tau\leq t-1$,
${\mathrm{Cov}\left({\mathcal{E}_{r+1}\left(t-1\right)},{Y_{r}\left(\tau\right)}\right)}=0$.

  2. 2.

${Y_{r}\left(\tau\right)}$ is a linear combination of
${Y_{r-1}\left(0:\tau\right)}$ and $Z_{r}(0:\tau)$. By the orthogonality
principle,
${\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{Y_{r-1}\left(0:t\right)}\right)}$.
${\mathcal{E}_{r}\left(t\right)}$ is independent of (and hence uncorrelated
with) the noise process $Z_{r}$ of the subsequent channel. Since $\tau\leq
t-1$,
${\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{Y_{r}\left(\tau\right)}\right)}=0$.
∎

######  Lemma 8.

In the generalized Scheme 1,

$\displaystyle{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{\mathcal{E}_{r+1}\left(t-1\right)}\right)}$
$\displaystyle={\mathrm{Var}\left({\mathcal{E}_{r}\left(t\right)}\right)}$
$\displaystyle\forall r,t\in\mathbb{Z}_{\geq 0}.$ (59)

###### Proof:

$\begin{aligned}
{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{\mathcal{E}_{r+1}\left(t-1\right)}\right)}&\stackrel{{\scriptstyle(a)}}{{=}}{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},S-{{{\hat{S}}}_{r+1}\left(t-1\right)}\right)}\stackrel{{\scriptstyle(b)}}{{=}}{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},S\right)}\\\
&\stackrel{{\scriptstyle(c)}}{{=}}{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{{{\hat{S}}}_{r}\left(t\right)}+{\mathcal{E}_{r}\left(t\right)}\right)}\stackrel{{\scriptstyle(d)}}{{=}}{\mathrm{Var}\left({\mathcal{E}_{r}\left(t\right)}\right)}\end{aligned}$

where $(a)$ and $(c)$ follow from (57); and $(b)$ and $c$ follow from
${\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{Y_{r-1}\left(0:t\right)}\right)}$
and
${\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{Y_{r-1}\left(0:t\right)}\right)}=0$,
respectively, which were proved at the end of the proof of Lemma 7, by noting
that ${{{\hat{S}}}_{r+1}\left(t-1\right)}$ and
${{{\hat{S}}}_{r}\left(t\right)}$ are linear combinations of
${Y_{r}\left(0:t-1\right)}$ and ${Y_{r-1}\left(t\right)}$, respectively. ∎

Proof of Lemma 1:

  1. 1.

Consider ${{{\hat{S}}}_{r}\left(t\right)}$ for $r\in\mathbb{N}$ of the
generalized Scheme 1. By Lemma 7, the entries of ${Y_{r-1}\left(0:t\right)}$
are uncorrelated, meaning that the LMMSE estimator
${{{\hat{S}}}_{r}\left(t\right)}$ equals

$\displaystyle{{{\hat{S}}}_{r}\left(t\right)}=\sum_{\tau=0}^{t}\frac{{\mathrm{Cov}\left(S,{Y_{r-1}\left(\tau\right)}\right)}}{{\mathrm{Var}\left({Y_{r-1}\left(\tau\right)}\right)}}\cdot{Y_{r-1}\left(\tau\right)}=\sum_{\tau=0}^{t}\frac{{\mathrm{Cov}\left(S,{X_{r-1}\left(\tau\right)}\right)}}{1+{\mathrm{Var}\left({X_{r-1}\left(\tau\right)}\right)}}\cdot{Y_{r-1}\left(\tau\right)},$
(60)

where the second equality follows from (8), the independence of $S$ and the
process $Y_{r-1}$, and
${\mathrm{Var}\left({Z_{r-1}\left(\tau\right)}\right)}=1$ for all $\tau$. Eq.
(60) suggests the following recursive form:

$\displaystyle{{{\hat{S}}}_{r}\left(t\right)}={{{\hat{S}}}_{r}\left(t-1\right)}+\frac{{\mathrm{Cov}\left(S,{X_{r-1}\left(t\right)}\right)}}{1+{\mathrm{Var}\left({X_{r-1}\left(t\right)}\right)}}\cdot{Y_{r-1}\left(\tau\right)}={{{\hat{S}}}_{r}\left(t-1\right)}+{{\gamma}_{r}\left(t\right)}{Y_{r-1}\left(\tau\right)},$
(61)

where the second equality follows from (25).

This proves that Scheme 1 and the generalized Scheme 1 are in fact identical.

  2. 2.

Follows immediately from the proof of part 1 of the lemma and from Lemma 7.

  3. 3.

By (24),
${\mathrm{Cov}\left(S,{X_{r}\left(t\right)}\right)}={{\beta}_{r}\left(t\right)}\left\\{{\mathrm{Cov}\left(S,{{{\hat{S}}}_{r}\left(t\right)}\right)}-{\mathrm{Cov}\left(S,{{{\hat{S}}}_{r+1}\left(t-1\right)}\right)}\right\\}$.
Substituting

$\displaystyle{\mathrm{Cov}\left(S,{{{\hat{S}}}_{r}\left(t\right)}\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}{\mathrm{Cov}\left(S,S\right)}-{\mathrm{Cov}\left(S,{\mathcal{E}_{r}\left(t\right)}\right)}\stackrel{{\scriptstyle(b)}}{{=}}{\mathrm{Var}\left(S\right)}-{\mathrm{Cov}\left({{{\hat{S}}}_{r}\left(t\right)}+{\mathcal{E}_{r}\left(t\right)},{\mathcal{E}_{r}\left(t\right)}\right)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}{\mathrm{Var}\left(S\right)}-{\mathrm{Var}\left({\mathcal{E}_{r}\left(t\right)}\right)}\stackrel{{\scriptstyle(d)}}{{=}}{\mathrm{Var}\left(S\right)}-{\mathrm{MSE}_{r}\left(t\right)},$
(62)

the proof follows, where $(a)$ and $(b)$ hold by the definition of
${\mathcal{E}_{r}\left(t\right)}$ (57), $(c)$ follows from the orthogonality
principle, and $(d)$ hold by the definition of
${\mathrm{MSE}_{r}\left(t\right)}$ (15) and (57).

  4. 4.

$\begin{aligned}
{\mathrm{Var}\left({X_{r}\left(t\right)}\right)}&\stackrel{{\scriptstyle(a)}}{{=}}\beta^{2}_{r}\left(t\right){\mathrm{Cov}\left({{{\hat{S}}}_{r}\left(t\right)}-{{{\hat{S}}}_{r+1}\left(t-1\right)},{{{\hat{S}}}_{r}\left(t\right)}-{{{\hat{S}}}_{r+1}\left(t-1\right)}\right)}\\\
&\stackrel{{\scriptstyle(b)}}{{=}}\beta^{2}_{r}\left(t\right){\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)}-{\mathcal{E}_{r+1}\left(t-1\right)},{\mathcal{E}_{r}\left(t\right)}-{\mathcal{E}_{r+1}\left(t-1\right)}\right)}\\\
&\stackrel{{\scriptstyle(c)}}{{=}}\beta^{2}_{r}\left(t\right)\left[{\mathrm{Var}\left({\mathcal{E}_{r}\left(t\right)}\right)}+{\mathrm{Var}\left({\mathcal{E}_{r+1}\left(t-1\right)}\right)}-2{\mathrm{Cov}\left({\mathcal{E}_{r}\left(t\right)},{\mathcal{E}_{r+1}\left(t-1\right)}\right)}\right]\\\
&\stackrel{{\scriptstyle(d)}}{{=}}\beta^{2}_{r}\left(t\right)\left[{\mathrm{Var}\left({\mathcal{E}_{r}\left(t\right)}\right)}-{\mathrm{Var}\left({\mathcal{E}_{r+1}\left(t-1\right)}\right)}\right],\end{aligned}$

where $(a)$ follows from (24), $(b)$ follows from (57), and $(d)$ follows from
Lemma 8. ∎

###### Proof:

${\mathrm{MSE}_{r}\left(t\right)}\stackrel{{\scriptstyle(i)}}{{=}}1-\sum_{\tau=1}^{t}\frac{{\mathrm{Cov}^{2}\left(S,{Y_{r-1}\left(\tau\right)}\right)}}{{\mathrm{Var}\left({Y_{r-1}\left(\tau\right)}\right)}}\stackrel{{\scriptstyle(ii)}}{{=}}1-\sum_{\tau=1}^{t}\frac{{\mathrm{Cov}^{2}\left(S,{X_{r-1}\left(\tau\right)}\right)}}{P+1}$,
where $(i)$ follows from the LMMSE expression [36, Eq. (7-85)] and parts 1 and
2 of Lemma 1; and $(ii)$ follows from (8), the independence of $S$ and the
unit-variance noise process $Z_{r-1}$, and by choosing
$\left\\{{{\beta}_{r-1}\left(\tau\right)}\middle|\tau\in\mathbb{Z}_{\geq
0}\right\\}$ such that
$\left\\{{X_{r-1}\left(\tau\right)}\middle|\tau\in\mathbb{Z}_{\geq
0}\right\\}$ satisfies the power constraint (9) with equality. This can be
rewritten recursively as

$\displaystyle{\mathrm{MSE}_{r}\left(t-1\right)}-{\mathrm{MSE}_{r}\left(t\right)}$
$\displaystyle=\frac{{\mathrm{Cov}^{2}\left(S,{X_{r-1}\left(t\right)}\right)}}{P+1}\stackrel{{\scriptstyle(a)}}{{=}}\beta^{2}_{r-1}\left(t\right)\cdot\frac{[{\mathrm{MSE}_{r}\left(t-1\right)}-{\mathrm{MSE}_{r-1}\left(t\right)}]^{2}}{P+1}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\bar{P}\cdot\left[{\mathrm{MSE}_{r}\left(t-1\right)}-{\mathrm{MSE}_{r-1}\left(t\right)}\right],$
(63)

where $(a)$ follows from part 3 of Lemma 1, and $(b)$ follows from (29a). This
proves (31).

We next solve the recursion (31) explicitly. Due to the linearity of the
recursion, ${\mathrm{MSE}_{r}\left(t\right)}$ equals the sum of the effects of
all initial conditions ${\mathrm{MSE}_{k}\left(-1\right)}=1$ for $1\leq k\leq
r$ (the zero boundary conditions ${\mathrm{MSE}_{0}\left(t\right)}=0$ have
zero effect). Consider all the trajectories from $(k,-1)$ to $(r,t)$, where at
each step along the trajectory either the time index increases by
$1$—corresponding to a multiplication by $1-\bar{P}$, or the relay index
increases by 1—corresponding to a multiplication the MSE by $\bar{P}$. There
are $t+1$ time steps and $r-k$ relay steps. Multiplying by the combinatorial
expression for the number of trajectories, we have that the effect of a single
condition is

$\displaystyle\binom{t+r-k}{r-k}(1-\bar{P})^{t+1}\bar{P}^{r-k}.$ (64)

Eq. (32) then follows by summing over all relevant $k$. ∎

###### Proof:

The claim is trivial for $v\geq P$ since
${\mathrm{MSE}_{r}\left(t\right)}\leq{\mathrm{Var}\left(S\right)}=1$. Thus, we
assume $v<P$ and bound the LMMSE at node $r\in\mathbb{N}$ at time
$t\in\mathbb{Z}_{\geq 0}$ as follows.

$\displaystyle{\mathrm{MSE}_{r}\left(t\right)}$
$\displaystyle=(1-\bar{P})\sum_{k=1}^{r}\binom{t+r-k}{r-k}{\operatorname{exp}\left\\{-(t+r-k)\left[{\mathbb{D}\left(\frac{r-k}{t+r-k}\middle\|\bar{P}\right)}+h\left(\frac{t}{t+r-k}\right)\right]\right\\}}$
(65)
$\displaystyle\leq{\operatorname{exp}\left\\{-\min_{k\in\left\\{1,2,\ldots,r\right\\}}(t+r-k){\mathbb{D}\left(\frac{r-k}{t+r-k}\middle\|\bar{P}\right)}+\log
r\right\\}},$ (66)

where the equality follows from (32) from Lemma 2 and the definitions of
$h\left(\cdot\right)$ and ${\mathbb{D}\left(\cdot\middle\|\cdot\right)}$ (5),
and the inequality follows from bounding the average by the maximum and from
[39, Ch. 11.1]

$\displaystyle{n\choose
i}\leq{\operatorname{exp}\left\\{-n\,h\left(\frac{i}{n}\right)\right\\}}.$
(67)

By taking $t=\left\lfloor{r/v}\right\rfloor$ as in the theorem statement and
defining $\lambda\triangleq\frac{r-k}{t}$, we have

$\displaystyle{\mathrm{MSE}_{r}\left(\left\lfloor{\frac{r}{v}}\right\rfloor\right)}$
$\displaystyle\leq{\operatorname{exp}\left\\{-\left\lfloor{\frac{r}{v}}\right\rfloor\inf_{\lambda\in(0,v)}(1+\lambda){\mathbb{D}\left(\frac{\lambda}{1+\lambda}\middle\|\bar{P}\right)}+\log
r\right\\}}$ (68a)
$\displaystyle\leq{\operatorname{exp}\left\\{-\left(\frac{r}{v}-1\right)(1+v){\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)}+\log
r\right\\}}$ (68b)
$\displaystyle\leq{\operatorname{exp}\left\\{-\frac{r}{\bar{v}}{\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)}-(1+P)\log{\bar{P}}+\log
r\right\\}},$ (68c)

where the second inequality holds since the expression in the infimum is
monotonically decreasing in $\lambda$ (for $v<P$) and by using
$\bar{v}=\frac{v}{1+v}$ (3) and $\left\lfloor{r/v}\right\rfloor\geq r/v-1$.
The last inequality holds since
${\mathbb{D}\left(\bar{v}\middle\|\bar{P}\right)}\leq-\log{\bar{P}}$ for all
$v<P$. ∎

##  Appendix B Proof of Lemma 4

To prove Lemma 4, we first introduce auxiliary definitions and results.

We will make use of the following notion of sub-Gaussianity as it appears in
[41, Ch. 2.1].666Other definitions that are equivalent up to constants exist,
e.g., in [42, Ch. 2.5].

######  Definition 1.

An RV $X$ with mean $\mu=\mathbb{E}\left[X\right]$ is sub-Gaussian with
variance proxy $\sigma^{2}\left(X\right)>0$ if

$\displaystyle\mathbb{E}\left[{\operatorname{exp}\left\\{\lambda(X-\mu)\right\\}}\right]$
$\displaystyle\leq{\operatorname{exp}\left\\{\frac{\sigma^{2}\left(X\right)\lambda^{2}}{2}\right\\}}$
$\displaystyle\forall\lambda\in\mathbb{R}.$ (69)

Clearly, if $X$ is sub-Gaussian with variance proxy
$\sigma^{2}\left(X\right)$, it is also sub-Gaussian with any variance proxy
greater than $\sigma^{2}\left(X\right)$. The following well-known properties
follow immediately from Definition 1 and Chernoff’s bound.

######  Property 1.

  1. 1.

A Gaussian RV $X$ with variance $\sigma^{2}$ is sub-Gaussian with
$\sigma^{2}\left(X\right)=\sigma^{2}$.

  2. 2.

A Rademacher RV (uniformly distributed over $\left\\{\pm 1\right\\}$) $X$ is
sub-Gaussian with $\sigma^{2}\left(X\right)=1$.

  3. 3.

Let $X_{1},\ldots,X_{n}$ be independent sub-Gaussian RVs with variance proxies
$\sigma^{2}_{1},\ldots,\sigma^{2}_{n}$, respectively. Let
$a_{1},\ldots,a_{n}\in\mathbb{R}$ be some constants. Then,
$\sum\limits_{i=1}^{n}a_{i}X_{i}$ is sub-Gaussian with
$\sum\limits_{i=1}^{n}a_{i}^{2}\sigma_{i}^{2}$.

  4. 4.

Chernoff–Hoeffding bound: Let $X$ be a zero-mean sub-Gaussian RV with variance
proxy $\sigma^{2}\left(X\right)>0$, and let $a$ be some positive constant.
Then,

$\displaystyle\Pr\left(\left|X\right|\geq a\right)\leq
2{\operatorname{exp}\left\\{-\frac{a^{2}}{2\sigma^{2}\left(X\right)}\right\\}}.$
(70)

We now return to Scheme 2 and prove the following property on
${\mathcal{E}^{\ell}_{r}\left(t\right)}$ of (38).

######  Lemma 9.

${\mathcal{E}^{\ell}_{r}\left(t\right)}$ is sub-Gaussian with variance proxy
that satisfies
$\sigma^{2}\left({\mathcal{E}^{\ell}_{r}\left(t\right)}\right)\leq{\mathrm{MSE}_{r}\left(t\right)}$.

###### Proof:

The inputs to the overall system are the noise samples
$\left\\{{Z_{r}\left(t\right)}\middle|r,t\in\mathbb{Z}_{\geq 0}\right\\}$ and
$S^{\ell}$, all of which are independent. The noise samples are Gaussian,
whereas $S^{\ell}$ equals a linear combination of independent Rademacher RVs
by (35) (which are also independent of the Gaussian noise samples), and hence
also ${\mathcal{E}^{\ell}_{r}\left(t\right)}$. By parts 1 and 2 of Property 1,
for all the elements in the linear combination, the variance proxy equals the
variance, while by part 3 the same holds for
${\mathcal{E}^{\ell}_{r}\left(t\right)}$. Thus,
${\mathcal{E}^{\ell}_{r}\left(t\right)}$ is sub-Gaussian with

$\displaystyle\sigma^{2}\left({\mathcal{E}^{\ell}_{r}\left(t\right)}\right)=\mathbb{E}\left[\left\\{{\mathcal{E}^{\ell}_{r}\left(t\right)}\right\\}^{2}\right]\leq{\mathrm{MSE}_{r}\left(t\right)},$
(71)

where the inequality follows from (39). ∎

###### Proof:

$\begin{aligned}
{\epsilon}_{r}\left(0:\ell\middle|t\right)&\stackrel{{\scriptstyle(a)}}{{\leq}}\Pr\left(\left|{\mathcal{E}^{\ell}_{r}\left(t\right)}\right|>d_{\ell}/2\right)\stackrel{{\scriptstyle(b)}}{{\leq}}2{\operatorname{exp}\left\\{-\frac{d_{\ell}^{2}/4}{2{\mathrm{MSE}_{r}\left(t\right)}}\right\\}}\\\
&\stackrel{{\scriptstyle(c)}}{{\leq}}2{\operatorname{exp}\left\\{-\frac{3}{2^{2\ell+1}\cdot{\mathrm{MSE}_{r}\left(t\right)}}\right\\}},\end{aligned}$

where ${(a)}$ follows from (41a), $(b)$ follows from the Chernoff–Hoeffding
bound (recall Property 1) and Lemma 9, and $(c)$ follows from (36). ∎

##  Appendix C Proof of Lemma 5

To make the analysis devoid of $\ell$, we will analyze the error probability
of $S^{n}$ in the infinite-constellation limit $S$ (37). Due to the linearity
of all the components of the scheme until the final decoding of the bits, one
can always attain the performance of decoding $S^{n}$ from a finite-
constellation $\ell\in\mathbb{N}$ by adding, to the term that is proportional
to $S^{\ell}$ in the decoding error, a uniform noise $U^{\ell}$ over
$[-d_{\ell}/2,d_{\ell}/2)$ that is independent of $S^{\ell}$ with the same
coefficient, such that $S$ is uniform over $[-\sqrt{3},\sqrt{3})$:

$\displaystyle S=S^{\ell}+U^{\ell},$ (72)

with $S^{\ell}$ as in (35) and

$\displaystyle
U^{\ell}=\sqrt{3}\sum_{i=\ell}^{\infty}(-1)^{B\left(i\right)}2^{-(i+1)};$ (73)

this will be be made precise in the sequel in (77).

Similarly, the decomposition (72) applies for any $n$:

$\displaystyle S=S^{n}+U^{n},$ (74)

where $U^{n}$ is given in (73) with $\ell$ replaced by $n$, it is independent
of $S^{n}$ and is uniformly distributed over $[-d_{n}/2,d_{n}/2)$ with

$\displaystyle d_{n}=\sqrt{3}\cdot 2^{-n+1}$ (75)

being the spacing between two constellation levels of $S^{n}$, in agreement
with (36).

Now notice that in Scheme 1, the estimate of $S^{\ell}$ at node
$r\in\mathbb{N}$ at time $t\in\mathbb{Z}_{\geq 0}$, is given by

$\displaystyle{{\hat{S}}^{\ell}_{r}\left(t\right)}={{\alpha}_{r}\left(t\right)}\cdot
S^{\ell}+{Z^{\mathrm{eff}}_{r}\left(t\right)},$ (76)

where ${Z^{\mathrm{eff}}_{r}\left(t\right)}$ is a combination of channel
noises, independent of $S^{\ell}$, and by the properties of MMSE estimation
(recall Lemma 1) ${{\alpha}_{r}\left(t\right)}\in(0,1)$. By (72), adding
${{\alpha}_{r}\left(t\right)}U^{\ell}$ to
${{\hat{S}}^{\ell}_{r}\left(t\right)}$ results in

$\displaystyle{{{\hat{S}}}_{r}\left(t\right)}={{\alpha}_{r}\left(t\right)}\cdot
S+{Z^{\mathrm{eff}}_{r}\left(t\right)}.$ (77)

To bound the error probability of decoding $S^{n}$ at node $r$ at time $t$, we
will analyze a suboptimal decoder that

  1. 1.

generates the estimate ${{\hat{S}}^{\ell}_{r}\left(t\right)}$ of step 3 of
Scheme 2;

  2. 2.

generates a randomly generated noise $U^{\ell}$ as in (73), which is uniformly
distributed over $[-d_{\ell}/2,d_{\ell}/2)$ and is independent of $S^{\ell}$
and $\left\\{{Z_{r}\left(t\right)}\right\\}$;

  3. 3.

adds ${{\alpha}_{r}\left(t\right)}U^{\ell}$ to
${{\hat{S}}^{\ell}_{r}\left(t\right)}$ [recall (76)] to generate
${{{\hat{S}}}_{r}\left(t\right)}$ of (77);

  4. 4.

decodes $S^{n}$ from ${{{\hat{S}}}_{r}\left(t\right)}$ using a nearest-
neighbor decoder (slicer) of $S^{n}$.

The prefix error probability of $S^{n}$ is bounded from above as follows.

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|t\right)$
$\displaystyle\leq\Pr\left(\left|S^{n}-{{{\hat{S}}}_{r}\left(t\right)}\right|\geq
d_{n}/2\right)$ (78a)
$\displaystyle=\Pr\left(\left|(1-{{\alpha}_{r}\left(t\right)})S^{n}-{{\alpha}_{r}\left(t\right)}U^{n}-{Z^{\mathrm{eff}}_{r}\left(t\right)}\right|\geq
d_{n}/2\right)$ (78b)
$\displaystyle=\int_{-d_{n}/2}^{d_{n}/2}\frac{1}{d_{n}}\Pr\left(\left|(1-{{\alpha}_{r}\left(t\right)})S^{n}-{{\alpha}_{r}\left(t\right)}u-{Z^{\mathrm{eff}}_{r}\left(t\right)}\right|\geq
d_{n}/2\right)du$ (78c)
$\displaystyle\leq\frac{1}{d_{n}}\int_{-d_{n}/2}^{d_{n}/2}\Pr\left(\left|(1-{{\alpha}_{r}\left(t\right)})S^{n}-{Z^{\mathrm{eff}}_{r}\left(t\right)}\right|\geq
d_{n}/2-{{\alpha}_{r}\left(t\right)}\cdot\left|u\right|\right)du,$ (78d)

where (78a) follows from the nearest-neighbor decision rule and since the
values that $S^{n}$ can take are distant by at least $d_{n}$, (78b) follows
from (74) and (77), (78c) holds since $U^{n}$ is uniformly distributed over
$[-d_{n}/2,d_{n}/2)$ and is independent of
$\left({Z^{\mathrm{eff}}_{r}\left(t\right)},S^{n}\right)$, (78d) follows from
the triangle inequality by noting that $0<{{\alpha}_{r}\left(t\right)}<1$.

Now define
${\mathcal{E}^{n}_{r}\left(t\right)}=(1-{{\alpha}_{r}\left(t\right)})S^{n}-{Z^{\mathrm{eff}}_{r}\left(t\right)}$.
Note that ${\mathcal{E}^{n}_{r}\left(t\right)}$ can be interpreted as the
estimation error $S^{n}-{{\hat{S}}^{n}_{r}\left(t\right)}$ as in (38), where
${{\hat{S}}^{n}_{r}\left(t\right)}$ is the estimate of $S^{n}$ if the packet
were of size $n$. Hence, ${\epsilon}_{r}\left(0:\ell\middle|t\right)$ can be
further bounded as follows.

$\displaystyle{\epsilon}_{r}\left(0:\ell\middle|t\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{2}{d_{n}}\int_{[1-{{\alpha}_{r}\left(t\right)}]d_{n}/2}^{d_{n}/2}\Pr\left(\left|{\mathcal{E}^{n}_{r}\left(t\right)}\right|\geq
x\right)dx\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{2}{d_{n}}\int_{0}^{\infty}\Pr\left(\left|{\mathcal{E}^{n}_{r}\left(t\right)}\right|\geq
x\right)dx$ (79a)
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{2}{d_{n}}\int_{0}^{\infty}\min\left\\{1,\frac{{\mathrm{MSE}_{r}\left(t\right)}}{x^{2}}\right\\}dx\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{2}{d_{n}}\left[\int_{0}^{\sqrt{{\mathrm{MSE}_{r}\left(t\right)}}}1dx+\int_{\sqrt{{\mathrm{MSE}_{r}\left(t\right)}}}^{\infty}\frac{{\mathrm{MSE}_{r}\left(t\right)}}{x^{2}}dx\right]$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}\frac{4}{d_{n}}\sqrt{{\mathrm{MSE}_{r}\left(t\right)}}\stackrel{{\scriptstyle(f)}}{{=}}\frac{2}{\sqrt{3}}\cdot
2^{n}\cdot\sqrt{{\mathrm{MSE}_{r}\left(t\right)}}\,,$ (79b)

where $(a)$ follows from (78) by noting that the integrand is an even
function, by the definition of ${\mathcal{E}^{n}_{r}\left(t\right)}$, and by
integration by substitution with $x=\frac{d_{n}}{2}-\alpha u$; $(b)$ holds
since the integrand is non-negative (and $0<{{\alpha}_{r}\left(t\right)}<1$);
$(c)$ holds by Chebyshev’s inequality and (39) (the same argument applies here
for $n$ in lieu of $\ell$), and since the probability is trivially bounded
from above by 1; and $(f)$ follows from (75). ∎

##  Appendix D Proof of Theorem 4

When analyzing Scheme 3, all of the analysis that we applied to Scheme 1 up to
the recursion relation (31) in Lemma 2 remains valid. In particular, with the
parameters ${{\beta}_{r}\left(t\right)}$ and ${{\gamma}_{r}\left(t\right)}$ of
(29), $\\{{{{\hat{S}}}_{r}\left(t\right)}\\}$ are the LMMSE estimators from
all available channel outputs (which are uncorrelated), and the power
constraint is always satisfied with equality. To see this, one may go through
the proofs and see that the assumption on the nature of
$\\{{{{\hat{S}}}_{0}\left(t\right)}\\}$ wasn never used.

Consequently, the MSE recursion of (31) remains valid for Scheme 3, albeit
with different boundary conditions (48) [and the same initial conditions
${\mathrm{MSE}_{r}\left(-1\right)}=1$, for all $r\in\mathbb{Z}_{\geq 0}$].

We first provide an explicit expression for the MSE, parallel to (32):

$\displaystyle{\mathrm{MSE}_{r}\left(t\right)}=\mathrm{MSE}^{\text{I}}_{r}(t)+\mathrm{MSE}^{\text{II}}_{r}(t),$
(80)

where

$\displaystyle\mathrm{MSE}^{\text{I}}_{r}(t)$
$\displaystyle=\left(1-\bar{P}\right)^{t+1}\sum_{k=1}^{r}\binom{t+r-k}{r-k}\bar{P}^{r-k},$
(81) $\displaystyle\mathrm{MSE}^{\text{II}}_{r}(t)$
$\displaystyle=\bar{P}^{r}\sum_{s=0}^{t-1}{\operatorname{exp}\left\\{-2R(t-s)\right\\}}\binom{r+s-1}{s}\left(1-\bar{P}\right)^{s}.$
(82)

This MSE follows by summing the contributions of all the initial conditions,
as done when proving (32). $\mathrm{MSE}^{\text{I}}_{r}(t)$ is the sum of
contributions of the initial conditions ${\mathrm{MSE}_{r}\left(-1\right)}=1$
for $r>0$, and indeed it equals the MSE of (32).
$\mathrm{MSE}^{\text{II}}_{r}(t)$ is the sum of contributions of the boundary
conditions ${\mathrm{MSE}_{0}\left(t\right)}=1$ for $t>0$, which can be
derived in a dual way to the first contribution, substituting the roles as
follows: $r\rightarrow t$, $t\rightarrow r-1$, $\bar{P}\rightarrow 1-\bar{P}$,
taking into account the different boundary conditions.

Now we move to the second stage, asymptotics. Since
$\mathrm{MSE}^{\text{I}}_{r}(t)$ is identical to single-source MSE of (32), by
Theorem 1, we have that

$\displaystyle\mathrm{MSE}^{\mathrm{I}}_{r}{\left(\left\lfloor{\frac{r}{t}}\right\rfloor\right)}$
$\displaystyle\leq{\operatorname{exp}\left\\{-rE_{1}(v)+o(r)\right\\}},$ (83)

where $E_{1}(v)$ is defined in (34).

For $\mathrm{MSE}^{\text{II}}_{r}(t)$, we proceed in a similar manner to the
proof of Theorem 1:

$\displaystyle\mathrm{MSE}^{\text{II}}_{r}(t)$
$\displaystyle=\bar{P}\,{\operatorname{exp}\left\\{-2Rt\right\\}}\sum_{s=0}^{t-1}\binom{r+s-1}{s}$
(84a)
$\displaystyle\qquad\cdot{\operatorname{exp}\left\\{-(r+s-1)\left[{\mathbb{D}\left(\frac{s}{r+s-1}\middle\|1-\bar{P}\right)}+h\left(\frac{s}{r+s-1}\right)\right]+2Rs\right\\}}$
(84b)
$\displaystyle\leq{\operatorname{exp}\left\\{-2Rt\right\\}}\sum_{s=0}^{t-1}{\operatorname{exp}\left\\{-\left[(s+r-1){\mathbb{D}\left(\frac{s}{s+r-1}\middle\|1-\bar{P}\right)}-2Rs\right]\right\\}}.$
(84c)

Denote the summands as
$a_{s}={\operatorname{exp}\left\\{-(r-1)\tilde{E}\left(\frac{s}{r-1}\right)\right\\}}$
for

$\displaystyle\tilde{E}(\delta)=(1+\delta){\mathbb{D}\left(\bar{\delta}\middle\|1-\bar{P}\right)}-2R\delta.$
(85)

Proceeding as in the proof of Theorem 1 would result in a correction term
$o(t)$ that grows with $t$. Instead, we derived a bound with a correction term
$o(r)$ that does not depend on $t$ and would prove more favorable. To that
end, notice that $\tilde{E}(\delta)$ is a convex function, with derivative

$\displaystyle\tilde{E}^{\prime}(\delta)=\log\left(\frac{\bar{\delta}}{1-\bar{P}}\right)-2R=\log\left(\frac{\bar{\delta}}{\eta}\right),$
(86)

which attains its (unconstrained) minimum at $\delta^{*}=\frac{\eta}{1-\eta}$
where $\eta$ was defined in (11).

Now, set $s^{*}$ to be the index of the maximal element $a_{s}$ in the sum. We
have two cases:

  1. 1.

If $(r-1)\delta^{*}\geq t-1$ the maximum is attained on the edge $s^{*}=t-1$,
and

$\displaystyle\sum_{s=0}^{t-1}a_{s}$ $\displaystyle\leq
ta_{s^{*}}\leq[(r-1)\delta^{*}+1]a_{s^{*}}.$ (87)

  2. 2.

The maximum is attained at n internal point such that
$\left|s^{*}-(r-1)\delta^{*}\right|\leq 1$, and

$\displaystyle\sum_{s=0}^{t-1}a_{s}\leq\sum_{s=0}^{\infty}a_{s}=\sum_{s=0}^{2s^{*}+1}a_{s}+\sum_{s=2(s^{*}+1)}^{\infty}a_{s}.$
(88)

The first term in (87) is bounded from above as

$\displaystyle\sum_{s=0}^{2s^{*}+1}a_{s}\leq 2(s^{*}+1)a_{s^{*}}\leq
2\left[(r-1)\delta^{*}+2\right]a_{s^{*}}.$ (89)

To bound the second term, notice that, by convexity,

$\displaystyle\tilde{E}\left(\frac{s}{r-1}\right)\geq\tilde{E}\left(\frac{2(s^{*}+1)}{r-1}\right)+\frac{s-2(s^{*}+1)}{r-1}\tilde{E}^{\prime}\left(\frac{2(s^{*}+1)}{r-1}\right),$
(90)

and, by invoking convexity and $\left|s^{*}-(r-1)\delta^{*}\right|\leq 1$, we
can further bound the derivative as

$\displaystyle\tilde{E}^{\prime}\left(\frac{2(s^{*}+1)}{r-1}\right)\geq\tilde{E}^{\prime}(2\delta^{*})=\log\frac{2}{1+\eta}.$
(91)

Consequently, all the elements in the second sum in (87) are bounded from
above as

$\displaystyle a_{s}\leq
a_{2(s^{*}+1)}\left(\frac{1+\eta}{2}\right)^{s-2(s^{*}+1)},$ (92)

and the infinite sum itself is bounded as

$\displaystyle\sum_{s=2(s^{*}+1)}^{\infty}a_{s}\leq\sum_{s=2(s^{*}+1)}^{\infty}a_{2(s^{*}+1)}\left(\frac{1+\eta}{2}\right)^{s-2(s^{*}+1)}\leq\frac{2}{1-\eta}a_{2s^{*}},$
(93)

where the geometric sum is finite since $\eta<1$ by definition (11). Since
$a_{2s^{*}}$ decays exponentially with $r$ with an exponent that is greater
than that of $a_{s}^{*}$, $a_{2s^{*}}=o_{r}\left(a_{s^{*}}\right)$.

We conclude that there exists a linear function $c(r)$ that does not depend on
$v$ (for both cases), such that

$\displaystyle\sum_{s=0}^{t-1}a_{s}\leq c(r)a_{s^{*}}.$ (94)

It follows that

$\displaystyle\mathrm{MSE}^{\text{II}}_{r}\left(\left\lfloor{\frac{r}{v}}\right\rfloor\right)$
$\displaystyle\leq{\operatorname{exp}\left\\{-rE_{2}(v)+o(r)\right\\}},$ (95)
$\displaystyle E_{2}(v)$ $\displaystyle\triangleq
v\inf_{\delta\in\left(0,\frac{1}{v}\right]}\tilde{E}(\delta)-2R,$ (96)

where $\tilde{E}(\cdot)$ was defined in (85) and the redundancy term $o(r)$ is
independent of $v$.

Since the infimum is $\delta^{*}$ for $v<\eta/(1-\eta)$ and the edge $1/v$
otherwise, $E_{2}(v)=E_{S}(v)$ for all $v$. Since $E_{2}(v)\leq E_{1}(v)$ for
all $v$, we obtain the desired result:

$\displaystyle{\mathrm{MSE}_{r}\left(\left\lfloor{\frac{r}{v}}\right\rfloor\right)}$
$\displaystyle\leq{\operatorname{exp}\left\\{-rE_{1}(v)+o(r)\right\\}}+{\operatorname{exp}\left\\{-rE_{2}(v)+o(r)\right\\}}$
(97)
$\displaystyle={\operatorname{exp}\left\\{-r\min(E_{1}(v),E_{2}(v))+o(r)\right\\}}={\operatorname{exp}\left\\{-rE_{S}(v)+o(r)\right\\}},$
(98)

where the correction term $o(r)$ is independent of $v$ as required. ∎

##  Appendix E Proofs for Section VI-B

###### Proof:

Consider first the boundary condition. By the construction of Scheme 4,

$\displaystyle\\!{\mathrm{MSE}_{0}\left(t\right)}$
$\displaystyle=\mathbb{E}\left[[S-{{{\hat{S}}}_{0}\left(t\right)}]^{2}\right]=\mathbb{E}\left[\left[S-S^{\ell\left\lfloor{\frac{t}{T}}\right\rfloor}\right]^{2}\right]=\mathbb{E}\left[\left(U^{\ell\left\lfloor{\frac{t}{T}}\right\rfloor}\right)^{2}\right]=\frac{\left(d_{\ell\left\lfloor{\frac{t}{T}}\right\rfloor}\right)^{2}}{12}=2^{-2\ell\left\lfloor{\frac{t}{T}}\right\rfloor},\
\quad$ (99)

where $U^{n}$ was defined in (73) for any $n\in\mathbb{N}$ and is uniformly
distributed over $[-d_{n}/2,d_{n}/2)$, and $d_{n}$ was defined in (75).
Recalling the rate definition (7), we have

$\displaystyle{\mathrm{MSE}_{0}\left(t\right)}\leq\exp\\{-2Rt\\}.$ (100)

Thus, indeed the MSE at node $r$ and time $t$ is at most
${\mathrm{MSE}_{r}\left(t\right)}$ of Scheme 3 with source refinement rate $R$
that equals our packet streaming rate $R$. This MSE
${\mathrm{MSE}_{r}\left(t\right)}$, in turn, is given by (80), and is bounded
as in Theorem 4.

We now bound the maximal bit error probability (13) as follows.

$\displaystyle P_{e}\left(r,\Delta\right)$
$\displaystyle\leq\sup_{\tau\in\mathbb{Z}_{\geq
0}}{\epsilon}_{r}(0:(\tau+1)\ell-1|\tau T+\Delta)$ (101a)
$\displaystyle\leq\sup_{\tau\in\mathbb{Z}_{\geq 0}}\frac{2}{\sqrt{3}}\cdot
2^{(\tau+1)\ell-1}\cdot\sqrt{{\mathrm{MSE}_{r}\left(\tau
T+\Delta\right)}},\quad$ (101b)

where (101a) follows from (22); and (101b) follows from Lemma 5 with
${\mathrm{MSE}_{r}\left(t\right)}$ of Scheme 3, by nothing that its proof in
Appendix C holds for any boundary conditions
${{{\hat{S}}}_{0}\left(t\right)}$.

To obtain the required asymptotic bound, we substitute
$r=\left\lceil{v\Delta}\right\rceil$ in (101):

$\displaystyle P_{e}\left(\left\lceil{v\Delta}\right\rceil,\Delta\right)$
$\displaystyle\leq\frac{2}{\sqrt{3}}\sup_{\tau\in\mathbb{Z}_{\geq
0}}2^{(\tau+1)\ell-1}\cdot\sqrt{{\mathrm{MSE}_{\left\lceil{v\Delta}\right\rceil}\left(\tau
T+\Delta\right)}}$ (102a) $\displaystyle=\sup_{\tau\in\mathbb{Z}_{\geq
0}}\exp\left\\{R\tau T-\frac{\tau T+\Delta}{2v}E_{S}\left(\frac{v\Delta}{\tau
T+\Delta}\right)+o(\Delta)\right\\}$ (102b)
$\displaystyle\leq\sup_{t_{0}\in\mathbb{Z}_{\geq
0}}\exp\left\\{Rt_{0}-\frac{t_{0}+\Delta}{2v}E_{S}\left(\frac{v\Delta}{t_{0}+\Delta}\right)+o(\Delta)\right\\},$
(102c)

where (102a) follows from (101); (102b) follows from (7), Theorem 4, and
noting that $E_{s}(\cdot)$ is a smooth function; and (102c) holds since
$T\mathbb{Z}_{\geq 0}\subset\mathbb{Z}_{\geq 0}$. The required result follows
by taking the $o(\Delta)$ correction term out of the optimization. This holds
true since the correction term is independent of the argument of
$E_{S}(\cdot)$, as shown in Theorem 4. ∎

###### Proof:

Recalling (11), we bound $P_{e}\left(v,\left\lfloor{r/v}\right\rfloor\right)$
for

$\displaystyle
v\leq{\operatorname{exp}\left\\{2(C-R)\right\\}}-1=\frac{1-\eta}{\eta}$ (103)

as follows.

$\displaystyle P_{e}\left(r,\left\lfloor{\frac{r}{v}}\right\rfloor\right)$
$\displaystyle\leq{\operatorname{exp}\left\\{-\inf_{t_{0}\in\mathbb{Z}_{\geq
0}}\left[\frac{t_{0}+\Delta}{2v}E_{S}\left(\frac{v\Delta}{t_{0}+\Delta}\right)-t_{0}R\right]+o(r)\right\\}}$
(104a)
$\displaystyle={\operatorname{exp}\left\\{-\left[\frac{1}{1-\eta}\left(\frac{{\mathbb{D}\left(1-\eta\middle\|\bar{P}\right)}}{2}-\eta
R\right)+R\right]\Delta+o(r)\right\\}},$ (104b)

where (104a) follows from Lemma 6, and (104b) holds for $v$ that satisfies
(103) by noting that the argument of $E_{S}(\cdot)$ is at most $v$ in this
case.

Now note that the exponent in (104b) at $v=\frac{1-\eta}{\eta}$ is positive:

$\displaystyle\Bigl{.}\frac{1}{1-\eta}\left(\frac{{\mathbb{D}\left(1-\eta\middle\|\bar{P}\right)}}{2}-\eta
R\right)+R\Bigr{|}_{v=\frac{1-\eta}{\eta}}=\frac{{\mathbb{D}\left(1-\eta\middle\|\bar{P}\right)}}{2(1-\eta)}>0.$
(105)

Since $P_{e}\left(r,\left\lfloor{r/v}\right\rfloor\right)$ is monotonically
increasing with $v$,
$\lim_{\Delta\to\infty}P_{e}\left(r,\left\lfloor{r/v}\right\rfloor\right)=0$
for all $v$ that satisfy (103). Thus all these velocities are achievable, and
the proof is concluded. ∎

## References

  * [1] S. G. Waxman, J. D. Kocsis, and P. K. Stys, _The Axon: Structure, Function, and Pathophysiology_. Oxford, UK: Oxford University Press, 1995.
  * [2] J.-A. Girault and E. Peles, “Development of nodes of Ranvier,” _Current opinion in neurobiology_ , vol. 12, no. 5, pp. 476–485, 2002.
  * [3] T. Berger and W. B. Levy, “A mathematical theory of energy efficient neural computation and communication,” vol. 56, no. 2, pp. 852–874, 2010.
  * [4] P. Suksompong and T. Berger, “Capacity analysis for integrate-and-fire neurons with descending action potential thresholds,” _IEEE Transactions on Information Theory_ , vol. 56, no. 2, pp. 838–851, 2010.
  * [5] J. Heinovski and F. Dressler, “Platoon formation: Optimized car to platoon assignment strategies and protocols,” in _IEEE Vehicular Networking Conference (VNC)_ , 2018.
  * [6] T. Nawaz, M. Seminara, S. Caputo, L. Mucchi, F. S. Cataliotti, and J. Catani, “IEEE 802.15. 7-compliant ultra-low latency relaying VLC system for safety-critical ITS,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 12, pp. 12 040–12 051, 2019.
  * [7] W. Huleihel, Y. Polyanskiy, and O. Shayevitz, “Relaying one bit across a tandem of binary-symmetric channels,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, 2019, pp. 2928–2932.
  * [8] V. Jog and P.-L. Loh, “Teaching and learning in uncertainty,” _IEEE Transactions on Information Theory_ , vol. 67, no. 1, pp. 598–615, 2020.
  * [9] Y. H. Ling and J. Scarlett, “Optimal rates of teaching and learning under uncertainty,” _IEEE Transactions on Information Theory_ , vol. 67, no. 11, pp. 7067–7080, August 2021.
  * [10] ——, “Multi-bit relaying over a tandem of channels,” _IEEE Transactions on Information Theory_ , vol. 69, no. 6, pp. 3511–3524, June 2023.
  * [11] S. Rajagopalan and L. Schulman, “A coding theorem for distributed computation,” in _Proceedings of the ACM Symposium on Theory of Computing (STOC)_ , 1994, pp. 790–799.
  * [12] S. K. Iyer and R. Vaze, “Achieving non-zero information velocity in wireless networks,” in _Proceedings of the Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)_ , 2015, pp. 584–590.
  * [13] Y. H. Ling and J. Scarlett, “Simple coding techniques for many-hop relaying,” _IEEE Transactions on Information Theory_ , vol. 68, no. 11, pp. 7043–7053, June 2022.
  * [14] M. Fidler, “Survey of deterministic and stochastic service curve models in the network calculus,” _IEEE Communications Surveys Tutorials_ , vol. 12, no. 1, pp. 59–86, 2010.
  * [15] M. Fidler and A. Rizk, “A guide to the stochastic network calculus,” _IEEE Communications Surveys Tutorials_ , vol. 17, no. 1, pp. 92–105, 2015.
  * [16] C.-S. Chang, _Performance Guarantees in Communication Networks_. Springer Science & Business Media, 2000.
  * [17] M. Fidler, “An end-to-end probabilistic network calculus with moment generating functions,” in _IEEE International Workshop on Quality of Service (IWQoS)_ , 2006, pp. 261–270.
  * [18] E. Domanovitz, T. Philosof, and A. Khina, “The information velocity of packet-erasure links,” in _Proceedings of the IEEE International Conference on Computer Communications (INFOCOM)_ , May 2022.
  * [19] R. Inovan and E. Telatar, private communication.
  * [20] A. Lalitha, A. Khina, T. Javidi, and V. Kostina, “Real-time binary posterior matching,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, Jul. 2019, pp. 2239–2243.
  * [21] J. P. M. Schalkwijk and T. Kailath, “A coding scheme for additive noise channels with feedback–I: No bandwidth constraint,” _IEEE Transactions on Information Theory_ , vol. 12, pp. 172–182, Apr. 1966.
  * [22] J. P. M. Schalkwijk, “A coding scheme for additive noise channels with feedback–ii: Band-limited signals,” _IEEE Transactions on Information Theory_ , vol. 12, no. 2, pp. 183–189, April 1966.
  * [23] R. G. Gallager and B. Nakiboğlu, “Variations on a theme by Schalkwijk and Kailath,” vol. 56, no. 1, pp. 6–17, Dec. 2009.
  * [24] P. Elias, “Channel capacity without coding,” in _Proceedings of the IRE_ , vol. 45, no. 3, Jan. 1957, pp. 381–381.
  * [25] B. Schein and R. G. Gallager, “The Gaussian parallel relay channel,” in _Proc. Int. Symp. Info. Theory (ISIT)_ , Sorrento, Italy, June 2000, p. 22.
  * [26] J. N. Laneman, D. N. Tse, and G. W. Wornell, “Cooperative diversity in wireless networks: Efficient protocols and outage behavior,” _IEEE Transactions on Information theory_ , vol. 50, no. 12, pp. 3062–3080, Novmber 2004.
  * [27] Y. Kochman, A. Khina, U. Erez, and R. Zamir, “Rematch-and-forward: Joint source/channel coding for parallel relaying with spectral mismatch,” _IEEE Transactions on Information Theory_ , vol. 60, no. 1, pp. 605–622, Jan. 2014.
  * [28] H. Yamamoto and K. Itoh, “Source coding theory for multiterminal communication systems with a remote source,” _Tran. IECE of Japan_ , vol. E 63, no. 10, pp. 700–706, 1980.
  * [29] T. Berger, Z. Zhang, and H. Viswanathan, “The CEO problem [multiterminal source coding],” _IEEE Transactions on Information Theory_ , vol. 42, no. 3, pp. 887–902, 1996.
  * [30] A. B. Wagner, S. Tavildar, and P. Viswanath, “Rate region of the quadratic Gaussian two-encoder source-coding problem,” _IEEE Transactions on Information Theory_ , vol. 54, no. 5, pp. 1938–1961, 2008.
  * [31] S. C. Draper and G. W. Wornell, “Successively structured CEO problems,” Lausanne, Switzerland, July 2002, p. 65.
  * [32] ——, “Side information aware coding strategies for sensor networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 22, no. 6, pp. 966–976, 2004.
  * [33] J. Chen, X. Zhang, T. Berger, and S. Wicker, “Rate allocation in distributed sensor network,” vol. 41, no. 1, Monticello, IL, USA, October 2003, pp. 531–540.
  * [34] W. H. R. Equitz and T. M. Cover, “Successive refinement of information,” _IEEE Transactions on Information Theory_ , vol. 37, no. 2, pp. 851–857, Mar. 1991.
  * [35] L. Lastras and T. Berger, “All sources are nearly successively refinable,” _IEEE Transactions on Information Theory_ , vol. 47, pp. 918–926, March 2001.
  * [36] A. Papoulis and S. U. Pillai, _Probability, Random Variables, and Stochastic Processes_ , 4th ed. Tata McGraw-Hill Education, 2002.
  * [37] R. G. Gallager, _Information Theory and Reliable Communication_. New York: John Wiley & Sons, 1968.
  * [38] A. El Gamal and Y.-H. Kim, _Network Information Theory_. Cambridge University Press, 2011.
  * [39] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. New York: Wiley, 2006.
  * [40] A. Ben-Yishai and O. Shayevitz, “The Gaussian channel with noisy feedback: Improving reliability via interaction,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Hong Kong, June 2015, pp. 2500–2504.
  * [41] M. J. Wainwright, _High-Dimensional Statistics: A Non-Asymptotic V iewpoint_. Cambridge, UK: Cambridge university press, 2019, vol. 48.
  * [42] R. Vershynin, _High-Dimensional Probability: An Introduction with Applications in Data Science_. Cambridge, UK: Cambridge university press, 2018, vol. 47.