The supremum of the Rényi entropy rate over the class of discrete-time stationary stochastic processes, whose marginals are supported by some given set and satisfy some given cost constraint, is computed. Unlike the Shannon entropy, the Rényi entropy of a random vector can exceed the sum of the Rényi entropies of its components, and the supremum is, therefore, typically not achieved by memoryless processes. It is nonetheless related to Shannon's entropy: when the Rényi parameter exceeds one, the supremum is equal to the corresponding supremum of Shannon's entropy, and when it is smaller than one, the supremum equals the logarithm of the volume of the support set. A Burg-like supremum of the Rényi entropy rate over the class of stochastic processes, whose autocovariance function begins with some given values, is also solved. It is not achieved by Gauss-Markov processes, but it is nonetheless related to Burg's supremum: the two are equal when the Rényi parameter exceeds one, and the former is infinite otherwise.

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum ρ-th moment of the number of performed tasks are derived. The key is an analog of the Kraft Inequality for partitions of finite sets. When a sequence of tasks is produced by a source of a given Rényi entropy rate of order 1=(1 + ρ) and n tasks are jointly described using nR bits, it is shown that for R larger than the Rényi entropy rate, the ρ-th moment of the ratio of performed tasks to n can be driven to one as n tends to infinity, and that for R less than the Rényi entropy rate it tends to infinity. This generalizes a recent result for IID sources by the same authors. A mismatched version of the direct part is also considered, where the code is designed according to the wrong law. The penalty incurred by the mismatch can be expressed in terms of a divergence measure that was shown by Sundaresan to play a similar role in the Massey-Arikan guessing problem.

Optimal error probabilities for transmission over the average-power-limited Gaussian channel with intermittent feedback are studied. For the two-message case, the asymptotic decay of the probability of error in the blocklength is double-exponential and is fully characterized. For positive rates a critical rate is identified below which a double-exponential decay is possible and above which it is not.

Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower-bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here we derive an upper bound that proves the conjecture.

A random variable Z taking value in a finite, nonatomic measure space (X;M; μ) and whose distribution is absolutely continuous with respect to μ is to be described using N labels. We seek the labeling that minimizes the ρ-th moment of the μ-volume of the set of points in X that have the same label as Z. The large-N asymptotics of this minimum are expressed in terms of the Rényi entropy of order 1=(1 + ρ).

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum pth moment of the number of performed tasks are derived. The case where a sequence of tasks is produced by a source and n tasks are jointly described using nR bits is considered. If R is larger than the Rényi entropy rate of the source of order 1/(1 + ρ) (provided it exists), then the ρth moment of the ratio of performed tasks to n can be driven to one as n tends to infinity. If R is smaller than the Rényi entropy rate, this moment tends to infinity. The results are generalized to account for the presence of side-information. In this more general setting, the key quantity is a conditional version of Rényi entropy that was introduced by Arimoto. For IID sources, two additional extensions are solved, one of a rate-distortion flavor and the other where different tasks may have different nonnegative costs. Finally, a divergence that was identified by Sundaresan as a mismatch penalty in the Massey-Arikan guessing problem is shown to play a similar role here.

The listsize capacity of a discrete memoryless channel is the largest transmission rate for which the expectation-or, more generally, the ρ-th moment-of the number of messages that could have produced the output of the channel approaches one as the blocklength tends to infinity. We show that for channels with feedback, this rate is upper bounded by the maximum of Gallager's E0function divided by ρ, and that equality holds when the zero-error capacity of the channel is positive. To establish this inequality, we prove that feedback does not increase the cutoff rate. Relationships to other notions of channel capacity are explored.

Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here, we derive an upper bound that proves the conjecture.

We study the zero-undetected-error capacity of the discrete memoryless channel whose directed channel graph is the cyclic triangle. We show that this capacity is upper-bounded by log 2 and approaches log 2 as the crossover probabilities tend to zero.

A sequence produced by a memoryless source is to be described using a fixed number of bits that is proportional to its length. Based on the description, a list that is guaranteed to contain the sequence must be produced. The trade-off between the description length and the moments of the listsize is studied when the sequence's length tends to infinity. It is characterized by the source's Rényi entropy. Extensions to scenarios with side information are also studied, where the key is conditional Rényi entropy. The lossy case where at least one of the elements of the list must be within a specified distortion from the source sequence is also solved.

We study the cutoff rate and the average-listsize capacity of discrete memoryless channels (DMCs) with feedback. We show that feedback can increase the average-listsize capacity but not the cutoff rate. For DMCs with positive zero-error capacity, we show that the average-listsize capacity with feedback is equal to the cutoff rate. For all other DMCs, we derive a lower bound on the average-listsize capacity with feedback. The bound is asymptotically tight for low-noise channels. We also show that a multi-letter version of Forney's lower bound on the average-listsize capacity of DMCs without feedback is asymptotically tight.

We propose an algorithm for computing the capacity of discrete rewritable storage devices subject to a constraint on the maximal number of rewrite operations. The linchpin is that-although the number of writing strategies is exponential in the maximal number of allowed rewrites-linear functionals of the probabilities they induce on the output space can be efficiently maximized using Dynamic Programming.