O modelo da pilha de areia de Deepak Dhar Resumo do seminário

O modelo da pilha de areia de
Deepak Dhar
Resumo do seminário
André Martin Timpanaro
29 de Novembro de 2007
1
O modelo BTW original (independente de gradientes)
O modelo BTW (Bak - Tang - Wiesenfeld ) original consiste de uma rede L × L
(que representa uma mesa em que a areia esta sendo colocada) onde cada um
dos sı́tios tem uma variável zi que representa a altura da pilha de areia.
A evolução do modelo é dada por 2 regras:
Adição de areia: Se todos os sı́tios tiverem alturas abaixo de 4, um grão de
areia é adicionado em um sı́tio escolhido aleatoriamente.
Avalanches: Se um sı́tio tiver pelo menos 4 grãos de areia, ele perde 4 grãos
de areia e os seus vizinhos ganham 1 grão cada.
Note que os sı́tios na borda tem menos do que 4 vizinhos, então nesses casos
ocorre perda de areia (a areia estaria caindo para fora da mesa)
2
A variante definida por Dhar
Nessa variante, nós vamos definir um modelo que generaliza a idéia do modelo
BTW com condição de relaxação dependente da altura.
Primeiro, nós não vamos fazer hipóteses sobre a geometria dessa pilha de
areia, de forma que qualquer sı́tio pode a priori receber diretamente a areia de
qualquer outro sı́tio que esteja relaxando.
Segundo, não vamos usar a hipótese que as alturas crı́ticas dos sı́tios são
iguais, nem que os sı́tios perdem areia da mesma forma.
2.1
Definição do modelo
Considere N sı́tios, cada um com um número inteiro zi representando a altura
da pilha no sı́tio i, um outro inteiro zic que representa a altura crı́tica desse
sı́tio e uma matriz de inteiros ∆ que define a geometria e a forma como os sı́tios
perdem e recebem areia na pilha.
As 2 regras de evolução do modelo BTW original ficam generalizadas como:
Adição de areia: Se zi < zic ∀ i, então um sı́tio escolhido aleatoriamente recebe um grão de areia (zi ← zi + 1)
Avalanches: Se zi ≥ zic para algum i, então as alturas de todos os sı́tios são
atualizadas segundo
zj ← zj − ∆ij ∀ j
(1)
Se uma configuração é tal que zi < zic ∀ i, ela é dita estável, senão ela é considerada instável.
2.2
Propriedades desejáveis da matriz ∆
Para que ∆ defina um modelo que guarde alguma semelhança com o modelo
BTW original, algumas propriedades precisam ser obedecidas
• Quando um sı́tio relaxa ele deve perder areia, logo ∆ii > 0 ∀ i
1
• Quando um sı́tio relaxa, os outros sı́tios não devem perder areia, logo
∆ij ≤ 0 ∀ i 6= j
• Quando
um sı́tio relaxa, a quantidade total de areia não aumenta, logo
P
∆
≥
0∀i
ij
j
• Qualquer configuração instável eventualmente relaxa para uma configuração
estável (como visto no apêndice A, uma condição suficiente para isso é que
det ∆ 6= 0)
Essas propriedades tem algumas consequências. Como os sı́tios nos quais a
areia é adicionada são aleatórios, eventualmente todos os sı́tios vão ter relaxado
pelo menos uma vez. Como um sı́tio só pode perder areia relaxando, a partir
da primeira vez que ele relaxou, a quantidade de areia nele nunca será menor do
que zic − ∆ii . Portanto sem perda de generalidade eu posso escolher zic = ∆ii
e logo todos os parâmetros relevantes do modelo podem ser definidos usando
a matriz ∆. Também segue que o modelo é um processo markoviano com um
número finito de configurações estáveis e que sem perda de generalidade zi ≥ 0.
2.3
Comutatividade do modelo
Na definição do modelo, não foi especificado o que acontece se 2 sı́tios ficarem
crı́ticos ao mesmo tempo. Na verdade isso não precisa ser especı́ficado, pois
a configuração estável resultante é a mesma independentemente de como os
relaxamentos sejam feitos.
Isso é facilmente verificado, seja C uma configuração instável, em que os
sı́tios tem tensões z1 , . . . , zN e tal que 2 sı́tios j e k distintos estejam crı́ticos
(com outros sı́tios podendo estar crı́ticos também). Se fizermos o relaxamento
do sı́tio j (apenas uma avalanche), a configuração C = (zi ) evolui para (zi −∆ji ).
Como ∆jk ≤ 0 o sı́tio k continua crı́tico. Relaxando k, essa nova configuração
passa a ser C ′ = (zi − ∆ji − ∆ki ). Fazendo o mesmo raciocı́nio mas relaxando
primeiro k e depois j chegamos na mesma configuração C ′ .
Logo não importa qual dos 2 relaxamentos é feito primeiro, a configuração
após todos os relaxamentos (quando ela voltar a ser estável) será a mesma. Esse
raciocı́nio pode ser extrapolado, de forma que qualquer que seja a ordem em
que eu fizer os relaxamentos, a configuração estável que é obtida é a mesma.
A primeira consequência dessa comutatividade é que as 2 regras de evolução
também comutam. Ou seja, se temos uma configuração C e fazemos uma certa
adição de areia (quantos grãos e em quais sı́tios quisermos) para depois fizermos
todos os relaxamentos obteremos uma configuração C ′ estável. Mas se eu fizesse
os relaxamentos de C até ela estabilizar, fizesse a mesma adição de areia e
esperasse novamente o sistema se estabilizar, eu teria novamente C ′ .
Para verificar isso, considere uma configuração C = (zi ) instável e que relaxa
nk vezes no k-ésimo sı́tio até ficar estável e por fim acrescentamos um grão no
sı́tio q (mas não relaxamos o sistema), as configurações serão




