АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК МЕТОДОМ РЕШЕНИЯ УРАВНЕНИЯ ПЕРВОЙ КРАТНОСТИ ТИПОВ

Аннотация

Рассматривается алгоритмическая сложность расчета точных распределений ве- роятностей значений статистик и их точных приближений методом решения уравнения первой кратности. В качестве точных приближений распределений вероятностей значе- ний статистик рассматриваются их Δточные распределения, отличающиеся от точных распределений не более чем на заранее заданную, сколь угодно малую величину Δ. Показыва- ется, что основой метода расчета точных распределений вероятностей значений стати- стик является перечисление элементов области поиска решений линейного уравнения кратности типов, составленной из векторов кратности типов, каждый элемент которо- го представляет собой число вхождений элементов определенного типа (какого-либо знака алфавита) в рассматриваемую выборку. Одновременно показывается, что для расчета точных приближений распределения вероятностей значений статистик применяется ме- тод ограничения области поиска решений. Приводится выражение определяющее алго- ритмическую сложность вычисления точных распределений методом решения уравнения первой кратности. Приведенное выражение является конечным и позволяет для каждого значения мощности алфавита определить максимальный объем выборки, для которой при использовании ограниченного вычислительного ресурса методом решения уравнения первой кратности могут быть рассчитаны точные распределения. Определена область пара- метров, представляемых объемом выборок и мощностью алфавита, для которых при ог- раниченном вычислительном ресурсе могут быть рассчитаны точные распределения. Для оценки алгоритмической сложности расчета точных приближений распределений приво- дится, впервые полученное, выражение для числа решений уравнения первой кратности с ограничением на значения координат векторов решений. Приводится выражение определяющее алгоритмическую сложность вычисления точных приближений методом решения уравнения первой кратности с ограничением на значения координат векторов решений. В качестве параметра ограничения координат векторов решений используется значение статистики максимальной частоты, вероятность превышения которого меньше заранее заданной, сколь угодно малой величины Δ, что позволяет рассчитывать точные прибли- жения распределений, отличающиеся от их точных распределений не более чем на выбран- ную величину Δ. Приведенное выражение является конечным и позволяет для каждого зна- чения алфавита определить максимальный объем выборки, для которой при использовании ограниченного вычислительного ресурса методом решения уравнения первой кратности при ограничениях задаваемых с помощью величины Δ могут быть рассчитаны точные приближения. Приводятся результаты вычислений максимальных объемов выборок для которых могут быть рассчитаны точные приближения. Показывается, что алгоритми- ческая сложность расчета точных распределений на много порядков превосходит слож- ность расчета их точных приближений. Показано, что применение метода первой крат- ности для расчета точных приближений позволяет при одинаковых значениях мощности алфавита увеличить, по сравнению с расчетом точных распределений, объём выборок в два и более раз.