The statement of Theorem 1 in [1] should have read as follows.

We find the exact typical error exponent of constant composition generalized random Gilbert-Varshamov (RGV) codes over discrete memoryless channels with generalized likelihood decoding. We show that the typical error exponent of the RGV ensemble is equal to the expurgated error exponent, provided that the RGV codebook parameters are chosen appropriately. We also prove that the random coding exponent converges in probability to the typical error exponent, and the corresponding non-asymptotic concentration rates are derived. Our results show that the decay rate of the lower tail is exponential while that of the upper tail is double exponential above the expurgated error exponent. The explicit dependence of the decay rates on the RGV distance functions is characterized.

We study the typical error exponent of constant composition generalized random Gilbert-Varshamov (RGV) codes over discrete memoryless channels (DMC) channels with generalized likelihood decoding. We show that the typical error exponent of the RGV ensemble is equal to the expurgated error exponent, provided that the RGV codebook parameters are chosen appropriately. We also prove that the exponent of a randomly chosen RGV code converges in probability to the typical error exponent; the lower tail is shown to decay exponentially while the upper tail decays double-exponentially above the expurgated exponent.

We establish exact asymptotic expressions for the normalized mutual information and minimum mean-square-error (MMSE) of sparse linear regression in the sub-linear sparsity regime. Our result is achieved by a generalization of the adaptive interpolation method in Bayesian inference for linear regimes to sub-linear ones. A modification of the well-known approximate message passing algorithm to approach the MMSE fundamental limit is also proposed, and its state evolution is rigorously analysed. Our results show that the traditional linear assumption between the signal dimension and number of observations in the replica and adaptive interpolation methods is not necessary for sparse signals. They also show how to modify the existing well-known AMP algorithms for linear regimes to sub-linear ones.

This paper estimates free energy, average mutual information, and minimum mean square error (MMSE) of a linear model under two assumptions: (1) the source is generated by a Markov chain, (2) the source is generated via a hidden Markov model. Our estimates are based on the replica method in statistical physics. We show that under the posterior mean estimator, the linear model with Markov sources or hidden Markov sources is decoupled into single-input AWGN channels with state information available at both encoder and decoder where the state distribution follows the left Perron-Frobenius eigenvector with unit Manhattan norm of the stochastic matrix of Markov chains. Numerical results show that the free energies and MSEs obtained via the replica method are closely approximate to their counterparts achieved by the Metropolis–Hastings algorithm or some well-known approximate message passing algorithms in the research literature.

This paper shows that, for discrete memoryless channels, the error exponent of a randomly generated code with independent codewords converges in probability to its expectation—the typical error exponent. For high rates, the result follows from the fact that the random-coding error exponent and the sphere-packing error exponent coincide. For low rates, instead, the convergence is based on the fact that the union bound accurately characterizes the error probability. The paper also zooms into the behavior at asymptotically low rates, and shows that the normalized error exponent converges in distribution to the standard Gaussian or a Gaussian-like distribution. We also state several results on the convergence of the error probability and error exponent for generic ensembles and channels.

In this paper, we estimate free energy, average mutual information, and minimum mean square error (MMSE) of a linear model under the assumption that the source is generated by a Markov chain. Our estimates are based on the replica method in statistical physics. We show that under the MMSE estimator, the linear model with Markov sources or hidden Markov sources is decoupled into single input AWGN channels with state information available at both encoder and decoder where the state distribution follows the stationary distribution of the stochastic matrix of Markov chains. Numerical results show that the free energies and MSEs obtained via the replica method are closely approximate to their counterparts via MCMC simulations.

We study the convergence in distribution of the error exponent of random codes, defined as the negative normalized logarithm of the probability of error, of both i.i.d. and constant-composition ensembles over discrete memoryless channels. For a constant number of messages, the distribution of the error exponent converges to that of the minimum of a set of independent normal random variables. For an increasing sub-exponential number of messages, the error exponent converges to a normal distribution, independent of the number of messages. As a byproduct, we provide a new method to prove the convergence to a normal distribution of an infinite number of random variables based on a modification of the Wasserstein metric.

