Anytime Capacity of Markov Channels

Paolo Minero

Department of EE University of Notre Dame Notre Dame, IN 46556, USA

Email: pminero@nd.edu

Massimo Franceschetti

Department of ECE University of California, San Diego La Jolla, CA 92093, USA Email: massimo@ece.ucsd.edu

Abstract—Several new expressions for the anytime capacity of Sahai and Mitter are presented for a time-varying rate-limited channel with noiseless output feedback. These follow from a parametric characterization obtained in the case of Markov channels, and include an explicit formula for the r-bit Markov erasure channel, as well as formulas for memoryless rate processes including Binomial, Poisson, and Geometric distributions. Beside the memoryless erasure channel and the additive white Gaussian noise channel with input power constraint, these are the only cases where explicit anytime capacity formulas are obtained. At the basis of these results is the study of the threshold function for mth moment stabilization of a scalar linear system controlled over a Markov time-varying digital feedback channel that depends on m and on the channel’s parameters. This threshold is shown to be a continuous and strictly decreasing function of m and to have as extreme values the Shannon capacity and the zero-error capacity as m tends to zero and infinity, respectively. Its operational interpretation is that of achievable communication rate, subject to a reliability constraint.

I. Introduction

We consider the problem of moment stabilization of a dynamical system where the estimated state is transmitted for control over a time-varying communication channel. A tutorial review of the problem with extensive references appears in [1].

The notion of Shannon capacity is in general not sufficient to characterize the trade-off between the entropy rate production of the plant, expressed by the growth of the state space spanned in open loop, and the communication rate required for its stabilization. A large Shannon capacity is useless for stabilization if it cannot be used in time for control. For the control signal to be effective, it must be appropriate to the current state of the system. Since decoding the wrong codeword implies applying a wrong signal and driving the system away from stability, applying an effective control signal depends on the history of whether previous codewords were decoded correctly or not. In essence, the stabilization problem is an example of interactive communication, where two-way communication occurs through the feedback loop between the plant and the controller. Alternative capacity notions with stronger reliability constraints than having a vanishing probability of error, have been proposed in the context of control, including the zeroerror capacity [2], originally introduced by Shannon [3], and the anytime capacity proposed by Sahai and Mitter [4], [5]– [8].

Within this general framework, we focus on the mth moment stabilization of an unstable scalar system whose state is communicated over a rate-limited channel capable of supporting R_{k} bits at each time step and evolving randomly in a Markovian fashion, see Fig. 1. The rate process is known casually to both encoder and decoder. Many variations of this “bit-pipe” model have been studied in the literature [9]–[29], including the case of fixed rate channel; the erasure channel where the rate process can assume value zero; and the packet loss channel, where the rate process can oscillate randomly between zero and infinity, allowing a real number of infinite precision to be transported across the channel in one time step. Connections between the rate limited and the packet loss channel have been pointed out in [22], [23], showing that results for the latter model can be recovered by appropriate limiting arguments.

The major contribution of this paper is the introduction of a stability threshold function of the channel’s parameters and of the moment stability number m that converges to the Shannon capacity for m → 0, to the zero-error capacity for m → ∞, and it provides a parametric characterization of the anytime capacity for the remaining values of m. This function yields a novel anytime capacity formula in the special case of the r-bit Markov erasure channel, as well as formulas for memoryless rate processes including Binomial, Poisson, and Geometric distributions.

Throughout the paper, the following notation is used. Logarithms are assumed to be in base two; random variables are denoted with uppercase letters, while their realizations with lowercase letters; matrices are also denoted in uppercase letters, using the special typeset A.

II. Moment Stabilization over Markov Channels We consider the stability of linear dynamical systems when

the estimated state is sent to the controller over a digital communication link whose state is described by a Markov process, as depicted in Fig. 1.

A. System model Consider the scalar dynamical system

x_{k+1} = λx_{k} + u_{k} + v_{k},
y_{k} = x_{k} + w_{k},  (1)

where k ∈ ℕ, and |λ| ≥ 1. The variable x_{k} represents the state of the system, u_{k} the control input, v_{k} is an additive stochastic disturbance, y_{k} is the sensor measurement, and w_{k} PSfrag replacements

Controller

Plant Estimator Encoder Decoder

Channel state

R_{k} information

Fig. 1. Feedback loop model. The estimated state is quantized, encoded and sent to a decoder over a digital channel of state R_{k} that evolves in time according to a Markov process.

is the measurement noise. Both disturbance and noise are independent of each other and of the initial condition x_{0}. They are also independent of the channel state, as defined below.

B. Channel Model

The state observer is connected to the actuator through a noiseless digital communication link that at each time k allows transmission without errors of R_{k} bits. The rate process {R_{k}}_{k≥0} is modeled as a homogeneous positive-recurrent Markov process defined on the finite set

R = {r̄_{1}, …, r̄_{n}},  (2)

for some integer numbers 0 ≤ r̄_{1} < ⋯ < r̄_{n}, and with onestep transition probability matrix P having entries

p_{ij} = P{R_{k} = r̄_{j}|R_{k−1} = r̄_{i}}  (3)

for every i, j ∈ {1, …, n}. In the sequel, we define R ∈ ℤ_{+}^{n×n} as the diagonal matrix with diagonal entries r̄_{1}, …, r̄_{n}, i.e.,

R = diag(r̄_{1}, …, r̄_{n}).  (4)

Encoder and decoder are supposed to have causal knowledge of the rate process.

This noiseless digital link corresponds to a discretememoryless channel with Markov state available causally at both the encoder and the decoder. A channel with state is defined by a triple (X ×S, p(y|x, s), Y) consisting of an input set X, a state set S, an output set Y, and a transition probability matrix p(y|x) for every x ∈ X, s ∈ S, and y ∈ Y. This channel is memoryless if the output y_{k} at time k is conditionally independent of everything else given (x_{k}, s_{k}). The state sequence is Markov if S_{0}, S_{1}, … forms a Markov chain. According to these definitions, our channel model is a discretememoryless channel with Markov state (X × S, p(y|x, s), Y) with X = Y = {1, …, r̄_{n}}, S = {r̄_{1}, ⋯, r̄_{n}},

p(y|x, s) = \begin{cases}1 & x = y and x ≤ s \\ 0. & otherwise \end{cases}  (5)

