Reinforced random walks (RRWs), including vertex-reinforced random walks (VRRWs) and edge-reinforced reinforced random walks (ERRWs), model phenomena where transition probabilities evolve based on prior visitation history [5], [8], [15], [16]. These models have found applications in various areas, such as network embedding [18], reinforced PageRank [6], and modeling animal behaviors [14], among others. However, statistical estimation of the parameters governing RRWs remains underexplored. This work focuses on estimating the initial edge weights of ERRWs using observed trajectory data. Leveraging the connections between ERRW and random walks in a random environment (RWRE) [9], [10], we propose an estimator based on the generalized method of moments and the “magic formula”. To analyze the sample complexity, we exploit the hyperbolic Gaussian structure embedded in the random environment to bound the order of the random conductance, and hence derive sample complexity bounds. These findings contribute to the theoretical foundation of promising statistical and algorithmic applications of ERRWs.

The Shannon-Hagelbarger theorem states that the effective resistance across any pair of nodes in a resistive network is a concave function of the edge resistances. We give an information-theoretic proof of this result, building on the theory of the Gaussian free field. This also allows us to prove an extension of the result to determinants of matrices of cross effective resistances.

In this paper, we study the type graph, namely, a bipartite graph induced by a joint type. We investigate the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale in the length$n$of the type. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the length of the type goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of$(R_{1},R_{2})$such that there exists a biclique of the type graph which has respectively$2^{nR_{1}}$and$2^{nR_{2}}$vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We then discuss the connections of these results to noninteractive simulation and hypercontractivity inequalities. Furthermore, as an application of our results, a new outer bound for the zero-error capacity region of the binary adder channel is provided, which improves the previously best known bound, due to Austrin, Kaski, Koivisto, and Nederlof. Our proofs in this paper are based on the method of types and linear algebra.

Graphical data arises naturally in several modern applications, including but not limited to internet graphs, social networks, genomics and proteomics. The typically large size of graphical data argues for the importance of designing universal compression methods for such data. In most applications, the graphical data is sparse, meaning that the number of edges in the graph scales more slowly than$n^{2}$, where$n$denotes the number of vertices. Although in some applications the number of edges scales linearly with$n$, in others the number of edges is much smaller than$n^{2}$but appears to scale superlinearly with$n$. We call the former sparse graphs and the latter heavy-tailed sparse graphs. In this paper we introduce a universal lossless compression method which is simultaneously applicable to both classes. We do this by employing the local weak convergence framework for sparse graphs and the sparse graphon framework for heavy-tailed sparse graphs.

The channel synthesis problem has been widely investigated over the last decade. In this paper, we consider the sequential version in which the encoder and the decoder work in a sequential way. Under a mild assumption on the target joint distribution we provide a complete (single-letter) characterization of the solution for the point-to-point case, which shows that the canonical symbol-by-symbol mapping is not optimal in general, but is indeed optimal if we make some additional assumptions on the encoder and decoder. We also extend this result to the broadcast scenario and the interactive communication scenario. We provide bounds in the broadcast setting and a complete characterization of the solution under a mild condition on the target joint distribution in the interactive communication case. Our proofs are based on a Rényi entropy method.

The channel synthesis problem has been widely investigated over the last decade. In this paper, we consider the sequential version in which the encoder and the decoder work in a sequential way. Under a mild assumption on the target joint distribution we provide a complete (single-letter) characterization of the solution for the point-to-point case, which shows that the canonical symbol-by-symbol mapping is not optimal in general, but is indeed optimal if we make some additional assumptions on the encoder and decoder. We also extend this result to the broadcast scenario and the interactive communication scenario. We provide bounds in the broadcast setting and a complete characterization of the solution under a mild condition on the target joint distribution in the interactive communication case.

Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. Such rich model classes may be too complex to admit uniformly consistent estimators. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the practical drawback that estimator performance is a function of the unknown model within the model class that is being estimated. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. In these cases, a line of analysis favors sample dependent guarantees. We explore this framework by studying rich model classes that may only admit pointwise consistency guarantees, yet enough information about the unknown model driving the observations needed to gauge estimator accuracy can be inferred from the sample at hand. In this paper we obtain a novel characterization of lossless compression problems over a countable alphabet in the data-derived framework in terms of what we term deceptive distributions. We also show that the ability to estimate the redundancy of compressing memoryless sources is equivalent to learning the underlying single-letter marginal in a data-derived fashion. We expect that the methodology underlying such characterizations in a data-derived estimation framework will be broadly applicable to a wide range of estimation problems, enabling a more systematic approach to data-derived guarantees.

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by adapting a proof technique from Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.

We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information rate is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information rate may not be strongly concave, our second algorithm proves to be at least locally convergent.

Graphical data arises naturally in several modern applications, including but not limited to internet graphs, social networks, genomics and proteomics. The typically large size of graphical data argues for the importance of designing universal compression methods for such data. In most applications, the graphical data is sparse, meaning that the number of edges in the graph scales more slowly than$n^{2}$, where$n$denotes the number of vertices. Although in some applications the number of edges scales linearly with$n$, in others the number of edges is much smaller than$n^{2}$but appears to scale superlinearly with$n$. We call the former sparse graphs and the latter heavy-tailed sparse graphs. In this paper we introduce a universal lossless compression method which is simultaneously applicable to both classes. We do this by employing the local weak convergence framework for sparse graphs and the sparse graphon framework for heavy-tailed sparse graphs.

In this paper, we study the type graph, namely a bipartite graph induced by a joint type. We study the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the blocklength goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of ($R_{1}, R_{2}$) such that there exists a biclique of the type graph which has respectively$e^{nR_{1}}$and$e^{nR_{2}}$vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We also apply similar techniques to strengthen small-set expansion theorems.

We introduce a fundamental lemma called the Poisson matching lemma, and apply it to prove one-shot achievability results for various settings, namely channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, distributed lossy source coding, multiple access channels and channel resolvability. Our one-shot bounds improve upon the best known one-shot bounds in most of the aforementioned settings (except multiple access channels and channel resolvability, where we recover bounds comparable to the best known bounds), with shorter proofs in some settings even when compared to the conventional asymptotic approach using typicality. The Poisson matching lemma replaces both the packing and covering lemmas, greatly simplifying the error analysis. This paper extends the work of Li and El Gamal on Poisson functional representation, which mainly considered variable-length source coding settings, whereas this paper studies fixed-length settings, and is not limited to source coding, showing that the Poisson functional representation is a viable alternative to typicality for most problems in network information theory.

This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process.

Many modern applications involve accessing and processing graphical data, i.e. data that is naturally indexed by graphs. Examples come from internet graphs, social networks, genomics and proteomics, and other sources. The typically large size of such data motivates seeking efficient ways for its compression and decompression. The current compression methods are usually tailored to specific models, or do not provide theoretical guarantees. In this paper, we introduce a low-complexity lossless compression algorithm for sparse marked graphs, i.e. graphical data indexed by sparse graphs, which is capable of universally achieving the optimal compression rate in a precisely defined sense. In order to define universality, we employ the framework of local weak convergence, which allows one to make sense of a notion of stochastic processes for graphs. Moreover, we investigate the performance of our algorithm through some experimental results on both synthetic and real-world data.

