Search

This article stands as a tribute to the enduring legacy of Jacob Ziv and his landmark contributions to information theory. Specifically, it delves into the groundbreaking individual-sequence approach -- a cornerstone of Ziv's academic pursuits. Together with Abraham Lempel, Ziv pioneered the renowned Lempel-Ziv (LZ) algorithm, a beacon of innovation in various versions. Beyond its original domain of universal data compression, this article underscores the broad utility of the individual-sequence approach and the LZ algorithm across a wide spectrum of problem areas. As we traverse through the forthcoming pages, it will also become evident how Ziv's visionary approach has left an indelible mark on my own research journey, as well as on those of numerous colleagues and former students. We shall explore, not only the technical power of the LZ algorithm, but also its profound impact on shaping the landscape of information theory and its applications., Comment: 10 pages, 3 figures, submitted to the IEEE BITS Magazine - The Information Theory Magazine

This monograph offers a toolbox of mathematical techniques, which have been effective and widely applicable in information-theoretic analysis. The first tool is a generalization of the method of types to Gaussian settings, and then to general exponential families. The second tool is Laplace and saddle-point integration, which allow to refine the results of the method of types, and are capable of obtaining more precise results. The third is the type class enumeration method, a principled method to evaluate the exact random-coding exponent of coded systems, which results in the best known exponent in various problem settings. The fourth subset of tools aimed at evaluating the expectation of non-linear functions of random variables, either via integral representations, or by a refinement of Jensen's inequality via change-of-measure, by complementing Jensen's inequality with a reversed inequality, or by a class of generalized Jensen's inequalities that are applicable for functions beyond convex/concave. Various application examples of all these tools are provided along this monograph., Comment: 154 pages, 1 figure, submitted for publication

We refine and extend Ziv's model and results regarding perfectly secure encryption of individual sequences. According to this model, the encrypter and the legitimate decrypter share in common a secret key, not shared with the unauthorized eavesdropper, who is aware of the encryption scheme and has some prior knowledge concerning the individual plaintext source sequence. This prior knowledge, combined with the cryptogram, is harnessed by eavesdropper which implements a finite-state machine as a mechanism for accepting or rejecting attempted guesses of the source plaintext. The encryption is considered perfectly secure if the cryptogram does not provide any new information to the eavesdropper that may enhance its knowledge concerning the plaintext beyond his prior knowledge. Ziv has shown that the key rate needed for perfect secrecy is essentially lower bounded by the finite-state compressibility of the plaintext sequence, a bound which is clearly asymptotically attained by Lempel-Ziv compression followed by one-time pad encryption. In this work, we consider some more general classes of finite-state eavesdroppers and derive the respective lower bounds on the key rates needed for perfect secrecy. These bounds are tighter and more refined than Ziv's bound and they are attained by encryption schemes that are based on different universal lossless compression schemes. We also extend our findings to the case where side information is available to the eavesdropper and the legitimate decrypter, but may or may not be available to the encrypter as well., Comment: 24 pages; submitted for publication

In continuation of an earlier study, we explore a Neymann-Pearson hypothesis testing scenario where, under the null hypothesis ($\cal{H}_0$), the received signal is a white noise process $N_t$, which is not Gaussian in general, and under the alternative hypothesis ($\cal{H}_1$), the received signal comprises a deterministic transmitted signal $s_t$ corrupted by additive white noise, the sum of $N_t$ and another noise process originating from the transmitter, denoted as $Z_t$, which is not necessarily Gaussian either. Our approach focuses on detectors that are based on the correlation and energy of the received signal, which are motivated by implementation simplicity. We optimize the detector parameters to achieve the best trade-off between missed-detection and false-alarm error exponents. First, we optimize the detectors for a given signal, resulting in a non-linear relation between the signal and correlator weights to be optimized. Subsequently, we optimize the transmitted signal and the detector parameters jointly, revealing that the optimal signal is a balanced ternary signal and the correlator has at most three different coefficients, thus facilitating a computationally feasible solution., Comment: 27 pages, 5 figures; submitted for publication

We establish a coding theorem and a matching converse theorem for separate encodings and joint decoding of individual sequences using finite-state machines. The achievable rate region is characterized in terms of the Lempel-Ziv (LZ) complexities, the conditional LZ complexities and the joint LZ complexity of the two source sequences. An important feature that is needed to this end, which may be interesting on its own right, is a certain asymptotic form of a chain rule for LZ complexities, which we establish in this work. The main emphasis in the achievability scheme is on the universal decoder and its properties. We then show that the achievable rate region is universally attainable by a modified version of Draper's universal incremental Slepian-Wolf (SW) coding scheme, provided that there exists a low-rate reliable feedback link., Comment: 26 pages; submitted for publication

We extend Ziv and Lempel's model of finite-state encoders to the realm of lossy compression of individual sequences. In particular, the model of the encoder includes a finite-state reconstruction codebook followed by an information lossless finite-state encoder that compresses the reconstruction codeword with no additional distortion. We first derive two different lower bounds to the compression ratio that depend on the number of states of the lossless encoder. Both bounds are asymptotically achievable by conceptually simple coding schemes. We then show that when the number of states of the lossless encoder is large enough in terms of the reconstruction block-length, the performance can be improved, sometimes significantly so. In particular, the improved performance is achievable using a random-coding ensemble that is universal, not only in terms of the source sequence, but also in terms of the distortion measure., Comment: 22 pages, 1 figure, submitted for publication