and state transition probabilities

p(s_{k+1} = r̄_{j}|s_{k} = r̄_{i}) = p_{ij}.  (6)

The Shannon capacity of this channel is [30]

C = ∑_{i=1}^{n} π_{i}r̄_{i},  (7)

where (π_{1}, …, π_{n}) denotes the unique stationary distribution of P.

The zero-error capacity of this channel is [3]

C_{0} = r̄_{1}.  (8)

The capacities in (7) and (8) are the limiting values of a stability threshold function indicating the channel’s ratereliability constraint required to achieve a given level of stabilization. As m → ∞ and the system is highly stable, then the stability threshold function tends to the zero-error capacity that has a hard reliability constraint of providing no decoding error. Conversely, as m → 0 and the system’s stability level decreases, then the stability threshold function tends to the Shannon capacity that has a weak reliability constraint of vanishing probability of error.

C. Stability threshold function

The system (1) is mth moment stable if

sup_{k} E[|X_{k}|^{m}] < ∞,  (9)

where the expectation is taken with respect to the random initial condition x_{0}, the additive disturbance v_{k}, and the rate process R_{k}.

The following Theorem establishes the stability threshold for the m-th moment stability of (1) in terms of the unstable mode |λ| and the spectral radius ρ(·) of P^{T}2^{−mR}, where 2^{−mR} denotes the base-2 matrix exponential of mR, i.e.,

2^{−mR} = diag(2^{−mr̄_{1}}, ⋯, 2^{−mr̄_{n}}).  (10)

Theorem 1. There exists a control scheme that stabilizes the scalar system (1) in mth momemt sense if and only if

log |λ| ≲ −\frac{1}{m} log ρ(P^{T}2^{−mR}) ≜ R(m).  (11)

The usage of the symbol “≲” indicates that while the necessary condition holds with a weak inequality, the sufficient condition requires a strong inequality.

We now mention several properties of the threshold function R(m).

Proposition 2. The following facts hold:

1) Monotonicity: R(m) is continuous and strictly decreasing for m > 0.

2) Convergence to the Shannon capacity:

lim_{m→0} R(m) = ∑_{i=1}^{n} π_{i}r̄_{i} = C.  (12)

3) Convergence to the Zero Error capacity:

R(m) ∼ r̄_{1} − \frac{1}{m} log p_{11}, as m → ∞,  (13)

and hence

lim_{m→∞} R(m) = r̄_{1} = C_{0}.  (14)

4) Sensitivity with respect to self-loop probabilities:

\frac{dR(m)}{dp_{ii}} = −\frac{2^{−mr̄_{ii}}}{mρ(P^{T}2^{−mR})} \frac{|D(1)|}{∑_{i=1}^{n} |D(i)|} < 0, (15)

where D := ρ(P^{T}2^{−mR})I−P^{T}2^{−mR}, I denotes the n× n identity matrix, and |D(i)| is the determinant of the matrix obtained by eliminating the ith row and the ith column from D. We also have the asymptotic behavior

\frac{dR(m)}{dp_{11}} ∼ −\frac{1}{mp_{11} ln(2)} as m → ∞.  (16)

5) The function mR(m) is nonnegative, strictly increasing, and strictly concave. If r̄_{1} ≠ 0, then mR(m) grows unbounded as m → ∞. If instead r̄_{1} = 0, then

lim_{m→∞} mR(m) = − log p_{11}.  (17)

III. Anytime Capacity of Markov Channels

We relate the stability threshold function R(m) to the anytime capacity. For the given Markov channel, it provides a parametric representation of the anytime capacity in terms of system’s stability level m.

The anytime capacity is defined in the following context [6]. Consider a system for information transmission that allows the decoding time to be infinite, and improves the reliability of the estimated message as time progresses. More precisely, at each step k in the evolution of the plant a new message m_{k} of r bits is generated that must be sent over the channel. The coder sends a bit over the channel at each k and the decoder upon reception of the new bit updates the estimates for all messages up to time k. It follows that at time k messages

m_{0}, m_{1}, …, m_{k}

are considered for estimation, while estimates

m̂_{0|k}, m̂_{1|k}, …, m̂_{k|k}

are constructed, given all the bits received up to time k. Hence, the processing operation for any message m_{i} continues indefinitely for all k ≥ i. A reliability level α is achieved in the given transmission system if for all k the probability that there exists at least a message in the past whose estimate is incorrect decreases α-exponentially with the number of bits received, namely for all d ≤ k

P{(M̂_{0|k}, …, M̂_{d|k}) ≠ (M_{0}, …, M_{d})} = O(2^{−αd}). (18)

The described communication system is characterized by a rate-reliability pair (r, α). The work in [6] has shown that for scalar systems the ability to achieve stability depends on the ability to construct such a communication system, in terms of achievable coding and decoding schemes, with a given ratereliability constraints.

To state this result in the context of our Markov channel, let the α-anytime capacity C_{A}(α) be the supremum of the rate r that can be achieved with reliability α. The problems of α-reliable communication and mth moment stabilization of a scalar system over a Markov channel are then equivalent in the sense of the following theorem.

Theorem 3 (Sahai, Mitter [6]). The necessary and sufficient condition for mth moment stabilization of a scalar system with bounded disturbances and in the presence of channel output feedback over a Markov channel is

log |λ| ≲ C_{A}(m log |λ|).  (19)

The anytime capacity is an intermediate notion between the zero-error capacity and the Shannon capacity. The zero-error capacity requires transmission without error. The Shannon capacity requires the decoding error to tend to zero by increasing the length of the code. In the presence of disturbances, only a critical value of the zero-error capacity can guarantee the almost sure stability of the system [2]. On the other hand, for scalar systems in presence of bounded disturbances, a critical value of the anytime capacity can guarantee the ability to stabilize the system in the weaker mth moment sense.

By combining Theorem 1 and Theorem 3, we obtain the following result.

Theorem 4. The following holds:

1) Parametric characterization of the anytime capacity: For every m > 0, the anytime capacity C_{A} satisfies

C_{A}(mR(m)) = R(m),  (20)

i.e., for every α ≥ 0, there exists a unique m(α) such that

m(α)R(m(α)) = α  (21)

and

C_{A}(α) = R(m(α)) = \frac{α}{m(α)}.  (22)

