Какова жесткая нижняя граница времени сбора купонов?

20

В классической задаче по сбору купонов хорошо известно, что время необходимое для завершения набора из случайно выбранных купонов, удовлетворяет , и .ТNE[T]nlnnVar(T)n2Pr(T>nlnn+cn)<ec

Эта верхняя граница лучше, чем та, которую дает неравенство Чебышева, которое было бы примерно 1/c2 .

У меня вопрос: есть ли соответствующая нижняя граница для Т для Чебышева T? (например, что-то вроде Pr(T<nlnncn)<eс )?

Дэвид
источник
Очевидная нижняя граница - это Pr(Т<N)знак равно0 , но я думаю, вы знаете об этом ...
Нестоп

Ответы:

14

Я даю это как второй ответ, так как анализ является полностью элементарным и дает именно желаемый результат.

Предложение Для с>0 и n1 ,

P(T<nжурналN-сN)<е-с,

Идея доказательства проста:

  1. Представьте время, пока все купоны не будут собраны, в виде Тзнак равноΣязнак равно1NТя , где Тя - время сбора я го (ранее) уникального купона. Тя геометрические случайные величины со средним времена NN-я+1 .
  2. Примените версию Чернова с привязкой и упростите.

доказательство

Для любого и любого имеем s > 0 P ( T < t ) = P ( e - s T > e - s t ) e s t E e - s TT s>0

п(Т<T)знак равноп(е-sТ>е-sT)еsTЕе-sТ,

Так как и независимы, мы можем написать T i E e - s T = n i = 1 E e - s T iТзнак равноΣяТяТя

Ее-sТзнак равноΠязнак равно1NЕе-sТя

Теперь, когда является геометрическим, скажем, с вероятностью успеха , тогда простое вычисление показывает p i E e - s T i = p iТяпя

Ее-sТязнак равнопяеs-1+пя,

Для нашей задачи : , , и т. Д. Следовательно, р 1 = 1 р 2 = 1 - 1 / п р 3 = 1 - 2 / п п Π я = 1 E е - с Т я = п П я = 1 я / ппяп1знак равно1п2знак равно1-1/Nп3знак равно1-2/N

Πязнак равно1NЕе-sТязнак равноΠязнак равно1Nя/Nеs-1+я/N,

Давайте выберем и для некоторого . Тогда и , давая t = n log n - c n c > 0 e s t = n e - c e s = e 1 / n1 + 1 / n n i = 1 i / nsзнак равно1/NTзнак равноNжурналN-сNс>0

еsTзнак равноNе-с
еsзнак равное1/N1+1/N
Πязнак равно1Nя/Nеs-1+я/NΠязнак равно1Nяя+1знак равно1N+1,

Сложив это вместе, мы получаем, что

п(Т<NжурналN-сN)NN+1е-с<е-с

по желанию.

кардинальный
источник
Это очень мило и именно то, что доктор прописал. Спасибо.
Дэвид
@ Дэвид, просто любопытно: что такое приложение?
кардинал
Длинная история. Я пытаюсь доказать нижнюю границу для времени смешивания цепи Маркова, которую я приготовил, чтобы проанализировать время работы интересующего меня алгоритма - который, как оказалось, сводится к нижней границе c .коллекторная проблема. Кстати, я пытался найти именно этот вид черновского стиля, но не понял, как избавиться от этого продукта в . Хороший выбор колла :-). с = 1 / няsзнак равно1/N
Дэвид
@ Дэвид, , хотя почти наверняка неоптимальный, казалось очевидной вещью, которую нужно попробовать, поскольку это дало , то есть тот же термин, что и термин, полученный при выводе для верхняя граница. e s t = n e - csзнак равно1/Nest=neс
кардинал
1
Запрос : Доказательство, которое я дал выше, принадлежит мне. Я работал над этим из удовольствия, так как проблема заинтриговала меня. Однако я не претендую на новизну. В самом деле, я не могу представить, что подобное доказательство, использующее подобную технику, еще не существует в литературе. Если кто-нибудь знает ссылку, пожалуйста , оставьте ее в качестве комментария здесь. Мне было бы очень интересно узнать об этом.
кардинал
9

