Search

Search Results

• CALCULATION OF THE NUMBER OF SOLUTIONS TO THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES UNDER RESTRICTIONS ON THE FREQUENCY OF OCCURRENCE OF ALPHABET CHARACTERS

  A.K. Melnikov

  2021-02-25

  Abstract ▼

  The article considers the number of solutions to the equation of the first 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. The equation
  of the first multiplicity of types relates the number of occurrences of elements of all types in
  the sample under consideration and the volume of this sample. The main attention is paid to the
  conclusion and proof of the correctness of the expression that determines the number of nonnegative
  integer solutions of the equation of the first multiplicity of types under conditions of restrictions
  on the frequency of occurrence of alphabet characters. The solution of the equation ofthe first multiplicity of types is the basis for calculating exact approximations of the probabilities
  of statistical values by the first multiplicity method, where the exact approximations are Δexact
  distributions that differ from the exact distributions by no more than a predetermined, arbitrarily
  small value Δ. The value that expresses the number of solutions to the equation of the first multiplicity
  of types is one of the values that determine the algorithmic complexity of the method of the
  first multiplicity, without knowing the value of which it is impossible to determine the parameters
  of samples for which, under restrictions on the computational resource, exact approximations of
  distributions can be calculated. Also, the value expressing the number of solutions to the equation
  of the first multiplicity of types is used in the method of the first multiplicity to limit the search area
  for solutions to the equation. The number of solutions to the equation of the first multiplicity is
  considered under conditions of restriction on the maximum value of the elements of the multiplicity
  vector, and the case is considered when one or more elements of the alphabet may be missing in
  the sample. First obtained the expression that defines the number of nonnegative integer solutions
  to equations of the first multiplicity of types in terms of restrictions on the values of the frequencies
  of occurrence of signs and the possibility of absence of one or more characters of the alphabet in
  the sample reviewed. Analytical expressions are obtained that allow calculating the number of
  integer nonnegative solutions of the equation of the first multiplicity of types for any values of the
  alphabet power, the sample size, and the limit on the maximum frequency of occurrence of alphabet
  characters. The form of the obtained expression allows you to use it when studying the algorithmic
  complexity of calculating exact approximations of probability distributions of statistical
  values with a pre-specified accuracy Δ.

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

  A.K. Melnikov

  2021-02-25

  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.