The problem of transmitting a parameter value over an additive white Gaussian noise (AWGN) channel is considered, where, in addition to the transmitter and the receiver, there is a helper that observes the noise non-causally and provides a description of limited rate $R_h$ to the transmitter and/or the receiver. We derive upper and lower bounds on the optimal achievable $\alpha$-th moment of the estimation error and show that they coincide for small values of $\alpha$ and for high values of $R_h$. The upper bound relies on a recently proposed channel-coding scheme that effectively conveys $R_h$ bits essentially error-free and the rest of the rate - over the same AWGN channel without help, with the error-free bits being allocated to the most significant bits of the quantized parameter. We then concentrate on the setting with a total transmit energy constraint, for which we derive achievability results for both channel coding and parameter modulation for several scenarios: when the helper assists only the transmitter or only the receiver and knows the noise, and when the helper assists the transmitter and/or the receiver and knows both the noise and the message. In particular, for the message-informed helper that assists both the receiver and the transmitter, it is shown that the error probability in the channel-coding task decays doubly exponentially. Finally, we translate these results to those for continuous-time power-limited AWGN channels with unconstrained bandwidth. As a byproduct, we show that the capacity with a message-informed helper that is available only at the transmitter can exceed the sum of the capacity without help and the help rate $R_h$, when the helper knows only the noise but not the message., Comment: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

We consider the problem of parameter estimation, based on noisy chaotic signals, from the viewpoint of twisted modulation for waveform communication. In particular, we study communication systems where the parameter to be estimated is conveyed as the initial condition of a chaotic dynamical system of a certain class and we examine its estimation performance in terms of the expectation of a given convex function of the estimation error at high SNR, under the demand that the probability of anomaly is kept small. We derive a lower bound on the weak-noise estimation error for this class of chaotic modulators, and argue that it can be outperformed by using the itinerary signal associated with the chaotic system instead of the main chaotic output signal., Comment: 29 pages; submitted for publication

It is well known that the traditional Jensen inequality is proved by lower bounding the given convex function, $f(x)$, by the tangential affine function that passes through the point $(E\{X\},f(E\{X\}))$, where $E\{X\}$ is the expectation of the random variable $X$. While this tangential affine function yields the tightest lower bound among all lower bounds induced by affine functions that are tangential to $f$, it turns out that when the function $f$ is just part of a more complicated expression whose expectation is to be bounded, the tightest lower bound might belong to a tangential affine function that passes through a point different than $(E\{X\},f(E\{X\}))$. In this paper, we take advantage of this observation, by optimizing the point of tangency with regard to the specific given expression, in a variety of cases, and thereby derive several families of inequalities, henceforth referred to as ``Jensen-like'' inequalities, which are new to the best knowledge of the author. The degree of tightness and the potential usefulness of these inequalities is demonstrated in several application examples related to information theory., Comment: 20 pages, 4 figures, submitted for publication

We propose a universal ensemble for random selection of rate-distortion codes, which is asymptotically optimal in a sample-wise sense. According to this ensemble, each reproduction vector, $\hbx$, is selected independently at random under the probability distribution that is proportional to $2^{-LZ(\hbx)}$, where $LZ(\hbx)$ is the code-length of $\hbx$ pertaining to the 1978 version of the Lempel-Ziv (LZ) algorithm. We show that, with high probability, the resulting codebook gives rise to an asymptotically optimal variable-rate lossy compression scheme under an arbitrary distortion measure, in the sense that a matching converse theorem also holds. According to the converse theorem, even if the decoder knew $\ell$-th order type of source vector in advance ($\ell$ being a large but fixed positive integer), the performance of the above-mentioned code could not have been improved essentially, for the vast majority of codewords that represent all source vectors in the same type. Finally, we provide a discussion of our results, which includes, among other things, a comparison to a coding scheme that selects the reproduction vector with the shortest LZ code length among all vectors that are within the allowed distortion from the source vector., Comment: 22 pages, submitted for publication

The Gaussian wiretap channel with rate-limited help, available at the legitimate receiver (Rx) or/and transmitter (Tx), is studied under various channel configurations (degraded, reversely degraded and non-degraded). In the case of Rx help and all channel configurations, the rate-limited help results in a secrecy capacity boost equal to the help rate irrespective of whether the help is secure or not, so that the secrecy of help does not provide any capacity increase. The secrecy capacity is positive for the reversely-degraded channel (where the no-help secrecy capacity is zero) and no wiretap coding is needed to achieve it. More noise at the legitimate receiver can sometimes result in higher secrecy capacity. The secrecy capacity with Rx help is not increased even if the helper is aware of the message being transmitted. The same secrecy capacity boost also holds if non-secure help is available to the transmitter (encoder), in addition to or instead of the same Rx help, so that, in the case of the joint Tx/Rx help, one help link can be omitted without affecting the capacity. If Rx/Tx help links are independent of each other, then the boost in the secrecy capacity is the sum of help rates and no link can be omitted without a loss in the capacity. Non-singular correlation of the receiver and eavesdropper noises does not affect the secrecy capacity and non-causal help does not bring in any capacity increase over the causal one., Comment: An extended version of the paper presented at the IEEE International Symposium on Information Theory, Helsinki, Finland, June 26 - July 1, 2022; submitted to IEEE Trans. Info. Theory

