Avalancha como proceso estocástico

16

Considere el siguiente proceso:

Hay contenedores dispuestos de arriba a abajo. Inicialmente, cada contenedor contiene una bola. En cada paso, nosotrosn

  1. recoger una pelota uniformemente al azar yb
  2. mueve todas las bolas desde el contenedor que contiene al contenedor debajo de él. Si ya era el contenedor más bajo, eliminamos las bolas del proceso.b

¿Cuántos pasos toma en espera hasta que el proceso finalice, es decir, hasta que todo n que se hayan eliminado bolas del proceso? ¿Se ha estudiado esto antes? ¿La respuesta se sigue fácilmente de técnicas conocidas?

En el mejor de los casos, el proceso puede finalizar después de pasos. En el peor de los casos, puede tomar Θ ( n 2 ) pasos. Sin embargo, ambos casos deberían ser muy improbables. Mi conjetura es que toma Θ ( n log n ) pasos e hice algunos experimentos que parecennΘ(n2)Θ(nlogn) confirmar esto.

(Tenga en cuenta que elegir un contenedor de manera uniforme al azar es un proceso muy diferente que obviamente tomará pasos para terminar).Θ(n2)

Matías
fuente
La pregunta parece interesante (aunque no sé la respuesta). Parece difícil debido a la no monotonía; Si todas las n bolas están en la bandeja superior, el proceso termina claramente en exactamente n pasos.
Tsuyoshi Ito

Respuestas:

11

No es realmente una respuesta, sino un comentario extenso sobre la respuesta de András.

La respuesta de András contiene una buena intuición, aunque no creo que sea un cálculo riguroso del número esperado de pasos. Creo que es quizás una buena aproximación a una respuesta, pero no parece tratar adecuadamente los casos en que el contenedor debajo del contenedor ocupado más alto se vacía antes de que el contenedor superior se vacíe hacia abajo. Aún así, esta podría ser una aproximación razonable para hacer (no estoy seguro).

Su cálculo contiene un error que afecta la escala. Voy a tomar exactamente el mismo punto de partida, y rehacer y expandir el cálculo.

Se pierde un factor de p dentro de la suma, ya que la probabilidad de elegir aleatoriamente el contenedor correcto es lugar de1pn . Como resultado tenemos1n

n+p=1nk=0(k+1)pn(npn)k=n+p=1npnk=0(k+1)(npn)k=n+p=1npnn2p2=n+np=1n1/p=n(1+Hn)

donde es el enésimo número armónico . Para aproximar H n simplemente podemos reemplazar la sumatoria con una integral: H nn + 1 1 1Hn=p=1n1/pHn. Por lo tanto, la escala esn(1+log(n+1))o aproximadamentenlog(n+1). Si bien esta escala no coincide exactamente con la escala del problema (vea la simulación a continuación), está casi exactamente por un factor delog(2).Hn1n+11xdx=log(n+1)n(1+log(n+1))nlog(n+1)log(2)

Simulación vs teoría

Círculos rojos: los puntos de datos de la simulación del proceso promediaron más de 10k ejecuciones. Verde: . Azul: n log ( n + 1 ) .nlog2(n+1)nlog(n+1)

Joe Fitzsimons
fuente
@ Joe: ¡Buen trabajo! Sería interesante mostrar ahora rigurosamente cómo entra el factor a partir de la creación de brechas. ln2
András Salamon
@ András: Realmente no tengo un buen presentimiento sobre si es una buena aproximación o no. La idea de @ Peter de que se formen racimos que se desplazan hacia abajo, parece que debería dar la expresión correcta suponiendo que es igualmente probable que se formen en cualquier contenedor.
Joe Fitzsimons
@ Joe: La bola más alta permanecerá aislada en casi 1/3 de los casos. Considere las 3 mejores bolas. Si el primero se elige primero (de esos 3), se unirá al tercero. Estos dos, a partir de entonces, se moverán dos veces más rápido que la bola superior. La distancia entre ellos y la bola superior es una caminata aleatoria muy sesgada y la probabilidad de que la bola superior se recupere está limitada por una pequeña (ish) constante (estimación aproximada del 15%). Pero la buena noticia es que el registro de bolas superior no debería importar realmente. Si todo lo demás se borra en n \ log n pasos, solo agregarán n \ log n pasos adicionales.
Matthias el
Aquí hay dos parcelas. Ambos muestran el número de pasos divididos por , hasta que todo, excepto log n, se borran. Para el primero, las bolas que caen del sistema aún se pueden recoger (como lo propuso András): tinyurl.com/2wg7a9y . Para el segundo, las bolas que salen del sistema ya no se recogen: tinyurl.com/33b63pq . Como puede ver, los límites que puede dar el primer proceso son probablemente demasiado débiles. ¿Quizás se puede ajustar considerando las fases (como escribió Peter en alguna parte) en las que siempre reducimos a la mitad el número de bolas en el sistema? nlognorte
Matthias
@Matthias: Analizar el tiempo esperado asumiendo que la intuición de Peter es correcta no es el obstáculo (al menos desde mi perspectiva). Para mí, probar que esta intuición es, de hecho, un reflejo justo de lo que sucede es necesario primero, aunque sospecho que es una buena aproximación.
Joe Fitzsimons
9

Editar: estoy dejando esta respuesta tal como está (por ahora) para ilustrar el desordenado proceso de probar los teoremas, algo que queda fuera de los artículos publicados. La intuición central aquí es que es suficiente enfocarse en la bola superior, ya que barre todo debajo de ella. Consulte los comentarios (en particular, @Michael que señala que pueden existir lagunas) y la respuesta posterior de @ Joe sobre cómo se identificaron y corrigieron los errores. Me gusta especialmente el uso de experimentos por parte de Joe para verificar que las fórmulas fueran sensatas.


El límite inferior es norte(1+π2/ /6 6)norte para el número esperado de pasos.

si1si2sinortesi1=nortesi2norte-1...siyonorte-yo+1si1si2sinorte1,2,...,norte) Estos pueden verse como eventos separados, uno tras otro. El número esperado de pasos es entonces

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
fuente
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
@András: If you want to show a reasonable upper bound, you have to use the fact that balls disappear from the process and are no longer picked. Otherwise, the top most ball is always only picked with probability 1/n and there is a good chance (maybe slightly less than 1/2) that this ball will stay isolated the whole time. For this ball, you will need n^2 steps.
Matthias
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