X
X
nj ∆ji  → zi + δiq −
(zi ) → zi −
nj ∆ji 
j
j
Se ao invés disso acrescentarmos o grão no sı́tio q da configuração sem relaxar
e, como a ordem em que os relaxamentos são feitos não importa, fizermos os
2
mesmos relaxamentos na mesma ordem que no primeiro caso (isso é possı́vel por
que nenhum desses relaxamentos deixa de existir por causa da adição do grão)
obtemos as seguintes configurações


X
(zi ) → (zi + δiq ) → zi + δiq −
nj ∆ji 
j
ou seja temos a mesma configuração nos 2 casos. Apesar dela não ser necessariamente estável, isso garante que as 2 configurações relaxam para a mesma
configuração estável e isso implica na comutatividade das 2 regras de evolução.
2.4
Operadores de evolução
Como a matriz ∆ é tal que qualquer configuração instável eventualmente relaxa para uma estável, podemos definir N operadores que dão a evolução das
configurações estáveis.
Seja C = (z1 , z2 , z3 , . . . , zN ) uma configuração estável. Para cada um dos
N sı́tios eu posso atribuir a C uma configuração estável, a saber, a que seria
obtida se eu acrescentasse um grão de areia naquele sı́tio e esperasse até a pilha
relaxar para uma configuração estável.
De forma mais precisa, se C é uma configuração estável, então ai C é a
configuração estável em que o sistema se encontra depois que um grão de areia
é adicionado no sı́tio i e todas as avalanches já aconteceram.
A evolução do modelo pode ser reescrita como o sorteio de um inteiro i
entre 1 e N e a configuração evolui segundo C ← ai C. Logo, como o modelo é
comutativo, segue que ai aj C = aj ai C ∀ i, j para todas as configurações estáveis
C. Isso é verificado trivialmente adicionando os 2 grãos de areia antes de fazer
o relaxamento.
2.5
Configurações recorrentes
Seja C uma configuração estável. C é dita recorrente se existem inteiros positivos
mi tais que
i
am
i C = C ∀i
(2)
Ou seja, se colocarmos grãos de areia em um mesmo sı́tio eventualmente
o sistema volta para a configuração C, independentemente de qual sı́tio tenha
sido escolhido.
2.5.1
Existência de configurações recorrentes
k
Suponha que C é tal que am
k C = C para todos os valores k = 1, . . . , q (q = 0
para uma configuração para a qual não existe k em que isso acontece). Vamos
aplicar então o operador aq+1 várias vezes em C. Como temos um número
finito de configurações estáveis, eventualmente vamos ter repetições, ou seja,
mq+1 ′
C = C ′ . Logo se k
existe uma configuração C ′ tal que C ′ = apq+1 C e que aq+1
está entre 1 e q:
p
p
mk p
mk
′
′
k
am
k C = ak aq+1 C = aq+1 ak C = aq+1 C = C
3
′
′
k
Logo C ′ é tal que am
k C = C para k = 1, . . . , q + 1. Segue por indução que
sempre existe pelo menos uma configuração recorrente.
2.5.2
O conjunto das configurações recorrentes
O conjunto das configurações recorrentes será denotado por R.
k
Seja C uma configuração recorrente. Então am
k C = C ∀ k, logo se