2) C_{A}(α) is a strictly decreasing function function of α > 0.

3) Convergence to the Shannon capacity:

lim_{α→0} C_{A}(α) = ∑_{i=1}^{n} π_{i}r_{i} = C,  (23)

4) Convergence to the Zero Error capacity: If r̄_{1} = 0, then for every α ≥ log(1/p_{11})

C_{A}(α) = 0 = C_{0}.  (24)

Conversely, if r̄_{1} ≠ 0, then C_{A}(α) has unbounded support and

C_{A}(α) ∼ r̄_{1} \frac{α}{α − log(1/p_{11})}, as α → ∞, (25)

hence

lim_{α→∞} C_{A}(α) = r̄_{1} = C_{0}.  (26)

IV. The Markov Erasure Channel

We use the stability threshold function R(m) to compute the anytime capacity of the Markov erasure channel. The Markov erasure channel corresponds to a two-state Markov process where n = 2 R = {0, r̄}, p_{12} = q, and p_{21} = p, where 0 < p, q < 1. In this case,

P^{T}2^{−mR} = (\begin{matrix}(1 − q) & \frac{1}{2^{mr̄}} p \\ q & \frac{1}{2^{mr̄}} (1 − p) \end{matrix}) ,  (27)

and we have the following result.

Theorem 5. The anytime capacity of the Markov Erasure Channel is

C_{A}(α) = \frac{αr̄}{α + log_{2} (\frac{1−p−2^{α}(1−p−q)}{1−(1−q)2^{α}})},  (28)

if 0 ≤ α < − log_{2}(1 − q), and 0 otherwise.

A. Special cases

Several special cases recover previous results in the literature. By (28) it follows that the anytime capacity of the binary erasure channel (BEC) with Markov erasures and with noiseless channel output feedback is

C_{A}(α) = \frac{α}{α + log_{2} (\frac{1−p−2^{α}(1−p−q)}{1−(1−q)2^{α}})}.  (29)

By letting q = 1 − p, the erasure process becomes i.i.d. and we recover the anytime capacity of the memoryless BEC with erasure probability p derived by Sahai [4, page 129] (in parametric form) and by Xu [8, Theorem 1.3] (in nonparametric form)

C_{A}(α) = \frac{α}{α + log_{2} (\frac{1−p}{1−p2^{α}} )}.  (30)

By (28), letting α → 0, we have that

lim_{α→0} C_{A}(α) = \frac{q}{p + q} r̄ = C,  (31)

where the expectation is taken with respect to the stationary distribution of P. This recovers the Shannon capacity of an r̄- bit erasure channel with Markov erasures and with noiseless channel output feedback.

In the case n = 2, r̄_{1} = 0, r̄_{2} = r, and an i.i.d. rate process with P{R_{k} = 0} = p_{1} and P {R_{k} = r} = p_{2} for all k’s, then the stability condition becomes

|λ|^{m} (p_{1} + p_{2}2^{−mr}) < 1,

which provides a converse to the achievable scheme of Yüksel and Meyn [31, Theorem 3.3].

If we further let r → ∞, then the stability condition p_{1} > 1/|λ|^{m} depends only on the erasure rate of the channel. In this case, our condition generalizes the packet loss model result in [24].

V. Memoryless Channels

Consider the special case of an i.i.d. rate process R_{k} where R_{k} ∼ R has probability mass function p_{i} = P{R = r̄_{i}}, r̄_{i} ∈ R. For t real, Let M_{R}(t) = 𝔼(e^{tR}) denote the moment generating function of R and let M_{R}^{−1}(y) denotes the inverse of the M_{R}(t), if it exists, i.e., M_{R}^{−1}(y) = t if and only if M_{R}(t) = y.

We have the following result.

Theorem 6. The anytime capacity of a memoryless channel with rate distribution R is

C_{A}(α) = \frac{ln 2^{−α}}{M_{R}^{−1}(2^{−α})}  (32)

for α < − log p_{11} if r̄_{0} = 0, or for any α > 0 if r̄_{0} ≠ 0.

Theorem 6 shows that in the case where the channel is memoryless, the anytime capacity can be evaluated by computing the inverse of the moment generating function of R, as illustrated in the next three examples.

Example V.1. Suppose that R is a binomial random variable with parameters k and 1 − p. Then,

M_{R}(t) = (p + (1 − p)e^{t})^{k}  (33)

and

M_{R}^{−1}(y) = ln \frac{y^{1/k} − p}{1 − p}, y < p^{k},  (34)

and thus by (32)

C_{A}(α) = \frac{α}{α/k + log_{2} (\frac{1−p}{1−p2^{α/k}} )}  (35)

for α < −k log p. Notice that (35) recovers (30) in the special case k = 1 in which R is Bernoulli with parameter 1 − p.

Example V.2. Suppose that R is a Poisson random variable with parameter λ. Then,

M_{R}(t) = e^{λ(e^{t}−1)}  (36)

and

M_{R}^{−1}(y) = ln(1 + 1/λ ln y), y > 0,  (37)

and thus by (32)

C_{A}(α) = −\frac{α}{log(1 − α/λ ln 2)}  (38)

for α < −λ/ ln 2.

Notice in both examples r̄_{1} = 0, so the anytime capacity has bounded support. In the next example r̄_{1} = 1 and thus the anytime capacity is defined for all α > 0.

Example V.3. Suppose that R is a geometric random variable with parameter p. Then,

M_{R}(t) = \frac{pe^{t}}{1 − (1 − p)e^{t}}  (39)

Fig. 2. Comparison of the anytime capacity for different memoryless channels. For the uniform distribution the plot is obtained numerically.

for t < − ln(1 − t) and

M_{R}^{−1}(y) = ln \frac{y}{p + y(1 − p)}, y > 0,  (40)

for y > 0, and thus

C_{A}(α) = \frac{α}{log((1 − p) + p2^{α})}, α > 0.  (41)

References

[1] M. Franceschetti and P. Minero, Elements of information theory for networked control systems, ser. Lecture notes in control and information sciences, Ch. 1, G. Como Ed. Springer, 2014.

[2] A. S. Matveev and A. V. Savkin, “Shannon zero error capacity in the problems of state estimation and stabilization via noisy communication channels,” International Journal of Control, vol. 80, no. 2, pp. 241–255, 2007.

