Лавина как случайный процесс

16

Рассмотрим следующий процесс:

Есть корзин, расположенных сверху вниз. Первоначально, каждая корзина содержит один шар. На каждом шагу мыN

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

Сколько шагов нужно ожидать, пока процесс не завершится, т. Е. Пока все шариков не будут удалены из процесса? Это изучалось раньше? Ответ легко следует из известных методов?N

В лучшем случае процесс может завершиться через шагов. В худшем случае это может сделать шагов. Оба случая должны быть очень маловероятными, хотя. Моя гипотеза состоит в том, что он принимает шагов, и я провел несколько экспериментов, которые, кажется, подтверждают это.NΘ(N2)Θ(NжурналN)

(Обратите внимание, что выбор корзины равномерно наугад - это совсем другой процесс, который, очевидно, потребует шагов для завершения.)Θ(N2)

Матиас
источник
Вопрос выглядит интересным (хотя я не знаю ответа). Это кажется трудным из-за немонотонности; если все n шаров находятся в верхней корзине, процесс явно завершается ровно за n шагов.
Цуёси Ито

Ответы:

11

Не совсем ответ, а расширенный комментарий к ответу Андраса.

Ответ Андраса содержит приятную интуицию, хотя я не верю, что это строгий расчет ожидаемого количества шагов. Я думаю, что это, возможно, хорошее приближение к ответу, но, похоже, оно не имеет должного отношения к случаям, когда корзина ниже самой высокой занятой корзины становится пустой до того, как верхняя корзина опустошается вниз. Тем не менее, это может быть разумным приближением (я не уверен).

Его расчет содержит ошибку, которая влияет на масштабирование. Я собираюсь взять точно такую ​​же отправную точку, и повторить и расширить расчет.

Он пропускает коэффициент p внутри суммирования, так как вероятность случайного выбора правильного бина равна а не1пN . В результате мы имеем1N

n+pзнак равно1NΣКзнак равно0(К+1)пN(N-пN)Кзнак равноN+Σпзнак равно1NпNΣКзнак равно0(К+1)(N-пN)Кзнак равноN+Σпзнак равно1NпNN2п2знак равноN+NΣпзнак равно1N1/пзнак равноN(1+ЧАСN)

где - это n-е гармоническое число . Чтобы приблизить H n, мы можем просто заменить суммирование на интеграл: H nn + 1 1 1ЧАСNзнак равноΣпзнак равно1N1/пЧАСN. Таким образом, масштабирование составляетn(1+log(n+1))или приблизительноnlog(n+1). Хотя это масштабирование не соответствует точно масштабированию задачи (см. Моделирование ниже), оно почти точно уменьшается вlog(2).ЧАСN1N+11ИксdИксзнак равножурнал(N+1)n(1+log(n+1))nlog(n+1)log(2)

Симуляция против теории

Красные круги: Точки данных от моделирования процесса в среднем за 10 000 циклов. Зеленый: . Синий: n log ( n + 1 ) .nlog2(n+1)nlog(n+1)

Джо Фитцсимонс
источник
@Joe: Хорошая работа! Было бы интересно сейчас строго показать, как фактор возникает из-за создания пробелов. ln2
Андрас Саламон
@ András: У меня нет особого ощущения, является ли это обоснованным приближением или нет. @ Идея Питера о формировании сгустков, которые смещаются вниз, похоже, должна дать правильное выражение, предполагая, что они одинаково вероятны в любом бункере.
Джо Фицсимонс
@Joe: самый верхний шар останется изолированным почти в 1/3 случаев. Рассмотрим 3 верхних мяча. Если первый выбирается средний (из этих 3), он присоединится к третьему. С тех пор эти двое будут двигаться в два раза быстрее, чем главный мяч. Расстояние между ними и верхним шаром является случайным блужданием с сильным смещением, и вероятность того, что верхний шар наверстает упущенное, ограничена малой постоянной (грубая оценка) (приблизительная оценка 15%). Но хорошая новость заключается в том, что топ-логин не должен иметь большого значения. Если все остальное будет очищено за n \ logn шагов, они будут добавлять только дополнительные n \ logn шагов.
Матиас
Вот два сюжета. Оба показывают количество шагов, деленное на , пока все, кроме log n шариков, не будет очищено. Для первого шарики, которые выпадают из системы, все еще могут быть выбраны (как предложил Андраш): tinyurl.com/2wg7a9y . Во втором случае шары, выпадающие из системы, больше не выбираются: tinyurl.com/33b63pq . Как видите, границы, которые может дать первый процесс, вероятно, слишком слабы. Может быть, это можно настроить, рассматривая фазы (как Питер написал где-то), в которых мы всегда вдвое уменьшаем количество шаров в системе? nlogn
Матиас
@Matthias: Анализ ожидаемого времени при условии, что интуиция Питера верна, не является препятствием (по крайней мере, с моей точки зрения). Мне сначала нужно доказать, что эта интуиция на самом деле является справедливым отражением того, что происходит, хотя я подозреваю, что это хорошее приближение.
Джо Фицсимонс
9

Редактировать: я оставляю этот ответ как есть (пока), чтобы проиллюстрировать грязный процесс доказательства теорем, что-то, что осталось из опубликованных работ. Основная интуиция здесь заключается в том, что достаточно сфокусироваться на верхнем шаре, так как он сметает все под ним. Пожалуйста, смотрите комментарии (в частности, @Michael, указывающий на возможные пробелы) и более поздний ответ @ Joe о том, как ошибки были выявлены и исправлены. Мне особенно нравится использование экспериментов Джо, чтобы перепроверить, что формулы были разумными.


N(1+π2/6)N

б1б2бNб1знак равноNб2N-1...бяN-я+1б1б2бN1,2,...,N). Это можно рассматривать как отдельные события, одно за другим. Ожидаемое количество шагов тогда

n+p=1nk=0k+1n(npn)k=n+p=1n11npk=1k(npn)k=n+p=1n11npn(np)/p2=n+np=1n11/p2(1+π2/6)n.

András Salamon
источник
3
@Andras @Joe: Holy schmoley. If all the people asking the questions on this site took their questions as seriously as you take answering them, this would be the badassest url on the internet.
Aaron Sterling
1
@András: I'm trying to understand your statement "a sequence of balls will clear all the bins precisely if it contains a subsequence...". Maybe I've misunderstood something, but say we have four balls. If the sequence is 3,4,3,2,4 then it seems to satisfy your subsequence requirement, yet not all the bins have been cleared.
Michael
1
@ Андрас: Если вы хотите показать разумную верхнюю границу, вы должны использовать тот факт, что шары исчезают из процесса и больше не выбираются. В противном случае самый верхний шар всегда выбирается только с вероятностью 1 / n, и есть большая вероятность (возможно, чуть меньше 1/2), что этот шар будет оставаться изолированным все время. Для этого шара вам понадобится n ^ 2 шага.
Матиас
1
@Michael: I think you have identified the mistake. I'm assuming falsely that the top ball will move down even if there is a gap.
András Salamon
2
Here's my intuition. After a few steps, some clump of balls is going to be larger than any other clump of balls. At this point, the clump moves faster than everything else, clears everything below it and falls out of the system. This whole process should take O(n) or maybe O(nlogn) steps. This first clump is uniformly distributed in the line, so on average it takes half the balls with it. Now, we're left with a system of around n/2 balls, and another clump forms. So after around logn clumps, we're done.
Peter Shor