Graphical data is comprised of a graph with marks on its edges and vertices. The mark indicates the value of some attribute associated to the respective edge or vertex. Examples of such data arise in social networks, molecular and systems biology, and web graphs, as well as in several other application areas. Our goal is to design schemes that can efficiently compress such graphical data without making assumptions about its stochastic properties. Namely, we wish to develop a universal compression algorithm for graphical data sources. To formalize this goal, we employ the framework of local weak convergence, also called the objective method, which provides a technique to think of a marked graph as a kind of stationary stochastic processes, stationary with respect to movement between vertices of the graph. In recent work, we have generalized a notion of entropy for unmarked graphs in this framework, due to Bordenave and Caputo, to the case of marked graphs. We use this notion to evaluate the efficiency of a compression scheme. The lossless compression scheme we propose in this paper is then proved to be universally optimal in a precise technical sense. It is also capable of performing local data queries in the compressed form.

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by mimicking the idea in Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.

We introduce the Poisson matching lemma and apply it to prove one-shot achievability results for channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, and distributed lossy source coding. Our one-shot bounds improve upon the best known bounds in the aforementioned settings, with shorter proofs in some settings even when compared to the conventional asymptotic typicality approach. The Poisson matching lemma replaces both the packing and covering lemmas. This paper extends the work of Li and El Gamal on Poisson functional representation for variable-length source coding settings, showing that the Poisson functional representation is a viable alternative to typicality for most problems in network information theory.

We analyze a class of vector multiple access channels with additive noise, where the sum of the dimensions of the transmitted signals matches that of the received signal. We first focus on the case without power constraints, in the Poltyrev sense, using point process techniques. We find the Poltyrev capacity region for noise processes that are independent and identically distributed over channel uses. For each rate vector strictly in the Poltyrev capacity region, we study, for each subset of the transmitters, the exponent of the decay in block length of the smallest possible probability that decoding results in error for each transmitter in that subset. In the case of independent and identically distributed Gaussian noise, with arbitrary positive definite covariance matrix, we derive random coding exponents for each type of error event-these are lower bounds to the true error exponents. This also leads to random coding error exponents in the traditional power-constrained case, where the power constraint at each transmitter is defined by an arbitrary positive definite matrix.

Marton's inner bound is the best known achievable rate region for a general two-receiver discrete memoryless broadcast channel. In this paper, we establish improved bounds on the cardinalities of the auxiliary random variables appearing in this inner bound to the true rate region. We combine a perturbation technique, along with a representation using concave envelopes of information-theoretic functions that involve the use of auxiliary random variables, to achieve this improvement. The new cardinality bounds lead to a proof that a randomized-time-division strategy achieves every rate triple in Marton's region for binary input broadcast channels. This extends the result by Hajek and Pursley which showed that the Cover-van der Muelen region was exhausted by the randomized-time-division strategy.

In contrast to time series, graphical data is data indexed by the nodes and edges of a graph. Modern applications such as the internet, social networks, genomics and proteomics generate graphical data, often at large scale. The large scale argues for the need to compress such data for storage and subsequent processing. Since this data might have several components available in different locations, it is also important to study distributed compression of graphical data. In this paper, we derive a rate region for this problem which is a counterpart of the Slepian-Wolf Theorem. We characterize the rate region when the statistical description of the distributed graphical data is one of two types - a marked sparse Erdos-Renyi ensemble or a marked configuration model. Our results are in terms of a generalization of the notion of entropy introduced by Bordenave and Caputo in the study of local weak limits of sparse graphs.

Let Z be a standard Gaussian random variable, X be independent of Z, and t be a strictly positive scalar. For the derivatives in t of the differential entropy of X+√tZ, McKean noticed that Gaussian X achieves the extreme for the first and second derivatives, and he conjectured that this holds for general orders of derivatives. Here we show that, when the probability density function of X+√tZ is log-concave, this conjecture holds for orders up to at least five. We also recover Toscani's result on the non-negativity of the third derivative of the entropy power of X+√tZ for log-concave densities, using a much simpler argument.

The entropy of a random variable is well-known to equal the exponential growth rate of the volumes of its typical sets. In this paper, we show that for any log-concave random variable X, the sequence of the [nθ]thintrinsic volumes of the typical sets of X in dimensions n ≥ 1 grows exponentially with a well-defined rate. We denote this rate by hX(θ), and call it the θthintrinsic entropy of X. We show that hX (θ) is a continuous function of θ over the range [0, 1], thereby providing a smooth interpolation between the values 0 and h(X) at the endpoints 0 and 1, respectively.

We consider the communication capacity of wireline networks for a two-unicast traffic pattern. The network has two sources and two destinations with each source communicating an independent message to its own destination, subject to the capacity constraints on the directed edges of the network. We propose a simple outer bound for the problem that we call the generalized network sharing (GNS) bound. We show that this bound is the tightest edge-cut bound for two-unicast networks and is tight in several cases, though it is not tight in general. We also show that the problem of computing the GNS bound is NP complete. Finally, we show that despite its seeming simplicity, the two-unicast problem is a very difficult problem: the general network coding problem can be reduced to two-unicast. As a consequence, linear coding is insufficient to achieve capacity for general two-unicast networks, and non-Shannon inequalities are necessary for characterizing the capacity of general two-unicast networks.

Atar, Chowdhary and Dupuis have recently exhibited a variational formula for exponential integrals of bounded measurable functions in terms of Rényi divergences. We show that a variational characterization of the Rényi divergences between two probability distributions on a measurable space in terms of relative entropies, when combined with the elementary variational formula for exponential integrals of bounded measurable functions in terms of relative entropy, yields the variational formula of Atar, Chowdhary and Dupuis as a corollary. We then develop an analogous variational characterization of the Rényi divergence rates between two stationary finite state Markov chains in terms of relative entropy rates. When combined with Varadhan's variational characterization of the spectral radius of square matrices with nonnegative entries in terms of relative entropy, this yields an analog of the variational formula of Atar, Chowdary and Dupuis in the framework of stationary finite state Markov chains.

Consider a data source comprised of a graph with marks on its edges and vertices. Examples of such data sources are social networks, biological data, web graphs, etc. Our goal is to design schemes that can efficiently compress and store such data. We aim for universal compression, i.e. without making assumptions about the stochastic properties of the data. To make sense of this, we employ the framework of local weak convergence, also called the objective method, which formalizes the notion of stationary stochastic processes indexed by graphs. We generalize a recently developed notion of entropy for such processes, due to Bordenave and Caputo, to the case of marked graphs, and argue that it is an appropriate way to evaluate the efficiency of a compression scheme. The lossless compression scheme we propose in this paper is then proved to be universally optimal. It is also capable of performing local data queries in the compressed form.

Theorem 5 of A. Gohari, V. Anantharam,IEEE Transactions on Information Theory, vol. 56, no. 8, pp. 3973-3996, 2010, states an upper bound on the secrecy capacity for the source model problem. It has a three page proof given in Appendix B of the paper. Unfortunately, we show that this bound does not provide any improvement over the simpler bound given in Corollary 1 of the paper. We also provide an example of a family of two agent source model problems where the one-way secrecy rate in each direction is zero, but the secrecy rate is nonzero and can be determined exactly as a conditional mutual information.