In this paper, we derive upper bounds on generalization errors for deep neural networks with Markov datasets. These bounds are developed based on Koltchinskii and Panchenko's approach for bounding the generalization error of combined classifiers with i.i.d. datasets. The development of new symmetrization inequalities in high-dimensional probability for Markov chains is a key element in our extension, where the spectral gap of the infinitesimal generator of the Markov chain plays a key parameter in these inequalities. We also propose a simple method to convert these bounds and other similar ones in traditional deep learning and machine learning to Bayesian counterparts for both i.i.d. and Markov datasets. Extensions to $m$-order homogeneous Markov chains such as AR and ARMA models and mixtures of several Markov data services are given.

We estimate the minimum mean square error (MMSE) of the linear model under hidden Markov priors. Our estimates are based on the replica method in statistical physics. We show that under the MMSE estimator, the linear model with hidden Markov sources is decoupled into single-input AWGN channels with state information available at both encoder and decoder where the state distribution follows the left Perron-Frobenius eigenvector with unit Manhattan norm of the stochastic matrix of Markov chains.

This paper studies the error exponent of i.i.d. randomly generated codes used for transmission over discrete memoryless channels with maximum likelihood decoding. Specifically, this paper shows that the error exponent of a code, defined as the negative normalized logarithm of the probability of error, converges in probability to the typical error exponent. For high rates, the result is a consequence of the fact that the random-coding error exponent and the sphere-packing error exponent coincide. For low rates, instead, the proof of convergence is based on the fact that the union bound accurately characterizes the probability of error.

The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model consisting of noisy phaseless measurements, which arises in a diverse range of settings such as optical detection, X-ray crystallography, electron microscopy, and coherent diffractive imaging. Our focus is on information-theoretic fundamental limits under an approximate recovery criterion, considering both discrete and Gaussian models for the sparse non-zero entries, along with Gaussian measurement matrices. In both cases, our bounds provide sharp thresholds with near-matching constant factors in several scaling regimes on the sparsity and signal-to-noise ratio. As a key step towards obtaining these results, we develop new concentration bounds for the conditional information content of log-concave random variables, which may be of independent interest.

A general time-varying feedback coding scheme is proposed for M-user fully connected symmetric Gaussian interference channels. Based on the analysis of the general coding scheme, we prove a theorem which gives a criterion for designing good time-varying feedback codes for Gaussian interference channels. The proposed scheme improves the Suh-Tse and Kramer inner bounds of the channel capacity for the cases of weak and not very strong interference when M = 2. This capacity improvement is more significant when the signal-to-noise ratio (SNR) is not very high. In addition, our coding scheme can be proved mathematically and numerically to outperform the Kramer code for M ≥ 2 when the SNR is equal to the interference-to-noise ratio (INR). Besides, the generalized degrees-of-freedom (GDoF) of our proposed coding scheme can be proved to be optimal in the all network situations (very weak, weak, strong, very strong) for any M. The numerical results show that our coding scheme can attain better performance than the Suh-Tse coding scheme for M = 2 or the MohajerTandon-Poor lattice coding scheme for M > 2. Furthermore, the simplicity of the encoding/decoding algorithms is another strong point of our proposed coding scheme compared with the Suh-Tse coding scheme when M = 2 and the Mohajer-TandonPoor lattice coding scheme when M > 2. More importantly, our results show that an optimal coding scheme for the symmetric Gaussian interference channels with feedback can be achieved by only using marginal posterior distributions under a better cooperation strategy between transmitters.

The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model consisting of noisy phaseless measurements, which arises in a diverse range of settings such as optical detection, X-ray crystallography, electron microscopy, and coherent diffractive imaging. Our focus is on information- theoretic fundamental limits under an approximate recovery criterion, with Gaussian measurements and a simple discrete model for the sparse non-zero entries. Our bounds provide sharp thresholds with near-matching constant factors in several scaling regimes on the sparsity and signal-to-noise ratio.