Y p
C ′ =  aj j  C
j
então

mk 
′
k
am
k C = ak
Y
j
p


aj j  C = 
Y
j


Y
p
k
 apj j  C = C ′
aj j  am
k C =

j
Ou seja, todas as configurações obtidas a partir de uma configuração recorrente também são recorrentes.
Suponha agora que C seja uma configuração estável qualquer e que está evoluindo segundo as regras do modelo. Usando o mesmo argumento que foi usado
para provar a existência de configurações recorrentes, segue que eventualmente
o sistema sempre evolui para configurações recorrentes.
Portanto as configurações do sistema no estado estacionário são exatamente
as configurações recorrentes. Além disso, qualquer configuração recorrente podem ser atingida partindo de qualquer outra configuração recorrente (com a
aplicação de um conjunto especı́fico de ai ’s).
Finalmente, podemos definir inversas para os operadores de evolução dentro
−n
i −n
i
do conjunto R. Como am
= aqm
, com
i C = C ∀ i e ∀ C ∈ R, então ai
i
qmi ≥ n.
ii
Considere agora a configuração a∆
i C, obtida acrescentando ∆ii grãos de
areia no sı́tio i. Isso torna o sı́tio i crı́tico, o que faz com que ele perca a areia
adicionada e faz com que os outros sı́tios recebam uma quantidade de areia igual
a −∆ij . Logo a configuração que é obtida após os relaxamentos é a mesma que
obterı́amos se tivessemos adicionado −∆ij grãos de areia para todos os sı́tios
exceto o i. Ou seja
Y −∆
ii
a∆
C
=
aj ij C ∀ C
i
j6=i
Os termos ∆ij , i 6= j são menores ou iguais a zero. Logo se C for recorrente,
então ela tem o operador
Y ∆
aj ij
j6=i
definido. Aplicando esse operador dos 2 lados da equação segue que
Y ∆
aj ij C = C ∀ C ∈ R
j
ou seja
4
Y
∆ij
aj
= IR ∀ i
(3)
j
onde IR é o operador identidade do conjunto R.
2.5.3
O grupo dos operadores de evolução
Os operadores ai são associativos, invertı́veis e definem uma identidade no conjunto R. De forma que o conjunto



Y
q
aj j , qj ∈ Z
G=