In this paper, we consider the additive white Gaussian noise (AWGN) channel with a power constraint called the (o, ρ)-power constraint, which is motivated by energy harvesting communication systems. Given a codeword, the constraint imposes a limit of σ + kρ on the total power of any k ≥ 1 consecutive transmitted symbols. Such a channel has infinite memory and evaluating its exact capacity is a difficult task. Consequently, we establish an n-letter capacity expression and seek bounds for the same. We obtain a lower bound on capacity by considering the volume of Sn(σ, ρ) ⊆ Rn, which is the set of all length n sequences satisfying the (σ, ρ)-power constraints. For a noise power of v, we obtain an upper bound on capacity by considering the volume of Sn(σ, ρ) ⊕ Bn(√nv), which is the Minkowski sum of Sn(σ, ρ) and the n-dimensional Euclidean ball of radius √nv. We analyze this bound using a result from convex geometry known as Steiner's formula, which gives the volume of this Minkowski sum in terms of the intrinsic volumes of Sn(σ, ρ). We show that as the dimension n increases, the logarithm of the sequence of intrinsic volumes of {Sn(σ, ρ)} converges to a limit function under an appropriate scaling. The upper bound on capacity is then expressed in terms of this limit function. We derive the asymptotic capacity in the low- and high-noise regime for the (σ, ρ)-power constrained AWGN channel, with strengthened results for the special case of σ = 0, which is the amplitude constrained AWGN channel.

We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed from P(x, y), and they output U and V, respectively, which is required to have a joint law that is close in total variation to a specified Q(u, v). It is known that the maximal correlation of U and V must necessarily be no bigger than that of X and Y if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if P(x, y) is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the k-agent version of this problem.

We analyze a class of vector multiple access channels with additive noise, where the sum of the dimensions of the transmitted signals matches that of the received signal. We first focus on the case without power constraints, using point process techniques. We derive the capacity region in the Poltyrev sense, a representation of the error probabilities for each subset of transmitters based on Palm theory, and random coding exponents for each type of error event in the case without power constraints, focusing on the case of independent and identically distributed Gaussian noise, with arbitrary positive definite covariance matrix at each time. This also leads to random coding error exponents in the traditional power-constrained case, where the power constraint at each transmitter is defined by an arbitrary positive definite matrix at each time.

We consider the additive white Gaussian noise (AWGN) channel with a (σ, ρ)-power constraint, which is motivated by energy harvesting communication systems. This constraint imposes a limit of σ + kρ on the total power of any k ≥ 1 consecutive transmitted symbols in a codeword. We analyze the capacity of this channel geometrically, by considering the set Sn(σ, ρ) ⊆ ℝnwhich is the set of all n-length sequences satisfying the (σ, ρ)-power constraints. For a noise power of ν, we obtain an upper bound on capacity by considering the volume of the Minkowski sum of Sn(σ, ρ) and the n-dimensional Euclidean ball of radius √(nν). We analyze this bound using a result from convex geometry known as Steiner's formula, which gives the volume of this Minkowski sum in terms of the intrinsic volumes of Sn(σ, ρ). We show that as n increases, the logarithms of the intrinsic volumes of {Sn(σ, ρ)} converge to a limit function under an appropriate scaling. An upper bound on capacity is obtained in terms of the limit function, thus pinning down the asymptotic capacity of the (σ, ρ)-power constrained AWGN channel in the low-noise regime. We derive stronger results when σ = 0, corresponding to the amplitude-constrained AWGN channel.

We consider convex sets obtained as one-sided typical sets of log-concave distributions, and show that the sequence of logarithms of intrinsic volumes corresponding to these typical sets converges to a limit function under an appropriate scaling. The limit function may be used to represent the exponential growth rate of intrinsic volumes of the typical sets. Since differential entropy is the exponential growth rate of the volume of typical sets, the exponential growth rate of intrinsic volumes generalizes the differential entropy of log-concave distributions. We conjecture a version of the entropy power inequality for such a generalization of differential entropy.

Peer-to-peer protocols that rely on fully random peer and chunk selection have recently been shown to suffer from instability. The culprit is referred to as the missing piece syndrome, whereby a single chunk is driven to near extinction, leading to an accumulation of peers having almost complete files, but waiting for the missing chunk. We investigate three distributed random peer sampling protocols that tackle this issue, and present proofs of their stability using Lyapunov function techniques. The first two protocols are based on the sampling of multiple peers and a rare chunk selection rule. The last protocol incorporates an incentive mechanism to prevent free riding. It is shown that this incentive mechanism interacts well with the rare chunk selection protocol and stability is maintained. Besides being stable for all arrival rates of peers, all three protocols are scalable in that the mean upload rate of each peer is bounded uniformly independent of the arrival rate.

In this paper we provide the correct tight constant to a data-processing inequality claimed by Erkip and Cover. The correct constant turns out to be a particular hypercontractivity parameter of (X,Y), rather than their squared maximal correlation. We also provide alternate geometric characterizations for both maximal correlation as well as the hypercontractivity parameter that characterizes the data-processing inequality.

In energy harvesting communication systems, the transmitter is adapted to harvest energy per time slot. The harvested energy is either used right away or is stored in a battery to facilitate future transmissions. We consider the problem of determining the Shannon capacity of an energy harvesting transmitter communicating over an additive white Gaussian noise (AWGN) channel, where the amount of energy harvested per time slot is a constant ρ and the battery has capacity σ. This imposes a new kind of power constraint on the transmitted codewords, and we call the resulting constrained channel a (σ, ρ) power constrained AWGN channel. When σ is 0 or ∞, the capacity of this channel is known. For the finite battery case, we obtain an expression for the channel capacity. We obtain bounds on capacity by considering the volume of Sn(σ, ρ) ⊆ ℝn, which is the set of all length n sequences satisfying the (σ, ρ) constraints.

In applications involving estimation, the relevant model classes of probability distributions are often too complex to admit estimators that converge to the truth with convergence rates that can be uniformly bounded over the entire model class as the sample size increases (uniform consistency). While it is often possible to get pointwise guarantees, so that the convergence rate of the estimator can be bounded in a model-dependent way, such pointwise gaurantees are unsatisfactory - estimator performance is a function of the very unknown quantity that is being estimated. Therefore, even if an estimator is consistent, how well it is doing may not be clear no matter what the sample size. Departing from this traditional uniform/pointwise dichotomy, a new analysis framework is explored by characterizing model classes of probability distributions that may only admit pointwise guarantees, yet where all the information about the unknown model needed to gauge estimator accuracy can be inferred from the sample at hand. To provide a focus to this suggested broad new paradigm, we analyze the universal compression problem in this data-driven pointwise consistency framework.

In this paper, we revisit the structure of infeasibility results in network information theory, based on a notion of information state. We also discuss ideas for generalizing a known outer bound for lossless transmission of independent sources over a network to one of lossy transmission of dependent sources over the same network. To concretely demonstrate this, we apply our ideas and prove new results for lossy transmission of dependent sources by generalizing: 1) the cut-set bound; 2) the best known outer bound on the capacity region of a general broadcast channel; and 3) the outer bound part of the result of Maric, Yates, and Kramer on strong interference channels with a common message.

We establish several new results on Marton's inner bound on the capacity region of the general broadcast channel. Inspired by the fact that Marton's coding scheme without superposition coding is optimal in the Gaussian case, we consider the class of binary input degraded broadcast channels with no common message that have the same property. We characterize this class. We also establish new properties of Marton's inner bound that help restrict the search space for computing the Marton sum rate. In particular, we establish an extension of the XOR case of the binary inequality of Nair, Wang, and Geng.

Shannon's entropy power inequality can be viewed as characterizing the minimum differential entropy achievable by the sum of two independent random variables with fixed differential entropies. The entropy power inequality has played a key role in resolving a number of problems in information theory. It is therefore interesting to examine the existence of a similar inequality for discrete random variables. In this paper, we obtain an entropy power inequality for random variables taking values in a group of order 2n, i.e., for such a group G, we explicitly characterize the function fG(x, y) giving the minimum entropy of the sum of two independent G-valued random variables with respective entropies x and y. Random variables achieving the extremum in this inequality are thus the analogs of Gaussians in this case, and these are also determined. It turns out that fG(x, y) is convex in x for fixed y and, by symmetry, convex in y for fixed x. This is a generalization to groups of order 2nof the result known as Mrs. Gerber's Lemma.

