The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. When the source distribution is unknown, a universal achievability result is obtained with an explicit “price for universality” term. This is based on a fine combinatorial estimate on the number of sequences with small empirical entropy, which might be of independent interest. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the excess-rate probability, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, morepragmaticrate, determined via the inverse error exponent function and the blocklength.

The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the rate, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, more pragmatic rate, determined via the inverse error exponent function and the blocklength.

Directed information has been used in information theory and in statistics as a functional that quantifies causal influences present in signals and empirical data. In this work, the causally conditional directed information (CCDI) rate is identified as a statistic for detecting causal relationships between discrete time series, in the presence of potential confounders. A hypothesis test is introduced for identifying the temporally causal influence of$(x_{n})$on$(y_{\mathrm{Y}})$, causally conditioned on a possibly confounding third time series$(z_{n})$. Under natural assumptions it is shown that the absence of temporally causal influence is equivalent to the CCDI rate being zero. The plug-in estimator for this functional is identified with the log-likelihood ratio test statistic for the desired test. This statistic is shown to be asymptotically normal under the alternative hypothesis and asymptotically$\chi^{2}$distributed under the null, facilitating the computation of p-values from empirical data. The resulting hypothesis test is employed in the analysis of spike train data recorded from neurons in the V4 and FEF brain regions of behaving animals during a visual attention task. The test results are seen to identify interesting and biologically relevant information.