[3] C. E. Shannon, “The zero-error capacity of a noisy channel,” IRE Transactions on Information Theory, vol. 2, pp. 8–19, 1956.

[4] A. Sahai, “Anytime information theory,” Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 2001.

[5] G. Como, F. Fagnani, and S. Zampieri, “Anytime reliable transmission of real-valued information through digital noisy channels,” SIAM J. Control Optim., vol. 48, no. 6, pp. 3903–3924, Apr. 2010.

[6] A. Sahai and S. K. Mitter, “The necessity and sufficiency of anytime capacity for stabilization of a linear system over a noisy communication link – Part I: Scalar systems,” IEEE Trans. Inf. Theory, vol. 52, no. 8, pp. 3369–3395, Aug. 2006.

[7] T. Şimşek, R. Jain, and P. Varaiya, “Scalar estimation and control with noisy binary observations,” IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1598–1603, Sept. 2004.

[8] Q. Xu, “Anytime capacity of the AWGN+Erasure channel with feedback,” Ph.D. Thesis, University of California at Berkeley, Berkeley, CA, 2005.

[9] W. S. Wong and R. Brockett, “Systems with finite communication bandwidth constraints. II. Stabilization with limited information feedback,” IEEE Transactions on Automatic Control, vol. 44, no. 5, pp. 1049–1053, May 1999.

[10] R. Brockett and D. Liberzon, “Quantized feedback stabilization of linear systems,” IEEE Transactions on Automatic Control, vol. 45, no. 7, pp. 1279–1289, July 2000.

[11] D. Liberzon, “On stabilization of linear systems with limited information,” IEEE Transactions on Automatic Control, vol. 48, no. 2, pp. 304– 307, Feb. 2003.

[12] D. Delchamps, “Stabilizing a linear system with quantized state feedback,” IEEE Transactions on Automatic Control, vol. 35, no. 8, pp. 916–924, Aug. 1990.

[13] N. Martins, M. Dahleh, and N. Elia, “Feedback stabilization of uncertain systems in the presence of a direct link,” IEEE Transactions on Automatic Control, vol. 51, no. 3, pp. 438–447, Mar. 2006.

[14] G. N. Nair and R. J. Evans, “Stabilizability of stochastic linear systems with finite feedback data rates,” SIAM J. Control Optim., vol. 43, no. 2, pp. 413–436, Feb. 2004.

[15] O. C. Imer, S. Yüksel, and T. Başar, “Optimal control of LTI systems over unreliable communication links,” Automatica, vol. 42, no. 9, pp. 1429–1439, 2006.

[16] S. Tatikonda and S. K. Mitter, “Control under communication constraints,” IEEE Transactions on Automatic Control, vol. 49, no. 7, pp. 1056–1068, July 2004.

[17] ——, “Control over noisy channels,” IEEE Transactions on Automatic Control, vol. 49, no. 7, pp. 1196–1201, July 2004.

[18] V. Gupta and N. Martins, “On stability in the presence of analog erasure channel between the controller and the actuator,” IEEE Transactions on Automatic Control, vol. 55, no. 1, pp. 175–179, Jan. 2010.

[19] S. Yüksel, “Stochastic stabilization of noisy linear systems with fixedrate limited feedback,” IEEE Transactions on Automatic Control, vol. 55, no. 12, pp. 2847–2853, Dec. 2010.

[20] S. Yüksel and T. Başar, “Control over noisy forward and reverse channels,” IEEE Transactions on Automatic Control, vol. 56, no. 5, pp. 1014–1029, May 2011.

[21] V. Borkar and S. Mitter, LQG Control with Communication Constraints. Communications,Computation, Control and Signal Processing: A Tribute to Thomas Kailath. Kluver, 1997.

[22] P. Minero, M. Franceschetti, S. Dey, and G. Nair, “Data rate theorem for stabilization over time-varying feedback channels,” IEEE Transactions on Automatic Control, vol. 54, no. 2, pp. 243–255, Feb. 2009.

[23] L. Coviello, P. Minero, and M. Franceschetti, “Stabilization over Markov feedback channels: The general case.” IEEE Transactions on Automatic Control, vol. 58, no. 2, pp. 349–362, 2013.

[24] V. Gupta, D. Spanos, B. Hassibi, and R. M. Murray, “Optimal LQG control across packet-dropping links,” Systems and Control Letters, vol. 56, no. 6, pp. 439–446, 2007.

[25] V. Gupta, N. Martins, and J. Baras, “Optimal output feedback control using two remote sensors over erasure channels,” IEEE Transactions on Automatic Control, vol. 54, no. 7, pp. 1463–1476, july 2009.

[26] L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and S. Sastry, “Foundations of control and estimation over lossy networks,” Proceedings of the IEEE, vol. 95, no. 1, pp. 163–187, Jan. 2007.

[27] M. Huang and S. Dey, “Stability of kalman filtering with Markovian packet losses,” Automatica, vol. 43, no. 4, pp. 598–607, 2007.

[28] N. Elia, “Remote stabilization over fading channels,” Systems and Control Letters, vol. 54, no. 3, pp. 237–249, 2005.

[29] N. Elia and S. K. Mitter, “Stabilization of linear systems with limited information,” IEEE Transactions on Automatic Control, vol. 46, no. 9, pp. 1384–1400, 2001.

[30] A. Goldsmith and P. Varaiya, “Capacity, mutual information, and coding for finite-state markov channels,” IEEE Trans. Inf. Theory, vol. 42, no. 3, pp. 868–886, May 1996.

[31] S. Yuksel and S. Meyn, “Random-time, state-dependent stochastic drift for markov chains and application to stochastic stabilization over erasure channels,” IEEE Transactions on Automatic Control, vol. 58, no. 1, pp. 47–59, Jan. 2012.

[32] E. Lutwak, D. Yang, and G. Zhang, “Crame acute;r-rao and momententropy inequalities for renyi entropy and generalized fisher information,” IEEE Trans. Inf. Theory, vol. 51, no. 2, pp. 473–478, Feb. 2005.

[33] S. Friedland, “Convex spectral functions,” Linear and Multilinear Algebra, vol. 9, no. 4, pp. 299–316, 1981.

[34] J. E. Cohen, “Derivatives of the spectral radius as a function of nonnegative matrix elements,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 83, pp. 183–190, 3 1978.