Marton's region is the best known inner bound for a general discrete memoryless broadcast channel. We establish improved bounds on the cardinalities of the auxiliary random variables. We combine the perturbation technique along with a representation using concave envelopes to achieve this improvement. As a corollary of this result, we show that a randomized time division strategy achieves the entire Marton's region for binary input broadcast channels, extending the previously known result for the sum-rate and validating a previous conjecture due to the same authors.

Shannon's Entropy Power Inequality (EPI) can be viewed as characterizing the minimum differential entropy achievable by the sum of two independent random variables with fixed differential entropies. The EPI is a powerful tool and has been used to resolve a number of problems in information theory. In this paper we examine the existence of a similar entropy inequality for discrete random variables. We obtain an entropy power inequality for random variables taking values in any group of order 2n, i.e. for such a group G we explicitly characterize the function fG(x, y) giving the minimum entropy of the group product of two independent G-valued random variables with respective entropies x and y. Random variables achieving the extremum in this inequality are thus the analogs of Gaussians, and these are also determined. It turns out that fG(x, y) is convex in x for fixed y and, by symmetry, convex in y for fixed x. This is a generalization to groups of order 2nof the result known as Mrs. Gerber's Lemma.

Marton's inner bound is the best known achievable region for a general discrete memoryless broadcast channel. To compute Marton's inner bound one has to solve an optimization problem over a set of joint distributions on the input and auxiliary random variables. The optimizers turn out to be structured in many cases. Finding properties of optimizers not only results in efficient evaluation of the region, but it may also help one to prove factorization of Marton's inner bound (and thus its optimality). The first part of this paper formulates this factorization approach explicitly and states some conjectures and results along this line. The second part of this paper focuses primarily on the structure of the optimizers. This section is inspired by a new binary inequality that recently resulted in a very simple characterization of the sum-rate of Marton's inner bound for binary input broadcast channels. This prompted us to investigate whether this inequality can be extended to larger cardinality input alphabets. We show that several of the results for the binary input case do carry over for higher cardinality alphabets and we present a collection of results that help restrict the search space of probability distributions to evaluate the boundary of Marton's inner bound in the general case. We also prove a new inequality for the binary skew-symmetric broadcast channel that yields a very simple characterization of the entire Marton inner bound for this channel.

We investigate the minimum pointwise redundancy of variable length lossy source codes operating at fixed distortion for sources with memory. The redundancy is defined by ln(X1n) − nR(D), where ln(X1n) is the code length at block size n and R(D) is the rate distortion function. We restrict ourselves to the case where R(D) can be calculated, namely the cases where the Shannon lower bound to R(D) holds with equality. In this case, for balanced distortion measures, we provide a pointwise lower bound to the code length sequence in terms of the entropy density process. We show that the minimum coding variance with distortion is lower bounded by the minimum lossless coding variance, and is non-zero unless the entropy density is deterministic. We also examine lossy coding in the presence of long range dependence, showing the existence of information sources for which long range dependence persists under any codec operating at the Shannon lower bound with fixed distortion.

The best known inner bound on the two-receiver general broadcast channel is due to Marton. However this region is not computable (except in certain special cases) as no bounds on the cardinality of its auxiliary random variables exist. Nor is it even clear that the inner bound is a closed set. The main obstacle in proving cardinality bounds is the fact that the traditional use of the Carathéodory theorem, the main known tool for proving cardinality bounds, does not yield a finite cardinality result. One of the main contributions of this paper is the introduction of a new tool based on an identity that relates the second derivative of the Shannon entropy of a discrete random variable (under a certain perturbation) to the corresponding Fisher information. In order to go beyond the traditional Carathéodory type arguments, we identify certain properties that the auxiliary random variables corresponding to the extreme points of the inner bound need to satisfy. These properties are then used to establish cardinality bounds on the auxiliary random variables of the inner bound, thereby proving the computability of the region, and its closedness. Lastly, we establish a conjecture of Nair and Zizhou that Marton's inner bound and the recent outer bound of Nair and El Gamal do not match in general.

In this paper we study the problem of generation of dependent random variables, known as the “coordination capacity” [4], [5], in multiterminal networks. In this model m nodes of the network are observing i.i.d. repetitions of X(1), X(2),..., X(m)distributed according to q(x(1), ..., x(m)). Given a joint distribution q(x(1), ..., x(m), y(1), ..., y(m)), the final goal of the ithnode is to construct the i.i.d. copies of Y(i)after the communication over the network where X(1), X(2),..., X(m), Y(1), Y(2),..., Y(m)are jointly distributed according to q(x(1), ..., x(m), y(1), ..., y(m)). To do this, the nodes can exchange messages over the network at rates not exceeding the capacity constraints of the links. This problem is difficult to solve even for the special case of two nodes. In this paper we prove new inner and outer bounds on the achievable rates for networks with two nodes.

We study a network security game where strategic players choose their investments in security. Since a player's investment can reduce the propagation of computer viruses, a key feature of the game is the positive externality exerted by the investment. With selfish players, unfortunately, the overall network security can be far from optimum. The contributions of this paper are as follows. 1) We first characterize the price of anarchy (POA) in the strategic-form game under an “Effective-investment” model and a “Bad-traffic” model, and give insight on how the POA depends on individual players' cost functions and their mutual influence. We also introduce the concept of “weighted POA” to bound the region of payoff vectors. 2) In a repeated game, players have more incentive to cooperate for their long term interests. We consider the socially best outcome that can be supported by the repeated game, as compared to the social optimum. 3) Next, we compare the benefits of improving security technology and improving incentives, and show that improving technology alone may not offset the price of anarchy. 4) Finally, we characterize the performance of correlated equilibrium (CE). Although the paper focuses on network security, many results are generally applicable to games with positive externalities .

In this paper, we study the Nair-El Gamal outer bound and Marton's inner bound for general two-receiver broadcast channels. We show that the Nair-El Gamal outer bound can be made fully computable. For the inner bound, we show that, unlike in the Gaussian case, for a degraded broadcast channel even without a common message, Marton's coding scheme without a superposition variable is in general insufficient for obtaining the capacity region. Further, we prove various results that help to restrict the search space for computing the sum-rate for Marton's inner bound. We establish the capacity region along certain directions and show that it coincides with Marton's inner bound. Lastly, we discuss an idea that may lead to a larger inner bound.

Analysis of variable bit-rate video data has shown that long range dependence persists across a wide variety of codecs. While codecs are generally lossy, one may conjecture, as a partial explanation for this fact, that there exist information sources for which any lossless code results in a bit-rate process that eventually dominates a long range dependent random process. We prove this to be true for discrete time long range dependent renewal processes under a mild technical assumption.

In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number r of repetitions, in the sense that no two strings in the code can give rise to the same string after r repetitions. We propose explicit number theoretic constructions of such subsets. In the case of $r=1$ repetition, the proposed construction is asymptotically optimal. For $r\geq1$, the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to r repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number r of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any r repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible.

Gibilisco and Isola have recently proposed a definition of Fisher information for random variables taking values in a finite group that is analogous to the definition for real valued random variables with a density. Based on this Fisher information concept, they claim to prove a Stam inequality for finite-group valued random variables that is analogous to the one in the case of real values. In this note we show these results, unfortunately, do not hold for nonabelian groups in general, by constructing explicit counterexamples.

