Характеристики и анализ графов ближайших соседей, порожденных случайными матрицами

А. А. Кислицын

Институт прикладной математики им. М.В. Келдыша РАН

Аннотация: Представлены результаты численного моделирования графов ближайших соседей, порожденных случайными матрицами расстояний. Рассмотрены как симметричные, так и несимметричные случайные матрицы. Исследованы эмпирические распределения графов по числу связных фрагментов, фрагментов по числу вершин, вершин по степеням. Полученные статистики рассматриваются как бенчмарк для нового подхода к оценке вероятности зависимости выборочных данных. Поскольку бенчмарк не зависит от функции распределения элементов случайных матриц, по является возможность табулировать непараметрический статистический критерий зависимости случайных элементов выборки по вероятности реализации структуры порожденного этой выборкой графа ближайших соседей. Найденные статистики позволяют также сравнивать различные генераторы псевдослучайных чисел и не которые естественные генераторы. Приведен пример с анализом графов, порожденных десятичным представлением числа $\pi$, и показано, что первые 50 миллиардов цифр этой записи не являются независимыми случайными величинами.

Ключевые слова: случайная матрица, граф ближайших соседей, распределение структур, критерий независимости случайных величин, десятичное представление числа $\pi$.

Поступила в редакцию: 26.02.2024
Исправленный вариант: 08.04.2024
Принята в печать: 13.05.2024

DOI: 10.20948/mm-2024-06-01