[35] O. Costa, D. Fragoso, and R. Marques, Discrete-Time Markov Jump Linear Systems, ser. Probability and its Applications. Springer, 2004.

[36] Y. Fang, K. A. Loparo, and X. Fend, “Almost sure and δ-moment stability of jump linear systems,” International Journal of Control, vol. 59, no. 5, pp. 1281–1307, 1994.

[37] A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge University Press, 2011.

Fig. 3. Stability threshold function and anytime capacity for Example A.1

Appendix A

Stability threshold function examples

Example A.1. Let n = 4,R = {1, 3, 4, 5} and P be is a 4 × 4 circulant matrix with first row equal to \frac{1}{16} (1, 13, 1, 1), namely

P = \frac{1}{16} [\begin{matrix}1 & 13 & 1 & 1 \\ 13 & 1 & 1 & 1 \\ 1 & 1 & 1 & 13 \\ 1 & 1 & 13 & 1 \end{matrix}] .  (42)

In this case it is easy to compute C = \frac{1}{4}(1 + 3 + 4 + 5) = \frac{13}{4} and C_{0} = 1. Figure 3 plots the stability threshold function R(m) (together with its asymptotic approximation) and the anytime capacity C_{A}(α). Both curves have the same shape and they are in fact related by an affine transformation as m grows. Furthermore, both curves have unbounded support and tend to one at infinity. There is a change of convexity for small values of m and α, as indication that R(m) and C_{A}(α) are generally not convex functions. In contrast, the function ϕ(m) = mR(m), reported in red in the top plot of Figure 3, is strictly convex and increasing.

Fig. 4. Stability threshold function and anytime capacity for Example A.2.

Example A.2. Let R = {0, 3, 4, 5} and P is as in (42). The only difference with the previous example is that r̄_{1} is now 0 instead than 1. In this case it is easy to compute C = \frac{1}{4}(0+3+ 4 + 5) = 3 and C_{0} = 0. Figure 4 plots the stability threshold function R(m) (together with its asymptotic approximation) and the anytime capacity C_{A}(α). In this case, while R(m) has unbounded support, C_{A}(α) is zero for all α ≥ − log p_{11} = log 16 = 4. This occurs because the function ϕ(m) = mR(m) saturates as m → ∞, tending to the limiting value − log p_{11} = 4.

When viewed together, the two examples above show that for some channels a communication system with an arbitrary rate-reliability pair (r, α) cannot be constructed, because the anytime capacity may have bounded support and tend abruptly to zero. However, in order to achieve mth moment stabilization it is sufficient to consider the simpler function R(m) = C_{A}(mR(m)), and construct a communication system whose reliability level depends on the desired stabilization level. It follows that we do not need to compute the whole anytime capacity if we are interested only in moment stabilization, and we may be content with determining the threshold function R(m) corresponding to its parametric representation. The extremal properties of R(m) determine the support of the anytime capacity corresponding to the achievable reliability level α. If R(m) = O(1/m) then the anytime capacity has support bounded by the pre-constant of the asymptotic order. On the other hand, if R(m) decreases at most sub-linearly to zero, or it tends to a constant zero-error capacity, then the anytime capacity has unbounded support and any reliability level α is achieved.

Appendix B Auxiliary Results

We first state without proof a series of auxiliary results that are needed in the rest of the paper. We begin with a maximum entropy result which generalizes the well-know result that the second moment of a continuous random variable X is lower bounded by its entropy power e^{2h(X)} to the case of the L^{m}- norm of a continuous random vector.

Lemma 1. Let X be a continuous n-dimensional vectorvalued random variable with 𝔼[||X||_{m}^{m}] < ∞, where m is a positive real number. Let ∥X∥_{m} = (∑_{i} |X_{i}|^{m})^{1/m} denotes the L^{m}-norm of X. Then,

𝔼[||X||_{m}^{m}] ≥ \frac{n}{c_{m}} e^{\frac{m}{n} h(X)}  (43)

where c_{m} = 2^{m}m^{1−m}e (Γ(\frac{1}{m}))^{m} and Γ(x) = ∫_{0}^{∞} e^{−t}t^{x−1}dt. Equality holds if and only if X_{1}, ⋯, X_{n} are i.i.d ∼ X, where

f_{X}(x) = \frac{exp (−\frac{|x|^{m}}{mμ^{m}} )}{2m^{(1−m)/m}μΓ (\frac{1}{m})}, x ∈ ℝ.  (44)

It should be remarked that inequality (43) with n = 1 is a special case of a result proved in [32] relating the mth moment and the Renyi entropy of a random variable.

Next, we state a known result on the log-convexity of the spectral radius of a nonnegative matrix which is needed to prove some of the properties of R(m).

Lemma 2 (Friedland Theorem 4.2 [33]). Let D_{n} be the set of n × n real-valued diagonal matrices. Let A be a fixed n × n non-negative matrix having a positive spectral radius. Define ϕ : D_{n} → ℝ by ϕ(D) := log ρ(e^{D}A). Then ϕ(D) is a convex functional on D_{n}. Specifically: for every D_{1}, D_{2} ∈ D_{n} and α ∈ (0, 1),

ϕ(αD_{1} + (1 − α)D_{2}) ≤ αϕ(D_{1}) + (1 − α)ϕ(D_{2}). (45)

Moreover, if A is irreducible and the diagonal entries of A are positive (or A is fully indecomposable) then equality holds in (45) if and only if

D_{1} − D_{2} = cI  (46)

for some c ∈ ℝ, where I is the identity matrix.

Next, we state a result on the derivative of the spectral radius as a function of non-negative matrix elements.

Lemma 3 (Cohen Theorem 1 [34]). Let A be a fixed n × n non-negative matrix having a positive spectral radius. Define D := ρ(A)I − A, where I denotes the n × n identity matrix. Then,

0 < \frac{dρ(A)}{da_{11}} = \frac{|D(1)|}{∑_{i=1}^{n} |D(i)|} < 1  (47)

where D := ρ(A)I−A, I denotes the n×n identity matrix, and |D(i)| is the determinant of the matrix obtained by eliminating the ith row and the ith column from D.

Finally, we state a result on the asymptotic behavior of P^{T}2^{−mR} as m → ∞.

Lemma 4. The following equality holds

