= -\log_2 (1-q) $ because the probability that $d$ consecutive zeros occurs is $(1-q)^d= 2^{-d (-\log_2(1-q))}$. In the case $n=2$, $\bar{r}_1=0$, $\bar{r}_2=r$, and an i.i.d. rate process with $\pr{R_k = 0}= p_1$ and $P\{R_k = r\}= p_2$ for all $k$'s, then the stability condition becomes \begin{align*} \la^m \left( p_1 + p_2 2^{-mr } \right)<1, \end{align*} which provides a converse to the achievable scheme of Y\"{u}ksel and Meyn~\verb|\cite[Theorem 3.3]{Yuksel--Meyn2013}|. If we further let $r~\to~\infty$, then the stability condition $p_1>1/\la^m$ depends only on the erasure rate of the channel. In this case, our condition generalizes the packet loss model result in~\verb|\cite{Gupta-etal-2007}|. \section{Memoryless Channels} Consider the special case of an i.i.d. rate process $R_k$ where $R_k \sim R$ has probability mass function $p_i=\pr{R=\bar{r}_i}$, $\bar{r}_i \in \mathcal{R}$. For $t$ real, Let $M_R(t)= \mathbb{E}( 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. \medskip \begin{theorem} \label{thm:memo} The anytime capacity of a memoryless channel with rate distribution $R$ is \begin{equation} C_A(\alpha) = \frac{\ln 2^{-\alpha} }{M_R^{-1}( 2^{- \alpha})} \label{eq:mmf3} \end{equation} for $\alpha < -\log p_{11}$ if $\bar{r}_0 = 0$, or for any $\alpha > 0 $ if $\bar{r}_0 \neq 0$. \end{theorem} \medskip Theorem~\verb|\ref{thm:memo}| 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. \begin{example} \label{ex4} Suppose that $R$ is a binomial random variable with parameters $k$ and $1-p$. Then, \begin{equation} M_R(t) = ( p + (1-p) e^{t})^k \end{equation} and \begin{equation} M_R^{-1}(y) = \ln \frac{y^{1/k} - p}{ 1-p }, \quad y < p^k, \end{equation} and thus by~\eqref{eq:mmf3} \begin{align} \label{eq:xu2} C_A(\alpha) = \frac{ \alpha }{ \alpha/k + \log_2 \left(\frac{ 1-p }{1-p2^{\alpha/k}}\right) } \end{align} for $\alpha < - k \log p$. Notice that ~\eqref{eq:xu2} recovers~\eqref{eq:xu} in the special case $k=1$ in which $R$ is Bernoulli with parameter $1-p$. \end{example} \begin{example} \label{ex4} Suppose that $R$ is a Poisson random variable with parameter $\lambda$. Then, \begin{equation} M_R(t) = e^{\lambda (e^{t}-1)} \end{equation} and \begin{equation} M_R^{-1}(y) = \ln (1 + 1/\lambda \ln y), \quad y > 0, \end{equation} and thus by~\eqref{eq:mmf3} \begin{align} C_A(\alpha) = -\frac{ \alpha }{ \log( 1 -\alpha/\lambda \ln 2 ) } \end{align} for $\alpha < - \lambda/\ln 2 $. \end{example} Notice in both examples $\bar{r}_1=0$, so the anytime capacity has bounded support. In the next example $\bar{r}_1=1$ and thus the anytime capacity is defined for all $\alpha>0$. \begin{example} \label{ex3} Suppose that $R$ is a geometric random variable with parameter $p$. Then, \begin{equation} M_R(t) = \frac{p e^{t}}{ 1- (1-p)e^{t} } \end{equation} for $t < - \ln(1-t)$ and \begin{equation} M_R^{-1}(y) = \ln \frac{y}{ p + y(1-p) }, \quad y > 0, \end{equation} for $y>0$, and thus \begin{align} C_A(\alpha) = \frac{\alpha }{ \log\bigl( (1-p) + p 2^{\alpha} \bigr) }, \quad \alpha > 0. \end{align} \end{example} \begin{figure} \begin{center} \includegraphics[width=3.1in]{any_comp.eps} \end{center} \caption{Comparison of the anytime capacity for different memoryless channels. For the uniform distribution the plot is obtained numerically.} \label{fig:t3} \end{figure} %\section{Conclusion} % %{\color{red} Incomplete} %A commonly encountered notion of stochastic stability in the MJLS literature~\verb|\cite{Costa-et-al-2004}| is the one of strong moment stability, according to which the MJLS~\eqref{eq:mjls} is stable if there exists a finite $\alpha_m \in \mathbb{R}$ such that %$ \E[ |Z|^m ] \to \alpha_m, \qquad \text{ as } m \to \infty. $ %Clearly, if a MJLS is strongly stable, then it is also weakly stable. It can be verified that the proof of the necessary condition in Theorem~\verb|\ref{lemmamjls}| extends to the case of strong moment stability, thereby establishing the necessity of~\eqref{eq:pp2} for the strong moment stability of~\eqref{eq:mjls}. In contrast, the subsampling technique used in the direct part of Theorem~\verb|\ref{lemmamjls}| is not suitable to prove strong moment stability because it cannot prevent undesirable fluctuations in the system dynamics between any two sampling periods. %In~\verb|\cite{minero-etal-2013}|, we presented a different proof technique based on the binomial expansion of $(a_k z_k+w_k)^m$ which can be used to prove that~\eqref{eq:pp} is a sufficient condition for the strong moment stability of~\eqref{eq:mjls}. This approach however requires $m$ to be an integer number, as opposed to the subsampling technique which can be applied to any $m>0$. % %\subsection{Error exponents} %We now compare the the anytime error exponent to error exponents of block codes. Specifically, we can compare the curves in Fig.~\verb|\ref{fig:scheme}| obtained by evaluating~\eqref{eq:anyMarkov} with the results by Como, Y\"{u}ksel, and Tatikonda in \verb|\cite[Section VI]{Comoetal2009}|. \emph{to do} %\begin{figure} %\begin{center} %\includegraphics[scale=0.5]{BECMemory.eps} %\end{center} %\caption{Anytime reliability of a BEC with Markov erasure for different recovery probability $q$ and $p=0.8$.} \label{fig:scheme} %\end{figure} \bibliographystyle{IEEEtran} \bibliography{bib_control} %\appendices %\section{Stability threshold function examples} %%We now give some representative examples of the stability threshold function, visually showing its extremal properties and its relationship with the anytime capacity. %\begin{example} %\label{ex1} %Let $n=4$,$\mathcal{R}=\{1,3,4,5\}$ and $\mtx{P}$ be is a $4 \times 4$ circulant matrix with first row equal to $\frac{1}{16}\left(1,13,1,1\right)$, namely %\begin{equation} %\label{eq:exP} %P= \frac{1}{16} %\begin{bmatrix} % 1 & 13 & 1 & 1 \\[0.3em] % 13 & 1 & 1 & 1 \\[0.3em] % 1 & 1 & 1 & 13 \\[0.3em] % 1 & 1 & 13 & 1 % \end{bmatrix}. %\end{equation} %In this case it is easy to compute $C= \frac{1}{4}(1+3+4+5) = \frac{13}{4}$ and $C_0=1$. Figure~\verb|\ref{fig:t2}| plots the stability threshold function $R(m)$ (together with its asymptotic approximation) and the anytime capacity $C_A(\alpha)$. 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 $\alpha$, as indication that $R(m)$ and $C_A(\alpha)$ are generally not convex functions. In contrast, the function $\phi(m)=m R(m)$, reported in red in the top plot of Figure~\verb|\ref{fig:t2}|, is strictly convex and increasing. %\end{example} %\begin{figure} %\begin{center} %\includegraphics[width=3.2in]{newt2.eps} %\includegraphics[width=3.2in]{c2.eps} %\end{center} %\caption{Stability threshold function and anytime capacity for Example~\verb|\ref{ex1}|} \label{fig:t2} %\end{figure} % %\begin{example} %\label{ex2} %Let $\mathcal{R}=\{0,3,4,5\}$ and $\mtx{P}$ is as in~\eqref{eq:exP}. The only difference with the previous example is that $\bar{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~\verb|\ref{fig:t1}| plots the stability threshold function $R(m)$ (together with its asymptotic approximation) and the anytime capacity $C_A(\alpha)$. In this case, while $R(m)$ has unbounded support, $C_A(\alpha)$ is zero for all $\alpha \ge - \log p_{11} = \log 16 = 4$. This occurs because the function $\phi(m)=m R(m)$ saturates as $m \rightarrow \infty$, tending to the limiting value $- \log p_{11}=4$. %\end{example} %\begin{figure} %\begin{center} %\includegraphics[width=3.2in]{newt1.eps} %\includegraphics[width=3.2in]{c1.eps} %\end{center} %\caption{Stability threshold function and anytime capacity for Example~\verb|\ref{ex2}|.} \label{fig:t1} %\end{figure} % %When viewed together, the two examples above show that for some channels a communication system with an arbitrary rate-reliability pair $(r,\alpha)$ cannot be constructed, because the anytime capacity may have bounded support and tend abruptly to zero. However, in order to achieve $m$th moment stabilization it is sufficient to consider the simpler function $R(m)=C_A(m R(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 $\alpha$. 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 $\alpha$ is achieved. % % % %\section{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. % %\begin{lemma} \label{lem:vme} % Let ${X}$ be a continuous $n$-dimensional vector-valued random variable with $\mathbb{E}[||{{X}}||_m^m]0$, it follows that %\begin{align} %\label{eq:0} %\mathbb{E}(|Y|^m) & \le 2^m \mathbb{E}(| B_k|^m |Y_k |^m) + \text{const}, %\end{align} %where $\text{const}$ represents a uniform bound on the $m$th moment of $\{C_k\}_k$. Let $v_{k,i} = \mathbb{E}( |Y_{k+1}|^m 1_{\{A_{k} = \bar{a}_i}\} )$, $i=1,\dotsc,n$. By repeatedly applying the law of total probability on both sides of~\eqref{eq:0}, it can be easily seen that the vector $v_k=(v_{k,1},\ldots,v_{k,n})^T$ satisfies the following component-wise vector inequality %\begin{equation} %v_{k+1} \leq 2^m \bigl( \mtx{P}^\tra \mtx{A}\bigr)^\tau v_{k} + c, %\end{equation} %where $c$ is again a constant that only depends on the statistics of the disturbance process. If~\eqref{eq:pp2} holds we can choose the subsampling rate $\tau$ large enough to ensure that $\rho(2^m \bigl( \mtx{P}^\tra \mtx{A}\bigr)^\tau) <1$ and thus that the above recursion remains bounded. Since $\E(|Y_{k}|^{m}) = \sum_{i=1}^{n}v_{k,i} $ it follows that $\rho(\mtx{P}^\tra \mtx{A}) < 1$ is sufficient to ensure that $\sup_{k} \E(|Y_k|^m) < \infty$ 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~\eqref{eq:mjls} is weakly stable. Therefore, we focus on the homogeneous setting wherein $w_k=0$ for all $k$ and let $v_{k,i} = \mathbb{E}( |Z_{k+1}|^m 1_{\{A_{k} = \bar{a}_i}\} )$ for $i=1,\dotsc,n$. By~\eqref{eq:mjls} and the law of total probability, the vector $v_k=(v_{k,1},\ldots,v_{k,n})^T$ evolves over time according to the linear system %\begin{equation} %v_{k+1} = \mtx{P}^\tra \mtx{A} v_{k}. %\end{equation} %Since $\E(|Z_{k}|^{m}) = \sum_{i=1}^{n}v_{k,i} $, we conclude that~\eqref{eq:weak} can hold only if the above linear system is stable and therefore only if $\rho(\mtx{P}^\tra \mtx{A}) \leq 1$, as claimed. %% %\end{IEEEproof} % %%Notice the trivial gap between the necessary and sufficient conditions in~\eqref{eq:pp} and ~\eqref{eq:pp2}. %in the case where $c \neq 0$ and $m < 2$. In this regime the EPI cannot be applied. %%To express the condition for transition to instability with a single inequality, while indicating the existence of this trivial gap, in the rest of the paper we write %%\begin{equation} %%\label{eq:sss} %%\rho(\mtx{P}^\tra \mtx{A}) \lesssim 1. %%\end{equation} %Theorem~\verb|\ref{lemmamjls}| extends the well known conditions for second moment stability given in~\verb|\cite{Costa-et-al-2004}| to $m$-th moment stability. A similar result appears in~\verb|\cite[Theorem 3.2]{fang--etal1994}| in the special case of a homogeneous MJLS driven by an i.i.d. rate process. % %%%%%%%%%%%%%%%%%%%%%% % %\section{Proofs} %\subsection{Theorem~\verb|\ref{thm1}|} % %{\em Necessity}. To establish the necessary condition, we prove that for every $k=0,1,\ldots$, %%\begin{equation} %%\E[|x_k|^2] \geq \tfrac{1}{2\pi e}\E[|z_k|^2], %%\end{equation} %\begin{equation} %\label{eq:lbstate2} %c_m \E[\vert X_k\vert^m] \ge \E[\vert Z_k\vert], %\end{equation} %where $c_m$ is a constant defined in Lemma~\verb|\ref{lem:vme}| and $\{z_k\}$ is a homogeneous MJLS with dynamics %\begin{align} %z_{k+1}=\frac{|\lambda|^m}{2^{mr_k}} z_k %\label{eq:zzzz} %\end{align} %and $z_0=e^{2h(X_0)}$. % %Let $S^k = \{S_0,\ldots,S_k \}$ denote the symbols transmitted over the digital link up to time $k$. By the law of total expectation and Lemma~\verb|\ref{lem:vme}| , %\begin{align} %\E ( |X_{k+1}|^m ) & \ge \frac{1}{c_m}~\E_{S^{k}} \bigl( e^{mh(X_{k+1}|S^{k}=a^{k}) }\bigr) %\label{eq:in_0}. %\end{align} %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~\verb|\cite{El-Gamal--Kim2011}|, and Assumption A2, it follows that %\begin{align} %& \E_{S^{k}} \bigl( e^{ m h(X_{k+1} |S^{k}=s^{k}) }\bigr)\nonumber \\ %% %& = \E_{S^{k}} \bigl( e^{m h(\lambda X_{k} + \hat{x}(s^{k}) + V_k |S^{k}=s^{k}) }\bigr) \nonumber \\ %% %% %& \ge \E_{S^{k}} \left( \bigl( e^{2 h(\lambda X_{k} |S^{k}=s^{k}) } + e^{2 h(V_k)} \; \bigr)^{\frac{m}{2}} \right) \nonumber \\ %% %& \ge \E_{S^{k}} \left( e^{m h(\lambda X_{k} |S^{k}=s^{k}) } \right) \nonumber \\ %% %& = |\lambda|^m \E_{S^{k}} \bigl( e^{mh(X_{k} |S^{k}=s^{k}) } \bigr) \label{eq:ineq1} %\end{align} %We can further lower bound~\eqref{eq:ineq1} as in Lemma~1 in~\verb|\cite{Minero-etal-2009}|, and obtain that for every $k \geq 0$ %\begin{equation} %\label{lem_min} %\E_{S^k|S^{k-1},R_k} \bigl( e^{ m h(X_k|S^{k}=s^{k})} \bigr) \geq \frac{1}{2^{mR_k}}e^{ m h(X_k|S^{k-1}=s^{k-1})}, %\end{equation} %with $S_{-1}=\emptyset$. By the tower rule of conditional expectation, it then follows that %\begin{align} %& \E_{S^{k}} \bigl( e^{m h(X_{k} |S^{k}=s^{k}) } \bigr) \geq \nonumber \\ %& \qquad \E_{S^{k-1},R_k} \left( \frac{1}{2^{m R_k } } e^{m h(X_k|S^{k-1}=s^{k-1}) } \right). \label{eq:ineq2} %\end{align} %Combining~\eqref{eq:ineq2} and~\eqref{eq:ineq1} gives %% %\begin{align} %& \E_{S^{k}} \left( e^{ m h(X_{k+1} |S^{k}=s^{k}) }\right) \nonumber \\ %%& = |\lambda|^2 \E_{S^{k-1},R_k} \bigl( \E_{S^{k}|S^{k-1},R_k} \bigl( e^{2h(x_{k} |S^{k}=s^{k}) } \bigr) \bigr) + \beta \nonumber \\ %% %%& \ge |\lambda|^2 \E_{S^{k-1},R_k} \left( \frac{1}{2^{2 R_k} } e^{2h(x_{k} |S^{k-1}=s^{k-1}) } \right) + \beta \nonumber \\ %% %& \geq \E_{R_k} \left( \frac{ |\lambda|^m }{2^{m R_k} } \E_{S^{k-1}|R_k} \bigl( e^{m h(X_{k} |S^{k-1}=s^{k-1}) } \bigr) \right). \label{eq:in_1} %\end{align} %% %Following similar steps and using the Markov chain $S^{k-1}\to ( S^{k-2},R_{k-1}) \to R_k$, we obtain %\begin{align} %& \E_{S^{k-1}|R_k} \bigl( e^{m h(X_{k} |S^{k-1}=s^{k-1}) } \bigr) \nonumber \\ %% %& \geq |\lambda|^m \E_{S^{k-1}|R_k} \bigl( e^{m h(X_{k-1} |S^{k-1}=s^{k-1}) } \bigr) \nonumber \\ %% %%& = |\lambda|^2 \E_{S^{k-2},R_{k-1}|R_k} \left( \E_{S^{k-1}|S^{k-2},R_{k-1}} \bigl[ e^{2h(x_{k-1} |S^{k-1}=s^{k-1}) } \bigr) \right) + \beta \nonumber \\ %% %& \ge \E_{S^{k-2},R_{k-1}|R_k} \left( \frac{|\lambda|^m}{2^{m R_{k-1}}} e^{m h(X_{k-1} |S^{k-2}=s^{k-2}) } \right) \nonumber \\ %% %& = \E_{R_{k-1}|R_k} \left( \frac{|\lambda|^m}{2^{2R_{k-1}}} \E_{S^{k-2}|R_{k-1},R_k} \bigl[ e^{2h(X_{k-1} |S^{k-2}=s^{k-2}) } \bigr] \right). \label{eq:in_2} %% %\end{align} %% %Substituting~\eqref{eq:in_2} into~\eqref{eq:in_1} and re-iterating $k$ times, it follows that $ \E_{S^{k}} \bigl( e^{ m h(X_{k+1} |S^{k}=s^{k}) }\bigr)$ is lower bounded by %\begin{align} %& \E_{R_{k-1},R_k} \Bigl( \frac{|\lambda|^{2m}}{2^{m(R_{k-1} + R_k )}} \nonumber \\ %& \qquad \qquad \times \E_{S^{k-2}|R_{k-1},R_k} \Bigl( e^{m h(X_{k-1} |S^{k-2}=s^{k-2}) } \Bigr) \Bigr) \nonumber \\ %% %& \geq \E_{R_{1},\dotsc,R_k} \left( \frac{|\lambda|^{mk} }{2^{m(R_{1} +\cdots + R_k )}} \E_{S_1 |R_{1},\dotsc,R_k} \Bigl( e^{m h(X_{1} |S_0=s_0 ) } \Bigr) \right) \label{eq:in_3} \\ %% %& = \E \left( \tfrac{|\lambda|^{m(k+1)} }{2^{m(R_{1} +\cdots + R_k )}} \right) e^{mh(X_{0})} \label{eq:in_4}, %% %\end{align} %where~\eqref{eq:in_3} 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 non-homogeneous MJLS with dynamics %\begin{align} %Z_{k+1}=|\lambda|^m/2^{mR_k} Z_k, %\label{eq:nec_mjls22} %\end{align} %with $z_0=e^{mh(X_0)}$. By taking the expectation on both sides of~\eqref{eq:nec_mjls22} and iterating $k$ times, it is easy to see that the right hand side of~\eqref{eq:in_4} is equal to the first moment of $Z_{k+1}$. Hence, combining~\eqref{eq:in_0}--\eqref{eq:in_4} we conclude that $\E(| X_k |^m) > \frac{1}{c_m}\E ( |Z_k| )$, which is the claim. % %{\em Sufficiency}. Let $\omega$ 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 %\begin{equation} %\label{eq:in_} %|x_k| \le z_k, \quad k=0,1,\ldots, %\end{equation} %where $Z_k$ is a homogeneous MJLS with dynamics %$$z_{k+1} = \frac{|\lambda|}{2^{R_k}}z_k + \omega, \quad k=0,1,\ldots$$ %and $z_0 = \omega$. To see this, consider the following inductive proof. By assumption, $|x_0|\leq \omega = z_0$. Assume that the claim holds for all times up to $k$, so $|x_{k}|\le 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 $\hat{x}_k$ of this interval and sends to the plant the control input $u_k = -\lambda \hat{x}_k$. By construction $|x_k-\hat{x}_k| \le z_k/2^{r_k}$, thus %\begin{align} %|x_{k+1}| & = |\lambda (x_k-\hat{x}_k) + v_k | \nonumber \\ %& \le |\lambda| |x_k-\hat{x}_k| + \omega \nonumber \\ %& \le \frac{|\lambda|}{2^{r_k}}z_k + \omega \nonumber \\ %& = z_{k+1} %\end{align} %i.e., the claim holds at time $k+1$ as well. It follows that $x_k$ is $m$th moment stable if the homogeneous MJLS $z_k$ is weakly $m$th moment stable, i.e., if and only if~\eqref{eq:Rm} holds. % % %\subsection{Proposition~\verb|\ref{prop1}|} %\label{App1} % %The monotonicity property is an immediate consequence of the log-convexity of the spectral radius of a nonnegative matrix, see, e.g.~\verb|\ref{thm:Friedland}|. Let $ \mtx{D}_1 = - m \mtx{R} \ln 2$, $ \mtx{D}_2 = \mtx{0}_{n\times n}$ and $\alpha = \frac{n}{m}$. Notice that $ 2^{-m \mtx{R}} = e^{ \mtx{D}_1}$, $\log \rho( \mtx{P}^\tra e^{ \mtx{D}_2} ) = 0$, and $\mtx{P}^\tra 2^{-m \mtx{R}} = \mtx{P}^\tra e^{\alpha \mtx{D}_1}$. Then, for every $n < m$, by Lemma~\verb|\ref{thm:Friedland}| %\begin{align} %-n R(m) & = \frac{n}{m} \log \rho( \mtx{P}^\tra 2^{-m \mtx{R}} ) \nonumber \\ %& = \alpha \log \rho( \mtx{P}^\tra e^{\mtx{D}_1} ) + (1-\alpha) \log \rho( \mtx{P}^\tra e^{\mtx{D}_2} ) \nonumber \\ %% %& > \log \rho( \mtx{P}^\tra e^{\alpha \mtx{D}_1 + (1-\alpha) \mtx{D}_2} ) \nonumber \\ %& = \log \rho( \mtx{P}^\tra 2^{-n\mtx{R}} ) \nonumber \\ %& = -n R(n). %\end{align} %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 \to 0$, observe that %\begin{align*} %& \lim_{m \to 0} R(m) \\ %& = \lim_{m \to 0} \log \rho\bigl( (\mtx{P}^\tra 2^{-m\mtx{R}})^{\frac{1}{m}} \bigr) \\ %% %& = \log \rho\bigl( \lim_{m \to 0}(\mtx{P}^\tra 2^{-m\mtx{R}})^{\frac{1}{m}} \bigr) \\ %% %& \stackrel{(a)}{=} \log \rho \left( \lim_{m \to 0} \left( \begin{bmatrix} % \pi_1 2^{m \bar{r}_1} & \cdots & \pi_1 2^{m \bar{r}_n} \\ % \vdots & \vdots & \vdots \\ % \pi_n 2^{m \bar{r}_1} & \cdots & \pi_n 2^{m \bar{r}_n} % \end{bmatrix} %\right)^{\frac{1}{m}} \right) \\ %% %& = \lim_{m \to 0} \frac{1}{m}\log \rho \left( \begin{bmatrix} % \pi_1 2^{m \bar{r}_1} & \cdots & \pi_1 2^{m \bar{r}_n} \\ % \vdots & \vdots & \vdots \\ % \pi_n 2^{m \bar{r}_1} & \cdots & \pi_n 2^{m \bar{r}_n} % \end{bmatrix} \right) \\ %% %& = \lim_{m \to 0} \frac{1}{m}\log \left( \sum_{i} \pi_i 2^{m\bar{r}_i} \right) %\\ %% %& \stackrel{(b)}{=} \lim_{m \to 0} \frac{ \sum_{i} \pi_i r _i 2^{m\bar{r}_i} }{ \sum_{i} \pi_i 2^{m\bar{r}_i} } %\\ %& = \sum_{i} \pi_i 2^{m\bar{r}_i} %\end{align*} %where (a) follows from Lemma~\verb|\ref{eq:lim1}| and (b) follows from l'H\^opital's rule. % %The convergence of $R(m)$ to the zero-error capacity as $m \to \infty$ can be proved using the fact that, as $m \to \infty$ %\begin{align*} %R(m) & = -\frac{1}{m}\log \rho (\mtx{P}^\tra 2^{-m \mtx{R}}) \\ %& = - \log \rho \Bigl( (\mtx{P}^\tra 2^{-m \mtx{R}})^{1/m} \Bigr)\\ %& = \bar{r}_1- \log \rho \left( \begin{bmatrix} % p_{11} & \cdots & p_{n1} 2^{-m(\bar{r}_n-\bar{r}_1)} \\ % \vdots & \vdots & \vdots \\ % p_{1n} & \cdots & p_{nn} 2^{-m(\bar{r}_n-\bar{r}_1)} % \end{bmatrix}^{1/m} \right) \\ %& \sim \bar{r}_1- \frac{1}{m} \log p_{11}, %\end{align*} %where the last equation follows from the fact that for any column vector $v=(v_1,\dotsc,v_n)^\tra$, $\rho(\begin{bmatrix} v & \mtx{0}_{n \times (n-1)} \end{bmatrix}) = v_1$. From the above asymptotic approximation it immediately follows that if $\bar{r}_1 =0$, then %\begin{equation} %\lim_{m \to \infty}mR(m) = - \log p_{11}. %\end{equation} % %Next, the property on the sensitivity with respect to self-loop probabilities is a direct application of a result in~\verb|\cite{Cohen1978}|, which is re-stated here as Lemma~\verb|\ref{lem:cohen}|, on the derivative of the spectral radius as a function of non-negative matrix elements. % %Next, the monotonicity property of $-m R(m) = \log \rho( \mtx{P}^\tra 2^{-m \mtx{R}} )$ %follows from the fact that all the entries of the matrix $\mtx{P}^\tra 2^{-m \mtx{R}}$ are monotonically decreasing in $m$. Finally, the strict concavity of $m R(m)$ is again a direct consequence of the log-convexity of the spectral radius of a nonnegative matrix stated in Lemma~\verb|\ref{thm:Friedland}|. % %%%% % %\subsection{Theorem~\verb|\ref{th:combining}|} %\begin{IEEEproof} %By Theorem~\verb|\ref{thm1}| and Theorem~\verb|\ref{thm2}|, at the boundaries of the stability region we must have that %\begin{equation} %\label{eq:any1} %\log |\lambda| = R(m). %\end{equation} %and %\begin{equation} %\label{eq:any2} %\log |\lambda| = C(m \log |\lambda|). %\end{equation} %Therefore,~\eqref{anytime2} follows by combining~\eqref{eq:any1} and~\eqref{eq:any2}. Next, by Proposition~\verb|\ref{prop1}|, the function $\phi(m)=mR(m)$ is increasing and strictly concave, thus invertible. It follows that for every $\alpha \ge 0$, there exists a unique $m := m(\alpha)$ such that %\begin{equation} %m R(m) = \alpha. %\end{equation} %Substituting this equality into~\eqref{anytime2}, it follows that $C_A(\alpha) = R\bigl( m(\alpha) \bigr).$ as claimed. The remaining properties are immediate consequences of Proposition~\verb|\ref{prop1}|. By definition, $C_A(\alpha)$ is non increasing in $\alpha$. Since both $mR(m)$ and $R(m)$ are both monotonic function of $m$, however, it follows that $C_A(\alpha)$ must be strictly decreasing in $\alpha$, thus establishing~2). Property~3) follows from~\eqref{anytime2} combined with the fact that $mR(m) \to 0 $ and $R(m) \to C$ as $m \to 0$. Similarly, property~4) follow directly by combining~\eqref{anytime2} with properties~3) and~5) in Proposition~\verb|\ref{prop1}|. %\end{IEEEproof} % %\subsection{Theorem~\verb|\ref{th:anyerasure}|} %\medskip %\begin{IEEEproof} %By~\eqref{eq:par} and the definition of $R(m)$, for every $\alpha$ there exists an $m(\alpha)$ such that %\begin{equation} %\label{eq:bec2a} %\rho(\mtx{P}^\tra 2^{-m(\alpha) \mtx{R}}) = 2^{-\alpha} %\end{equation} %In the case of a Markov erasure channel, a simple calculation shows that %\begin{equation} %\label{eq:bec2} %\rho(\mtx{P}^\tra 2^{-m \mtx{R}})=\frac{\text{tr}}{2}+\frac{1}{2}\sqrt{\text{tr}^2-4\text{det}}, %\end{equation} %where $\text{tr}$ and $\text{det}$ denote the trace and determinant of~\eqref{eq:bec}, respectively. By combining~\eqref{eq:bec2a} and~\eqref{eq:bec2} and squaring both sides of the resulting equation, it follows that $m(\alpha)$ must satisfy %\begin{equation} %\label{eq:bec3} %2^{-\alpha} \text{tr} - 4 \text{det} = 2^{-\alpha+1}, %\end{equation} %where $\text{tr} = (1-q) +2^{-m(\alpha) \bar{r}}(1-p)$ and $\text{det} = 2^{-m(\alpha) \bar{r}} (1-p-q)$. Solving~\eqref{eq:bec3} yields %\begin{equation} %\label{bec4} %m(\alpha) = \frac{1}{ \bar{r}} \left( \alpha + \log_2 \left(\frac{ 1-p - 2^{\alpha}(1-p-q)}{1-(1-q)2^{\alpha}}\right) \right) %\end{equation} %for $0\le \alpha < -\log_2 (1-q) $. Finally, substituting~\eqref{bec4} into~\eqref{anytime2b} yields~\eqref{eq:anyMarkov}. %\end{IEEEproof} % % %\subsection{Theorem~\verb|\ref{thm:memo}|} %\begin{IEEEproof} %In the special case of an i.i.d. rate process, %\begin{equation*} %\mtx{P}^\tra 2^{-m \mtx{R}} =\bigl(p_1,\ldots,p_n \bigr)^\mathrm{T} \bigl(2^{-m \bar{r}_1},\dotsc,2^{-m \bar{r}_n}\bigr) %\end{equation*} %is a rank-one matrix whose only nonzero eigenvalue is $\sum_{i=1}^n p_i 2^{-m \bar{r}_i} = \mathbb{E}( 2^{-mR})$. Therefore, in this case %\begin{align} %R(m) & = -\frac{1}{m}\log \mathbb{E}( 2^{-mR}) \nonumber \\ %& = -\frac{1}{m}\log M_R( -m \ln 2 ). %\label{eq:mmf} %\end{align} %By combining~\eqref{eq:par} and~\eqref{eq:mmf}, we find that $\alpha = -\log M_R( -m(\alpha) \ln 2 )$ and so %\begin{align} %m(\alpha) = -\frac{1}{\ln 2 } M_R^{-1}( 2^{- \alpha}), %\label{eq:mmf2} %\end{align} %where $M_R^{-1}(y)$ exists in light of property 5) in Proposition~\verb|\ref{prop1}|. Thus, by~\eqref{anytime2b},~\eqref{eq:mmf3} follows. %\end{IEEEproof} \end{document}