ABSTRACT
The problem of testing random number generators is considered and a new method for comparing the power of different statistical tests is proposed. It is based on the definitions of random sequence developed in the framework of algorithmic information theory and allows comparing the power of different tests in some cases when the available methods of mathematical statistics do not distinguish between tests. In particular, it is shown that tests based on data compression methods using dictionaries should be included in test batteries.
ABSTRACT
We consider the problem of constructing an unconditionally secure cipher with a short key for the case where the probability distribution of encrypted messages is unknown. Note that unconditional security means that an adversary with no computational constraints can only obtain a negligible amount of information ("leakage") about an encrypted message (without knowing the key). Here, we consider the case of a priori (partially) unknown message source statistics. More specifically, the message source probability distribution belongs to a given family of distributions. We propose an unconditionally secure cipher for this case. As an example, one can consider constructing a single cipher for texts written in any of the languages of the European Union. That is, the message to be encrypted could be written in any of these languages.
ABSTRACT
In recent years, the task of translating from one language to another has attracted wide attention from researchers due to numerous practical uses, ranging from the translation of various texts and speeches, including the so-called "machine" translation, to the dubbing of films and numerous other video materials. To study this problem, we propose to use the information-theoretic method for assessing the quality of translations. We based our approach on the classification of sources of text variability proposed by A.N. Kolmogorov: information content, form, and unconscious author's style. It is clear that the unconscious "author's" style is influenced by the translator. So researchers need special methods to determine how accurately the author's style is conveyed, because it, in a sense, determines the quality of the translation. In this paper, we propose a method that allows us to estimate the quality of translation from different translators. The method is used to study translations of classical English-language works into Russian and, conversely, Russian classics into English. We successfully used this method to determine the attribution of literary texts.
ABSTRACT
We consider the problems of the authorship of literary texts in the framework of the quantitative study of literature. This article proposes a methodology for authorship attribution of literary texts based on the use of data compressors. Unlike other methods, the suggested one gives a possibility to make statistically verified results. This method is used to solve two problems of attribution in Russian literature.
ABSTRACT
The problem of constructing effective statistical tests for random number generators (RNG) is considered. Currently, there are hundreds of RNG statistical tests that are often combined into so-called batteries, each containing from a dozen to more than one hundred tests. When a battery test is used, it is applied to a sequence generated by the RNG, and the calculation time is determined by the length of the sequence and the number of tests. Generally speaking, the longer is the sequence, the smaller are the deviations from randomness that can be found by a specific test. Thus, when a battery is applied, on the one hand, the "better" are the tests in the battery, the more chances there are to reject a "bad" RNG. On the other hand, the larger is the battery, the less time it can spend on each test and, therefore, the shorter is the test sequence. In turn, this reduces the ability to find small deviations from randomness. To reduce this trade-off, we propose an adaptive way to use batteries (and other sets) of tests, which requires less time but, in a certain sense, preserves the power of the original battery. We call this method time-adaptive battery of tests. The suggested method is based on the theorem which describes asymptotic properties of the so-called p-values of tests. Namely, the theorem claims that, if the RNG can be modeled by a stationary ergodic source, the value - l o g π ( x 1 x 2 x n ) / n goes to 1 - h when n grows, where x 1 x 2 is the sequence, π ( ) is the p-value of the most powerful test, and h is the limit Shannon entropy of the source.
ABSTRACT
Using the data-compression method we revealed a similarity between hunting behaviors of the common shrew, which is insectivorous, and several rodent species with different types of diet. Seven rodent species studied displayed succinct, highly predictable hunting stereotypes, in which it was easy for the data compressor to find regularities. The generalist Norway rat, with its changeable manipulation of prey and less predictable transitions between stereotype elements, significantly differs from other species. The levels of complexities of hunting stereotypes in young and adult rats are similar, and both groups had no prior experience with the prey, so one can assume that it is not learning, but rather the specificity of the organization of the stereotype that is responsible for the nature of the hunting behavior in rats. We speculate that rodents possess different types of hunting behaviors, one of which is based on a succinct insectivorous standard, and another type, perhaps characteristic of generalists, which is less ordered and is characterized by poorly predictable transitions between elements. We suggest that the data-compression method may well be more broadly applicable to behavioral analysis.
