Łukasz Dębowski

We analyze long-range dependence (LRD) for word time series, understood as a slower than exponential decay of the two-point Shannon mutual information. We achieve this by examining the decay of the cosine correlation, a proxy object defined in terms of the cosine similarity between word2vec embeddings of two words, computed by an analogy to the Pearson correlation. By the Pinsker inequality, the squared cosine correlation between two random vectors lower bounds the mutual information between them. Using the Standardized Project Gutenberg Corpus, we find that the cosine correlation between word2vec embeddings exhibits a readily visible stretched exponential decay for lags roughly up to 1000 words, thus corroborating the presence of LRD. By contrast, for the Human vs. LLM Text Corpus entailing texts generated by large language models, there is no systematic signal of LRD. Our findings may support the need for novel memory-rich architectures in large language models that exceed not only hidden Markov models but also Transformers.

We analyze long-range dependence (LRD) for word time series, understood as a slower than exponential decay of the two-point Shannon mutual information. We do it by examining the decay of the cosine correlation, a proxy object defined in terms of the cosine similarity between word2vec embeddings of two words, computed by an analogy to the Pearson correlation. By the Pinsker inequality, the squared cosine correlation between two random vectors lower bounds the mutual information between them. Using the Standardized Project Gutenberg Corpus, we find that the cosine correlation between word2vec embeddings exhibits a readily visible stretched exponential decay for lags roughly up to 1000 words, thus corroborating the presence of LRD. By contrast, for the Human vs. LLM Text Corpus entailing texts generated by large language models, there is no systematic signal of LRD. Our findings may support the need for novel memory-rich architectures in large language models that exceed not only hidden Markov models but also Transformers.

The reviewed article is an account of generalized entropic inequalities, a topic investigated by the author and his collaborators since the 1990s. This paper is a popular short account of the topic, whereas the corresponding hard results have already...

Motivated by problems of statistical language modeling, we consider probability measures on infinite sequences over two countable alphabets of a different cardinality, such as letters and words. We introduce an invertible mapping between such measures, called the normalized transport, that preserves both stationarity and ergodicity. The normalized transport applies so called self-avoiding codes that generalize comma-separated codes and specialize bijective stationary codes. The normalized transport is also connected to the usual measure transport via underlying asymptotically mean stationary measures. It preserves the ergodic decomposition. The normalized transport and self-avoiding codes arise in the problem of successive recurrence times. In particular, we show that successive recurrence times are ergodic for an ergodic measure, which strengthens a result by Chen Moy from 1959. We also relate the entropy rates of processes linked by the normalized transport.

By an analogy to the duality between the recurrence time and the longest match length, we introduce a quantity dual to the maximal repetition length, which we call the repetition time. Extending prior results, we sandwich the repetition time in terms of unconditional and conditional min-entropies. The upper bound holds if the mixing rate ϕ(n) is summable, whereas the lower bound only assumes stationarity. Our reasoning makes a repeated use of dualities between so-called times and so-called counts that generalize the duality of the recurrence time and the longest match length. We also discuss the analogy of these results with the Wyner-Ziv/Ornstein-Weiss theorem, which sandwiches the recurrence time in terms of Shannon entropies.

The article introduces corrections to Zipf's and Heaps' laws based on systematic models of the proportion of hapaxes, i.e., words that occur once. The derivation rests on two assumptions: The first one is the standard urn model which predicts that marginal frequency distributions for shorter texts look as if word tokens were sampled blindly from a given longer text. The second assumption posits that the hapax rate is a simple function of the text length. Four such functions are discussed: the constant model, the Davis model, the linear model, and the logistic model. It is shown that the logistic model yields the best fit.

In the article "Universal Densities Exist for Every Finite Reference Measure" (IEEE Trans. Inform. Theory, vol. 69, no. 8, pp. 5277--5288, 2023) we neglected to mention relevant contributions of Boris Ryabko. We cited a source by him that contains a construction of the universal density that we claimed to be our own invention without checking the source after drafting the article. Our article was motivated by a preprint by Feutrill and Roughan, about which we had learned when reviewing the PhD thesis by Andrew Feutrill. Whereas we were not allowed to contact Feutrill and Roughan besides the review form, we developed some ideas of theirs further, ignoring that we stepped into the area previously researched by Ryabko. Our published results exceed those by Ryabko but the article should have been refocused to report Ryabko's contributions. In this note, we detail our citation mistakes.

As it is known, universal codes, which estimate the entropy rate consistently, exist for stationary ergodic sources over finite alphabets but not over countably infinite ones. We generalize universal coding as the problem of universal densities with respect to a fixed reference measure on a countably generated measurable space. We show that universal densities, which estimate the differential entropy rate consistently, exist for finite reference measures. Thus finite alphabets are not necessary in some sense. To exhibit a universal density, we adapt the nonparametric differential (NPD) entropy rate estimator by Feutrill and Roughan. Our modification is analogous to Ryabko’s modification of prediction by partial matching (PPM) by Cleary and Witten. Whereas Ryabko considered a mixture over Markov orders, we consider a mixture over quantization levels. Moreover, we demonstrate that any universal density induces a strongly consistent Cesàro mean estimator of conditional density given an infinite past. This yields a universal predictor with the $0-1$ loss for a countable alphabet. Finally, we specialize universal densities to processes over natural numbers and on the real line. We derive sufficient conditions for consistent estimation of the entropy rate with respect to infinite reference measures in these domains.