В классической задаче по сбору купонов хорошо известно, что время необходимое для завершения набора из случайно выбранных купонов, удовлетворяет , и .
Эта верхняя граница лучше, чем та, которую дает неравенство Чебышева, которое было бы примерно .
У меня вопрос: есть ли соответствующая нижняя граница для Т для Чебышева ? (например, что-то вроде )?
Ответы:
Я даю это как второй ответ, так как анализ является полностью элементарным и дает именно желаемый результат.
Предложение Дляc>0 и n≥1 ,
Идея доказательства проста:
доказательство
Для любого и любого имеем s > 0 P ( T < t ) = P ( e - s T > e - s t ) ≤ e s t E e - s TT с > 0
Так как и независимы, мы можем написать T i E e - s T = n ∏ i = 1 E e - s T iТ= ∑яТя Тя
Теперь, когда является геометрическим, скажем, с вероятностью успеха , тогда простое вычисление показывает p i E e - s T i = p iТя пя
Для нашей задачи : , , и т. Д. Следовательно, р 1 = 1 р 2 = 1 - 1 / п р 3 = 1 - 2 / п п Π я = 1 E е - с Т я = п П я = 1 я / ппя п1= 1 п2= 1 - 1 / n п3= 1 - 2 / n
Давайте выберем и для некоторого . Тогда и , давая t = n log n - c n c > 0 e s t = n e - c e s = e 1 / n ≥ 1 + 1 / n n ∏ i = 1 i / ns = 1 / n t = n logn - c n с > 0
Сложив это вместе, мы получаем, что
по желанию.
источник
Хотя @cardinal уже дал ответ, который дает именно ту оценку, которую я искал, я нашел похожий аргумент в стиле Черноффа, который может дать более сильную оценку:
Предложение : (это сильнее для )с > π 2
Доказательство :
Как и в ответе @ 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 - я / н Е[ Tя] = 1 / ря Е[ T] = ∑Nя = 1Е[ Tя] = n ∑Nя = 11я≥ n logN
Определите теперь новые переменные и . Затем мы можем написать 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я: = Tя- E[ Tя] S: = ∑яSя
Вычисляя средние, мы имеем
es-1≥sez
Таким образом, поскольку , мы можем написать Pr(T≤пвойтип-сп)≤ е 1Σяп- 2я= n2Σn - 1я = 11я2≤ n2π2/ 6
Минимизируя при , мы наконец получаемс > 0
источник
Важное примечание : я решил удалить доказательство, которое я дал изначально в этом ответе. Это было длиннее, более вычислительно, использовало большие молотки и показало более слабый результат по сравнению с другим доказательством, которое я дал. Все вокруг, плохой подход (на мой взгляд). Если вам действительно интересно, я полагаю, вы можете посмотреть изменения.
Асимптотические результаты, которые я первоначально процитировал и которые все еще находятся ниже в этом ответе, показывают, что при мы можем сделать немного лучше, чем оценка, доказанная в другом ответе, который справедлив для всех .n → ∞ N
Следующие асимптотические результаты имеют место
и
Константа и пределы взяты как . Обратите внимание, что, хотя они разделены на два результата, они в значительной степени совпадают с результатами, так как не обязательно должен быть неотрицательным в любом случае.c ∈ R n → ∞ с
См., Например, Motwani and Raghavan, Randomized Algorithms , pp. 60--63 для доказательства.
Также : Дэвид любезно предоставил доказательство своей заявленной верхней границы в комментариях к этому ответу.
источник
Бенджамин Доерр дает (в главе «Анализ эвристики рандомизированного поиска: инструменты из теории вероятностей» в книге «Теория эвристики рандомизированного поиска», см. Ссылку на онлайн-PDF) несколько простое доказательство
Предложение Пусть будет временем остановки процесса получения купона. Тогда .Т Pr [ T≤ ( 1 - ϵ ) ( n - 1 ) lnn ] ≤ e- нε
Это, кажется, дает желаемую асимптотику (из второго ответа @ cardinal), но с преимуществом истинности для всех и .N ε
Вот примерный набросок.
Доказательство Эскиз: Пусть будет событием , что -й купон собираются в первом розыгрышей. Таким образом, . Ключевым фактом является то, что имеют отрицательную корреляцию для любого , . Наглядно это достаточно понятно, так как , зная , что -ый купон в первом черпает бы сделать это менее вероятно , что -го купона также обращается в первую розыгрышах.Икся я T Pr [ Xя= 1 ] = ( 1 - 1 / n )T Икся я⊆ [ п ] Pr [ ∀ i ∈ I, Xя= 1 ] ≤ ∏i ∈ IPr [ Xя= 1 ] я T J T
Можно доказать это утверждение, но увеличив набор на 1 на каждом шаге. Тогда она сводится к показывая , что , для . Эквивалентно, путем усреднения это сводится к тому, чтобы показать, что . Doerr только дает интуитивный аргумент для этого. Один из способов доказательства заключается в следующем. Можно заметить, что при условии наличия купона после всех купонов в , что вероятность получения нового купона от после получения до настоящего времени теперь равна , вместо предыдущегоя Pr [ ∀ i ∈ I, Xя= 1 | ИксJ= 1 ] ≤ Pr [ ∀ i ∈ I, Xя= 1 ] j ∉ я j I I k | Я | - кPr [ ∀ i ∈ I, Xя= 1 | ИксJ= 0 ] ≥ Pr [ ∀ i ∈ I, Xя= 1 ] J я я К | Я| -к| я| -кn - 1 жя| я| -кN . Таким образом, разлагая время, чтобы собрать все купоны как сумму геометрических случайных величин, мы можем видеть, что обусловливание на -компоненте, наступающем после того, как увеличивает вероятности успеха, и, следовательно, выполнение кондиционирования только повышает вероятность сбора купонов раньше ( стохастическим доминированием: каждая геометрическая случайная переменная увеличивается в терминах стохастического доминирования посредством обусловленности, и это доминирование может затем применяться к сумме).J я
Учитывая эту отрицательную корреляцию, отсюда следует, что , что дает желаемая граница с . t = ( 1 - ϵ ) ( n - 1 ) ln nPr [ T≤ ( 1 - ϵ ) ( n - 1 ) lnn ] ≤ ( 1 - ( 1 - 1 / n )T)N t = ( 1 - ϵ ) ( n - 1 ) lnN
источник