lim_{m→0}(P^{T}2^{−mR})^{\frac{1}{m}} = lim_{m→0} ([\begin{matrix}π_{1}2^{mr̄_{1}} & ⋯ & π_{1}2^{mr̄_{n}} \\ ⋮ & ⋮ & ⋮ \\ π_{n}2^{mr̄_{1}} & ⋯ & π_{n}2^{mr̄_{n}} \end{matrix} ])^{\frac{1}{m}}

Appendix C Markov Jump Linear Systems.

Consider the scalar non-homogeneous MJLS [35] with dynamics

z_{k+1} = a_{k}z_{k} + w_{k},  (48)

where z_{k} denotes the state, w_{k} is an additive disturbance, and {A_{k}}_{k≥0} is a Markov rate process defined on a finite set

A = {ā_{1}, …, ā_{n}} ⊆ ℝ^{n},  (49)

and with one-step transition probability matrix P having entries

p_{ij} = P{A_{k} = ā_{j}|A_{k−1} = r̄_{i}}  (50)

for every i, j ∈ {1, …, n}.

We assume that the initial condition Z_{0} and the disturbance process {W_{k}}_{k} are mutually independent random variables with finite mth moment. The system (48) is said to be weakly mth moment stable if

sup_{k} E(|Z|^{m}) < ∞.  (51)

Let A ∈ ℤ_{+}^{n×n} be a diagonal matrix with diagonal entries ā_{1}, …, ā_{n}, i.e.,

A = diag(|ā_{1}|^{m}, …, |ā_{n}|^{m}).  (52)

The following theorem states the necessary and sufficient condition for m-th moment stability of the system (48).

Theorem 7. For any m ∈ ℝ^{+}, the MJLS (48) is weakly mth moment stable iff

ρ(P^{T}A) ≲ 1.  (53)

Proof: The sufficient condition is obtained by subsampling the original MJLS at a sampling rate of τ samples and then showing the weak stability of the subsampled system Y_{k} = Z_{kτ}, k = 0, 1, · · ·. The weak stability of {Y_{k}}_{k} is sufficient to ensure that (51) holds, because the mth moment of the system in fact cannot grow unbounded in any finite time horizon due the assumptions that |ā_{1}|, …, |ā_{n}| are finite and that sup_{k} 𝔼(|W_{k}|^{m}) ≤ ∞.

By iterating (48) τ times, it can be seen that the subsampled process is a non-homogeneous MJLS with dynamics

y_{k+1} = b_{k}y_{k} + c_{k},  (54)

where for every k ≥ 0 we define B_{k} = ∏_{j=kτ}^{(k+1)τ−1} A_{k} as the random expansion of the open-loop system during the k-th sampling interval and C_{k} = ∑_{j=0}^{τ−1}(∏_{i=j}^{τ−1} A_{kτ+i})W_{kτ+j} as the total disturbance entering the system in the k-th sampling interval. Notice that sup_{k} 𝔼(|C_{k}|^{m}) < ∞, since by assumption the disturbance process {W_{k}}_{k} has bounded mth moment.

By taking the mth power in both sides of (54) and by applying the inequality (x + y)^{m} ≤ 2^{m}(x^{m} + y^{m}), which holds for any m > 0, it follows that

𝔼(|Y |^{m}) ≤ 2^{m}𝔼(|B_{k}|^{m}|Y_{k}|^{m}) + const,  (55)

where const represents a uniform bound on the mth moment of {C_{k}}_{k}. Let v_{k,i} = 𝔼(|Y_{k+1}|^{m}1_{{A_{k}=ā_{i}}}), i = 1, …, n. By repeatedly applying the law of total probability on both sides of (55), it can be easily seen that the vector v_{k} = (v_{k,1}, …, v_{k,n})^{T} satisfies the following component-wise vector inequality

v_{k+1} ≤ 2^{m}(P^{T}A)^{τ} v_{k} + c,  (56)

where c is again a constant that only depends on the statistics of the disturbance process. If (??) holds we can choose the subsampling rate τ large enough to ensure that ρ(2^{m}(P^{T}A)^{τ}) < 1 and thus that the above recursion remains bounded. Since E(|Y_{k}|^{m}) = ∑_{i=1}^{n} v_{k,i} it follows that ρ(P^{T}A) < 1 is sufficient to ensure that sup_{k} E(|Y_{k}|^{m}) < ∞ as desired.

The proof of the necessary condition relies on the fact that the non-homogeneous MJLS {Z_{k}}_{k} is weakly stable only if the homogeneous MJLS obtained by setting w_{k} = 0 in (48) is weakly stable. Therefore, we focus on the homogeneous setting wherein w_{k} = 0 for all k and let v_{k,i} = 𝔼(|Z_{k+1}|^{m}1_{{A_{k}=ā_{i}}}) for i = 1, …, n. By (48) and the law of total probability, the vector v_{k} = (v_{k,1}, …, v_{k,n})^{T} evolves over time according to the linear system

v_{k+1} = P^{T}Av_{k}.  (57)

Since E(|Z_{k}|^{m}) = ∑_{i=1}^{n} v_{k,i}, we conclude that (51) can hold only if the above linear system is stable and therefore only if ρ(P^{T}A) ≤ 1, as claimed.

Theorem 7 extends the well known conditions for second moment stability given in [35] to m-th moment stability. A similar result appears in [36, Theorem 3.2] in the special case of a homogeneous MJLS driven by an i.i.d. rate process.

Appendix D Proofs

A. Theorem 1

Necessity. To establish the necessary condition, we prove that for every k = 0, 1, …,

c_{m} E[|X_{k}|^{m}] ≥ E[|Z_{k}|],  (58)

where c_{m} is a constant defined in Lemma 1 and {z_{k}} is a homogeneous MJLS with dynamics

z_{k+1} = \frac{|λ|^{m}}{2^{mr_{k}}} z_{k}  (59)

and z_{0} = e^{2h(X_{0})}.

Let S^{k} = {S_{0}, …, S_{k}} denote the symbols transmitted over the digital link up to time k. By the law of total expectation and Lemma 1 ,

E(|X_{k+1}|^{m}) ≥ \frac{1}{c_{m}} E_{S^{k}}(e^{mh(X_{k+1}|S^{k}=a^{k})}). (60)