Хотя @cardinal уже дал ответ, который дает именно ту оценку, которую я искал, я нашел похожий аргумент в стиле Черноффа, который может дать более сильную оценку:

Предложение : (это сильнее для )с > π 2

пр(ТNжурналN-сN)ехр(-3с2π2),
с>π23

Доказательство :

Как и в ответе @ cardinal, мы можем использовать тот факт, что является суммой независимых геометрических случайных величин с вероятностями успеха . Отсюда следует, что и .T i p i = 1 - i / n E [ T i ] = 1 / p i E [ T ] = n i = 1 E [ T i ] = n n i = 1 1ТТяпязнак равно1-я/NЕ[Тя]знак равно1/пяЕ[Т]знак равноΣязнак равно1NЕ[Тя]знак равноNΣязнак равно1N1яNжурналN

Определите теперь новые переменные и . Затем мы можем написать S : = i S i Pr ( T n log n - c n ) Pr ( T E [ T ] - c n ) = Pr ( S - c n ) = Pr ( exp ( - s S)Sязнак равноТя-Е[Тя]Sзнак равноΣяSя

Pr(ТNжурналN-сN)Pr(ТЕ[Т]-сN)знак равноPr(S-сN)
знак равноPr(ехр(-sS)ехр(sсN))е-sсNЕ[е-sS]

Вычисляя средние, мы имеем

es-1sez

Е[е-sS]знак равноΠяЕ[е-sSя]знак равноΠяеs/пя1+1пя(еs-1)е12s2Σяпя-2
где неравенство следует из фактов, что а также для .еs-1sz0еZ1+Zе12Z2Z0

Таким образом, поскольку , мы можем написать Pr(Tпвойтип-сп) е 1Σяпя-2знак равноN2Σязнак равно1N-11я2N2π2/6

Pr(ТNжурналN-сN)е112(Nπs)2-sсN,

Минимизируя при , мы наконец получаем s>0

Pr(ТNжурналN-сN)е-3с2π2
Дэвид
источник
1
(+1) По модулю пару мелких опечаток, это приятно. Расширение вокруг чего-то близкого к среднему, как вы это сделали, часто работает лучше. Я не удивлен, увидев сходимость более высокого порядка в свете асимптотических результатов. Теперь, если вы показываете подобную верхнюю границу, это доказывает, что является субэкспоненциальным в терминологии Вершинина, что имеет много значений в отношении концентрации меры. (Т-NжурналN)/N
кардинал
1
Аргумент, кажется, не обобщается непосредственно на верхнюю границу. Заменив на (и на ), можно проделать те же самые шаги до момента вычисления . Однако на данный момент лучшее, что я могу сделать, - это использовать , который все еще оставляет и я надеваю не знаю, что с этим делатьс-сs-sЕ[еsS]Πяе-s/пя1-sпяе-Z1-Zехр(Z22(1-Z))
Е[еsS]е12s2Σяпя2(1-s/пя)
Дэвид
2
Интересно, однако, что весь аргумент (для нижней границы), кажется, работает не только для задачи сборщика купонов, но и для любой суммы неидентичных, независимых геометрических переменных с ограниченной дисперсией. В частности: задано , где каждый является независимым GV с вероятностью успеха , и где , затем Тзнак равноΣяТяТяпяΣяпя-2A<
Pr(ТЕ[Т]-a)е-a22A
Дэвид
4

Важное примечание : я решил удалить доказательство, которое я дал изначально в этом ответе. Это было длиннее, более вычислительно, использовало большие молотки и показало более слабый результат по сравнению с другим доказательством, которое я дал. Все вокруг, плохой подход (на мой взгляд). Если вам действительно интересно, я полагаю, вы можете посмотреть изменения.

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


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

п(Т>NжурналN+сN)1-е-е-с

и

п(ТNжурналN-сN)е-ес,

Константа и пределы взяты как . Обратите внимание, что, хотя они разделены на два результата, они в значительной степени совпадают с результатами, так как не обязательно должен быть неотрицательным в любом случае.срNс

См., Например, Motwani and Raghavan, Randomized Algorithms , pp. 60--63 для доказательства.


Также : Дэвид любезно предоставил доказательство своей заявленной верхней границы в комментариях к этому ответу.

кардинальный
источник
Да, это верно для каждого фиксированного . (Очень простое) доказательство можно найти, например, в книге Левина, Переса и Вильмера «Цепи Маркова и времена смешивания», предложение 2.4. Однако доказательство не работает для нижней границы. N
Дэвид
1
Фактически, я мог бы также переписать доказательство здесь: «Пусть будет событием, когда тый [купонный] тип не появляется среди первых нарисованных купонов. Заметим сначала, что . Так как каждое испытание имеет вероятность не получить купон а испытания независимы, правая часть сверху ограничена сверху как , доказывая (2.7). " AяяNжурналN+сNп(τ>NжурналN+сN)знак равноп(яAя)Σяп(Aя)1-N-1яΣя(1-1/N)NжурналN+сNNехр(NжурналN+сNN)знак равное-с
Дэвид
@ Давид, это мило и достаточно просто. Я быстро поиграл с расширением формулы включения-исключения другим термином, но быстро никуда не попал и не успел посмотреть дальше. Событие эквивалентно тому, что после испытаний не осталось купонов . С этим должен быть связан мартингейл. Вы пробовали неравенство Хеффдинга на (предполагаемом) ассоциированном мартингале? Асимптотический результат предполагает сильную меру концентрации. {Т<TN}TN
кардинал
@ Дэвид, в твоем доказательстве есть перевернутый знак, но я уверен, что это очевидно и для других читателей.
кардинал
@ Дэвид, пожалуйста, смотрите мой другой ответ на ваш вопрос. Метод отличается от верхней границы, которую вы даете, но используемые инструменты почти такие же элементарные, в отличие от ответа, который я дал здесь.
кардинал
2

Бенджамин Доерр дает (в главе «Анализ эвристики рандомизированного поиска: инструменты из теории вероятностей» в книге «Теория эвристики рандомизированного поиска», см. Ссылку на онлайн-PDF) несколько простое доказательство

Предложение Пусть будет временем остановки процесса получения купона. Тогда .ТPr[Т(1-ε)(N-1)перN]е-Nε

Это, кажется, дает желаемую асимптотику (из второго ответа @ cardinal), но с преимуществом истинности для всех и .Nε

Вот примерный набросок.

Доказательство Эскиз: Пусть будет событием , что -й купон собираются в первом розыгрышей. Таким образом, . Ключевым фактом является то, что имеют отрицательную корреляцию для любого , . Наглядно это достаточно понятно, так как , зная , что -ый купон в первом черпает бы сделать это менее вероятно , что -го купона также обращается в первую розыгрышах. ИксяяTPr[Иксязнак равно1]знак равно(1-1/N)TИксяя[N]Pr[яя,Иксязнак равно1]ΠяяPr[Иксязнак равно1]яTJT

Можно доказать это утверждение, но увеличив набор на 1 на каждом шаге. Тогда она сводится к показывая , что , для . Эквивалентно, путем усреднения это сводится к тому, чтобы показать, что . Doerr только дает интуитивный аргумент для этого. Один из способов доказательства заключается в следующем. Можно заметить, что при условии наличия купона после всех купонов в , что вероятность получения нового купона от после получения до настоящего времени теперь равна , вместо предыдущегояPr[яя,Иксязнак равно1|ИксJзнак равно1]Pr[яя,Иксязнак равно1]Jяj I I k | Я | - кPr[яя,Иксязнак равно1|ИксJзнак равно0]Pr[яя,Иксязнак равно1]JяяК | Я| -к|я|-КN-1 жя|я|-КN . Таким образом, разлагая время, чтобы собрать все купоны как сумму геометрических случайных величин, мы можем видеть, что обусловливание на -компоненте, наступающем после того, как увеличивает вероятности успеха, и, следовательно, выполнение кондиционирования только повышает вероятность сбора купонов раньше ( стохастическим доминированием: каждая геометрическая случайная переменная увеличивается в терминах стохастического доминирования посредством обусловленности, и это доминирование может затем применяться к сумме).Jя

Учитывая эту отрицательную корреляцию, отсюда следует, что , что дает желаемая граница с . t = ( 1 - ϵ ) ( n - 1 ) ln nPr[Т(1-ε)(N-1)перN](1-(1-1/N)T)NTзнак равно(1-ε)(N-1)перN

miforbes
источник