The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class of$C_{p, \gamma}$array-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes for$\gamma = 2,3,4$, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models, multiple terminals wish to create a shared secret key that is secure from a passive eavesdropper. The terminals have access to a noiseless public communication channel and an additional resource that depends on the model. In the source model, the resource is an external source that repeatedly beams correlated randomness to the terminals; whereas in the channel model, the resource is a secure but noisy discrete memoryless broadcast channel. We derive new lower and upper bounds on the secret key capacity under both the source model and the channel model. The technique used for deriving our bound for the source model is to find certain properties of functions of joint probability distributions which, applied to the joint distribution of the source, will imply that they dominate the secret key capacity, and then prove the bound by a verification argument. A similar technique is used for the channel model. Finally, we also define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement. This generalizes an earlier result of Csiszár and Narayan.

This is the second part of a two-part paper on information-theoretically secure secret key agreement. This part covers the secret key capacity under the channel model. In this model, multiple terminals wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. The terminals are all connected to a noiseless and authenticated but insecure channel, called the “public channel.” Furthermore, the terminals have access to a secure but noisy discrete memoryless broadcast channel (DMBC). The first terminal can choose a sequence of inputs to the DMBC, which has outputs at the other terminals and at the eavesdropper. After each channel use, the terminals can engage in arbitrarily many rounds of interactive authenticated communication over the public channel. At the end, each legitimate terminal should be able to generate the secret key. In this paper, we derive new lower and upper bounds on the secrecy capacity. In each case, an example is provided to show that the new bound represents a strict improvement over the previously best known bound. This part of the paper is not standalone, and is written under the assumption that the reader has access to Part I, which is published in the same issue.

In this paper, we generalize the well known cutset bound (see for example [1, p. 444]) to the problem of lossy transmission of functions of arbitrarily correlated sources over a discrete memoryless multiterminal network.

The best known inner bound on the two-receiver general broadcast channel without a common message is due to Marton. This result was subsequently generalized in and to broadcast channels with a common message. However the latter region is not computable (except in certain special cases) as no bounds on the cardinality of its auxiliary random variables exist. Nor is it even clear that the inner bound is a closed set. The main obstacle in proving cardinality bounds is the fact that the Carathe¿odory theorem, the main known tool for proving cardinality bounds, does not yield a finite cardinality result. Our new tool is based on an identity that relates the second derivative of the Shannon entropy of a discrete random variable (under a certain perturbation) to the corresponding Fisher information. In order to go beyond the traditional Carathe¿odory type arguments, we identify certain properties that the auxiliary random variables corresponding to the extreme points of the inner bound satisfy. These properties are then used to establish cardinality bounds on the auxiliary random variables of the inner bound, thereby proving the computability of the region, and its closedness. Although existence of cardinality bounds renders Marton's inner bound computable, it is still hard to evaluate the region. It is however shown that the computation can be significantly simplified if we further assume that Marton's inner bound and the recent outer bound of Nair and El Gamal match at the given particular channel. In order to demonstrate this, we consider a large class of binary input broadcast channels and compute maximum of the sum rate of private messages assuming that the inner and the outer bound match at the given broadcast channel. We also show that the inner and the outer bound do not match for some broadcast channels, thus establishing a conjecture of.

We present some simple information inequalities on binary sums of Bernoulli random variables that appear to be new. Consequences for information across binary input memoryless symmetric channels are also presented.

Multiuser information-theoretic analysis of achievable communication rate regions over networks traditionally assumes that individual sources of information are independent.

The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10-30. By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.

Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with such a structure to a hardware emulation platform. High-throughput emulation allows for the exploration of the low bit-error rate (BER) region and provides statistics of the error traces, which illuminate the causes of the error floors of the (2048, 1723) Reed-Solomon based LDPC (RS-LDPC) code and the (2209, 1978) array-based LDPC code. Two classes of error events are observed: oscillatory behavior and convergence to a class of non-codewords, termed absorbing sets. The influence of absorbing sets can be exacerbated by message quantization and decoder implementation. In particular, quantization and the log-tanh function approximation in sum-product decoders

A class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity-check (LDPC) decoders at low error rates. Past experiments have shown that a class of (8,8) absorbing sets determines the error floor performance of the (2048,1723) Reed-Solomon based LDPC code (RS-LDPC). A postprocessing approach is formulated to exploit the structure of the absorbing set by biasing the reliabilities of selected messages in a message-passing decoder. The approach converges quickly and can be efficiently implemented with minimal overhead. Hardware emulation of the decoder with postprocessing shows more than two orders of magnitude improvement in the very low bit error rate performance and error- floor-free operation below a BER of 10-12.

We define a class of problems in the theory of Euclidean point processes, motivated by the study of the error exponent (reliability function) for additive noise channels. For the case of Gaussian noise this gives an interesting perspective on the Poltyrev exponent. It also suggests an approach to attack the long standing gap between the best known upper and lower bounds on the reliability function of the traditional AWGN channel, using techniques from point process theory.

We develop a prefixing method for correcting any prescribed number r of repetition errors in an arbitrary binary block code. The proposed method constructs a prefix for each codeword such that the resulting strings are all of the same length and despite any r repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. Further, the prefix length scales logarithmically with the blocklength of the original code, so the added redundancy is asymptotically negligible.

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.

Abstract — The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding, is known to approach Shannon limits in the asymptotic limit of large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a method, based on importance sampling and high SNR asymptotics as applied to suitably defined absorbing structures within the LDPC code, to predict error floors. Our results are in very close agreement with hardware-based experimental results, and moreover extend the prediction of the error probability to even lower regions. We compute both importance sampling estimates of error probabilities and deterministic estimates that are guaranteed to lower bound the error probability in the high SNR regime. I.

We prove a new outer bound on the rate–distortion region for the multiterminal source-coding problem. This bound subsumes the best outer bound in the literature and improves upon it strictly in some cases. The improved bound enables us to obtain a new, conclusive result for the binary erasure version of the “CEO problem.” The bound recovers many of the converse results that have been established for special cases of the problem, including the recent one for the Gaussian two-encoder problem.

Low density parity check codes (LDPC) are known to perform very well under iterative decoding. However, these codes also exhibit a change in the slope of the bit error rate (BER) vs. signal to noise ratio (SNR) curve in the very low BER region. In our earlier work using hardware emulation in this deep BER regime we argue that this behavior can be attributed to specific structures within the Tanner graph associated with an LDPC code, called absorbing sets. In this paper we provide a detailed theoretical analysis of absorbing sets for array-based LDPC codes Cp.gamma. Specifically, we identify and enumerate all the smallest absorbing sets for these array-based LDPC codes with gamma = 2,3,4 with standard parity check matrix. Experiments carried out on the emulation platform show excellent agreement with our theoretical results.

A. class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity- check (LDPC) decoders. In particular, the quantization scheme strongly affects which absorbing sets dominate in the error-floor region. Absorbing sets may be characterized as weak or strong. They are a characteristic of the parity check matrix of a code. Conventional quantization schemes applied to a (2209,1978) array-based LDPC code can induce low-weight weak absorbing sets and, as a result, elevate the error floor. Adaptive quantization schemes alleviate the effects of weak absorbing sets, and, as a result, only the strong ones dominate the error floor of an optimized decoder implementation. Another benefit of an adaptive quantization scheme is that it performs well even in very few iterations.

We are motivated by the widely studied phenomenon called stochastic resonance, namely that in several sensing systems, both natural and engineered, the introduction of noise can enhance the ability of the system to perceive signals in the environment. We adopt an information theoretic viewpoint, evaluating the quality of sensing via the mutual information rate between the environmental signal and the observations. Viewing what would be considered noise in stochastic resonance as an open loop control and using Markov decision theory techniques, we discuss the problem of optimal choice of this control in order to maximize this mutual information rate. We determine the corresponding dynamic programming recursion: it involves the conditional law of certain conditional laws associated to the dynamics. We prove that the optimal control may be chosen as a deterministic function of this law of laws.