It follows that the m-th moment of the state is lower bounded by the average entropy power of X_{k} conditional on S^{k}. From the translation invariance property of the differential entropy, the conditional version of entropy power inequality [37], and Assumption A2, it follows that

E_{S^{k}}(e^{mh(X_{k+1}|S^{k}=s^{k})})
= E_{S^{k}}(e^{mh(λX_{k}+x̂(s^{k})+V_{k}|S^{k}=s^{k})})
≥ E_{S^{k}} ((e^{2h(λX_{k}|S^{k}=s^{k})} + e^{2h(V_{k})} )^{\frac{m}{2}} )
≥ E_{S^{k}} (e^{mh(λX_{k}|S^{k}=s^{k})})
= |λ|^{m} E_{S^{k}}(e^{mh(X_{k}|S^{k}=s^{k})})  (61)

We can further lower bound (61) as in Lemma 1 in [22], and obtain that for every k ≥ 0

E_{S^{k}|S^{k−1},R_{k}}(e^{mh(X_{k}|S^{k}=s^{k})}) ≥ \frac{1}{2^{mR_{k}}} e^{mh(X_{k}|S^{k−1}=s^{k−1})},

(62)

with S_{−1} = ∅. By the tower rule of conditional expectation, it then follows that

E_{S^{k}}(e^{mh(X_{k}|S^{k}=s^{k})}) ≥
E_{S^{k−1},R_{k}} (\frac{1}{2^{mR_{k}}} e^{mh(X_{k}|S^{k−1}=s^{k−1})}) . (63)

Combining (63) and (61) gives

E_{S^{k}} (e^{mh(X_{k+1}|S^{k}=s^{k})})
≥ E_{R_{k}} (\frac{|λ|^{m}}{2^{mR_{k}}} E_{S^{k−1}|R_{k}}(e^{mh(X_{k}|S^{k−1}=s^{k−1})})) . (64)

Following similar steps and using the Markov chain S^{k−1} → (S^{k−2}, R_{k−1}) → R_{k}, we obtain

E_{S^{k−1}|R_{k}}(e^{mh(X_{k}|S^{k−1}=s^{k−1})})

≥ |λ|^{m} E_{S^{k−1}|R_{k}}(e^{mh(X_{k−1}|S^{k−1}=s^{k−1})})

≥ E_{S^{k−2},R_{k−1}|R_{k}} (\frac{|λ|^{m}}{2^{mR_{k−1}}} e^{mh(X_{k−1}|S^{k−2}=s^{k−2})})

= E_{R_{k−1}|R_{k}} (\frac{|λ|^{m}}{2^{2R_{k−1}}} E_{S^{k−2}|R_{k−1},R_{k}}[e^{2h(X_{k−1}|S^{k−2}=s^{k−2})}]) . (65)

Substituting (65) into (64) and re-iterating k times, it follows that E_{S^{k}}(e^{mh(X_{k+1}|S^{k}=s^{k})}) is lower bounded by

E_{R_{k−1},R_{k}}(\frac{|λ|^{2m}}{2^{m(R_{k−1}+R_{k})}}

× E_{S^{k−2}|R_{k−1},R_{k}}(e^{mh(X_{k−1}|S^{k−2}=s^{k−2})}))

≥ E_{R_{1},...,R_{k}} (\frac{|λ|^{mk}}{2^{m(R_{1}+···+R_{k})}} E_{S_{1}|R_{1},...,R_{k}}(e^{mh(X_{1}|S_{0}=s_{0})})) (66)

= E (\frac{|λ|^{m(k+1)}}{2^{m(R_{1}+···+R_{k})}} ) e^{mh(X_{0})},  (67)

where (66) uses the fact that the initial condition of the state x_{0} is independent of the rate process R_{k}. Let {Z_{k}} be a nonhomogeneous MJLS with dynamics

Z_{k+1} = |λ|^{m}/2^{mR_{k}}Z_{k},  (68)

with z_{0} = e^{mh(X_{0})}. By taking the expectation on both sides of (68) and iterating k times, it is easy to see that the right hand side of (67) is equal to the first moment of Z_{k+1}. Hence, combining (60)–(67) we conclude that E(|X_{k}|^{m}) > \frac{1}{c_{m}} E(|Z_{k}|), which is the claim.

Sufficiency. Let ω denote a uniform bound on the measure of the support of the initial condition, the noise, and the disturbance. Then, we claim that the plant dynamics can be bounded as follows

|x_{k}| ≤ z_{k}, k = 0, 1, …,  (69)

where Z_{k} is a homogeneous MJLS with dynamics

z_{k+1} = \frac{|λ|}{2^{R_{k}}} z_{k} + ω, k = 0, 1, …

and z_{0} = ω. To see this, consider the following inductive proof. By assumption, |x_{0}| ≤ ω = z_{0}. Assume that the claim holds for all times up to k, so |x_{k}| ≤ z_{k}. Suppose that at time k the uncertainty set [−z_{k}, z_{k}] is quantized using a r_{k}-bit uniform quantizer, and that the encoder communicates to the decoder the interval containing the state. Then, the decoder approximates the state by the centroid x̂_{k} of this interval and sends to the plant the control input u_{k} = −λx̂_{k}. By construction |x_{k} − x̂_{k}| ≤ z_{k}/2^{r_{k}}, thus

|x_{k+1}| = |λ(x_{k} − x̂_{k}) + v_{k}|

≤ |λ||x_{k} − x̂_{k}| + ω

≤ \frac{|λ|}{2^{r_{k}}} z_{k} + ω

= z_{k+1}  (70)

i.e., the claim holds at time k + 1 as well. It follows that x_{k} is mth moment stable if the homogeneous MJLS z_{k} is weakly mth moment stable, i.e., if and only if (11) holds.

B. Proposition 2

The monotonicity property is an immediate consequence of the log-convexity of the spectral radius of a nonnegative matrix, see, e.g. 2. Let D_{1} = −mR ln 2, D_{2} = 0_{n×n} and α = \frac{n}{m}. Notice that 2^{−mR} = e^{D_{1}}, log ρ(P^{T}e^{D_{2}}) = 0, and P^{T}2^{−mR} = P^{T}e^{αD_{1}}. Then, for every n < m, by Lemma 2

−nR(m) = \frac{n}{m} log ρ(P^{T}2^{−mR})
= α log ρ(P^{T}e^{D_{1}}) + (1 − α) log ρ(P^{T}e^{D_{2}})