We consider an ensemble of constant composition codes that are subsets of linear codes: while the encoder uses only the constant-composition subcode, the decoder operates as if the full linear code was used, with the motivation of simultaneously benefiting both from the probabilistic shaping of the channel input and from the linear structure of the code. We prove that the codebook mismatch can be fully compensated by using a mismatched additive decoding metric that achieves the random coding error exponent of (non-linear) constant composition codes. As the coding rate tends to the mutual information, the optimal mismatched metric approaches the maximum a posteriori probability (MAP) metric, showing that codebook mismatch with mismatched MAP metric is capacity-achieving for the optimal input assignment., Comment: 25 pages, one figure, submitted for publication

We derive various error exponents for communication channels with random states, which are available non-causally at the encoder only. For both the finite-alphabet Gel'fand-Pinsker channel and its Gaussian counterpart, the dirty-paper channel, we derive random coding exponents, error exponents of the typical random codes (TRCs), and error exponents of expurgated codes. For the two channel models, we analyze some sub-optimal bin-index decoders, which turn out to be asymptotically optimal, at least for the random coding error exponent. For the dirty-paper channel, we show explicitly via a numerical example, that both the error exponent of the TRC and the expurgated exponent strictly improve upon the random coding exponent, at relatively low coding rates, which is a known fact for discrete memoryless channels without random states. We also show that at rates below capacity, the optimal values of the dirty-paper design parameter $\alpha$ in the random coding sense and in the TRC exponent sense are different from one another, and they are both different from the optimal $\alpha$ that is required for attaining the channel capacity. For the Gel'fand-Pinsker channel, we allow for a variable-rate random binning code construction, and prove that the previously proposed maximum penalized mutual information decoder is asymptotically optimal within a given class of decoders, at least for the random coding error exponent.

We prove the existence of codebooks for d-semifaithful lossy compression that are simultaneously universal with respect to both the class of finite-alphabet memoryless sources and the class of all bounded additive distortion measures. By applying independent random selection of the codewords according to a mixture of all memoryless sources, we achieve redundancy rates that are within O(log n/n) close to the empirical rate-distortion function of every given source vector with respect to every bounded distortion measure. As outlined in the last section, the principal ideas can also be extended significantly beyond the class of memoryless sources, namely, to the setting of individual sequences encoded by finite-state machines., Comment: 21 pages; submitted for publication

We consider the classical Neymann-Pearson hypothesis testing problem of signal detection, where under the null hypothesis ($\calH_0$), the received signal is white Gaussian noise, and under the alternative hypothesis ($\calH_1$), the received signal includes also an additional non-Gaussian random signal, which in turn can be viewed as a deterministic waveform plus zero-mean, non-Gaussian noise. However, instead of the classical likelihood ratio test detector, which might be difficult to implement, in general, we impose a (mismatched) correlation detector, which is relatively easy to implement, and we characterize the optimal correlator weights in the sense of the best trade-off between the false-alarm error exponent and the missed-detection error exponent. Those optimal correlator weights depend (non-linearly, in general) on the underlying deterministic waveform under $\calH_1$. We then assume that the deterministic waveform may also be free to be optimized (subject to a power constraint), jointly with the correlator, and show that both the optimal waveform and the optimal correlator weights may take on values in a small finite set of typically no more than two to four levels, depending on the distribution of the non-Gaussian noise component. Finally, we outline an extension of the scope to a wider class of detectors that are based on linear combinations of the correlation and the energy of the received signal., Comment: 29 pages, 4 figures, submitted for publication

In this paper, we consider the problem of guessing a sequence subject to a distortion constraint. Specifically, we assume the following game between Alice and Bob: Alice has a sequence $\bx$ of length $n$. Bob wishes to guess $\bx$, yet he is satisfied with finding any sequence $\hat{\bx}$ which is within a given distortion $D$ from $\bx$. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses (the \emph{guesswork}), and analyzing its properties (e.g., its $\rho$--th moment) has several applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering contemporary biometrically--secured systems, where the "password" which protects the data is not a single, fixed vector but rather a \emph{ball of feature vectors} centered at some $\bx$, and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in \emph{four different setups}: memoryless sources, guessing through a noisy channel, sources with memory and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is \emph{five--fold universal}, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level., Comment: Submitted to IEEE Transactions on Information Theory

We consider the problem of encoding a deterministic source sequence (a.k.a.\ individual sequence) for the degraded wiretap channel by means of an encoder and decoder that can both be implemented as finite--state machines. Our first main result is a necessary condition for both reliable and secure transmission in terms of the given source sequence, the bandwidth expansion factor, the secrecy capacity, the number of states of the encoder and the number of states of the decoder. Equivalently, this necessary condition can be presented as a converse bound (i.e., a lower bound) on the smallest achievable bandwidth expansion factor. The bound is asymptotically achievable by Lempel-Ziv compression followed by good channel coding for the wiretap channel. Given that the lower bound is saturated, we also derive a lower bound on the minimum necessary rate of purely random bits needed for local randomness at the encoder in order to meet the security constraint. This bound too is achieved by the same achievability scheme. Finally, we extend the main results to the case where the legitimate decoder has access to a side information sequence, which is another individual sequence that may be related to the source sequence, and a noisy version of the side information sequence leaks to the wiretapper., Comment: 34 pages, submitted for publication

