UFPE-CCEN. Semestre 2011/1. Disciplina PGE-966: Processos estocasticos.
Prof. Andrei Toom
PERCOLAÇÃO
Observação teorica:
O livro mais recomendado é de A. Toom, ”Contornos, Conjuntos Convexos, e
Autômatos Celulares.” 23-o Colóquio Brasileiro de Matemática, IMPA, 2001.
Acima dos teoremas declarados no livro, precisamos o seguinte:
Teorema. Seja G um grafo desenhado no plano, onde cada elo e não-orientado, logo
ou aberto ou fechado. Seja A, B dois vertices deste grafo. Não existe caminho finito
aberto no grafo G conectando A e B se e somente se no grafo dual:
ou existe uma cerca aberta separando A de B ,
ou existe um caminho bi-infinito aberto separando A de B .
1
Exercı́cos sobre percolação
Problema 1.
j
6
-
O
i
Esta figura apresenta o grafo infinito que chamamos de “papel quadriculado”.
Em termos matemáticos é um grafo infinito com os vértices em Z2 formado pelo
conjunto de pares (i, j) , onde i e j são números inteiros. Qualquer vértice (i, j)
está conectado, através de elos, com quatro visinhos proximos. Cada elo está
aberto (nos ambos sentidos) com probabilidade ε e fechado (nos ambos sentidos)
com probaboilidade 1 − ε . Estados de elos diferentes são sempre independentes.
Seja O = (0, 0) a origem e o único fonte de liquido. Escolhemos um outro vertice
v = (i, j) 6= (0, 0) . Denotamos de P (v, ε) a probabilidade que existe um caminho
aberto, qual conecta os vertices v e O .
(a) Para quais v e quais ε temos P (v, ε) = 0 ?
(b) Para quais v e quais ε temos P (v, ε) = 1 ?
2
Problema 2.
j
6
i
i
i
i
i
i
-
i
i
i
i
Esta figura apresenta o mesmo grafo infinito que no problema 1 e que chamamos
de “papel quadriculado”. Em termos matemáticos é um grafo infinito com os
vértices em Z2 formado pelo conjunto de pares (i, j) , onde i e j são números
inteiros. Qualquer vértice (i, j) está conectado, através de elos, com quatro visinhos proximos. Cada elo está aberto (nos ambos sentidos) com probabilidade ε e
fechado (nos ambos sentidos) com probaboilidade 1−ε . Estados de elos diferentes
são independentes.
Neste problema temos 9 fontes de liquido marcados com circulos. Denotamos de
P a probabilidade que o conjunto de vertices molhados está infinito. Denotamos
de ε∗ o valor crı́tico de ε , a saber P é zero se ε < ε∗ e P é positivo se ε > ε∗ .
Provar que 0 < ε∗ < 1 .
3
Problema 3.
Temos o mesmo grafo chamado “papel quadriculado”. Como antes, cada elo está
aberto (nos ambos sentidos) com probabilidade ε e fechado (nos ambos sentidos)
com probaboilidade 1 − ε . Estados de elos diferentes são sempre independentes.
Denotamos de P (ε) a probabilidade que existem numeros inteiros x, y tais que
os vertices (x, −5) e (y, 5) são conectados com caminho aberto.
(a) Para quais ε temos P (ε) = 0 ?
(b) Para quais ε temos P (ε) = 1 ?
Problema 4.
Temos uma tira infinita do papel quadriculado. Seus vertices são pares (i, j) onde
i é qualquer número inteiro, mas j ∈ [0, 9] . Dois vertices são conectados com
elo na mesma condição como antes. Cada elo está aberto (nos ambos sentidos)
com probabilidade ε e fechado (nos ambos sentidos) com probaboilidade 1 − ε .
Estados de elos diferentes são sempre independentes. O vertice O = (0, 0) é o
único fonte do liquido. Denotamos de P (ε) a probabilidade que o conjunto de
verctices molhados é infinito..
(a) Para quais ε temos P (ε) = 0 ?
(b) Para quais ε temos P (ε) = 1 ?
4
Problema 5.
Temos grafo não orientado com conjunto de vertices - conjunto de números naturais. Definimos distância entre dois vertices assim: Dist(i, j) = |i − j| . Dois
vertices i, j são conectados com elo se Dist(i, j) ≤ 7. Cada elo está aberto
com probabilidade ε e fechado com probabilidade 1 − ε . Denotamos de P (ε) a
probabilidade que existe um caminho infinito aberto auto-evitando começando em
0 . Descobrir os valores de P (ε) para todos valores de ε .
Problema 6.
Temos grafo não orientado com conjunto de vertices {(i, j) : i = 0, 1, 2, . . . , j =
0, 1, 2, . . .} . Definimos distância entre dois vertices assim:
Dist((i1 , j1 ), (i2 , j2 )) = |i1 − i2 | + |j1 − j2 |.
Dois vertices v1 , v2 são conectados com elo se Dist(v1 , v2 ) = 1. Cada elo está
aberto com probabilidade ε e fechado com probabilidade 1 − ε . Denotamos
de P (ε) a probabilidade que existe um caminho infinito aberto auto-evitando
começando em (0, 0) . Denotamos de ε∗ a fronteira entre os valores de ε onde
P (ε) = 0 e os valores de ε onde P (ε) > 0 . Provar que 0 < ε∗ < 1 .
5
GABARITOS
Problema 1:
Se ε = 0, logo P (v, ε) = 0 para todos v .
Se 0 < ε < 1, logo 0 < P (v, ε) < 1 para todos v .
Se ε = 1, logo P (v, ε) = 1 para todos v .
Problema 2: usar metodos conhecidos.
Problema 3:
Se ε = 0 . logo P (ε) = 0 .
Se ε > 0 . logo P (ε) = 1
Problema 4:
Se ε = 1 . logo P (ε) = 1 .
Se ε < 1 . logo P (ε) = 0 .
Problema 5:
Se ε = 1 . logo P (ε) = 1 .
Se ε < 1 . logo P (ε) = 0 .
Problema 6: usar metodos conhecidos.
6