> log ρ(P^{T}e^{αD_{1}+(1−α)D_{2}})
= log ρ(P^{T}2^{−nR})
= −nR(n).  (71)

By dividing both sides by −n, it then follows that R(n) > R(m), establishing that R(m) is a strictly decreasing function of m.

To establish the convergence of R(m) to the Shannon capacity as m → 0, observe that

lim_{m→0} R(m)

= lim_{m→0} log ρ((P^{T}2^{−mR})^{\frac{1}{m}} )

= log ρ( lim_{m→0}(P^{T}2^{−mR})^{\frac{1}{m}} )

=^{(a)} log ρ ( lim_{m→0} ([\begin{matrix}π_{1}2^{mr̄_{1}} & ⋯ & π_{1}2^{mr̄_{n}} \\ ⋮ & ⋮ & ⋮ \\ π_{n}2^{mr̄_{1}} & ⋯ & π_{n}2^{mr̄_{n}} \end{matrix} ])^{\frac{1}{m}} )

= lim_{m→0} \frac{1}{m} log ρ ([\begin{matrix}π_{1}2^{mr̄_{1}} & ⋯ & π_{1}2^{mr̄_{n}} \\ ⋮ & ⋮ & ⋮ \\ π_{n}2^{mr̄_{1}} & ⋯ & π_{n}2^{mr̄_{n}} \end{matrix} ])

= lim_{m→0} \frac{1}{m} log (∑_{i} π_{i}2^{mr̄_{i}})

=^{(b)} lim_{m→0} \frac{∑_{i} π_{i}r_{i}2^{mr̄_{i}}}{∑_{i} π_{i}2^{mr̄_{i}}}

= ∑_{i} π_{i}2^{mr̄_{i}}

where (a) follows from Lemma 4 and (b) follows from l’Hôpital’s rule.

The convergence of R(m) to the zero-error capacity as m → ∞ can be proved using the fact that, as m → ∞

R(m) = −\frac{1}{m} log ρ(P^{T}2^{−mR})

= − log ρ((P^{T}2^{−mR})^{1/m})

= r̄_{1} − log ρ ([\begin{matrix}p_{11} & ⋯ & p_{n1}2^{−m(r̄_{n}−r̄_{1})} \\ ⋮ & ⋮ & ⋮ \\ p_{1n} & ⋯ & p_{nn}2^{−m(r̄_{n}−r̄_{1})} \end{matrix}]^{1/m})

∼ r̄_{1} − \frac{1}{m} log p_{11},

where the last equation follows from the fact that for any column vector v = (v_{1}, …, v_{n})^{T}, ρ([v 0_{n×(n−1)}]) = v_{1}. From the above asymptotic approximation it immediately follows that if r̄_{1} = 0, then

lim_{m→∞} mR(m) = − log p_{11}.  (72)

Next, the property on the sensitivity with respect to selfloop probabilities is a direct application of a result in [34], which is re-stated here as Lemma 3, on the derivative of the spectral radius as a function of non-negative matrix elements.

Next, the monotonicity property of −mR(m) = log ρ(P^{T}2^{−mR}) follows from the fact that all the entries of the matrix P^{T}2^{−mR} are monotonically decreasing in m. Finally, the strict concavity of mR(m) is again a direct consequence of the log-convexity of the spectral radius of a nonnegative matrix stated in Lemma 2.

C. Theorem 4

Proof: By Theorem 1 and Theorem 3, at the boundaries of the stability region we must have that

log |λ| = R(m).  (73)

and

log |λ| = C(m log |λ|).  (74)

Therefore, (20) follows by combining (73) and (74). Next, by Proposition 2, the function ϕ(m) = mR(m) is increasing and strictly concave, thus invertible. It follows that for every α ≥ 0, there exists a unique m := m(α) such that

mR(m) = α.  (75)

Substituting this equality into (20), it follows that C_{A}(α) = R(m(α)). as claimed. The remaining properties are immediate consequences of Proposition 2. By definition, C_{A}(α) is non increasing in α. Since both mR(m) and R(m) are both monotonic function of m, however, it follows that C_{A}(α) must be strictly decreasing in α, thus establishing 2). Property 3) follows from (20) combined with the fact that mR(m) → 0 and R(m) → C as m → 0. Similarly, property 4) follow directly by combining (20) with properties 3) and 5) in Proposition 2.

D. Theorem 5

Proof: By (21) and the definition of R(m), for every α there exists an m(α) such that

ρ(P^{T}2^{−m(α)R}) = 2^{−α}  (76)

In the case of a Markov erasure channel, a simple calculation shows that

ρ(P^{T}2^{−mR}) = \frac{tr}{2} + \frac{1}{2}\sqrt{tr^{2} − 4det},  (77)

where tr and det denote the trace and determinant of (27), respectively. By combining (76) and (77) and squaring both sides of the resulting equation, it follows that m(α) must satisfy

2^{−α}tr − 4det = 2^{−α+1},  (78)

where tr = (1 − q) + 2^{−m(α)r̄}(1 − p) and det = 2^{−m(α)r̄}(1 − p − q). Solving (78) yields

m(α) = \frac{1}{r̄} (α + log_{2} (\frac{1 − p − 2^{α}(1 − p − q)}{1 − (1 − q)2^{α}})) (79)

for 0 ≤ α < − log_{2}(1 − q). Finally, substituting (79) into (22) yields (28).

E. Theorem 6 Proof: In the special case of an i.i.d. rate process,

P^{T}2^{−mR} = (p_{1}, …, p_{n})^{T}(2^{−mr̄_{1}}, …, 2^{−mr̄_{n}})

is a rank-one matrix whose only nonzero eigenvalue is ∑_{i=1}^{n} p_{i}2^{−mr̄_{i}} = 𝔼(2^{−mR}). Therefore, in this case

R(m) = −\frac{1}{m} log 𝔼(2^{−mR})
= −\frac{1}{m} log M_{R}(−m ln 2).  (80)

By combining (21) and (80), we find that α = − log M_{R}(−m(α) ln 2) and so

m(α) = −\frac{1}{ln 2}M_{R}^{−1}(2^{−α}),  (81)

where M_{R}^{−1}(y) exists in light of property 5) in Proposition 2. Thus, by (22), (32) follows.