In this paper we revisit previously proposed techniques for constructing some families of subsets of binary strings (codes) that are immune to multiple repetition errors. In particular, we discuss a technique to construct single repetition error correcting codes and use number theoretic methods to give an explicit formula for the cardinalities of these codes. This approach results in codes the ratio of whose cardinality to the best upper bounds approaches unity in the increasing codelength limit (asymptotic optimality). We also discuss a somewhat different technique to construct multiple repetition error correcting codes. Here the cardinalities are asymptotically within a fixed constant of the best known upper bounds. Our constructions are asymptotically better by a constant factor than the best previously known such constructions, due to Levenshtein.

We derive a new upper bound on the secrecy capacity in the source model with eavesdropper which strictly improves the currently best upper bound, i.e. the double intrinsic information bound of Renner and Wolf. Furthermore, unlike that bound, which is defined only in the case of two terminals, the new upper bound is not specific to the two terminals case. We define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement.

We analyze the performance of a Reed–Muller RM$\,(1, m)$code over a channel that, in addition to substitution errors, permits either the repetition of a single bit or the deletion of a single bit; the latter feature is used to model synchronization errors. We first analyze the run-length structure of this code. We enumerate all pairs of codewords that can result in the same sequence after the deletion of a single bit, and propose a simple way to prune the code by dropping one information bit such that the resulting linear subcode has good post-deletion and post-repetition minimum distance. A bounded distance decoding algorithm is provided for the use of this pruned code over the channel. This algorithm has the same order of complexity as the usual fast Hadamard transform based decoder for the RM$\,(1, m)$code.

Several high performance LDPC codes have parity-check matrices composed of permutation submatrices. We design a parallel-serial architecture to map the decoder of any structured LDPC code in this large family to a hardware emulation platform. A peak throughput of 240 Mb/s is achieved in decoding the (2048,1723) Reed-Solomon based LDPC (RS-LDPC) code. Experiments in the low bit error rate (BER) region provide statistics of the error traces, which are used to investigate the causes of the error floor. In a low precision implementation, the error floors are dominated by the fixed-point decoding effects, whereas in a higher precision implementation the errors are attributed to special configurations within the code, whose effect is exacerbated in a fixed-point decoder. This new characterization leads to an improved decoding strategy and higher performance.

We describe a method for enhancing the synchronization error correction properties of an array-based low density parity check (LDPC) code. The proposed method uses code expurgation: a linear subcode is retained for message encoding and additional input bits are used for protection against synchronization errors. The method is easy to implement and incurs minimal loss in rate

In this letter, we apply the Kikuchi approximation method to the problem of joint decoding of a low-density parity-check code and a partial-response channel. The Kikuchi method is, in general, more powerful than the conventional loopy belief propagation (BP) algorithm, and can produce better approximations to an underlying inference problem. We will first review the Kikuchi approximation method and the generalized BP algorithm, which is an iterative message-passing algorithm based on this method. We will then report simulation results which show that the Kikuchi method outperforms the best conventional iterative method

We prove a new outer bound on the rate-distortion region for the multiterminal source-coding problem. This bound subsumes the best known bound in the literature and improves upon it strictly in some cases. The improved bound enables us to obtain a new, conclusive result for the binary-erasure instance of the "CEO problem." The bound recovers many of the converse results that have been established for special cases of the problem, including the recent one for the Gaussian version of the CEO problem

In this letter, we examine a general method of approximation, known as the Kikuchi approximation method, for finding the marginals of a product distribution, as well as the corresponding partition function. The Kikuchi approximation method defines a certain constrained optimization problem, called the Kikuchi problem, and treats its stationary points as approximations to the desired marginals. We show how to associate a graph to any Kikuchi problem and describe a class of local message-passing algorithms along the edges of any such graph, which attempt to find the solutions to the problem. Implementation of these algorithms on graphs with fewer edges requires fewer operations in each iteration. We therefore characterize minimal graphs for a Kikuchi problem, which are those with the minimum number of edges. We show with empirical results that these simpler algorithms often offer significant savings in computational complexity, without suffering a loss in the convergence rate. We give conditions for the convexity of a given Kikuchi problem and the exactness of the approximations in terms of the loops of the minimal graph. More precisely, we show that if the minimal graph is cycle free, then the Kikuchi approximation method is exact, and the converse is also true generically. Together with the fact that in the cycle-free case, the iterative algorithms are equivalent to the well-known belief propagation algorithm, our results imply that, generically, the Kikuchi approximation method can be exact if and only if traditional junction tree methods could also solve the problem exactly.

We determine the reliability function of the exponential-server timing channel (ESTC) in the limit as the data rate approaches zero. The limit shows that at low rates, the ESTC is strictly more reliable than the Poisson channel without dark current, answering a question Arikan posed in these Transactions. The proof employs a distance metric over inputs to timing channels that parallels Euclidean and Hamming distance for conventional channels. A consequence of the proof is that bounded-distance decoding, with distance measured according to this metric, is exponentially optimum for the ESTC in the low-rate regime. We also prove the straight-line bound for the channel and a bound on the reliability of timing channels with general service distributions in the limit as the data rate approaches zero.

The ideal Poisson channel, the ideal Poisson channel with feedback, the exponential-server timing channel, and the exponential-server timing channel with feedback are known to have the same capacity. We show that above this capacity they have the same reliability function, which we determine. For the ideal Poisson channel without feedback, this improves upon the strong converse of Burnashev and Kutoyants.

In this paper, we develop a measure-theoretic version of the junction tree algorithm to compute desired marginals of a product function. We reformulate the problem in a measure-theoretic framework, where the desired marginals are viewed as corresponding conditional expectations of a product of random variables. We generalize the notions of independence and junction trees to collections of /spl sigma/-fields on a space with a signed measure. We provide an algorithm to find such a junction tree when one exists. We also give a general procedure to augment the /spl sigma/-fields to create independencies, which we call "lifting." This procedure is the counterpart of the moralization and triangulation procedure in the conventional generalized distributive law (GDL) framework, in order to guarantee the existence of a junction tree. Our procedure includes the conventional GDL procedure as a special case. However, it can take advantage of structures at the atomic level of the sample space to produce junction tree-based algorithms for computing the desired marginals that are less complex than those GDL can discover, as we argue through examples. Our formalism gives a new way by which one can hope to find low-complexity algorithms for marginalization problems.

We exhibit upper and lower bounds on the pairwise error probability of the exponential-server timing channel in terms of an appropriately-defined distance between codewords. We show that this distance plays a crucial role in determining the reliability function at low rates. In particular, by lower bounding the minimum distance of good-low rates codes, we provide an improved lower bound on the reliability function of the channel at rate zero. This improved bound proves that at low rates, the exponential-server timing channel is strictly more reliable than the related Poisson channel with zero dark current, answering an open question posed by Arikan. Some remarks are also made about using the results of this paper to prove an improved upper bound on the reliability function at rate zero.