j
i
é um grupo abeliano, onde os elementos ai tem os vı́nculos am
= IR (idemi
potência) e o da eq.3. Dois elementos desse grupo só são distintos se existe um
elemento de R que eles levam em configurações diferentes quando aplicados.
Como toda configuração recorrente pode ser obtida partindo de uma configuração recorrente qualquer, o conjunto R pode ser escrito como
R = {gC, g ∈ G}
onde C é um elemento qualquer de R.
2.6
A equação mestra
Se Pest for a distribuição de probabilidade estacionária das configurações do sistema (a variável aleatória em questão) então Pest (C) = 0 se C não for recorrente.
A equação mestra do problema é então (para uma configuração recorrente)
X
Pt+1 (C) = Pt (C) +
(Pt (C ′ )T (C, C ′ ) − Pt (C)T (C ′ , C))
C ′ ∈R
Mas cada um dos C ′ é da forma gC, onde g ∈ G, logo
X
Pt+1 (C) = Pt (C) +
(Pt (gC)T (C, gC) − Pt (C)T (gC, C)) =
g∈G
= Pt (C) +
X
(Pt (gC)T (g −1 (gC), gC) − Pt (C)T (gC, C))
g∈G
reoordenando a primeira soma (Pt (gC)T (g −1 (gC), gC)) de forma que ela
seja sobre os g −1 temos
Pt+1 (C) = Pt (C) +
X
(Pt (g −1 C)T (g(g −1 C), g −1 C) − Pt (C)T (gC, C))
g∈G
Mas T (gA, A) = T (gB, B) ∀ A, B ∈ R, pois são necessários os mesmos relaxamentos para a transição A → gA e para a B → gB. Logo T (gA, A) = φ(g)
(φ(g) é no fundo a probabilidade de se sortear o elemento g como sendo o operador de evolução na hora de fazer a adição de areia), logo
5
Pt+1 (C) = Pt (C) +
X
φ(g)(Pt (g −1 C) − Pt (C))
(4)
g∈G
e no estado estacionário temos
X
φ(g)(P (C) − P (g −1 C)) = 0 ∀ C ∈ R
(5)
g∈G
Para encontrar a evolução temporal podemos pegar a eq. 4 e reescrevê-la
como
X
Pt+1 (C) =
φ(h)Pt (h−1 C) ∀ C ∈ R ⇒
h∈G
Pt+1 (gC0 ) =
X
φ(h)Pt (h−1 gC0 ) ∀ g ∈ G
h∈G
Fazendo a mudança de variável h−1 g = j ⇒ h = gj −1 logo
X
Pt+1 (gC0 ) =
φ(gj −1 )Pt (jC0 ) ∀ g ∈ G
j∈G
Podemos escrever isso numa forma matricial, se Φ = (φ(gi gj−1 )) e P~n =
(Pn (gi C0 )):
P~t+1 = Φ.P~t
(6)
onde os gi são os elementos de G ordenados de 1 a NG , o número de elementos
de G.
Uma solução trivial para a eq. 5 é Peq (C) = cte. ∀ C ∈ R, ou seja todas as
configurações recorrentes serem equiprováveis. Como provado no apêndice B,
esse é a única solução estacionária.
A condição para o balanceamento detalhado é
P (C ′ )T (C, C ′ ) = P (C)T (C ′ , C) ∀ C, C ′ ∈ R ⇒
φ(g −1 )P (gC) = φ(g)P (C) ∀ g ∈ G
Como as configurações recorrentes são equiprováveis, temos φ(g) = φ(g −1 ).
Essa equação não é obedecida sempre, pois se g 6= ai temos que φ(g) = 0,
enquanto que φ(ai ) 6= 0 sempre. Da definição de inversa dos operadores ai
segue que só em casos especiais vamos ter φ(ai ) = φ(a−1
i ).
2.7
O número de configurações recorrentes
Nós encontramos uma solução para a equação mestra, mas para obtermos as
probabilidades exatas, precisamos ainda saber quantas configurações recorrentes
um certo sistema vai ter, pois a solução é:
0
se C ∈
/R
1
se
C
∈
R
NR
Pela definição de G temos que NR = NG . Como o grupo G é comutativo ele
tem representações da forma
6
aj ≡ eiγj
O vı́nculo da eq. 3 passa a ser a equação
P
X
ei j γj ∆kj = 1 ∀ k ⇒
∆ij γj = 2πni , ni ∈ Z
j
ou em uma forma matricial
~γ
= ~n
(7)
2π
que é um sistema linear. A representação do grupo G é única. Logo, se
eu fixar a representação eu passo a ter uma relação entre os ~γ e os operadores
de evolução e consequentemente com os elementos de G. Além disso, todos os
elementos de G são gerados dessa forma.
Se det ∆ 6= 0 então os ~γ podem ser obtidos a partir de
∆.
~γ = 2π∆−1~n
Para cada valor de ~n eu tenho uma solução distinta de ~γ . A região em que
estão as soluções de ~γ levando em conta a periodicidade dos ai com relação
a eles é um hipercubo de dimensão N e aresta 2π. Nesse caso a eq. 7 pode
ser encarada como uma transformação linear cuja matriz é ∆ nessa base e que
está sendo aplicada em um hipercubo de aresta 1. O hipervolume do sólido
resultante é dado pelo jacobiano da transformação | det ∆|.
O número de pontos cujas coordenadas são todas inteiras e que estão dentro
do hipervolume resultante é a razão entre esse hipervolume e o hipervolume da
célula unitária desses pontos. Logo temos | det ∆| soluções distintas para os ~γ e
que geram operadores distintos. Segue que
NR = NG = | det ∆|
Devemos lembrar aqui que assumimos que det ∆ 6= 0 nesse raciocı́nio. Essa
equação não vale para esse caso pois ~γ = ~n = ~0 é sempre solução (essa solução
dá a identidade do grupo).
Logo, no caso em que det ∆ 6= 0 a solução da equação mestra é
0
se C ∈
/R
1
se
C
∈
R
| det ∆|
A
Condição suficiente para estabilidade do modelo
Suponha que C seja uma configuração instável e que não relaxa para uma configuração estável. Como a quantidade de areia não aumenta, o número de configurações instáveis é limitado (Ele é no máximo (Q+1)N , onde Q é a quantidade
de areia no sistema todo). Então, se eu evoluir a configuração C através de avalanches, eventualmente eu alcanço uma configuração C ′ que acaba se repetindo.
Entre os 2 instantes em que o sistema atingiu a configuração C ′ o sı́tio k relaxou
7
mk vezes. A quantidade de areia perdida por um sı́tio j qualquer durante esses
relaxamentos é dada por
X
mi ∆ij
i
Mas como o sistema saiu de uma configuração e voltou para ela durante esses
relaxamentos temos que
X
mi ∆ij = 0 ∀ j
i
escrevendo essa equação matricialmente temos
m∆
~ = ~0 ⇒ det ∆ = 0
Logo, se det ∆ 6= 0, toda configuração instável relaxa para uma configuração
estável.
B
Condição suficiente para a unicidade de uma
solução estacionária
Suponha que T seja uma matriz estocástica de um processo markoviano, tal que
∀ i, j∃k1 , . . . , km tais que T (i, k1 ), T (k1 , k2 ), . . . , T (kl , kl+1 ), . . . , T (km , j) 6= 0
ou seja, qualquer estado é acessı́vel pelos outros. E também, tal que só existe
um número finito N de estados.
Suponha agora que ~u é um auto-vetor de T a esquerda com auto-valor 1
(sempre existe pelo menos o auto-vetor ui = 1 ∀ i). Então ~u.T = ~u, ou de forma
explı́cita
X
uk T (k, j) = uj ∀ j
k
o que implica que
X
(uk − uj )T (k, j) = 0 ∀ j
k
Como existe um número finito de estados, o conjunto
M = {j|uj = min uk }
k
não é vazio. Se j ∈ M , então (uk − uj )T (k, j) ≥ 0, logo T (k, j) 6= 0 ⇒ uk =
uj . Portanto, T (k, j) 6= 0 ⇒ k ∈ M .
Mas então, M = {1, . . . , N }, pois por hipótese
∀ i, j∃k1 , . . . , km tais que T (i, k1 ), T (k1 , k2 ), . . . , T (kl , kl+1 ), . . . , T (km , j) 6= 0
(isso implica que se j ∈ M , então km ∈ M ⇒ km−1 ∈ M ⇒ . . . ⇒ i ∈ M ∀ i)
8
Segue que a multiplicidade geométrica do auto-valor 1 a esquerda é 1. Como
a multiplicidade geométrica é igual a esquerda e a direita (isso pode ser provado
usando o teorema de Jordan), então só existe um auto-vetor ~v de T a direita
com auto-valor 1. Além disso, qualquer outro auto-vetor a direita é ortonormal
a ~u e logo, tal que a soma de suas componentes é zero, o que implica que as
componentes de ~v são positivas. Portanto ~v é a única solução estacionária.
(Note que isso não impede a existência de auto-valores diferentes de 1 mas
com módulo 1)
B.1
Aplicação ao modelo de Dhar
A probabilidade do sistema se encontrar em uma configuração que não é recorrente tende a zero a medida que o sistema evolui, de forma que essas configurações podem ser desconsideradas quando estamos interessados no estado
estacionário.
O modelo para uma certa matriz ∆ passa a ser um processo markoviano,
cuja matriz estocástica é a matriz Φ (eq. 6). Temos que φ(g) 6= 0 se e somente
se g = ai para algum i. Logo Φij 6= 0 se e somente se gi = ak gj para algum k.
Da definição de G, dados gi , gj ∈ G, então
!
Y p
Y p
−1
k
k
gi gj =
ak ⇒ gi =
ak gj
k
k
Logo, denotando Φi,j por Φ(gi , gj ), temos Φ(ak gj , gj ) 6= 0, então
Φ(a1 gj , gj ), Φ(a21 gj , a1 gj ), . . . , Φ(ap11 gj , a1p1 −1 gj ), . . . ,
, Φ(ap11 ap22 gj , ap11 ap22 −1 gj ), . . . , Φ gi , a−1
N gi 6= 0
Logo o modelo que leva em conta somente as configurações recorrentes obedece a condição da seção anterior, o que implica que P~eq é o único estado estacionário.
9