In this paper, we investigate the performance of the Viterbi decoding algorithm with/without Automatic Repeat reQuest (ARQ) over a Rician flat fading channel with unlimited interleaving. We show that the decay rate of the average bit error probability with respect to the bit energy to noise ratio is at least equal to dfat high-bit energy to noise ratio for both cases (with ARQ and without ARQ), where dfis the free distance of the convolutional code. The Yamamoto-Itoh flag helps to reduce the average bit error probability by a factor of 4(d)fwith a negligible retransmission rate. We also prove an interesting result that the average bit error probability decays exponentially fast with respect to the Rician factor for any fixed bit energy per noise ratio. In addition, the average bit error exponent with respect to the Rician factor is shown to be df.

We consider data transmission across discrete memoryless channels (DMCs) using variable-length codes with feedback. We consider the family of such codes whose rates are ρN below the channel capacity C, where ρN is a positive sequence that tends to zero slower than the reciprocal of the square root of the expectation of the (random) blocklength N. This is known as the moderate deviations regime, and we establish the optimal moderate deviations constant. We show that in this scenario, the error probability decays sub-exponentially with speed exp(-(B/C)NρN), where B is the maximum relative entropy between output distributions of the DMC.

We consider transmission of discrete memoryless sources (DMSes) across discrete memoryless channels (DMCs) using variable-length lossy source-channel codes with feedback. The reliability function (optimum error exponent) is shown to be equal to max{0, B(1 - R(D)/C)},, where R(D) is the ratedistortion function of the source, B is the maximum relative entropy between output distributions of the DMC, and C is the Shannon capacity of the channel. We show that in this asymptotic regime, separate source-channel coding is, in fact, optimal.

In this paper, we investigate the performance of the Viterbi decoding algorithm with/without Automatic Repeat reQuest (ARQ) over a Rician flat fading channel with unlimited interleaving. We show that the decay rate of the average bit error probability with respect to the bit energy to noise ratio is of order between dfand df+1 at high bit energy to noise ratio for both cases (with ARQ and without ARQ), where dfis the free distance of the convolutional code. The Yamamoto-Itoh flag helps to reduce the average bit error probability by a factorof 4df with a negligible retransmission rate. We also prove an interesting result that the average bit error probability decays exponentially fast with respect to the Rician factor for any fixed bit energy per noise ratio. In addition, the average bit error exponent with respect to the Rician factor is shown to be df.

We consider transmission of discrete memoryless sources (DMSes) across discrete memoryless channels (DMCs) using variable-length lossy source-channel codes with feedback. The reliability function (optimum error exponent) is shown to be equal to max{0, B(1-R(D)/C)}, where R(D) is the ratedistortion function of the source, B is the maximum relative entropy between output distributions of the DMC, and C is the Shannon capacity of the channel. We show that, in this setting and in this asymptotic regime, separate source-channel coding is, in fact, optimal.

We characterize the fundamental limits of transmission of information over a Gaussian multiple access channel (MAC) with the use of variable-length feedback codes and under a non-vanishing error probability formalism. We develop new achievability and converse techniques to handle the continuous nature of the channel and the presence of expected power constraints. We establish the ε-capacity regions and bounds on the second-order asymptotics of the Gaussian MAC with variable-length feedback with termination codes and stopfeedback codes. We show that the former outperforms the latter significantly. Due to the multi-terminal nature of the channel model, we leverage tools from renewal theory developed by Lai and Siegmund to bound the asymptotic behavior of the maximum of a finite number of stopping times.

We derive upper and lower bounds on the reliability function for the discrete memoryless broadcast channel with common message and variable-length feedback. We show that the bounds are tight when the broadcast channel is stochastically degraded. We adapt and supplement new ideas to Yamamoto and Itoh's two-phase coding scheme for the direct part and Burnashev's proof technique for the converse part.

We characterize the information-theoretic limits of the Gaussian multiple access channel (MAC) when variable-length stop-feedback is available at the encoder and a non-vanishing error probability is permitted. Due to the continuous nature of the channel and the presence of expected power constraints, we need to develop new achievability and converse techniques. Due to the multi-terminal nature of the channel model, we are faced with the need to bound the asymptotic behavior of the expected value of the maximum of several stopping times. We do so by leveraging tools from renewal theory developed by Gut (1974) and Lai and Siegmund (1979).