The DNA storage channel is considered, in which the $M$ Deoxyribonucleic acid (DNA) molecules comprising each codeword are stored without order, sampled $N$ times with replacement, and then sequenced over a discrete memoryless channel. For a constant coverage depth $M/N$ and molecule length scaling $\Theta(\log M)$, lower (achievability) and upper (converse) bounds on the capacity of the channel, as well as a lower (achievability) bound on the reliability function of the channel are provided. Both the lower and upper bounds on the capacity generalize a bound which was previously known to hold only for the binary symmetric sequencing channel, and only under certain restrictions on the molecule length scaling and the crossover probability parameters. When specified to binary symmetric sequencing channel, these restrictions are completely removed for the lower bound and are significantly relaxed for the upper bound in the high-noise regime. The lower bound on the reliability function is achieved under a universal decoder, and reveals that the dominant error event is that of outage -- the event in which the capacity of the channel induced by the DNA molecule sampling operation does not support the target rate.

We study the following semi-deterministic setting of the joint source-channel coding problem: a deterministic source sequence (a.k.a. individual sequence) is transmitted via a memoryless channel, using delay-limited encoder and decoder, which are both implementable by periodically-varying finite-state machines, and the decoder is granted with access to side information, which is a noisy version of the source sequence. We first derive a lower bound on the achievable expected distortion in terms of the empirical statistics of the source sequence, the number of states of the encoder, the number of states of the decoder, their period, and the overall delay. The bound is shown to be asymptotically achievable by universal block codes in the limit of long blocks. We also derive a lower bound to the best achievable excess--distortion probability and discuss situations where it is achievable. Here, of course, source coding and channel coding cannot be completely separated without loss of optimality. Finally, we outline a few extensions of the model considered, such as: (i) incorporating a common reconstruction constraint, (ii) availability of side information at both ends, and (iii) extension to the Shannon channel with causal state information at the encoder. This work both extends and improves on earlier work of the same flavor (Ziv 1980, Merhav 2014), which focused only on the expected distortion, without side information at either end, and without the above mentioned additional ingredients., Comment: 30 pages; 1 figure, submitted for publication. Revised version of the original article

A source sequence is to be guessed with some fidelity based on a rate-limited description of an observed sequence with which it is correlated. The trade-off between the description rate and the exponential growth rate of the least power mean of the number of guesses is characterized.

We consider a point-to-point communication system, where in addition to the encoder and the decoder, there is a helper that observes non-causally the realization of the noise vector and provides a (lossy) rate-$R_{\mbox{\tiny h}}$ description of it to the encoder ($R_{\mbox{\tiny h}} < \infty$). While Lapidoth and Marti (2020) derived coding theorems, associated with achievable channel-coding rates (of the main encoder) for this model, here our focus is on error exponents. We consider both continuous-alphabet, additive white Gaussian channels and finite-alphabet, modulo-additive channels, and for each one of them, we study the cases of both fixed-rate and variable-rate noise descriptions by the helper. Our main finding is that, as long as the channel-coding rate, $R$, is below the helper-rate, $R_{\mbox{\tiny h}}$, the achievable error exponent is unlimited (i.e., it can be made arbitrarily large), and in some of the cases, it is even strictly infinite (i.e., the error probability can be made strictly zero). However, in the range of coding rates $(R_{\mbox{\tiny h}},R_{\mbox{\tiny h}}+C_0)$, $C_0$ being the ordinary channel capacity (without help), the best achievable error exponent is finite and strictly positive, although there is a certain gap between our upper bound (converse bound) and lower bound (achievability) on the highest achievable error exponent. This means that the model of encoder-assisted communication is essentially equivalent to a model, where in addition to the noisy channel between the encoder and decoder, there is also a parallel noiseless bit-pipe of capacity $R_{\mbox{\tiny h}}$. We also extend the scope to the Gaussian multiple access channel (MAC) and characterize the rate sub-region, where the achievable error exponent is unlimited or even infinite., Comment: 21 pages; submitted for publication

We derive various error exponents in the bee identification problem under two different decoding rules. Under na\"ive decoding, which decodes each bee independently of the others, we analyze a general discrete memoryless channel and a relatively wide family of stochastic decoders. Upper and lower bounds to the random coding error exponent are derived and proved to be equal at relatively high coding rates. Then, we propose a lower bound on the error exponent of the typical random code, which improves upon the random coding exponent at low coding rates. We also derive a third bound, which is related to expurgated codes, which turns out to be strictly higher than the other bounds, also at relatively low rates. We show that the universal maximum mutual information decoder is optimal with respect to the typical random code and the expurgated code. Moving further, we derive error exponents under optimal decoding, the relatively wide family of symmetric channels, and the maximum likelihood decoder. We first propose a random coding lower bound, and then, an improved bound which stems from an expurgation process. We show numerically that our second bound strictly improves upon the random coding bound at an intermediate range of coding rates, where a bound derived in a previous work no longer holds.

Traditionally, ensembles of Slepian-Wolf (SW) codes are defined such that every bin of each $n$-vector of each source is randomly drawn under the uniform distribution across the sets $\{0,1,\ldots,2^{nR_X}-1\}$ and $\{0,1,\ldots,2^{nR_Y}-1\}$, where $R_X$ and $R_Y$ are the coding rates of the two sources, $X$ and $Y$, respectively. In a few more recent works, where only one source, say, $X$, is compressed and the other one, $Y$, serves as side information available at the decoder, the scope is extended to variable-rate S-W (VRSW) codes, where the rate is allowed to depend on the type class of the source string, but still, the random-binning distribution is assumed uniform within the corresponding, type-dependent, bin index set. In this expository work, we investigate the role of the uniformity of the random binning distribution from the perspective of the trade-off between the reliability (defined in terms of the error exponent) and the compression performance (measured from the viewpoint of the source coding exponent). To this end, we study a much wider class of random-binning distributions, which includes the ensemble of VRSW codes as a special case, but it also goes considerably beyond. We first show that, with the exception of some pathological cases, the smaller ensemble, of VRSW codes, is as good as the larger ensemble in terms the trade-off between the error exponent and the source coding exponent. Notwithstanding this finding, the wider class of ensembles proposed is motivated in two ways. The first is that it outperforms VRSW codes in the above-mentioned pathological cases, and the second is that it allows robustness: in the event of a system failure that causes unavailability of the compressed bit-stream from one of the sources, it still allows reconstruction of the other source within some controllable distortion., Comment: 30 pages; submitted for publication