Viswanath and Anantharam (1999) characterize the sum capacity of multiaccess vector channels. For a given number of users, received powers, spreading gain, and noise covariance matrix in a code-division multiple-access (CDMA) system, Viswanath and Anantharam present a combinatorial algorithm to generate a set of signature sequences that achieves the maximum sum capacity. These sets also minimize a performance measure called generalized total square correlation (TSC/sub g/). Ulukus and Yates (2001) propose an iterative algorithm suitable for distributed implementation: at each step, one signature sequence is replaced by its linear minimum mean-square error (MMSE) filter. This algorithm results in a decrease of TSC/sub g/ at each step. The MMSE iteration has fixed points not only at the optimal configurations which attain the global minimum TSC/sub g/ but also at other configurations which are suboptimal. The authors of claim that simulations show that when starting with random sequences, the algorithm converges to optimum sets of sequences, but they give no formal proof. We show that the TSC/sub g/ function has no local minima, in the sense that given any suboptimal set of sequences, there exist arbitrarily close sets with lower TSC/sub g/. Therefore, only the optimal sets are stable fixed points of the MMSE iteration. We define a noisy version of the MMSE iteration as follows: after replacing all the signature sequences, one at a time, by their linear MMSE filter, we add a bounded random noise to all the sequences. Using our observation about the TSC/sub g/ function, we can prove that if we choose the bound on the noise adequately, making it decrease to zero, the noisy MMSE iteration converges to the set of optimal configurations with probability one for any initial set of sequences.

Summary form only given. The lack of viable designs for an optical buffer makes all-optical packet switched networking a challenging problem. One systems level idea to deal with this issue is to use erasure codes at the packet level, together with deflection routing whenever packets contend for a destination. There is an important trade-off in the use of such codes: low rate coding allows for session level recovery from more packet losses, but also involves higher packet rates, which causes more erasures on competing streams. Some novel information theoretic problem formulations motivated by this trade-off are discussed.

We consider direct sequence code division multiple access (DS-CDMA), modeling interference from users communicating with neighboring base stations by additive colored noise. We consider two types of receiver structures: first we consider the information-theoretically optimal receiver and use the sum capacity of the channel as our performance measure. Second, we consider the linear minimum mean square error (LMMSE) receiver and use the signal-to-interference ratio (SIR) of the estimate of the symbol transmitted as our performance measure. Our main result is a constructive characterization of the possible performance in both these scenarios. A central contribution of this characterization is the derivation of a qualitative feature of the optimal performance measure in both the scenarios studied. We show that the sum capacity is a saddle function: it is convex in the additive noise covariances and concave in the user received powers. In the linear receiver case, we show that the mini average power required to meet a set of target performance requirements of the users is a saddle function: it is convex in the additive noise covariances and concave in the set of performance requirements.

In a communication network, a good rate allocation algorithm should reflect the utilities of the users while being fair. We investigate this fundamental problem of achieving the system optimal rates in the sense of maximizing aggregate utility, in a distributed manner, using only the information available at the end hosts of the network. This is done by decomposing the overall system problem into subproblems for the network and for the individual users by introducing a pricing scheme. The users are to solve the problem of maximizing individual net utility, which is the utility less the amount they pay. We provide algorithms for the network to adjust its prices and the users to adjust their window sizes such that at an equilibrium the system optimum is achieved. Further, the equilibrium prices are such that the system optimum achieves weighted proportional fairness. It is notable that the update algorithms of the users do not require any explicit feedback from the network, rendering them easily deployable over the Internet. Our scheme is incentive compatible in that there is no benefit to the users to lie about their utilities.

Two decoding schedules and the corresponding serialized architectures for low-density parity-check (LDPC) decoders are presented. They are applied to codes with parity-check matrices generated either randomly or using geometric properties of elements in Galois fields. Both decoding schedules have low computational requirements. The original concurrent decoding schedule has a large storage requirement that is dependent on the total number of edges in the underlying bipartite graph, while a new, staggered decoding schedule which uses an approximation of the belief propagation, has a reduced memory requirement that is dependent only on the number of bits in the block. The performance of these decoding schedules is evaluated through simulations on a magnetic recording channel.

We investigate the fundamental problem of achieving the system optimal rates, which maximize the total user utility, in a distributed network environment using only the information available at the end hosts. This is done by decomposing the overall system problem into subproblems for the network and for the individual users and introducing an incentive-compatible pricing scheme. The users are to solve the problem of maximizing individual net utility, which is their utility less the amount they pay. This is done using a window based algorithm. We provide an algorithm for the network to adjust its prices and the users to adjust their window sizes such that at an equilibrium the system optimum is achieved. It is notable that our algorithm does not require any explicit feedback from the network and can be deployed over the Internet with modifications only at the end hosts. Our scheme is incentive compatible in that there is no benefit to the users to lie about their utilities.

Dynamic resource allocation is an important means to increase the sum capacity of fading multiple-access channels (MACs). In this paper, we consider vector multi-access channels (channels where each user has multiple degrees of freedom) and study the effect of power allocation as a function of the channel state on the sum capacity (or spectral efficiency) defined as the maximum sum of rates of users per unit degree of freedom at which the users can jointly transmit reliably, in an information-theoretic sense, assuming random directions of received signal. Direct-sequence code-division multiple-access (DS-CDMA) channels and MACs with multiple antennas at the receiver are two systems that fall under the model. Our main result is the identification of a simple dynamic power-allocation scheme that is optimal in a large system, i.e., with a large number of users and a correspondingly large number of degrees of freedom. A key feature of this policy is that, for any user, it depends on the instantaneous amplitude of channel state of that user alone and the structure of the policy is "water-filling." In the contest of DS-CDMA and in the special case of no fading, the asymptotically optimal power policy of water-filling simplifies to constant power allocation over all realizations of signature sequences; this result verifies the conjecture made in Verdu and Shamai (1999). We study the behavior of the asymptotically optimal water-filling policy in various regimes of number of users per unit degree of freedom and signal-to-noise ratio (SNR). We also generalize this result to multiple classes, i.e., the situation when users in different classes have different average power constraints.

We investigate the fundamental problem of achieving the system optimal rates in a distributed environment, which maximize the total user utility, using only the information available at the end hosts. This is done by decomposing the system problem into two subproblems-network and user problems-and introducing an incentive-compatible pricing scheme, while maintaining proportional fairness. We demonstrate that when users update their parameters by solving their own optimization problem, at an equilibrium the system optimum is achieved. Furthermore, this algorithm does not require any explicit feedback from the network and can be deployed over the Internet with modifications only on the end hosts. In the second part of the paper we model as a noncooperative game the case where the choice of each user's action has nonnegligible effect on the price per unit flow at the resources and investigate the Nash equilibria of the game. We show, in the simple case of a single bottleneck, that there exists a unique Nash equilibrium of the game. Further, as the number of users increases, the unique Nash equilibrium approaches the system optimum.

We generalize our previous results on generating common randomness at two terminals to a situation where any finite number of agents, interconnected by an arbitrary network of independent, point-to-point, discrete memoryless channels, wish to generate common randomness by interactive communication over the network. Our main result is an exact characterization of the common randomness capacity of such a network, i.e., the maximum number of bits of randomness that all the agents can agree on per step of communication. As a by-product, we also obtain a purely combinatorial result, viz., a characterization of (the incidence vectors of) the spanning arborescences rooted at a specified vertex in a digraph, and having exactly one edge exiting the root, as precisely the extreme points of a certain unbounded convex polyhedron, described by a system of linear inequalities.

We propose some improvements of TCP Vegas and compare its performance characteristics with TCP Reno. We argue through analysis that TCP Vegas, with its better bandwidth estimation scheme, uses the network resources more efficiently and fairly than TCP Reno. Simulation results are given that support the results of the analysis.

It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100% throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times.