In this paper, we consider single-and multi-user Gaussian channels with feedback under expected power constraints and with non-vanishing error probabilities. In the first of two contributions, we study asymptotic expansions for the additive white Gaussian noise (AWGN) channel with feedback under the average error probability formalism. By drawing ideas from Gallager and Nakiboǧlu's work for the direct part and the meta-converse for the converse part, we establish the e-capacity and show that it depends on e in general and so the strong converse fails to hold. Furthermore, we provide bounds on the second-order term in the asymptotic expansion. We show that for any positive integer L, the second-order term is bounded between a term proportional to - ln(L) n (where ln(L)(·) is the L-fold nested logarithm function) and a term proportional to +(n ln n)1/2, where n is the blocklength. The lower bound on the second-order term shows that feedback does provide an improvement in the maximal achievable rate over the case where no feedback is available. In our second contribution, we establish the e-capacity region for the AWGN multiple access channel with feedback under the expected power constraint by combining ideas from hypothesis testing, information spectrum analysis, Ozarow's coding scheme, and power control.

In this paper, we analyze the asymptotic expansion for additive white Gaussian noise (AWGN) channels with feedback under an expected power constraint and the average error probability formalism. We show that the ε-capacity depends on ε in general and so the strong converse fails to hold. Furthermore, we provide bounds on the second-order term in the asymptotic expansion. We show that the second-order term is bounded between −ln ln n and a term that is proportional to +√n ln n. The lower bound on the second-order term shows that feedback does provide an improvement in the maximal achievable rate over the case where no feedback is available.

In this paper, we propose a new coding scheme for symmetric Gaussian interference channels with feedback based on the ideas of time-varying coding schemes. The proposed scheme improves the Suh-Tse and Kramer inner bounds of the channel capacity for the cases of weak and not very strong interference. This improvement is more significant when the signal-to-noise ratio (SNR) is not very high. It is shown theoretically and numerically that our coding scheme can outperform the Kramer code. In addition, the generalized degrees-of-freedom of our proposed coding scheme is equal to the Suh-Tse scheme in the strong interference case. The numerical results show that our coding scheme can attain better performance than the Suh-Tse coding scheme for all channel parameters. Furthermore, the simplicity of the encoding/decoding algorithms is another strong point of our proposed coding scheme compared with the Suh-Tse coding scheme. More importantly, our results show that an optimal coding scheme for the symmetric Gaussian interference channels with feedback can be achieved by using only marginal posterior distributions under a better cooperation strategy between transmitters.

Posterior matching is a method proposed by Ofer Shayevitz and Meir Feder to design capacity achieving coding schemes for general point-to-point memoryless channels with feedback. In this paper, we present a way to extend posterior matching based encoding and variable rate decoding ideas for Gaussian MAC with feedback, referred to as time-varying posterior matching scheme, analyze the achievable rate region and error probabilities of the extended encoding-decoding scheme. The time-varying posterior matching scheme is a generalization of the Shayevitz and Feder's posterior matching scheme when the posterior distributions of the input messages given output are not fixed over transmission time slots. It turns out that our designed posterior matching obtains the linear-feedback sum-capacity for the symmetric multiuser Gaussian MAC. Besides, the encoding scheme in this paper is designed for the real Gaussian MAC to obtain that performance, which is different from previous approaches where encoding schemes are designed for the complex Gaussian MAC. More importantly, this paper shows potential of posterior matching in designing optimal coding schemes for multiuser channels with feedback.

Information theory traditionally deals with the problem of transmitting sequences over a communication channel and finding the maximum number of messages that a transmitter can send so that the receiver recovers these messages with arbitrarily small probability of error. However, databases of various sorts have come into existence in recent years that require the transmission of new sources of data (e.g., graphs and sets) over communication channels. Here, we investigate a communication model transmitting Erdos-Rényi (unlabeled) graphs to a destination over a Binary Symmetric Channel (BSC). We find the capacity of such a channel - called the Structural Binary Symmetric Channel (SBSC) - to be C = 1 - h(ε) where h(ε) is the binary entropy of the error bit rate ε.