We consider the problem of (almost) lossless source coding of two correlated memoryless sources using separate encoders and a joint decoder, that is, Slepian-Wolf (S-W) coding. In our setting, the encoding and decoding are asynchronous, i.e., there is a certain relative delay between the two sources. Neither the source parameters nor the relative delay are known to the encoders and the decoder. Since we assume that both encoders implement standard random binning, which does not require such knowledge anyway, the focus of this work is on the decoder. Our main contribution is in proposing a universal decoder, that independent of the unknown source parameters and the relative delay, and at the same time, is asymptotically as good as the optimal maximum a posteriori probability (MAP) decoder in the sense of the random coding error exponent achieved.Consequently, the achievable rate region is also the same as if the source parameters and the delay were known to the decoder., Comment: 23 pages, submitted for publication

We provide two results concerning the optimality of the maximum mutual information (MMI) decoder. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the MMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the MMI decoders are equal. These results strengthen the well known result due to Csisz\'ar and K\"orner, according to which, these decoders achieve equal random coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random coding error exponents, at least at low coding rates. While the universal optimality of the MMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble, when it comes to typical and expurgated exponents, this commutation can no longer be carried out. Therefore, the proof of the universal optimality of the MMI decoder must be completely different and it turns out to be highly non-trivial.

We discuss work extraction from classical information engines (e.g., Szil\'ard) with $N$-particles, $q$ partitions, and initial arbitrary non-equilibrium states. In particular, we focus on their {\em optimal} behaviour, which includes the measurement of a set of quantities $\Phi$ with a feedback protocol that extracts the maximal average amount of work. We show that the optimal non-equilibrium state to which the engine should be driven before the measurement is given by the normalised maximum-likelihood probability distribution of a statistical model that admits $\Phi$ as sufficient statistics. Furthermore, we show that the minimax universal code redundancy $\mathcal{R}^*$ associated to this model, provides an upper bound to the work that the demon can extract on average from the cycle, in units of $k_{\rm B}T$. We also find that, in the limit of $N$ large, the maximum average extracted work cannot exceed $H[\Phi]/2$, i.e. one half times the Shannon entropy of the measurement. Our results establish a connection between optimal work extraction in stochastic thermodynamics and optimal universal data compression, providing design principles for optimal information engines. In particular, they suggest that: (i) optimal coding is thermodynamically efficient, and (ii) it is essential to drive the system into a critical state in order to achieve optimal performance., Comment: 26 pages, 5 figures. To appear in JSTAT

Typical random codes (TRC) in a communication scenario of source coding with side information at the decoder is the main subject of this work. We study the semi-deterministic code ensemble, which is a certain variant of the ordinary random binning code ensemble. In this code ensemble, the relatively small type classes of the source are deterministically partitioned into the available bins in a one-to-one manner. As a consequence, the error probability decreases dramatically. The random binning error exponent and the error exponent of the TRC are derived and proved to be equal to one another in a few important special cases. We show that the performance under optimal decoding can be attained also by certain universal decoders, e.g., the stochastic likelihood decoder with an empirical entropy metric. Moreover, we discuss the trade-offs between the error exponent and the excess-rate exponent for the typical random semi-deterministic code and characterize its optimal rate function. We show that for any pair of correlated information sources, both error and excess-rate probabilities are exponentially vanishing when the blocklength tends to infinity.

This work is an extension of our earlier article, where a well-known integral representation of the logarithmic function was explored, and was accompanied with demonstrations of its usefulness in obtaining compact, easily-calculable, exact formulas for quantities that involve expectations of the logarithm of a positive random variable. Here, in the same spirit, we derive an exact integral representation (in one or two dimensions) of the moment of a nonnegative random variable, or the sum of such independent random variables, where the moment order is a general positive noninteger real (also known as fractional moments). The proposed formula is applied to a variety of examples with an information-theoretic motivation, and it is shown how it facilitates their numerical evaluations. In particular, when applied to the calculation of a moment of the sum of a large number, $n$, of nonnegative random variables, it is clear that integration over one or two dimensions, as suggested by our proposed integral representation, is significantly easier than the alternative of integrating over $n$ dimensions, as needed in the direct calculation of the desired moment., Comment: Published in Entropy, vol. 22, no. 6, paper 707, pages 1-29, June 2020. Available at: https://www.mdpi.com/1099-4300/22/6/707

This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double-exponentially small; upper and lower bounds to the double-exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.

We explore a well-known integral representation of the logarithmic function, and demonstrate its usefulness in obtaining compact, easily-computable exact formulas for quantities that involve expectations and higher moments of the logarithm of a positive random variable (or the logarithm of a sum of positive random variables). The integral representation of the logarithm is proved useful in a variety of information-theoretic applications, including universal lossless data compression, entropy and differential entropy evaluations, and the calculation of the ergodic capacity of the single-input, multiple-output (SIMO) Gaussian channel with random parameters (known to both transmitter and receiver). This integral representation and its variants are anticipated to serve as a useful tool in additional applications, as a rigorous alternative to the popular (but non-rigorous) replica method (at least in some situations)., Comment: Published in the Entropy journal, vol.22, no.1, paper 51, pp. 1--23, January 2020. See https://www.mdpi.com/1099-4300/22/1/51

We consider the problem of guessing a random, finite-alphabet, secret $n$-vector, where the guesses are transmitted via a noisy channel. We provide a single-letter formula for the best achievable exponential growth rate of the $\rho$--th moment of the number of guesses, as a function of $n$. This formula exhibits a fairly clear insight concerning the penalty due to the noise. We describe two different randomized schemes that achieve the optimal guessing exponent. One of them is fully universal in the sense of being independent of source (that governs the vector to be guessed), the channel (that corrupts the guesses), and the moment power $\rho$. Interestingly, it turns out that, in general, the optimal guessing exponent function exhibits a phase transition when it is examined either as a function of the channel parameters, or as a function of $\rho$: as long as the channel is not too distant (in a certain sense to be defined precisely) from the identity channel (i.e., the clean channel), or equivalently, as long $\rho$ is larger than a certain critical value, $\rho_{\mbox{\tiny c}}$, there is no penalty at all in the guessing exponent, compared to the case of noiseless guessing., Comment: 17 pages; 2 figues; submitted for publication

A Lagrange-dual (Gallager-style) lower bound is derived for the error exponent function of the typical random code (TRC) pertaining to the i.i.d. random coding ensemble and mismatched stochastic likelihood decoding. While the original expression, derived from the method of types (the Csiszar-style expression) involves minimization over probability distributions defined on the channel input--output alphabets, the new Lagrange-dual formula involves optimization of five parameters, independently of the alphabet sizes. For both stochastic and deterministic mismatched decoding (including maximum likelihood decoding as a special case),we provide a rather comprehensive discussion on the insight behind the various ingredients of this formula and describe how its behavior varies as the coding rate exhausts the relevant range. Among other things, it is demonstrated that this expression simultaneously generalizes both the expurgated error exponent function (at zero rate) and the classical random coding exponent function at high rates, where it also meets the sphere--packing bound., Comment: 21 pages, submitted for publication

Motivated by earlier results on universal randomized guessing, we consider an individual-sequence approach to the guessing problem: in this setting, the goal is to guess a secret, individual (deterministic) vector $x^n=(x_1,\ldots,x_n)$, by using a finite-state machine that sequentially generates randomized guesses from a stream of purely random bits. We define the finite-state guessing exponent as the asymptotic normalized logarithm of the minimum achievable moment of the number of randomized guesses, generated by any finite-state machine, until $x^n$ is guessed successfully. We show that the finite-state guessing exponent of any sequence is intimately related to its finite-state compressibility (due to Lempel and Ziv), and it is asymptotically achieved by the decoder of (a certain modified version of) the 1978 Lempel-Ziv data compression algorithm (a.k.a. the LZ78 algorithm), fed by purely random bits. The results are also extended to the case where the guessing machine has access to a side information sequence, $y^n=(y_1,\ldots,y_n)$, which is also an individual sequence., Comment: 23 pages, 1 figure, submitted for publication

We address the problem of modulating a parameter onto a power-limited signal, transmitted over a discrete-time Gaussian channel and estimating this parameter at the receiver. Continuing an earlier work, where the optimal trade-off between the weak-noise estimation performance and the outage probability (threshold-effect breakdown) was studied for a single (scalar) parameter, here we extend the derivation of the weak-noise estimation performance to the case of a multi-dimensional vector parameter. This turns out to be a non-trivial extension, that provides a few insights and it has some interesting implications, which are discussed in depth. Several modifications and extensions of the basic setup are also studied and discussed., Comment: 20 pages, 1 figure, submitted for publication

In continuation to an earlier work, where error exponents of typical random codes were studied in the context of general block coding, with no underlying structure, here we carry out a parallel study on typical random, time-varying trellis codes for general discrete memoryless channels, focusing on a certain range of low rates. By analyzing an upper bound to the error probability of the typical random trellis code, using the method of types, we first derive a Csiszar-style error exponent formula (with respect to the constraint length), which allows to easily identify and characterize properties of good codes and dominant error events. We also derive a Gallager-style form of this error exponent, which turns out to be related to the expurgated error exponent. The main result is further extended to channels with memory and mismatch., Comment: 26 pages, 3 figures, submitted for publication

The error exponent of the typical random code is defined as the asymptotic normalized expectation of the logarithm of the probability of error, as opposed to the traditional definition of the random coding exponent as the normalized logarithm of the expectation of the probability of error with respect to a given ensemble of codes. For a certain ensemble of independent codewords, with a given power spectrum, and a generalized stochastic mismatched decoder, we characterize the error exponent the typical random codes (TRC) for the colored Gaussian channel, with emphasis on the range of low rates, where the TRC error exponent differs in value from the ordinary random coding error exponent. The error exponent formula, which is exponentially tight at some range of low rates, is presented as the maximum of a certain function with respect to one parameter only (in the spirit of Gallager's formulas) in the case of matched decoding, and two parameters in the case of mismatched decoding. Several aspects of the main results are discussed. These include: general properties, a parametric representation, critical rates, phase transitions, optimal input spectrum (water pouring), and comparison to the random coding exponent., Comment: 36 pages; submitted for publication

Consider the problem of guessing the realization of a random vector $\textbf{X}$ by repeatedly submitting queries (guesses) of the form "Is $\textbf{X}$ equal to $\textbf{x}$?" until an affirmative answer is obtained. In this setup, a key figure of merit is the number of queries required until the right vector is identified, a number that is termed the \emph{guesswork}. Typically, one wishes to devise a guessing strategy which minimizes a certain guesswork moment. In this work, we study a universal, decentralized scenario where the guesser does not know the distribution of $\textbf{X}$, and is not allowed to use a strategy which prepares a list of words to be guessed in advance, or even remember which words were already used. Such a scenario is useful, for example, if bots within a Botnet carry out a brute-force attack in order to guess a password or decrypt a message, yet cannot coordinate the guesses between them or even know how many bots actually participate in the attack. We devise universal decentralized guessing strategies, first, for memoryless sources, and then generalize them for finite-state sources. In each case, we derive the guessing exponent, and then prove its asymptotic optimality by deriving a compatible converse bound. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information. Finally, for all above scenarios, we design efficient algorithms in order to sample from the universal distributions, resulting in strategies which do not depend on the source distribution, are efficient to implement, and can be used asynchronously by multiple agents.

Biometric authentication systems, based on secret key generation, work as follows. In the enrollment stage, an individual provides a biometric signal that is mapped into a secret key and a helper message, the former being prepared to become available to the system at a later time (for authentication), and the latter is stored in a public database. When an authorized user requests authentication, claiming his/her identity as one of the subscribers, he/she has to provide a biometric signal again, and then the system, which retrieves also the helper message of the claimed subscriber, produces an estimate of the secret key, that is finally compared to the secret key of the claimed user. In case of a match, the authentication request is approved, otherwise, it is rejected. Evidently, there is an inherent tension between two desired, but conflicting, properties of the helper message encoder: on the one hand, the encoding should be informative enough concerning the identity of the real subscriber, in order to approve him/her in the authentication stage, but on the other hand, it should not be too informative, as otherwise, unauthorized imposters could easily fool the system and gain access. A good encoder should then trade off the two kinds of errors: the false reject (FR) error and the false accept (FA) error. In this work, we investigate trade-offs between the random coding FR error exponent and the best achievable FA error exponent. We compare two types of ensembles of codes: fixed-rate codes and variable-rate codes, and we show that the latter class of codes offers considerable improvement compared to the former. In doing this, we characterize the optimal rate functions for both types of codes. We also examine privacy leakage constraints for both fixed-rate codes and variable-rate codes., Comment: 23 pages, 1 figure, submitted for publication

We focus on the problem of modulating a parameter onto a power-limited signal transmitted over a discrete-time Gaussian channel and estimating this parameter at the receiver. Considering the well-known threshold effect in non-linear modulation systems, our approach is the following: instead of deriving upper and lower bounds on the total estimation error, which weigh both weak-noise errors and anomalous errors beyond the threshold, we separate the two kinds of errors. In particular, we derive upper and lower bounds on the best achievable trade-off between the exponential decay rate of the weak-noise expected error cost and the exponential decay rate of the probability of the anomalous error event, also referred to as the outage event. This outage event is left to be defined as part of the communication system design problem. Our achievability scheme, which is based on lattice codes, meets the lower bound at the high signal-to-noise (SNR) limit and for a certain range of trade-offs between the weak--noise error cost and the outage exponent., Comment: 19 pages; submitted for publication

We study a binary hypothesis testing problem in which a defender must decide whether or not a test sequence has been drawn from a given memoryless source $P_0$ whereas, an attacker strives to impede the correct detection. With respect to previous works, the adversarial setup addressed in this paper considers an attacker who is active under both hypotheses, namely, a fully active attacker, as opposed to a partially active attacker who is active under one hypothesis only. In the fully active setup, the attacker distorts sequences drawn both from $P_0$ and from an alternative memoryless source $P_1$, up to a certain distortion level, which is possibly different under the two hypotheses, in order to maximize the confusion in distinguishing between the two sources, i.e., to induce both false positive and false negative errors at the detector, also referred to as the defender. We model the defender-attacker interaction as a game and study two versions of this game, the Neyman-Pearson game and the Bayesian game. Our main result is in the characterization of an attack strategy that is asymptotically both dominant (i.e., optimal no matter what the defender's strategy is) and universal, i.e., independent of $P_0$ and $P_1$. From the analysis of the equilibrium payoff, we also derive the best achievable performance of the defender, by relaxing the requirement on the exponential decay rate of the false positive error probability in the Neyman--Pearson setup and the tradeoff between the error exponents in the Bayesian setup. Such analysis permits to characterize the conditions for the distinguishability of the two sources given the distortion levels.

This work contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the GLD exponents are at least as tight as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2017) and one of our ML-based expurgated exponents. By that, we actually prove the existence of hierarchical codebooks that achieve the best of the random coding exponent and the expurgated exponent simultaneously for both users.

We define the error exponent of the typical random code as the long-block limit of the negative normalized expectation of the logarithm of the error probability of the random code, as opposed to the traditional random coding error exponent, which is the limit of the negative normalized logarithm of the expectation of the error probability. For the ensemble of uniformly randomly drawn fixed composition codes, we provide exact error exponents of typical random codes for a general discrete memoryless channel (DMC) and a wide class of (stochastic) decoders, collectively referred to as the generalized likelihood decoder (GLD). This ensemble of fixed composition codes is shown to be no worse than any other ensemble of independent codewords that are drawn under a permutation--invariant distribution (e.g., i.i.d. codewords). We also present relationships between the error exponent of the typical random code and the ordinary random coding error exponent, as well as the expurgated exponent for the GLD. Finally, we demonstrate that our analysis technique is applicable also to more general communication scenarios, such as list decoding (for fixed-size lists) as well as decoding with an erasure/list option in Forney's sense., Comment: 26 pages, submitted for publication

We study the ensemble performance of biometric authentication systems, based on secret key generation, which work as follows. In the enrollment stage, an individual provides a biometric signal that is mapped into a secret key and a helper message, the former being prepared to become available to the system at a later time (for authentication), and the latter is stored in a public database. When an authorized user requests authentication, claiming his/her identity as one of the subscribers, s/he has to provide a biometric signal again, and then the system, which retrieves also the helper message of the claimed subscriber, produces an estimate of the secret key, that is finally compared to the secret key of the claimed user. In case of a match, the authentication request is approved, otherwise, it is rejected.Referring to an ensemble of systems based on Slepian-Wolf binning, we provide a detailed analysis of the false-reject and false-accept probabilities, for a wide class of stochastic decoders. We also comment on the security for the typical code in the ensemble., Comment: 26 pages; submitted for publication

This purpose of this letter is to handle a gap that was found in the proof of Theorem 2 in the paper "The generalized stochastic likelihood decoder: random coding and expurgated bounds.", Comment: 7 pages. Submitted for publication

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given metric decoding rule. Specifically, it is assumed that the mismatched decoder has an incorrect assumption on the impulse response function. The mismatch capacity is the highest achievable rate for a given decoding rule. Existing lower bounds to the mismatch capacity for channels and decoding metrics with memory (as in our model) are presented only in the form of multi-letter expressions that have not been calculated in practice. Consequently, they provide little insight on the mismatch problem. In this paper, we derive computable single-letter lower bounds to the mismatch capacity, and discuss some implications of our results. Our achievable rates are based on two ensembles, the ensemble of codewords generated by an autoregressive process, and the ensemble of codewords drawn uniformly over a "type class" of real-valued sequences. Computation of our achievable rates demonstrates non-trivial behavior of the achievable rates as a function of the mismatched parameters. As a simple application of our technique, we derive also the random coding exponent associated with a mismatched decoder which assumes that there is no ISI at all. Finally, we compare our results with universal decoders which are designed outside the true class of channels that we consider in this paper.

Considering the problem of risk-sensitive parameter estimation, we propose a fairly wide family of lower bounds on the exponential moments of the quadratic error, both in the Bayesian and the non--Bayesian regime. This family of bounds, which is based on a change of measures, offers considerable freedom in the choice of the reference measure, and our efforts are devoted to explore this freedom to a certain extent. Our focus is mostly on signal models that are relevant to communication problems, namely, models of a parameter-dependent signal (modulated signal) corrupted by additive white Gaussian noise, but the methodology proposed is also applicable to other types of parametric families, such as models of linear systems driven by random input signals (white noise, in most cases), and others. In addition to the well known motivations of the risk-sensitive cost function (i.e., the exponential quadratic cost function), which is most notably, the robustness to model uncertainty, we also view this cost function as a tool for studying fundamental limits concerning the tail behavior of the estimation error. Another interesting aspect, that we demonstrate in a certain parametric model, is that the risk-sensitive cost function may be subjected to phase transitions, owing to some analogies with statistical mechanics., Comment: 28 pages; 4 figures; submitted for publication

This work contains two main contributions concerning the asymmetric broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information (MMI) universal decoder, which achieve the corresponding random coding exponents of optimal decoding. In addition, we introduce some lower bounds, which involve optimization over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel show improvements over previously derived error exponents for the same model.

We consider a system model of a general finite-state machine (ratchet) that simultaneously interacts with three kinds of reservoirs: a heat reservoir, a work reservoir, and an information reservoir, the latter being taken to be a running digital tape whose symbols interact sequentially with the machine. As has been shown in earlier work, this finite-state machine can act as a demon (with memory), which creates a net flow of energy from the heat reservoir into the work reservoir (thus extracting useful work) at the price of increasing the entropy of the information reservoir. Under very few assumptions, we propose a simple derivation of a family of inequalities that relate the work extraction with the entropy production. These inequalities can be seen as either upper bounds on the extractable work or as lower bounds on the entropy production, depending on the point of view. Many of these bounds are relatively easy to calculate and they are tight in the sense that equality can be approached arbitrarily closely. In their basic forms, these inequalities are applicable to any finite number of cycles (and not only asymptotically), and for a general input information sequence (possibly correlated), which is not necessarily assumed even stationary. Several known results are obtained as special cases., Comment: 18 pages, 2 figures, submitted for publication

Motivated by applications of biometric identification and content identification systems, we consider the problem of random coding for channels, where each codeword undergoes lossy compression (vector quantization), and where the decoder bases its decision only on the compressed codewords and the channel output, which is in turn, the channel's response to the transmission of an original codeword, before compression. For memoryless sources and memoryless channels with finite alphabets, we propose a new universal decoder and analyze its error exponent, which improves on an earlier result by Dasarathy and Draper (2011), who used the classic maximum mutual information (MMI) universal decoder. Further, we show that our universal decoder provides the same error exponent as that of the optimal, maximum likelihood (ML) decoder, at least as long as all single-letter transition probabilities of the channel are positive. We conjecture that the same argument remains true even without this positivity condition., Comment: 31 pages; submitted for publication