Эта проблема связана с исследованиями моей лаборатории в области робототехники:
Случайным образом нарисуйте чисел из набора без замены и отсортируйте числа в порядке возрастания. .
Из этого отсортированного списка чисел , создайте разницу между последовательными числами и границами: . Это дает пробелов.
Каково распределение максимального разрыва?
Это может быть оформлено с использованием статистики заказа :
См. Ссылку для распределения пробелов , но этот вопрос задает распределение максимального пробела.
Я был бы удовлетворен средним значением, .
Если все зазоры имеют размер 1. Если то есть один зазор с размером и возможных местоположений. Максимальный размер промежутка составляет , и этот промежуток может быть помещен до или после любого из чисел, в общей сложности возможных позиций. Наименьший максимальный размер зазора - . Определите вероятность любой данной комбинации .
Я частично решил функцию вероятности массы как
Текущая работа (1): Уравнение для первого промежутка, является простым:
Текущая работа (2): легко запустить симуляции Монте-Карло.
simMaxGap[m_, n_] := Max[Differences[Sort[Join[RandomSample[Range[m], n], {0, m+1}]]]];
m = 1000; n = 1; trials = 100000;
SmoothHistogram[Table[simMaxGap[m, n], {trials}], Filling -> Axis,
Frame -> {True, True, False, False},
FrameLabel -> {"k (Max gap)", "Probability"},
PlotLabel -> StringForm["m=``,n=``,smooth histogram of maximum map for `` trials", m, n, trials]][![enter image description here][1]][1]
Ответы:
Пусть - вероятность того, что минимум равен ; то есть выборка состоит из и -подмножества . Есть таких подмножеств из одинаково вероятных подмножеств, откудаa ( 1 ) g g n - 1 { g + 1 , g + 2 , … , m } ( m - gf(g;n,m) a(1) g g n−1 {g+1,g+2,…,m} ( м(m−gn−1) (mn)
Добавление для всех возможных значений больших дает функцию выживанияf(k;n,m) k g
Пусть будет случайной величиной, заданной наибольшим разрывом:Gn,m
(Это отвечает на вопрос в том виде, в котором он был изначально сформулирован, прежде чем он был изменен, чтобы включить пробел между и .)a(n) m
Мы вычислим его функцию выживания из которого легко получить все распределение . Метод представляет собой динамическую программу, начинающуюся с , для которой очевидно, что
Для больших обратите внимание, что событие является непересекающимся объединением событияn>1 Gn,m>g
для которого самый первый разрыв превышает , а отдельные событияg g
для которого первый зазор равен а зазор больше, чем возникает позже в образце. Закон полной вероятности утверждает, что вероятности этих событий добавляют, откудаk g
Исправив и выложив двусторонний массив с индексами и , мы можем вычислить , используя заполнить первую строку и заполнить каждую последующую строку, используя операций для каждой строки. Следовательно, таблица может быть завершена в операций и всех таблиц для через может быть построена в операций.g i=1,2,…,n j=1,2,…,m P(g;n,m) (1) (2) O(gm) O(gmn) g=1 g=m−n+1 O(m3n)
Эти графики показывают функцию выживания от для . При увеличении график перемещается влево, что соответствует уменьшению шансов на большие промежутки.g→P(g;n,64) n=1,2,4,8,16,32,64 n
Закрытые формулы для могут быть получены во многих особых случаях, особенно для больших , но я не смог получить закрытую формулу, которая применима ко всем . Хорошие приближения легко доступны, если заменить эту задачу аналогичной задачей для непрерывных равномерных переменных.P(g;n,m) n g,n,m
Наконец, ожидание получается суммированием его функции выживания, начиная с :Gn,m g=0
Этот контурный график ожидания показывает контуры на , переходящие от темного к светлому.2,4,6,…,32
источник