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

16

Эта проблема связана с исследованиями моей лаборатории в области робототехники:

Случайным образом нарисуйте чисел из набора без замены и отсортируйте числа в порядке возрастания. .n{1,2,,m}1nm

Из этого отсортированного списка чисел , создайте разницу между последовательными числами и границами: . Это дает пробелов.{a(1),a(2),,a(n)}g={a(1),a(2)a(1),,a(n)a(n1),m+1a(n)}n+1

Каково распределение максимального разрыва?

P(max(g)=k)=P(k;m,n)=?

Это может быть оформлено с использованием статистики заказа : P(g(n+1)=k)=P(k;m,n)=?

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

Я был бы удовлетворен средним значением, E[g(n+1)] .

Если n=m все зазоры имеют размер 1. Если n+1=m то есть один зазор с размером 2 и n+1 возможных местоположений. Максимальный размер промежутка составляет mn+1 , и этот промежуток может быть помещен до или после любого из n чисел, в общей сложности n+1 возможных позиций. Наименьший максимальный размер зазора - mnn+1 . Определите вероятность любой данной комбинации T=(mn)1 .

Я частично решил функцию вероятности массы как (1)P(g(n+1)=k)=P(k;m,n)={0k<mnn+11k=mnn+11k=1 (occurs when m=n)T(n+1)k=2 (occurs when m=n+1)T(n+1)k=m(n1)n?m(n1)nkmn+1T(n+1)k=mn+10k>mn+1

Текущая работа (1): Уравнение для первого промежутка, a(1) является простым:

P(a(1)=k)=P(k;m,n)=1(mn)k=1mn+1(mk1n1)
Ожидаемое значение имеет простое значение: E[P(a(1))]=1(mn)k=1mn+1(mk1n1)k=mn1+n . По симметрии я ожидаю, что все n промежутков будут иметь это распределение. Возможно, решение может быть найдено путем извлечения из этого распределения n раз.

Текущая работа (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]
AaronBecker
источник
1
С этими условиями вы должны иметь n <= m. Я думаю, что вы хотите g = {a_ (1), a_ (2) -a_ (1), ..., a_ (n) -a_ (n-1)}. Случайный выбор означает выбор каждого числа с вероятностью 1 / м на первом тираже? Поскольку вы не заменяете, вероятность будет 1 / (m-1) на втором и так далее до 1 на m-м тираже, если n = m. Если n <m, это прекратилось бы раньше, когда последний розыгрыш имел вероятность 1 / (m- (n-1)) на n-м розыгрыше.
Майкл Р. Черник
2
Ваше первоначальное описание не имело смысла, потому что (я полагаю) вы перенесли двух подписчиков. Пожалуйста, убедитесь, что мое редактирование соответствует вашему намерению: в частности, подтвердите, что вы имеете в виду, что должно быть пробелов, из которых является первым. н а ( 1 )gna(1)
whuber
1
@ Gung Я думаю, что это исследование, а не самообучение
Glen_b
1
Я думаю, что ваш минимальный и максимальный размер зазора должен быть и . Минимальный размер пробела - это когда выбираются последовательные целые числа, а максимальный размер пробела - при выборе и первых целых чисел (или и )m - n + 1 m n - 1 1 , , n - 1 1 m - n + 2 , , m1mn+1mn11,,n11mn+2,,m
вероятностная
1
Спасибо, Майкл Черник, и, вероятно, ваши исправления были внесены. Спасибо @whuber за исправление!
AaronBecker

Ответы:

9

Пусть - вероятность того, что минимум равен ; то есть выборка состоит из и -подмножества . Есть таких подмножеств из одинаково вероятных подмножеств, откудаa ( 1 ) g g n - 1 { g + 1 , g + 2 , , m } ( m - gf(g;n,m)a(1)ggn1{g+1,g+2,,m}( м(mgn1)(mn)

Pr(a(1)=g=f(g;n,m)=(mgn1)(mn).

Добавление для всех возможных значений больших дает функцию выживанияf(k;n,m)kg

Pr(a(1)>g)=Q(g;n,m)=(mg)(mg1n1)n(mn).

Пусть будет случайной величиной, заданной наибольшим разрывом:Gn,m

Gn,m=max(a(1),a(2)a(1),,a(n)a(n1)).

(Это отвечает на вопрос в том виде, в котором он был изначально сформулирован, прежде чем он был изменен, чтобы включить пробел между и .)a(n)m Мы вычислим его функцию выживания из которого легко получить все распределение . Метод представляет собой динамическую программу, начинающуюся с , для которой очевидно, что

P(g;n,m)=Pr(Gn,m>g),
Gn,mn=1

(1)P(g;1,m)=Pr(G1,m>1)=mgm, g=0,1,,m.

Для больших обратите внимание, что событие является непересекающимся объединением событияn>1Gn,m>g

a1>g,

для которого самый первый разрыв превышает , а отдельные событияgg

a1=k and Gn1,mk>g, k=1,2,,g

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

(2)P(g;n,m)=Q(g;n,m)+k=1gf(k;n,m)P(g;n1,mk).

Исправив и выложив двусторонний массив с индексами и , мы можем вычислить , используя заполнить первую строку и заполнить каждую последующую строку, используя операций для каждой строки. Следовательно, таблица может быть завершена в операций и всех таблиц для через может быть построена в операций.gi=1,2,,nj=1,2,,mP(g;n,m)(1)(2)O(gm)O(gmn)g=1g=mn+1O(m3n)

фигура

Эти графики показывают функцию выживания от для . При увеличении график перемещается влево, что соответствует уменьшению шансов на большие промежутки.gP(g;n,64)n=1,2,4,8,16,32,64n

Закрытые формулы для могут быть получены во многих особых случаях, особенно для больших , но я не смог получить закрытую формулу, которая применима ко всем . Хорошие приближения легко доступны, если заменить эту задачу аналогичной задачей для непрерывных равномерных переменных.P(g;n,m)ng,n,m

Наконец, ожидание получается суммированием его функции выживания, начиная с :Gn,mg=0

E(Gn,m)=g=0mn+1P(g;n,m).

Рисунок 2: контурный график ожидания

Этот контурный график ожидания показывает контуры на , переходящие от темного к светлому.2,4,6,,32

Whuber
источник
Предложение: строка «Пусть будет случайной величиной, заданной наибольшим разрывом:», пожалуйста, добавьте последний разрывGn,mm+1an . Ваш график ожиданий соответствует моему симуляции Монте-Карло.
AaronBecker,