AZAndrei Mikhailovich Zubkov

Andrei Mikhailovich Zubkov

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Andrei Mikhailovich Zubkov has a total of 81 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • О статистической проверке сложных гипотез об $s$-мерном равномерном распределении вероятностей двоичных последовательностей

    by Yurii Semenovich Kharin, Andrei Mikhailovich Zubkov

    Рассматривается задача построения и анализа критерия статистической проверки сложных гипотез об $s$-мерном равномерном распределении вероятностей двоичных последовательностей. Предложена естественная для приложений модель сложной нулевой гипотезы $H_0^{\varepsilon}$, фиксирующая максимально допустимый уровень отклонений $\varepsilon$ от равномерного распределения. Разработан подход к построению критерия проверки сложных гипотез $H_0^{\varepsilon}$, $\overline{H_0^{\varepsilon}}$, основанный на асимптотическом разложении (по $\varepsilon\rightarrow 0$) логарифмической статистики отношения правдоподобия. Построен состоятельный критерий с заданным асимптотическим уровнем значимости и исследована мощность теоретически и в компьютерных экспериментах. Описан также критерий, основанный на статистике Пирсона.


  • Статистические критерии равномерности распределения и независимости векторов, использующие попарные расстояния

    by Andrei Mikhailovich Zubkov

    Задача проверки статистической гипотезы о равномерности распределения и независимости случайных векторов представляет как теоретический, так и практический интерес. В работах ряда авторов предлагались различные подходы к ее решению. В ряде критериев проверки гипотез о равновероятности распределения случайных векторов в области многомерного пространства или об их независимости в качестве статистик используются функции от попарных расстояний между точками выборки. В настоящей работе содержится краткий обзор таких критериев и предлагается еще один критерий проверки гипотезы о равномерности распределения, основанный на попарных расстояниях.

  • Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences

    by Andrei Mikhailovich Zubkov, Aleksandr Aleksandrovich Serov

    Представлены и обсуждаются результаты эмпирического тестирования возможности обнаружения длинных повторов в двоичных последовательностях набором статистических тестов NIST. Набор детерминированных двоичных последовательностей, которые не отклоняются пакетом NIST, искажается детерминированным образом. Для того чтобы повредить двоичную последовательность, выбирается несколько ее подстрок фиксированной длины и каждая подстрока дублируется в случайном месте последовательности. Длина повторяющихся подстрок была выбрана значительно большей типичной длины самой длинной повторяющейся подстроки. Если количество повторяющихся подстрок в поврежденной последовательности невелико, то пакет NIST не отклоняет такие неслучайные криптографически слабые двоичные последовательности. Описан алгоритм, реализующий поиск самого длинного повторения подстрок в двоичной последовательности длины $n$. Этот алгоритм основан на дереве суффиксов, и его временная и пространственная сложности имеют порядок $O(n)$.


  • Вероятность принадлежности нескольких вершин одной связной компоненте случайного равновероятного отображения

    by Andrei Mikhailovich Zubkov, P V Khalipov

    Найдены предельные значения вероятности того, что $k$ элементов принадлежат одной и той же связной компоненте случайного равновероятного отображения конечного множества (при стремлении числа элементов этого множества к бесконечности).

  • Энтропия как характеристика качества случайных последовательностей

    by Andrei Mikhailovich Zubkov

    Обсуждаются вопросы, связанные со смыслами, в которых термин «энтропия» используется в различных областях (статистической физике, теории информации, теории динамических систем), и применениями этого понятия как характеристики независимости и равновероятности символов конечного алфавита. Главная цель - показать на этом примере, что корректная интерпретация результатов применения статистических критериев должна содержать фактически используемые априорные предположения о вероятностных моделях анализируемых последовательностей. Приведен пример последовательностей с энтропией, близкой к максимально возможной, но неудовлетворительных с точки зрения криптографических применений.


  • A natural approach to the experimental study of dependence between statistical tests

    by Andrei Mikhailovich Zubkov, Aleksandr Aleksandrovich Serov

    Для проверки гипотезы о независимости критериев в пакете NIST для 10000 отрезков двоичных последовательностей вычислялось число $\nu$ критериев, отклонявших гипотезу о том, что это отрезок равновероятной последовательности Бернулли. Для независимых критериев с одной и той же вероятностью ошибки число $\nu$ должно иметь биномиальное распределение. Оказалось, что совокупности из 14 и из 162 критериев пакета NIST не удовлетворяют этому условию, но 11 критериев из 14 удовлетворяют. Показано также, что некоторые последовательности, состоящие из чередующихся отрезков двух линейных рекуррент, не отклоняются критериями пакета NIST.


  • Вычисление распределений статистик с помощью цепей Маркова

    by Andrei Mikhailovich Zubkov, Marina Viktorovna Filina

    Описан подход к построению вычислительно эффективных алгоритмов точного вычисления распределений статистик с помощью цепей Маркова. В качестве примеров рассмотрены статистика Пирсона, число пустых ячеек при случайных размещениях частиц, статистика Колмогорова - Смирнова. Указаны возможности распространения подхода, в частности, на вычисление совместных распределений статистик.


  • Памяти Игоря Александровича Круглова

    by Gennadii Vasil'Evich Balakin, S M Buravlev, Sergei Pavlovich Gorshkov, Andrei Mikhailovich Zubkov, Grigorii Ivanovich Ivchenko, A V Knyazev, Andrei Petrovich Kovalenko, Oleg Alekseevich Kozlitin, Viktor Alekseevich Kopyttsev, Alexander Vladimirovich Lapshin, et al.

  • Оценки расстояния по вариации между распределениями двух наборов независимых случайных величин

    by Andrei Mikhailovich Zubkov

    Получены явные нижние и верхние оценки расстояний по вариации между распределениями наборов $(X_1,\ldots,X_n)$ и $(Y_1,\ldots,Y_n)$ независимых, но не обязательно одинаково распределенных (внутри каждого набора) случайных величин в терминах расстояний по вариации $\rho_k$ между распределениями отдельных компонент $X_k$ и $Y_k$, $k=1,\ldots,n$. Оценки для случая однородных выборок были опубликованы в этом журнале в 2018 г. Качественно полученные в настоящей работе оценки согласуются с оценками для однородных случаев.


  • Почти линейные участки графиков функций

    by Andrei Mikhailovich Zubkov, Oleg Pavlovich Orlov

    Пусть $f\colon \mathbb{R} \to \mathbb{R}$ - такая функция, что ее график $\{(x, f(x))\}_{x \in \mathbb{R}}$ в $\mathbb{R}^2$ является спрямляемой кривой. Доказано, что тогда для любых $L < \infty$ и $\varepsilon > 0$ существуют такие точки $A = (a, f(a))$ и $B = (b, f(b))$, что расстояние между $A$ и $B$ больше $L$, а расстояния от всех точек $(x, f(x))$, $a \leqslant x \leqslant b$, до отрезка $AB$ не больше $\varepsilon |AB|$. Приведен пример плоской спрямляемой кривой, для которой это утверждение неверно. Показано, что для покоординатно не убывающей последовательности целых точек плоскости с ограниченными расстояниями между соседними точками при любом $r < \infty$ существует прямая, содержащая не меньше $r$ точек этой последовательности. Библиография: 2 названия.