The sum capacity of a multiuser synchronous CDMA system is completely characterized in the general case of asymmetric user power constraints-this solves the open problem posed by Rupf and Massey (see ibid., vol.40, p.1261-6, 1994) which had solved the equal power constraint case. We identify the signature sequences with real components that achieve sum capacity and indicate a simple recursive algorithm to construct them.

There has been intense effort in the past decade to develop multiuser receiver structures which mitigate interference between users in spread-spectrum systems. While much of this research is performed at the physical layer, the appropriate power control and choice of signature sequences in conjunction with multiuser receivers and the resulting network user capacity is not well understood. In this paper we will focus on a single cell and consider both the uplink and downlink scenarios and assume a synchronous CDMA (S-CDMA) system. We characterize the user capacity of a single cell with the optimal linear receiver (MMSE receiver). The user capacity of the system is the maximum number of users per unit processing gain admissible in the system such that each user has its quality-of-service (QoS) requirement (expressed in terms of its desired signal-to-interference ratio) met. This characterization allows one to describe the user capacity through a simple effective bandwidth characterization: users are allowed in the system if and only if the sum of their effective bandwidths is less than the processing gain of the system. The effective bandwidth of each user is a simple monotonic function of its QoS requirement. We identify the optimal signature sequences and power control strategies so that the users meet their QoS requirement. The optimality is in the sense of minimizing the sum of allocated powers. It turns out that with this optimal allocation of signature sequences and powers, the linear MMSE receiver is just the corresponding matched filter for each user. We also characterize the effect of transmit power constraints on the user capacity.

We study the following problem: two agents Alice and Bob are connected to each other by independent discrete memoryless channels. They wish to generate common randomness, i.e. agree on a common random variable, by communicating interactively over the two channels. Assuming that Alice and Bob are allowed access to independent external random sources at rates (in bits per step of communication) of H/sub A/ and H/sub B/, respectively, we show that they can generate common randomness at a rate of max{min[H/sub A/+H(W|Q),I(P;V)]+min[H/sub B/+H(V|P), I(Q;W)]} bits per step, by exploiting the noise on the two channels. Here, V is the channel from Alice to Bob, and W is the channel from Bob to Alice. The maximum is over all probability distributions P and Q on the input alphabets of V and W, respectively. We also prove a strong converse which establishes the above rate as the highest attainable in this situation.

We determine the region of all identification and transmission rate-pairs achievable over a discrete memoryless channel (DMC) with perfect and instantaneous feedback, for both randomized and deterministic encoding. As a by-product, we also have a new proof of Kemperman's (1973) strong converse to Shannon's coding theorem for DMC's with feedback.

It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be shown to be limited to approximately 58%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm.

The Shannon capacity of the single-server queue is analyzed. We show that the capacity is lowest, equal to e/sup -1/ nats per average service time, when the service time distribution is exponential. Further, this capacity cannot be increased by feedback. For general service time distributions, upper bounds for the Shannon capacity are determined. The capacities of the telephone signaling channel and of queues with information-bearing packets are also analyzed.

The problem of designing burst reducing flow controllers for traffic in an ATM network is studied. By requiring that the output flow obey certain burstiness constraints, it is shown that an optimal design exists and that it can be easily implemented in real time. Two versions of the problem are considered. The first one places constraints on the buffer size and the second one on the maximum delay that a cell can experience. Both problems are solved for arbitrary traffic processes. To treat the problems in this generality the authors introduce reflection mappings and use them, in a rather novel way, to establish optimality results. As a by-product of the analysis and methods, the optimality of the popular leaky bucket flow control scheme is also established.>

The leaky bucket is a simple flow control scheme for ATM networks. An arriving cell can be transmitted only if it finds a token in the token buffer, in which case it is transmitted instantaneously by consuming a token. If the token buffer is empty, the cell has to wait until the generation of a new token. For purposes of analysis the authors assume an infinite cell buffer. The control parameter is the token buffer size C. The authors examine the burstiness of the output how as a function of C and show that the burstiness increases with C. In particular the output flow is always less bursty than the input flow. This monotonicity simplifies optimal choice of the token buffer size. The result is true for fairly arbitrary input flows and deterministic token generation times.>

The problem is to allocate a fixed number of buffers among the nodes of an open network of exponential servers with Bernoulli routing and Poisson arrivals so as to optimize some performance criterion associated with the time to buffer overflow, such as maximizing its mean or maximizing the probability that it exceeds some value. In earlier work, the authors used pathwise probabilistic arguments to derive a simple rule of thumb for this problem: allocate the buffers in inverse proportion to the logarithms of the effective service rates at the nodes. Effective service rate denotes the ratio of the service rate to the stationary arrival rate in the network with infinite buffers. They showed that this rule of thumb is accurate to within a known constant times the logarithm of the number of buffers as the number of buffers to be allocated becomes large. In the present paper, the authors use time reversal and Poisson clumping arguments to show that their rule of thumb is, in fact, much better than previously demonstrated. They show that the optimal buffer allocation is within a constant of the rule of thumb as the number of buffers to be allocated becomes large, although now they cannot estimate the constant. In numerical terms, the earlier result reduced the search space for the optimal buffer allocation from O(N/sup J-1/) to O((log N)/sup J-1/), where J denotes the number of nodes and N the number of buffers to be allocated. The improvement reduces the search space to O(1).>

A class of discrete-time quasi-reversible nodes called monotone, which includes discrete-time analogs of the ./M/ infinity and ./M/1 nodes, is considered. For stationary ergodic nonnegative integer valued arrival processes, the existence and uniqueness of stationary regimes are proven when a natural rate condition is met. Coupling is used to prove the contractiveness of the input-output map relative to a natural distance on the space of stationary arrival processes that is analogous to Ornstein's d distance. A consequence is that the only stationary ergodic fixed points of the input-output map are the processes of independent and identically distributed Poisson random variables meeting the rate condition.>

A version of the discrete-time slotted ALOHA protocol operating with finitely many buffered terminals is considered. The stability region is defined to be the set of vectors of arrival rates lambda =( lambda /sub 1/,. . ., lambda /sub M/) for which there exists a vector of transmission probabilities such that the system is stable. It is assumed that arrivals are independent from slot to slot, and the following model for the arrival distribution in a slot is assumed: the total number of arrivals in any slots is geometrically distributed, with the probability that such an arrival is at node i being lambda /sub i/ times ( Sigma /sub k/ lambda /sub k/)/sup -1/, independent of the others. With this arrival model, it is proven that the closure of the stability region of the protocol is the same as the closure of the Shannon capacity region of the collision channel without feedback, as determined by J.L. Massey and P. Mathys (1985). At present it is not clear if this result depends on the choice of arrival distribution. The basic probabilistic observation is that the stationary distribution and certain conditional distributions derived from it have positive correlations for bounded increasing functions.>

It is pointed out that the basic results can be proved fairly easily if one uses a Sanov theorem for the distribution of types. Such a theorem comes easily from large deviation theory. A caveat is that this technique only identifies the error exponent up to terms o(n) in the exponent, whereas the combinatorial arguments give an estimate up to terms O(log n) in the exponent.>

Pathwise probabilistic arguments are used to justify a simple rule of thumb by which buffer allocation can be carried out. The model for the underlying network is the skeleton of an open Jackson network. The problem of how to distribute in the best possible way a fixed number N of available buffer spaces among the nodes of the network is considered. The goal is to optimize some performance criterion associated with the time to buffer overflow, such as its mean or the probability that it exceeds some value. It is argued that for any such performance criterion the assignment should be done roughly in inverse proportion to the logarithms of the effective service rates at the nodes. Effective service means the ratio of the service rate to the stationary arrival rate at the node in the network with inifinite buffers.>