Avalanche como processo estocástico

16

Considere o seguinte processo:

Existem compartimentos organizados de cima para baixo. Inicialmente, cada caixa contém uma bola. Em cada passo, nósn

  1. escolha uma bola aleatória eb
  2. mova todas as bolas da bandeja que contém para a bandeja abaixo dela. Se já era o compartimento mais baixo, removemos as bolas do processo.b

Quantas etapas são necessárias na expectativa até o término do processo, ou seja, até que todas as bolas tenham sido removidas do processo? Isso já foi estudado antes? A resposta segue facilmente de técnicas conhecidas?n

Na melhor das hipóteses, o processo pode terminar após etapas. Na pior das hipóteses, pode etapas . Ambos os casos devem ser muito improváveis. Minha conjectura é que são necessários passos e fiz algumas experiências que parecem confirmar isso.Θ ( n 2 ) Θ ( n log n )nΘ(n2)Θ(nregistron)

(Observe que escolher uma lixeira uniformemente aleatoriamente é um processo muito diferente que obviamente levará etapas para concluir.)Θ(n2)

Matthias
fonte
A pergunta parece interessante (embora eu não saiba a resposta). Parece difícil por causa da não monotonicidade; se todas as n bolas estiverem na bandeja superior, o processo terminará claramente em exatamente n etapas.
Tsuyoshi Ito

Respostas:

11

Não é realmente uma resposta, mas um comentário extenso sobre a resposta de András.

A resposta de András contém uma boa intuição, embora eu não acredite que seja um cálculo rigoroso do número esperado de etapas. Acho que talvez seja uma boa aproximação a uma resposta, mas não parece lidar adequadamente com os casos em que a lixeira abaixo da lixeira ocupada mais alta fica vazia antes que a lixeira superior seja esvaziada para baixo. Ainda assim, essa pode ser uma aproximação razoável a ser feita (não tenho certeza).

Seu cálculo contém um erro que afeta a escala. Vou pegar exatamente o mesmo ponto de partida, refazer e expandir o cálculo.

Ele perde um fator de p dentro da soma, pois a probabilidade de escolher aleatoriamente o compartimento correto é vez de . Como resultado, temos 1pn1 1n

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

onde é o enésimo número do harmônico . Para aproximar , podemos simplesmente substituir a soma por uma integral: . Portanto, a escala é ou aproximadamente . Embora essa escala não corresponda exatamente à escala do problema (veja a simulação abaixo), ela ocorre quase por exatamente um fator de .H N H Nn + 1 1 1Hn=p=1 1n1 1/pHnHn1 1n+1 11 1xdx=registro(n+1 1)n(1 1+registro(n+1 1))nregistro(n+1 1)registro(2)

Simulação vs teoria

Círculos vermelhos: pontos de dados da simulação do processo com média de 10 mil execuções. Verde: . Azul: .nregistro2(n+1 1)nregistro(n+1 1)

Joe Fitzsimons
fonte
@ Joe: Bom trabalho! Seria interessante agora mostrar rigorosamente como o fator vem da criação de lacunas. em2
András Salamon
@ András: Eu realmente não tenho um bom pressentimento se essa é uma boa aproximação a ser feita ou não. A idéia de Peter de formar cachos que se deslocam para baixo parece que deve dar a expressão correta, assumindo que eles têm a mesma probabilidade de se formar em qualquer caixote.
Joe Fitzsimons
@ Joe: A bola mais alta permanecerá isolada em quase 1/3 dos casos. Considere as três principais bolas. Se a do meio for escolhida primeiro (dentre as 3), ela se juntará à terceira. Esses dois, a partir de então, se moverão duas vezes mais rápido que a bola de cima. A distância entre eles e a bola de cima é uma caminhada aleatória fortemente enviesada e a probabilidade de a bola de alcançar é limitada por uma constante pequena (ish) (estimativa aproximada de 15%). Mas a boa notícia é que as melhores bolas de log n não devem realmente importar. Se todo o resto for limpo em n \ log n etapas, elas adicionarão apenas n \ log n etapas adicionais.
Matthias
Aqui estão duas parcelas. Ambos mostram o número de etapas divididas por , até que todas as bolas, exceto sejam limpas. No primeiro, bolas que abandonam o sistema ainda podem ser escolhidas (como András o propôs): tinyurl.com/2wg7a9y . Para o segundo, as bolas que saem do sistema não são mais escolhidas: tinyurl.com/33b63pq . Como você pode ver, os limites que o primeiro processo pode dar são provavelmente muito fracos. Talvez possa ser sintonizado considerando fases (como Peter escreveu em algum lugar) nas quais sempre reduzimos pela metade o número de bolas no sistema? nregistron
Matthias
@ Matthias: Analisar o tempo esperado assumindo que a intuição de Peter está correta não é o obstáculo (pelo menos da minha perspectiva). Para mim, provar que essa intuição é de fato um reflexo justo do que acontece é necessário primeiro, embora eu suspeite que seja uma boa aproximação.
Joe Fitzsimons
9

Edit: Estou deixando esta resposta como está (por enquanto) para ilustrar o processo confuso de provar teoremas, algo que é deixado de fora dos trabalhos publicados. A principal intuição aqui é que basta focar na bola de cima, pois ela varre tudo abaixo dela. Por favor, veja os comentários (em particular @Michael apontando que podem ocorrer lacunas) e a resposta posterior de @ Joe sobre como os erros foram identificados e corrigidos. Gosto especialmente do uso de experimentos de Joe para verificar se as fórmulas eram sensatas.


n(1 1+π2/6)n

b1 1b2bnb1 1=nb2n-1 1...bEun-Eu+1 1b1 1b2bn1 1,2,...,n) Estes podem ser vistos como eventos separados, um após o outro. O número esperado de etapas é então

n+p=1 1nk=0 0k+1 1n(n-pn)k=n+p=1 1n-1 11 1n-pk=1 1k(n-pn)k=n+p=1 1n-1 11 1n-pn(n-p)/p2=n+np=1 1n-1 11 1/p2(1 1+π2/6)n.

András Salamon
fonte
3
@ Andras @ Joe: Puta merda. Se todas as pessoas que fazem as perguntas neste site levaram as perguntas tão a sério quanto você as responde, esse seria o URL mais ruim da Internet.
Aaron Sterling
11
@ András: Estou tentando entender sua afirmação "uma sequência de bolas limpará todas as caixas exatamente se contiver uma subsequência ...". Talvez eu tenha entendido algo errado, mas digamos que temos quatro bolas. Se a sequência for 3,4,3,2,4, parece que ela satisfaz seus requisitos de subsequência, mas nem todos os compartimentos foram limpos.
Michael
11
@ András: Se você deseja mostrar um limite superior razoável, deve usar o fato de que as bolas desaparecem do processo e não são mais colhidas. Caso contrário, a bola mais alta é sempre escolhida apenas com probabilidade 1 / n e há uma boa chance (talvez um pouco menos que 1/2) de que essa bola fique isolada o tempo todo. Para esta bola, você precisará de n ^ 2 passos.
Matthias
11
@ Michael: Eu acho que você identificou o erro. Estou assumindo falsamente que a bola de cima se moverá para baixo, mesmo que haja uma lacuna.
András Salamon
2
O(n)O(nregistron)n/2registron