Распределение расстояний

[Alex_J]

(Оффтоп)

Продолжаем развлекаться.

Задался вопросом - а какова доля пар точек на каждом конкретном расстоянии внутри многообразия?
Интегралы в явном виде брать долго, сложно и муторно в большинстве случаев кроме элементарных (отрезок и т.д.)
Поэтому промонтекарлил задачу, вот некоторые результаты.
Ещё раз: это распределения расстояний между точками того или иного многообразия. На картинках даны названия фигур, кривых и т.д. Многообразия есть и несвязные.
Как делаю: равномерно бросаю N точек на многообразие и затем считаю попарно расстояния.
Есть странности: например, почему у квадрата кривая исходит из (0,0) ? Как думаете, будет ли различие в результатах, если бросать точки попарно на каждую единицу выборки?
Объяснение исхода из нуля может быть таково: просто в силу геометрии ближе к данной точке площадь (а значит и мощность множества точек) меньше, чем дальше. Поэтому при малых $r$ с расстоянием растёт и вероятность упасть следующей точке, ну и количество точек выше.
Почему вблизи нуля распределение линейно? $dS=\pi r dr$, т.е. число точек на окружности радиуса $r$ пропорционально $r$.
Но почему вблизи нуля для кольца нулевой толщины и границы квадрата значение - не нуль?
Потому что на одномерном множестве число точек на малом расстоянии $\Delta r$ не менее 2 (либо 1 для граничной точки, но она просто не видна в распределении).











Интересности:

Если наложить требование: отрезок, соединяющий две точки, целиком лежит внутри многообразия, то нужно считать по-другому, зато и результаты будут другие, например на кольце нулевой толщины для $r=0$ будет 2 точки, далее везде 0.

Несвязные области просто суммируются по своим внутренним расстояниям, "межобластные" не берём.

Если представить многообразие как карту региона с равномерно распределенными точками отправки и доставки грузов, то можем узнать наиболее вероятное расстояние перевозок, ну и другие параметры. Можно добавлять весовые функции в зависимости от... много от чего.

Теперь посмотрим многомерные фигуры, сравним результаты.




С увеличением размерности гиперкуб даёт всё более близкое к похожему на нормальное распределение.
Возможно, это поможет лучше представить многомерные пространства.

Дискретные случаи - наборы отдельных точек - показывать не буду, там вполне очевидные полосы на конкретных расстояниях. Впрочем, эти полосы могут иметь отношение к кристаллографии.

Кто возьмётся исследовать фракталы?
Кто объяснит скачок на картинке для границы квадрата?

Заказывайте многообразия.

-- 17.04.2013, 18:21 --


(т.е. дальние торцы параллелепипеда $a$ x $a$ x $1.414a$ со всеми прямыми углаи)

[Xaositect]

Alex_J в сообщении #711628 писал(а):

Кто объяснит скачок на картинке для границы квадрата?

Это же просто. Квадрат делится на три случая - одна и та же сторона(четверть случаев), смежные (половина) и противоположные(четверть). Случай противоположных сторон сосредоточен на отрезке [сторона, диагональ], причем плотность вероятности на левом конце ненулевая и убывает к нулю.
Квадрат вполне руками считается, муторно, правда. Да и все остальное скорее всего тоже считается, с компьютером уж точно.

[arseniiv]

Было бы вообще замечательно, если бы на графиках были оценки дисперсии отложены.

Приближение к нормальному распределению у гиперкубов увеличивающейся размерности, кстати, легко объяснимо с помощью ЦПТ. Только получается приближение к корню из нормально распределённой величины.

(Надеюсь, с применимостью ЦПТ не напортачил…)

[Alex_J]

Выборка 10 млн., 200 баров гистограммы, нормировка значений по ординате - по объёму выборки. Единица по оси абсцисс отвечает максимальному из встретившихся расстояний (точная верхняя грань, по сути). Нормировка позволяет не привязываться к абсолютным размерам фигурыи иметь дело только с её относительными размерами. Своеобразная аналогия с форм-фактором, только в виде гистограммы.

arseniiv в сообщении #711698 писал(а):

Было бы вообще замечательно, если бы на графиках были оценки дисперсии отложены.

Шумок немного виден (например левая часть графика для границы квадрата), вот примерно такой разброс и есть.

Xaositect в сообщении #711695 писал(а):

Квадрат вполне руками считается, муторно, правда. Да и все остальное скорее всего тоже считается, с компьютером уж точно.

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

Ну а многомерность обсчитывать это просто жесть

arseniiv в сообщении #711698 писал(а):

Приближение к нормальному распределению у гиперкубов увеличивающейся размерности, кстати, легко объяснимо с помощью ЦПТ.

А как посчитать сигму исходя из сути задачи?

[arseniiv]

Alex_J в сообщении #711732 писал(а):

А как посчитать сигму исходя из сути задачи?

Я лучше не скажу, а то напутаю, но вроде бы ничего не мешает взять оценку сигмы из ЦПТ и потом вычислить сигму «корненормального» распределения по этой?

[_Ivana]

(Оффтоп)

Спасибо, интересно, и картинки красочные

[Alex_J]

Интересно ещё вот что. Я получал гистограммы по двум алгоритмам и получал одинаковый результат: сначала накидал точки а потом прошёл все пары; и кидал попарно каждый раз новые точки.
А в каких ситуациях алгоритмы дали бы разные результаты? Можно ли доказать, что эти два алгоритма идентичны?
Различия могут вылезти при малых выборках, но как бы сконструировать задачу, чтобы результаты принципиально отличались?

[gris]

Результаты не будут отличаться при достаточном количестве испытаний, а время работы может отличаться сильно. Если попасть точкой в многообразие просто, то проще кидать каждый раз по точке и находить расстояние до предыдущей. А если попасть трудно, или на проверку попадания тратится много времени, то лучше накидать побольше и использовать все пары.

[Aritaborian]

У Эрика есть статьи на эту тему. См. в разделе Random Point Picking. К рассматриваемой задаче относятся статьи типа Square Line Picking etc.
А вообще тема интересная.

[Aritaborian]

Alex_J, в чём графики рисовали?

[Alex_J]

Aritaborian
в онлайн сервисе. Не помню какой, гугл подскажет ))