ALGORITHMIC COMPLEXITY OF CALCULATING EXACT APPROXIMATIONS OF PROBABILITY DISTRIBUTIONS OF STATISTICAL VALUES BY SOLVING THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES

Abstract

We consider the algorithmic complexity of calculating the exact probability distributions of statistical values and their exact approximations by solving the first multiplicity equation. As exact approximations of probability distributions of statistical values, we consider their Δ−exact distributions that differ from the exact distributions by no more than a predetermined, arbitrarily small valueΔ. It is shown that the basis of the method for calculating the exact probability distributions of statistical values is the enumeration of elements of the search area for solutions to a linear equation of multiplicity of types, composed of vectors of multiplicity of types, each element of which is the number of occurrences of elements of a certain type (any sign of the alphabet) in the sample under consideration. At the same time, it is shown that the method of limiting the search area for solutions is used to calculate exact approximations of the probability distribution of statistical values. An expression is given that defines the algorithmic complexity of calculating exact distributions by solving the first multiplicity equation. The given expression is finite and allows for each value of the alphabet power to determine the maximum sample size for which, using a limited computational resource, exact distributions can be calculated by solving the first multiplicity equation. The range of parameters represented by the sample size and alphabet power for which exact distributions can be calculated with a limited computing resource is defined. To estimate the algorithmic complexity of calculating exact approximations of distributions, we present an expression for the first time obtained for the number of solutions to the equation of the first multiplicity with a restriction on the coordinate values of the solution vectors. An expression is given that defines the algorithmic complexity of calculating exact approximations by solving the first multiplicity equation with a restriction on the coordinate values of the solution vectors. As a parameter for limiting the coordinates of solution vectors, the maximum frequency statistic value is used, the probability of exceeding it is less than a pre-set, arbitrarily small valueΔ, which allows calculating exact approximations of distributions that differ from their exact distributions by no more than the selected value Δ. The given expression is finite and allows for each value of the alphabet to determine the maximum sample size for which, when using a limited computational resource, exact approximations can be calculated by solving the equation of the first multiplicity under the restrictions set using the valueΔ. The results of calculations of the maximum sample volumes for which exact approximations can be calculated are presented. It is shown that the algorithmiccomplexity of calculating exact distributions exceeds the complexity of calculating their exact approximations by many orders of magnitude. It is shown that the use of the first multiplicity method for calculating exact approximations allows for the same values of the alphabet power to increase the sample volume by two or more times compared to the calculation of exact distributions.