O Processo de Stavskaya com Comprimento Variável

UNIVERSIDADE FEDERAL DE PERNAMBUCO
^
CENTRO DE CIENCIAS
EXATAS E DA NATUREZA
TESE DE DOUTORADO EM MATEMÁTICA COMPUTACIONAL
O Processo de Stavskaya com Comprimento Variável
Frank Sinatra Gomes da Silva
Recife, agosto de 2013
O Processo de Stavskaya com Comprimento Variável
Frank Sinatra Gomes da Silva
Orientador: Andrei Toom
Co-Orientador: Alex Dias Ramos
Área de Concentração: Probabilidade
Tese de Doutorado apresentada ao colegiado do curso de
Pós-Graduacão em Matemática Computacional da Universidade
Federal de Pernambuco, como requisito parcial para obtenção do
Tı́tulo de Doutor em Matemática Computacional.
Recife, agosto de 2013
Catalogação na fonte
Bibliotecária Jane Souto Maior, CRB4-571
Silva, Frank Sinatra Gomes da
O processo de Stavskaya com comprimento variável /
Frank Sinatra Gomes da Silva. - Recife: O Autor, 2013.
x, 63 f. : il., fig.
Orientador: Andrei Toom.
Tese (doutorado) - Universidade Federal de Pernambuco. CCEN,
Matemática Computacional, 2013.
Inclui bibliografia e apêndice.
1. Probabilidade. 2. Processos Estocásticos. I. Toom, Andrei
(orientador). II. Título.
519.2
CDD (23. ed.)
MEI2013 – 111
UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE CI~?,NCIASEXATAS E DA NATUREZA
DOUTORADO EM MATEMATICA COMPUTACIONAL
"0PROCESSODE STAVSKAYA COM COMPRIMENTO
VARH VEL"
A Banca Examinadora composta pelos Professores: ANDRE1 TOOM
(Orientador e Presidente d a Banca Examinadora), do Departamento de
do Departamento de
Estatistica da UFPE; GAUSS MOUTINHO CORDEIRO,
Estatistica da UFPE; KLAUS LEITE PINTOVASCONCELLOS,
do Departamento de
LEMOS, do Departamento
Estatistica da UFPE; MANOELJose MACHADOSOARES
STOSIC,do Departamento de Estatistica e
de Matematica d a UFPE; e BORKO
Informatica d a UFRPE, considera o candidate:
Secretaria do Programa de Doutorado em Matematica Computational do
Centro de Ciencias Exatas e da Natureza d a Universidade Federal de
Pernambuco, aos 12 dias do mes de agosto de 2013.
-
Av. Prof. Luls Barros Freire, s/no, Cidade Universithria - CEP: 50670-901 - Recife PE
FONE/FAX: (81) 2126.8412- E-mail: [email protected] - Home Page: www.ppgmcufpe.br
i
Aos meus pais, Esequiel e Josefa.
Agradecimentos
A Deus e a seu filho Jesus, fonte de sabedoria.
Aos meus pais pelo esforço em educar-me e a minha famı́lia.
Ao Prezado Prof. Andrei Toom pela simplicidade e disponibilidade.
Ao Prof. Dr. Alex Dias Ramos e a Profª. Dra. Caliteia Santana de Sousa pela
atenção, paci^encia e disponibilidade com que me conduziram.
Aos amigos e colegas de curso, entre eles: Ana Carla, Manoel Wallace e Ronaldo
Ven^ancio, pelo companheirismo e partilha de vida e conhecimento.
Aos professores do Programa de doutorado em Matemática Computacional pela
partilha do conhecimento.
Ao Prof.
Dr.
Klaus Vasconcellos pelo ensino da disciplina Probabilidade
Avançada.
Ao coordenador do Programa de Pós-Gradução em Matemática Computacional
Prof. Dr. Sı́vio Melo pela atenção concedida aos alunos e ao vice coordenador
deste programa Prof. Dr. Josenildo dos Santos.
Às secretárias Heloisa Henrique da Silva e Conceição Couto pelo profissionalismo.
Aos Professores Gauss Cordeiro, Klaus Vasconcellos, Manoel Lemos e Borko
Stosic por suas contribuições a este trabalho.
Ao meu compadre Dionı́sio e minha comadre Angela pelos agradáveis encontros
nos fins de semana ajudando a suavisar minha jornada.
ii
Resumo
Esta tese tem a intenção de ajudar a descobrir, até que ponto podemos confiar em
simulações computacionais no estudo de processos aleatórios com interação local.
Para isto, examinamos uma nova versão do bem conhecido processo de Stavskaya
clássico, que é um processo em tempo discreto, análogo ao processo de contato.
Tal como a maioria dos processos aleatórios estudados até agora, Stavskaya é de
comprimento constante, isto é, seus componentes não aparecem ou desaparecem
no decurso do seu funcionamento. O processo que estudamos aqui é similar ao de
Stavskaya; ele também é de tempo discreto e seus estados também são sequ^encias
bi-infinitas, cujos termos assumem apenas dois valores, que denotamos por ⊖ e ⊕,
e a medida concentrada na configuração “todos mais”, que vamos denotar por 𝛿⊕ ,
também é invariante. Entretanto, o operador, chamado VarStav , estudado aqui,
é de comprimento variável, ou seja, componentes podem aparecer ou desaparecer
no decurso do seu funcionamento.
O operador VarStav é uma composição dos seguintes dois operadores. O primeiro operador, chamado “nascimento”, cria uma nova componente no estado ⊕
entre cada duas componentes vizinhas com probabilidade 𝛽, independente do que
acontece nos outros lugares. O segundo operador, chamado “Matança”, age assim:
sempre que um ⊕ é vizinho esquerdo de um ⊖, ele desaparece (como se destruı́do
pelo seu vizinho direito) com probabilidade 𝛼 independentemente dos estados de
outros componentes.
iii
iv
Provamos, para todo 𝛼 < 1 e 𝛽 > 0, que a sequ^encia de medidas 𝛿⊖ ( VarStav )𝑡
(o resultado de 𝑡 aplicações iterativas de VarStav na medida inicial 𝛿⊖ concentrada na configuração “todos menos”), tende para a medida 𝛿⊕ , concentrada na
configuração “todos mais”, quando 𝑡 → ∞. Tal comportamento é frequentemente
chamado ergódico. Entretanto, as simulações de Monte Carlo e aproximação do
caos, que foram realizadas, comportam-se como se 𝛿⊖ ( VarStav )𝑡 tendesse a 𝛿⊕
mais lentamente para alguns valores de 𝛼, 𝛽 ∈ (0, 1), do que para outros. Baseados nestes resultados numéricos, conjecturamos que VarStav tem fase, mas não
no sentido usual, como acontece no processo de Stavskaya clássico.
Palavras-chave: Processos aleatórios, comprimento variável, aproximação do
caos, ergodicidade, método Monte Carlo.
Abstract
This thesis is intended to help to figure out, to which extent may we rely on
computer simulations in the study of random processes with local interaction.
For this purpose we examine a new version of the well-known Stavskaya process,
which is a discrete-time analog of the well-known contact processes. Like the bulk
of random processes studied till now, Stavskaya process is constant-length, that is
its components do not appear or disappear in the course of its functioning. The
process, which we study here, is similar to Stavskaya; it is also discrete-time and
its states also are bi-infinite sequences, whose terms take only two values, which we
denote by “minus”and “plus”, and the measure concentrated in the configuration
“all pluses”also is invariant. However, the operator, called VarStav and studied
here, is variable-length, which means that components may appear and disappear
in the course of its functioning.
The operator VarStav is a composition of the following two operators. The first
operator, called “birth”, creates a new component in the state “plus”between every
two neighboring components with probability 𝛽 independently from what happens
at other places.
The second operator, called “murder”, acts thus: whenever a
plus is a left neighbor of a minus, this plus disappears (as if killed by its right
neighbor) with probability 𝛼 independently from states of other components.
We prove for all 𝛼 < 1 and 𝛽 > 0 that the sequence of measures 𝛿⊖ ( VarStav )𝑡
(the result of 𝑡 iterative applications of VarStav to the initial measure 𝛿⊖ concentrav
vi
ted in the configuration “all minuses”) tends to the measure 𝛿⊕ concentrated in the
configuration ”all pluses”as 𝑡 → ∞. Such behavior is often called ergodic. However, the Monte Carlo simulations and Chaos approximations, which we performed,
behave as if 𝛿⊖ ( VarStav )𝑡 tended to 𝛿⊕ much slower for some 𝛼, 𝛽 ∈ (0, 1) than
for some others. Based on these numerical results, we conjecture that VarStav
has phases, but not in that simple sense as the classical Stavskaya process.
Key words: particle random process, variable length, Monte Carlo, Chaos
approximation, mean-field approximation, metastability.
Sumário
1 Introdução
1.1
O Processo de Stavskaya Clássico: sua origem e propriedades . . . .
1.1.1
1.2
3
O processo de Stavskaya clássico: modelagem computacional 10
Descrição de nosso processo . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1
Redução para o processo Singular . . . . . . . . . . . . . . . 12
2 Teorema principal
2.1
8
15
Prova do Teorema principal . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1
Medidas sobre Z+ . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2
Passos e escadas . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.3
𝒩 -operadores . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.4
Os 𝒩 -operadores Sing e Sing 𝑟 . . . . . . . . . . . . . . . . 29
2.1.5
A medida invariante de Sing 𝑟 . . . . . . . . . . . . . . . . . 34
3 Aproximação do caos
38
3.1
Aproximação do caos para o PSC . . . . . . . . . . . . . . . . . . . 39
3.2
Aproximação do caos para o PSCV . . . . . . . . . . . . . . . . . . 43
vii
viii
4 Simulação de Monte Carlo do processo Singular
4.1
48
̂︀
Simulação de IE(𝑚𝑎𝑥(𝑆
𝑡 )) . . . . . . . . . . . . . . . . . . . . . . . 51
5 Conclusões
56
A Cálculos da aproximação do caos para o PSCV
58
Lista de Figuras
2.1
Os cı́rculos pretos mostram os valores de 𝜆𝑟 que é a medida invariante normalizada do 𝒩 -operador Sing 𝑟 para o caso 𝑞 = 3 e 𝑟 = 8
em escala logarı́tmica. As linhas ligando os pontos pretos são apenas para auxiliar a impressão visual. A parte esquerda do gráfico
com números de zero até 𝑞 − 1 representa a garrafa onde o g^enio do
folclore árabe foi inicialmente capturado. Leva muito tempo para ele
alcançar o gargálo 𝑞, mas uma vez que ele o atinge, ele facilmente
cresce exponencialmente.
. . . . . . . . . . . . . . . . . . . . . . . 31
3.1
Comportamento limite para a aproximação do caos no PSC. . . . . 42
3.2
Comportamento limite para a aproximação do caos no PSCV. . . . 47
4.1
Estimação das linhas de transição entre ergodicidade e não ergodicidade para PSCV, obtidas pela aproximação do caos (caos) e Método
de Monte Carlo (M.C.) . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2
Comportamento da estimativa da média de 𝑚𝑎𝑥(𝑆𝑡 ), para 𝛼 =
0, 1 𝑖, 𝑖 = 1, 2, . . . , 9 e 𝛽 variando de 0 até 0, 13. Para cada par
de 𝛼 e 𝛽, foram realizados 100 experimentos independentes. . . . . . 54
4.3
Gráfico que mostra, para 𝛼 = 0, 5 e 𝛽 = 0, 02, os valores de 𝑆𝑡 , na
simulação do processo Singular
. . . . . . . . . . . . . . . . . . . . 55
ix
Lista de Sı́mbolos
Conjunto dos números inteiros não negativos, p.4.
Conjunto dos números inteiros, p.4.
Conjunto dos números reais, p.4.
Alfabeto, um conjunto finito, não vazio,
formado por letras, p.4.
Z
𝒜
Espaço configuracional, p.4.
𝑊
Palavra, uma sequ^encia finita de letras, p.4.
|𝑊 |
Comprimento da palavra 𝑊 , p.4.
Λ
Palavra vazia, p.4.
𝑑𝑖𝑐(𝒜)
Dicionário, conjunto de palavras em 𝒜, p.4.
𝑐𝑜𝑛𝑐𝑎𝑡(𝑊1 , 𝑊2 , . . . , 𝑊𝑛 ) Concatenação das palavras 𝑊1 , 𝑊2 , . . . , 𝑊𝑛 , p.4.
𝜇(𝑊 )
Frequ^encia relativa da palavra 𝑊 em uma
medida 𝜇, p.5.
ℳ𝒜
Conjunto das medidas uniformes em 𝒜, p.5.
𝛿𝑎
Medida concentrada na configuração “todos 𝑎”, p.6.
𝛿𝑛
Medida de probabilidade concentrada no
estado 𝑛 ∈ Z+ , p.13.
Z
Z
𝐷 : 𝒜 −→ 𝒜
Operador determinı́stico, age em configurações, p.6.
𝐴 : ℳ𝒜 −→ ℳ𝒜
Operador aleatório, age em medidas, p.6.
Z𝑛
Classe dos restos módulo n, p.10.
IE(𝑇 )
Esperança da variável aleatória 𝑇 , p.10.
𝒞
Operador caótico, p.38.
𝑡
𝑓
A 𝑡–ésima iteração de 𝑓 , p.39.
𝑈
Variável aleatória com distribuição uniforme
no intervalo (0, 1), p.28.
Bin (𝑛, 𝑝)
Variável aleatória com distribuição binomial
com par^ametros 𝑛 e 𝑝, p.28.
Z+
Z
R
𝒜
x
1
𝜇𝑛
𝜌
𝑉 −→ 𝑊
𝒩
Δ𝑏𝑖𝑟𝑡ℎ
Flip 𝛽
𝜇(𝑦 𝑥)
conf
𝐿
𝑆
Stav
Birth inter
Murder inter
𝛽
Λ −→ ⊕
𝛼
⊕⊖ −→ ⊖
VarStav
Single
Birth
Murder
S𝑡
Sing
Sing 𝑟
𝜆𝑟
M
Sequ^encia de medidas sobre Z+ , p.18.
Notação para operadores de substituição,
em que 𝑉, 𝑊 são palavras e 𝜌 ∈ [0, 1], p.8.
Conjunto de medidas de probabilidade
sobre Z+ , p.13.
Variável binomial definida a partir de Birth, p.13.
Operador de interação aletório com
comprimento constante, usado no PSC, p.8.
Probabilidade condicional de ir ao estado 𝑦
a partir de 𝑥, p.13.
Qualquer configuração em {⊖, ⊕}Z , p.14.
Conjunto inferior em Z+ , p.17.
Conjunto superior em Z+ , p.17.
Operador de interação determinı́stico com
comprimento constante, usado no PSC, p.8.
Operador de interação nascimento, p.11.
Operador de interação matança, p.11.
Operador de interação nascimento na
notação de operadores de substituição, p.11.
Operador de interação matança na
notação de operadores de substituição, p.11.
Operador de interação que define
nosso processo, p.12.
𝒩 -operador Singular, p.13.
𝒩 -operador Nascimento, p.13.
𝒩 -operador Matança, p.13.
Variável aleatória com distribuição
𝛿0 ( Single )𝑡 , 𝑝.15.
𝒩 -operador local chamado sing, p.29.
𝒩 -operador local definido a partir de Sing , p.30.
Medida invariante normalizada de Sing 𝑟 , p.34.
Matriz de transição definida a partir de Sing 𝑟 ,
p.34.
2
I
0
𝛽 * (𝛼)
max(𝑆𝑡 )
Ø
i.i.d.
̂︀
IE(𝑚𝑎𝑥(𝑆
𝑡 ))
Matriz Identidade de ordem 𝑟 + 1, p.35.
Matriz Nula com 𝑟 + 1 colunas, p.35.
Valor crı́tico na aproximação do caos para
o nosso processo, p.43.
Máximo do procedimento imitação,
para 𝑡 de zero a 10000, p.52.
Medida nula, p.21.
Independente e identicamente distribuı́do, p.28.
Estimativa da média de max(𝑆𝑡 ), p.52.
Capı́tulo 1
Introdução
Até que ponto podemos confiar em simulação computacional no estudo de processos aleatórios? A import^ancia desta questão é inegável. A famosa abordagem
de Kolmogorov-Smirnov e suas modificações posteriores, especialmente aquelas
multidimensionais (veja por exemplo [13] e trabalhos citados nele), são muito importantes. O número de dimensões em muitos estudos de processos aleatórios, de
acordo com nossas observações, é fixo e frequentemente pequeno, enquanto que em
processos com interação local ele é infinito (em estudos teóricos) ou grande (em
simulações computacionais). Embora alguns estudos valiosos tenham sido conduzidos na área de processos aleatórios (veja, por exemplo [1, 3, 4, 10, 11, 12]), ainda
não temos uma teoria geral. Neste contexto, a construção de diversos exemplos
pode ser útil para a compreensão destas ideias. A meta desta tese é estudar um
exemplo de um novo tipo, isto é, um processo de comprimento variável, para ilustrar um aparente conflito entre simulação computacional de processos aleatórios e
seu estudo teórico.
O processo que estudamos aqui é de comprimento variável, isto é, seus componentes podem aparecer ou desaparecer ao longo de seu funcionamento. Algumas
classes destes processos t^em sido estudadas em [15, 16, 17, 18, 30, 31, 32]. A base
teórica para esses estudos foi estabelecida em [20, 33].
3
4
Como no processo de Stavskaya clássico, nosso processo é uma disputa entre
duas tend^encias, nascer ou morrer, ou seja: por um lado ⊕ “nascem”, mas por
outro lado, eles são “assassinados” e desejamos descobrir qual tend^encia prevalecerá.
Ao longo do texto vamos denotar R como sendo o conjunto dos números reais,
Z o conjunto dos números inteiros e Z+ o conjunto dos inteiros não negativos. O
conjunto finito e não vazio 𝒜 será chamado de alfabeto e seus elementos de letras.
Uma sequ^encia finita de letras será chamada palavra e uma palavra genérica será
indicada por 𝑊 . Denotamos por |𝑊 | o comprimento da palavra 𝑊 , que é definido pelo número de letras que a constitui. A palavra vazia, cujo comprimento é
zero, será representada por Λ. O conjunto de palavras em um alfabeto 𝒜 é chamado dicionário de 𝒜 e denotado por 𝑑𝑖𝑐(𝒜). Dada uma sequ^encia de palavras
𝑊1 , 𝑊2 , . . . , 𝑊𝑛 , indicamos por 𝑐𝑜𝑛𝑐𝑎𝑡(𝑊1 , 𝑊2 , . . . , 𝑊𝑛 ) e denominamos sua concatenação a palavra obtida escrevendo todas essas palavras uma após a outra na ordem em que foram listadas. Por exemplo, a concatenação de 𝑊1 = (𝑎1 , 𝑎2 , . . . , 𝑎𝑛 )
e 𝑊2 = (𝑏1 , 𝑏2 , . . . , 𝑏𝑚 ), é a palavra, (𝑎1 , 𝑎2 , . . . , 𝑎𝑛 , 𝑏1 , 𝑏2 , . . . , 𝑏𝑚 ), cujo comprimento é igual a 𝑛 + 𝑚. Note que, quando a palavra vazia é concatenada com
qualquer palavra 𝑊 , o resultado é a palavra 𝑊 . Formalmente,
∀ 𝑊,
𝑐𝑜𝑛𝑐𝑎𝑡(Λ, 𝑊 ) = 𝑐𝑜𝑛𝑐𝑎𝑡(𝑊, Λ) = 𝑊,
(1.1)
ou seja, a palavra vazia é o elemento neutro para a operação de concatenação.
Denominamos de espaço o conjunto dos números inteiros Z, cujos elementos são
as componentes. Vamos denotar 𝒜Z o espaço configuracional o qual é o conjunto
de sequ^encias bi-infinitas cujos termos são elementos de 𝒜. Denomina-se cilindro
fino definido pelos 𝑎𝑖’𝑠 ao conjunto 𝒞 da forma
𝒞 = {𝑥 ∈ 𝒜Z : 𝑥𝑖 = 𝑎𝑖 , ∀𝑖 ∈ [𝑚, 𝑛]},
(1.2)
5
em que 𝑎𝑖 ∈ 𝒜 e 𝑚, 𝑛 ∈ Z, 𝑚 ≤ 𝑛. Na 𝜎–álgebra gerada por esses cilindros finos
vamos considerar medidas de probabilidade, ou seja, medidas normalizadas em 𝒜Z .
Denominamos uma medida de uniforme se esta é invariante sob translações. Com
uma medida uniforme 𝜇 e uma palavra qualquer 𝑊 = (𝑎1 , 𝑎2 , . . . , 𝑎𝑛 ) podemos
escrever, para todo 𝑖 ∈ Z,
𝜇(𝑊 ) = 𝜇(𝑎1 , 𝑎2 , . . . , 𝑎𝑛 ) = 𝜇(𝑥𝑖+1 = 𝑎1 , 𝑥𝑖+2 = 𝑎2 , . . . , 𝑥𝑖+𝑛 = 𝑎𝑛 ),
(1.3)
em que 𝑎1 , 𝑎2 , . . . , 𝑎𝑛 é uma sequ^encia de letras que formam a palavra 𝑊 . Vamos
indicar por ℳ𝒜 o conjunto de medidas uniformes em 𝒜Z e, por converg^encia
em ℳ𝒜 , a converg^encia em todas as palavras de 𝑑𝑖𝑐(𝒜). Portanto a primeira
igualdade em (1.3) serve como notação abreviada para qualquer medida uniforme
normalizada em ℳ𝒜 . Como 𝜇 é uniforme e independe de 𝑖, a equação (1.3) é a
frequ^encia relativa da palavra 𝑊 nessa medida. Por exemplo, se 𝑊 = {𝑎} então
𝜇(𝑊 ) = 𝜇(𝑎) é a frequ^encia relativa da letra 𝑎 na medida 𝜇. Para 𝜇(𝑊 ) ser
consistente devemos ter, ∀ 𝑊 ∈ 𝑑𝑖𝑐(𝒜), 𝜇(𝑊 ) ≥ 0 e
∑︁
∑︁
𝜇(𝑊 ) =
𝜇(𝑊, 𝑎) =
𝜇(𝑎, 𝑊 ),
𝑎∈𝒜
(1.4)
𝑎∈𝒜
em que (𝑊, 𝑎) e (𝑎, 𝑊 ) podem ser entendidos como concatenações da palavra
𝑊 com a palavra formada pela letra 𝑎 em que esta última se encontra em duas
posições possı́veis. Suponhamos, por simplicidade, que 𝑊 = Λ e 𝒜 = {𝑎1 , 𝑎2 }.
Dessa forma, usando (1.4), podemos escrever que
𝜇(Λ) = 𝜇(Λ, 𝑎1 ) + 𝜇(Λ, 𝑎2 ).
(1.5)
Considerando (1.5) e usando (1.1), obtemos
𝜇(Λ) = 𝜇(𝑎1 ) + 𝜇(𝑎2 ).
Como
𝜇(𝑎1 ) + 𝜇(𝑎2 ) = 1,
(1.6)
6
temos que 𝜇(Λ) = 1, ou seja, a medida 𝜇 sobre a palavra vazia é 1. Denominamos
uma 𝛿–medida e indicamos por 𝛿𝑎 a medida concentrada na configuração em que
todas as componentes são iguais a 𝑎, em que 𝑎 ∈ 𝒜.
A seguir, vamos definir operadores determinı́sticos e aleatórios. Um operador
determinı́stico 𝐷 é uma função que leva configurações em configurações, ou seja,
𝐷 : 𝒜Z −→ 𝒜Z age em configurações. Seja 𝑗1 , 𝑗2 , . . . , 𝑗𝑛 ∈ Z uma lista a qual
denominamos vetores vizinhos e sejam 𝑗 + 𝑗1 , 𝑗 + 𝑗2 , . . . , 𝑗 + 𝑗𝑛 os pontos aos quais
denominamos os vizinhos de j. 𝐷 transforma qualquer configuração 𝑥 em uma
configuração 𝐷𝑥, em que a 𝑥𝑗 –ésima coordenada é
(𝐷𝑥)𝑗 = 𝑓 (𝑥𝑗+𝑗1 , 𝑥𝑗+𝑗2 , . . . , 𝑥𝑗+𝑗𝑛 )
(1.7)
∀𝑗 ∈ Z e 𝑓 uma função de 𝒜𝑛 em 𝒜. Um operador 𝐴 é denominado aleatório
ou probabilı́stico se ele age em medidas, isto é, 𝐴 : ℳ𝒜 −→ ℳ𝒜 . Definiremos
definir monotonicidade para esses operadores. Primeiro para o determinı́stico.
Seja 𝑥, 𝑦 ∈ 𝒜Z . Dizemos que a configuração 𝑥 precede (sucede) a configuração 𝑦 e
indicamos 𝑥 ≺ 𝑦 (𝑥 ≻ 𝑦), quando 𝑥𝑖 ≤ 𝑦𝑖 (𝑥𝑖 ≥ 𝑦𝑖 ) para todo 𝑖 ∈ Z. Dizemos que
𝐷 é monótono se
𝑥 ≺ 𝑦 =⇒ 𝐷𝑥 ≺ 𝐷𝑦.
Equivalentemente, como 𝐷 é definido em termos de 𝑓 em (1.7), definimos, também,
que
𝑥1 ≤ 𝑦1 , · · · , 𝑥𝑛 ≤ 𝑦𝑛 =⇒ 𝑓 (𝑥1 , · · · , 𝑥𝑛 ) ≤ 𝑓 (𝑦1 , · · · , 𝑦𝑛 ).
Vamos agora definir para o operador aleatório. Uma função real 𝐹 sobre 𝒜Z é
denominada monótona quando
𝑥 ≺ 𝑦 =⇒ 𝐹 (𝑥) ≤ 𝐹 (𝑦).
Seja 𝜇 e 𝜈 duas medidas sob nosso espaço configuracional. Dizemos que 𝜇 ≺ 𝜈 se
7
para cada função monótona 𝐹, temos
IE(𝐹 | 𝜇) ≤ IE(𝐹 | 𝜈),
em que IE(𝐹 | ·) é a esperança matemática de 𝐹 na respectiva medida. Uma
sequ^encia de medidas 𝜇𝑛 é não decrescente se 𝜇𝑛 ≺ 𝜇𝑛+1 . Um operador 𝑃 sob ℳ𝒜
é denominado monótono se
𝜇 ≺ 𝜈 =⇒ 𝜇𝑃 ≺ 𝜈𝑃.
A palavra processo aqui significa uma sequ^encia de medidas uniformes normalizadas 𝜇𝑛 = 𝜇𝑃 𝑛 , sendo 𝜇𝑃 𝑛 o resultado de 𝑛 aplicações iterativas de um operador
𝑃 em uma medida inicial 𝜇. Uma medida 𝜇 é invariante para 𝑃 se 𝜇𝑃 = 𝜇 e,
além disso, diremos que 𝑃 é ergódico se lim 𝜇𝑃 𝑡 existe e é o mesmo para toda
𝑡→∞
medida 𝜇. Caso contrário, 𝑃 é dito não ergódico.
Vamos escrever eventos e funções após medidas e operadores entre medidas e
eventos, isto é, se 𝑃 e 𝑄 são dois operadores quaisquer, 𝜇 uma medida e 𝐸 um
evento, então 𝜈 = 𝜇𝑃 𝑄 é a medida obtida de 𝜇 por aplicação, primeiro do operador
𝑃 e depois do operador 𝑄. Assim 𝜈(𝐸) é o valor da medida 𝜈 no evento 𝐸. Um
operador 𝑃 agindo em ℳ𝒜 é denominado operador linear se para cada 𝑎, 𝑏 ∈ R e
quaisquer 𝜇, 𝜈 ∈ ℳ𝒜
(︀
)︀
(︀
)︀
(︀
)︀
𝑎 𝜇 + 𝑏 𝜈 𝑃 = 𝑎 𝜇𝑃 + 𝑏 𝜈𝑃 .
Operadores ou processos os quais criam ou eliminam componentes são denominados operadores de comprimento variável ou processos de comprimento variável,
respectivamente. Caso contrário, denominaremos de operadores de comprimento
constante ou processos de comprimento constante.
Até aqui, denominamos todas as funções de ℳ𝒜 em ℳ𝒜 de operadores; Vamos
a partir de agora denominá-las de operadores de interação, reservando a palavra
8
“operadores” para outro propósito. Em particular, os operadores de Stavskaya e
o operador VarStav , definido na Seção 1.2, que é objeto de trabalho desta tese,
são operadores de interação. Os operadores de interação, com os quais lidamos
aqui, são casos particulares da classe dos operadores de substituição, definidos de
𝜌
modo geral em [20, 33] e denotados por 𝑉 −→ 𝑊 , em que 𝑉, 𝑊 são palavras e
𝜌 ∈ [0, 1] é um número real. Esta fórmula representa um operador de interação,
que substitui qualquer entrada da palavra 𝑉, numa configuração, por uma palavra
𝑊, com uma probabilidade 𝜌.
1.1
O Processo de Stavskaya Clássico: sua origem e propriedades
O Processo de Stavskaya Clássico (PSC) usa como conjunto de componentes o
conjunto de números inteiros Z. Cada componente 𝑘 tem duas letras possı́veis,
denominadas menos e mais, cuja representação é ⊖ e ⊕. Dessa maneira, o espaço
configuracional é {⊖, ⊕}Z .
O PSC é definido a partir de dois operadores de interação especı́ficos, ambos
são de comprimento constante: flip denotado por Flip 𝛽 : ℳ{⊖,
⊕}
−→ ℳ{⊖,
⊕}
e stav denotado por Stav : {⊖, ⊕}Z −→ {⊖, ⊕}Z . Flip 𝛽 é um operador de
interação aleatório, o qual torna cada ⊖ em ⊕ com probabilidade 𝛽, independentemente do que acontece nas outras componentes. Stav é um operador de
interação determinı́stico o qual pode ser definido pela seguinte regra
{︂
⊕, se 𝑥𝑘 = 𝑥𝑘+1 = ⊕
( Stav 𝑥)𝑘 =
⊖,
c.c.
(1.8)
∀ 𝑥 ∈ 𝒜Z , 𝑘 ∈ Z. Como 𝒜 = {⊖, ⊕}, por (1.8) temos quatro possibilidades
para o operador de interação Stav e usando a notação dada em (1.7), podemos
9
escrever
( Stav 𝑥)𝑘 = 𝑓 (⊕, ⊕) = ⊕,
( Stav 𝑥)𝑘 = 𝑓 (⊕, ⊖) = ⊖,
( Stav 𝑥)𝑘 = 𝑓 (⊖, ⊕) = ⊖,
( Stav 𝑥)𝑘 = 𝑓 (⊖, ⊖) = ⊖.
Dessa maneira, Stav favorece a letra ⊖, pois se um ⊕ é vizinho esquerdo de
um ⊖, então, após sua aplicação a componente na letra ⊕ se torna ⊖, porém a
componente na letra ⊖ nunca se torna ⊕. Usando nossas notações, o PSC pode ser
definido como a superposição, Stav Flip 𝛽 , aplicada iterativamente a uma medida
inicial 𝜇𝑖𝑛𝑖𝑐 , ou seja
𝜇𝑖𝑛𝑖𝑐 ( Stav Flip 𝛽 )𝑡
(1.9)
em que a cada passo de tempo a ação de Stav ocorre antes de Flip 𝛽 .
O PSC foi introduzido em [22] como um modelo para redes neurais e é um dos
primeiros exemplos de processos aleatórios, em que a exist^encia de transição fásica
e valor crı́tico foram provadas de forma rigorosa.
Vamos denotar por 𝛿⊕ e 𝛿⊖ as medidas concentradas nas configurações em que
todas as componentes são iguais a ⊕ e ⊖, respectivamente. É certo que 𝛿⊕ é uma
medida invariante, uma vez que se iniciamos o processo em “todos mais” ele nunca
muda. Esse processo apresenta comportamentos diferentes para valores pequenos
de 𝛽 e para valores grandes de 𝛽. Como observado em [22] o PSC é érgodico se
𝛽 é bastante grande, isto é, ele admite uma única medida invariante, 𝛿⊕ . Toom
em [25] provou que para valores bastante pequenos de 𝛽 o PSC possui pelo menos
uma medida invariante não–trivial, diferente de 𝛿⊕ , que denotaremos aqui por
𝜇𝑖𝑛𝑣 . Este fato tinha sido sugerido por simulação computacional no artigo original,
porém sem uma prova formal. Na verdade, todas as simulações computacionais
do PSC realizadas até então estão de acordo pelo menos qualitativamente, com os
resultados teóricos. Um fato interessante do PSC é sua conexão com problemas
10
da teoria de percolação, veja por exemplo [27] e [29].
1.1.1
O processo de Stavskaya clássico: modelagem computacional
A modelagem computacional, embora não rigorosa, constitui um modo adequado
para estudar processos aleatórios. Para se estudar o PSC computacionalmente,
uma versão finita dele se faz necessária, uma vez que a memória computacional
é finita. Para este estudo podemos fazer a seguinte suposição: versões finitas de
processos aleatórios convergem rapidamente se, e somente se, processos aleatórios
infinitos análogos são ergódicos.
A versão finita do processo de Stavskaya usa como conjunto de componentes
Z𝑛 = {0, . . . , 𝑛 − 1}, que é a classe dos restos módulo 𝑛. Os operadores permanecem os mesmos do PSC. Para a modelagem computacional do PSC o processo
converge rapidamente com 𝛽 grande, enquanto para 𝛽 pequeno o processo converge
lentamente.
Denotemos por 𝑥𝑡𝑖 a componente 𝑥𝑖 no tempo 𝑡. Introduzimos uma nova variável
𝑇 definida como o primeiro 𝑡, para qual ∀ 𝑖 ∈ Z𝑛 : 𝑥𝑡𝑖 = ⊕. Agora, denotamos IE(𝑇 )
a esperança matemática de 𝑇 . Assim, para 𝛽 bastante grande, pelos resultados
obtidos em [22], podemos escrever que
𝑐1 ln 𝑛 < IE(𝑇 ) < 𝑐2 ln 𝑛 + 𝑐3
(1.10)
e, para 𝛽 bastante pequeno, pelos resultados obtidos em [25], temos
exp(𝑐4 𝑛) < IE(𝑇 ) < exp(𝑐5 𝑛),
(1.11)
em que 𝑐𝑗 (𝑗 = 1, . . . , 5) são par^ametros positivos dependendo apenas de 𝛽. Dessa
maneira, processos finitos mostram algum tipo de transição de fase no sentido do
tempo médio convergir lentamente (1.10) ou rapidamente (1.11).
11
1.2
Descrição de nosso processo
A nossa atenção é concentrada num processo com comprimento variável, análogo
ao processo de Stavskaya, o qual será denominado de Processo de Stavskaya com
Comprimento Variável e denotado por PSCV. Este processo possui um conjunto
de componentes e um espaço configuracional id^enticos àqueles definidos na Seção
1.1. O PSCV é definido a partir da superposição de dois operadores de interação,
cada um também de comprimento variável, nascimento e matança.
𝛽
O operador de substituição nascimento, Λ −→ ⊕, com par^ametro 𝛽 ∈ [0, 1]
será denotado por Birth inter , em que inter significa interação. Ele age da seguinte
forma: entre quaisquer duas componentes vizinhas aparece uma nova componente
⊕, com probabilidade 𝛽, independentemente do que acontece nas outras componentes. Se considerarmos um processo similar finito, cada ação do operador de
interação nascimento produz uma letra ⊕, o que aumentaria o comprimento da
configuração por um. Este operador de interação transforma cada medida uniforme 𝜇, com 𝜇(⊕) = 𝑥, em uma medida uniforme 𝜇 Birth inter com
𝑥+𝛽
𝜇 Birth inter (⊕) =
.
(1.12)
1+𝛽
Em outras palavras, (1.12) pode ser interpretado como a frequ^encia relativa de ⊕
após a aplicação de Birth inter .
𝛼
O operador de substituição matança, ⊕⊖ −→ ⊖, com par^ametro 𝛼 ∈ [0, 1],
será denotado por Murder inter . Ele age da seguinte forma: cada ⊖ mata seu
vizinho esquerdo com probabilidade 𝛼 se este vizinho é ⊕, independentemente do
que acontece nas outras componentes. Se considerarmos um processo similar finito,
cada ação de eliminação de um ⊕, decresceria o comprimento da configuração por
um. Da mesma maneira que em Birth inter , este operador de interação transforma
cada medida uniforme 𝜇, com 𝜇(⊕) = 𝑦, em uma medida uniforme 𝜇 Murder inter
12
tal que
𝑦 − 𝛼𝑧
,
(1.13)
1 − 𝛼𝑧
em que 𝑧 = 𝜇(⊕, ⊖) é a densidade de ⊕ que é vizinho esquerdo de ⊖. Em
𝜇 Murder inter (⊕) =
outras palavras, (1.13) é a frequ^encia relativa de ⊕ após aplicação do operador
de interação matança. Neste caso, 𝛼𝑧 é a proporção de ⊕ que “morre” sendo
vizinho esquerdo de ⊖, depois da aplicação de Murder inter . Finalmente, definimos
o operador de interação VarStav como esta composição:
VarStav = Birth inter ∘ Murder inter .
O PSCV é definido pela seguinte sequ^encia de medidas
𝜇𝑡 = 𝜇𝑖𝑛𝑖𝑐 ( VarStav )𝑡 ,
(1.14)
em que desejamos saber o que acontece quando 𝑡 → ∞. A medida 𝛿⊕ é uma medida
invariante para o PSCV. De fato, se 𝜇𝑖𝑛𝑖𝑐 = 𝛿⊕ , as letras destas componentes nunca
mudam no decorrer do tempo e, caso surjam uma ou mais componentes, estas
nunca serão ⊖, impossibilitando que algum ⊖ mate algum ⊕ que seja seu vizinho
esquerdo.
1.2.1
Redução para o processo Singular
É bem conhecido que o problema de ergodicidade e alguns outros problemas importantes são algoritmicamente insolúveis, até mesmo para tradicionais operadores de
comprimento constante com interação local conforme observado em [7, 14], por isso
são insolúveis para a classe mais ampla de operadores com comprimento variável.
Tal problema torna-se solúvel apenas quando os operadores em questão tem alguma propriedade conveniente. O operador de interação VarStav é não-linear,
mas sua propriedade especialmente conveniente é que ele pode ser reduzido a uma
13
sequ^encia bi-infinita de processos independentes e identicamente distribuı́dos, cada
um determinado por um operador linear, denominado 𝑆𝑖𝑛𝑔𝑢𝑙𝑎𝑟, e denotado por
Single , que vamos apresentar. Parece que a maioria dos usuais processos com
tempo contı́nuo (exemplos podem ser vistos em [8, 9]), e seus análogos com tempo
discreto (exemplos podem ser observados em [22, 26, 28]), não t^em esta propriedade.
A partir de agora, usaremos a palavra operador (sem qualquer outra denominação adicional) para qualquer cadeia de Markov homog^enea em tempo discreto,
com o conjunto de estados em Z+ (ou seu subconjunto). Também denotamos por
𝒩 o conjunto de medidas de probabilidade sobre Z+ . Dessa forma, qualquer operador age de 𝒩 em 𝒩 e é, essencialmente, uma cadeia de Markov, cujos elementos
de sua matriz de transição são denotados por 𝜇(𝑦 𝑥) : a probabilidade condicional
de ir ao estado 𝑦 se estamos no estado 𝑥. Em particular, para qualquer natural 𝑛
denotamos por 𝛿𝑛 a medida de probabilidade sobre Z+ concentrada no estado 𝑛.
Dada uma sequ^encia de medidas 𝛿⊖ ( VarStav )𝑡 sobre ℳ𝒜 , definiremos a sequ^encia
correspondente 𝛿0 ( Single )𝑡 , em que Single é um operador linear de 𝒩 em 𝒩 , que
vamos definir agora. Primeiro vamos definir um operador, que denotaremos por
Birth : 𝒩 → 𝒩 , porque ele corresponde a ação de Birth inter . Para todo 𝑥, 𝑦 ∈ Z+
)︂
⎧(︂
𝑥
+
1
⎨
𝛽 𝑦−𝑥 (1 − 𝛽)2𝑥−𝑦+1
se 𝑥 ≤ 𝑦 ≤ 2𝑥 + 1,
𝑦−𝑥
Birth(𝑦 𝑥) =
(1.15)
⎩
0 caso contrário.
Em outras palavras, 𝑦 = 𝑥 + Δ𝑏𝑖𝑟𝑡ℎ , com a variável aleatória Δ𝑏𝑖𝑟𝑡ℎ tendo uma
distribuição binomial, porque corresponde a uma soma de 𝑥+1 variáveis aleatórias
independentes, cada uma dessas igual a 1 com probabilidade 𝛽 e 0 com probabilidade 1 − 𝛽.
Outro operador, o qual denotamos por Murder : 𝒩 → 𝒩 , porque ele corres-
14
ponde a ação de Murder inter , age como segue:
⎧
⎪
se 𝑦 = 𝑥 − 1,
⎪
⎨𝛼
Murder (𝑦 𝑥) =
1−𝛼
⎪
⎪
⎩0
se 𝑦 = 𝑥,
(1.16)
em todos os outros casos.
Finalmente, definimos o operador Single como a composição
Single = Birth ∘ Murder
(1.17)
(primeiro Birth, depois Murder). Assim, definimos os operadores Birth, Murder
e Single . Todos eles são lineares e são, de fato, cadeias de Markov tendo Z+ (ou
um subconjunto deste) como o conjunto de estados.
Para qualquer configuração conf ∈ {⊖, ⊕}Z , denominamos um par de números
inteiros (𝑥, 𝑦), sendo 𝑥 < 𝑦, menos consecutivos se conf(𝑥) = conf(𝑦) = ⊖ e
todas as componentes de conf entre 𝑥 e 𝑦 são iguais a ⊕. Neste caso, também
denominamos 𝑦 o próximo menos depois de 𝑥.
Lema principal. Para cada número natural 𝑡, na medida 𝛿⊖ ( VarStav )𝑡 , assumindo que um certo componente é um ⊖, o número de ⊕ entre ele e o próximo
menos é independente do número de ⊕ entre todos os outros pares de menos consecutivos e tem a mesma distribuição da variável aleatória 𝛿0 ( Single )𝑡 .
O lema principal desempenha papel fundamental nesta tese, pois ele reduz operadores não lineares sobre {⊖, ⊕}Z a operadores lineares sobre Z+ . Sua prova segue
de nossas definições.
Capı́tulo 2
Teorema principal
Nosso principal resultado é este:
se 𝛼 < 1 e 𝛽 > 0, então 𝛿⊖ ( VarStav )𝑡 → 𝛿⊕ quando 𝑡 → ∞,
(2.1)
em que converg^encia significa converg^encia em todos os cilindros finos. A proposição (2.1) é equivalente à seguinte condição:
Teorema principal.
se 𝛼 < 1 e 𝛽 > 0, então 𝛿⊖ ( VarStav )𝑡 (⊕) → 1 quando 𝑡 → ∞.
2.1
(2.2)
Prova do Teorema principal
Para provar o teorema principal usamos o seguinte corolário do lema principal:
𝛿⊖ ( VarStav )𝑡 (⊕) =
IE(S𝑡 )
1 + IE(S𝑡 )
para todo 𝑡 ∈ Z+ ,
(2.3)
em que IE(·) significa esperança matemática e S𝑡 é uma variável aleatória com
distribuição 𝛿0 ( Single )𝑡 . Precisamos, também, do seguinte resultado:
IE (S𝑡 ) → ∞ quando 𝑡 → ∞.
15
(2.4)
16
É evidente que (2.3), juntamente com (2.4), implicam em (2.2). Como (2.3) já
está provada, resta-nos provar (2.4).
Dizemos que uma sequ^encia de variáveis aleatórias reais (𝑋𝑘 ) cresce completamente quando 𝑘 → ∞, se para cada número real 𝑥, a sequ^encia de números
IP(𝑋𝑘 ≤ 𝑥) tende a zero quando 𝑘 → ∞.
Lema 1 Se uma sequ^encia (𝑋𝑘 ) de variáveis aleatórias sobre Z+ cresce completamente quando 𝑘 → ∞, então a sequ^encia de seus valores esperados IE(𝑋𝑘 ) tende
a ∞ quando 𝑘 → ∞.
Prova. Desde que a sequ^encia (𝑋𝑘 ) cresça completamente, para qualquer 𝑁 e
qualquer 𝜀 > 0, existe um 𝑘0 tal que
∀ 𝑘 ≥ 𝑘0 : IP(𝑋𝑘 ≥ 𝑁 ) ≥ 1 − 𝜀.
É bem conhecido que para qualquer variável aleatória 𝑋 e qualquer número 𝑁 ′
IE(𝑋) ≥ 𝑁 ′ · IP(𝑋 ≥ 𝑁 ′ ).
Escolhendo 𝜀 = 1/2 e 𝑁 ′ = 2𝑁 , obtemos:
∀ 𝑘 ≥ 𝑘0 : IE(𝑋𝑘 ) ≥ 𝑁 ′ · IP(𝑋𝑘 ≥ 𝑁 ′ ) ≥ 𝑁 ′ · (1 − 𝜀) = 2𝑁 ·
O Lema 1 está provado.
1
= 𝑁.
2
17
A partir de agora vamos nos concentrar em provar o seguinte resultado:
A sequ^encia 𝛿0 ( Single )𝑡
cresce completamente quando 𝑡 → ∞.
(2.5)
É evidente que (2.5) e o Lema 1 implicam em (2.4). Assim, resta-nos apenas
provar (2.5). Para isto, precisamos de alguns tipos de ordem parcial. Estas ordens
são geralmente bem conhecidas, porém as incluimos em uma forma conveniente a
nosso propósito.
2.1.1
Medidas sobre Z+
Dizemos que um conjunto 𝐿 ⊂ Z+ é inferior se
(𝑥 ∈ 𝐿,
𝑦 < 𝑥) =⇒ 𝑦 ∈ 𝐿.
Analogamente, dizemos que um conjunto 𝑆 ⊂ Z+ é superior se
(𝑥 ∈ 𝑆,
𝑥 < 𝑦) =⇒ 𝑦 ∈ 𝑆.
Note que, se 𝑆 é superior, então Z+ ∖𝑆 é inferior e vice-versa. Qualquer conjunto
inferior 𝐿 ou é vazio, ou coincide com Z+ , ou é dado pela fórmula
𝐿 = {𝑛 : 𝑛 < 𝑛0 }, sendo 𝑛0 um par^ametro.
Analogamente, qualquer conjunto superior 𝑆 ou é vazio, ou coincide com Z+ , ou
é dado pela fórmula
𝑆 = {𝑛 : 𝑛 ≥ 𝑛0 }, sendo 𝑛0 um par^ametro.
Agora, dadas as medidas 𝜇 e 𝜈 ∈ 𝒩 , dizemos que 𝜇 precede 𝜈 e escrevemos
18
𝜇 ≺ 𝜈 se
𝜇(𝐿) ≥ 𝜈(𝐿) para todo inferior 𝐿,
que é equivalente a
𝜇(𝑆) ≤ 𝜈(𝑆) para todo superior 𝑆.
Lema 2 Considere duas sequ^encias de medidas (𝜇𝑛 ) e (𝜈𝑛 ) sobre Z+ , tal que 𝜇𝑛 ≺
𝑚
𝑚
∑︁
∑︁
𝜈𝑛 para todo natural 𝑛. Então,
𝜇𝑛 ≺
𝜈𝑛 para todo natural 𝑛.
𝑛=1
𝑛=1
Prova. A prova deste lema será feita por indução finita.
Base de indução: 𝜇1 ≺ 𝜈1 .
Hipótese de indução:
𝑚−1
∑︁
𝑛=1
𝜇𝑛 ≺
𝑚−1
∑︁
𝜈𝑛 .
𝑛=1
Passo de indução: Sabemos que
𝜇𝑚 (𝑆) ≤ 𝜈𝑚 (𝑆) para todo conjunto superior 𝑆.
De (2.6) e da hipótese de indução
𝑚−1
∑︁
𝜇𝑛 (𝑆) ≤
𝑛=1
𝑚−1
∑︁
𝜈𝑛 (𝑆) para todo superior 𝑆.
𝑛=1
Usando (2.6) temos
𝑚
∑︁
𝜇𝑛 (𝑆) ≤
𝑛=1
O Lema 2 está provado.
𝑚
∑︁
𝑛=1
𝜈𝑛 (𝑆) para todo superior 𝑆.
(2.6)
19
Para qualquer natural 𝑛 vamos denotar por 𝛿𝑛 a medida sobre Z+ concentrada
no estado 𝑛.
Denominamos uma medida 𝜇 sobre Z+ de local, se o conjunto
{𝑛 ∈ Z+ 𝜇(𝑛) ̸= 0} é finito.
Denominamos um par (𝜇, 𝜈) de local se 𝜇 e 𝜈 são locais.
2.1.2
Passos e escadas
Vamos denominar um par local (𝜇, 𝜈) de passo se existirem 𝑎 e 𝑏, naturais e um
número real 𝑝 > 0 tal que 𝑎 < 𝑏 e
⎧
⎪
⎨−𝑝
∀ 𝑘 ∈ Z+ : 𝜈(𝑘) − 𝜇(𝑘) =
𝑝
⎪
⎩
0
se 𝑘 = 𝑎,
se 𝑘 = 𝑏,
em todos os outros casos.
Lema 3 Se (𝜇, 𝜈) é um passo, então 𝜇 ≺ 𝜈.
Prova. Seja 𝐿𝑘 = {1, 2, . . . , 𝑘} e 𝑝 > 0. Desde que 𝜈 − 𝜇 seja um passo, temos
(︀
)︀
(︀
)︀
(𝜈 − 𝜇) (𝐿𝑘 ) ∈ {0, −𝑝} =⇒ 𝜈(𝐿𝑘 ) = 𝜇(𝐿𝑘 ) or 𝜈(𝐿𝑘 ) < 𝜇(𝐿𝑘 ) .
O Lema 3 está provado.
Dadas duas medidas 𝜇, 𝜈 ∈ 𝒩 , denominamos uma sequ^encia de medidas
𝜋1 , 𝜋2 , . . . , 𝜋𝑛 uma escada de 𝜇 a 𝜈 se 𝜋1 = 𝜇, 𝜋𝑛 = 𝜈 e cada par (𝜋𝑖 , 𝜋𝑖+1 ) é
um passo, para 𝑖 = 1, . . . , 𝑛 − 1. O caso 𝜇 = 𝜈 acontece quando 𝑛 = 1.
Lema 4 Considere duas medidas 𝜇, 𝜈 ∈ 𝒩 . Então 𝜇 ≺ 𝜈 se, e somente se, existe
uma escada de 𝜇 a 𝜈.
Prova. Na direção (⇐). Se existe uma escada de 𝜇 a 𝜈, é porque, por definição, o
par (𝜇, 𝜈) é um passo e pelo Lema 3 segue a implicação. Vamos provar na outra
20
direção (⇒). Para qualquer par (𝜇, 𝜈) denotamos por max(𝜇, 𝜈) o máximo do
par (𝜇, 𝜈) como o maior número natural 𝑚 tal que
𝜇(𝑚) ̸= 0 ou 𝜈(𝑚) ̸= 0.
Provaremos o Lema 4 por indução em max(𝜇, 𝜈).
Base de indução. Suponha que max(𝜇, 𝜈) = 0. Então, 𝜇 = 𝜈 e o Lema 4 é
verdadeiro.
Passo de indução. Suponha que o Lema 4 já esteja provado para todos os pares,
cujo máximo não exceda 𝑚. Suponha que, agora, temos um novo par (𝜇, 𝜈), cujo
máximo vale 𝑚 + 1 e tal que 𝜇 ≺ 𝜈. Vamos submeter este par a uma sequ^encia
de operações como segue.
Uma vez que o conjunto [𝑚 + 1, ∞) é superior,
𝜇[𝑚 + 1, ∞) ≤ 𝜈[𝑚 + 1, ∞).
Por outro lado, desde que max(𝜇, 𝜈) = 𝑚 + 1,
𝜇[𝑚 + 1, ∞) = 𝜇(𝑚 + 1) e 𝜈[𝑚 + 1, ∞) = 𝜈(𝑚 + 1).
Portanto, 𝜇(𝑚 + 1) ≤ 𝜈(𝑚 + 1). Agora vamos considerar dois casos.
Caso 1: Suponha que 𝜇(𝑚 + 1) > 0. Então, realizamos a seguinte operação:
subtraı́mos de ambos os valores 𝜇(𝑚 + 1) e 𝜈(𝑚 + 1) a quantidade 𝜇(𝑚 + 1). As
escadas, que sabemos existir para o par resultante, é válida também para o par
(𝜇, 𝜈).
21
Caso 2: Suponha que 𝜇(𝑚 + 1) = 0. Então, 𝜈(𝑚 + 1) > 0 e existe um 𝑘 < 𝑚 + 1
tal que 𝜇(𝑘) > 𝜈(𝑘). Assim, assumimos,
(︀
)︀
𝑝 = min 𝜇(𝑘) − 𝜈(𝑘), 𝜈(𝑚 + 1) − 𝜇(𝑚 + 1)
e formamos o seguinte passo:
∀ 𝑖 ∈ Z+ : passo(𝑘) =
⎧
⎪
−𝑝
⎪
⎪
⎨
𝑝
⎪
⎪
⎪
⎩ 0
se 𝑖 = 𝑘,
se 𝑖 = 𝑚 + 1,
(2.7)
em todos os outros casos.
O par resultante (𝜇′ , 𝜈 ′ ) tem seu máximo não excedendo 𝑚. Pela hipótese de
indução, este par é ligado por uma escada. Portanto, o par (𝜇, 𝜈), também é
ligado por uma escada obtida dele ao incluir um passo extra (2.7).
O Lema 4 está provado.
2.1.3
𝒩 -operadores
Ao longo desta tese, por cadeia de Markov, queremos dizer uma cadeia de Markov
com tempo discreto, homog^enea no tempo, com um conjunto finito ou enumerável
de estados.
Vamos denominar um 𝒩 -𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟 qualquer cadeia de Markov finita com Z+
ou um subconjunto de Z+ como o conjunto de estados.
Denominamos um 𝒩 -operador 𝑃 local se para cada medida local 𝜇 sobre 𝒩 , a
medida 𝜇𝑃, também, é local.
Um 𝒩 -operador 𝑃 é monótono se ∀ 𝜇, 𝜈 : (𝜇 ≺ 𝜈) =⇒ (𝜇𝑃 ≺ 𝜈𝑃 ).
Denominamos medida nula e denotamos por Ø, a medida que atribui valor zero
a todo subconjunto de Z+ .
22
Lema 5 Seja 𝑚, 𝑛 ∈ Z e 𝑚 < 𝑛. Então 𝛿𝑚 ≺ 𝛿𝑛 .
Prova. Considere o conjunto inferior 𝐿𝑘 = {0, 1, . . . , 𝑘}. Lembremos que, para
qualquer conjunto 𝐴,
{︃
𝛿𝑛 (𝐴) =
1,
se 𝑛 ∈ 𝐴;
0,
se 𝑛 ∈
/ 𝐴.
(2.8)
Vamos considerar os seguintes casos.
Caso 1: Suponha 𝑚 < 𝑛 < 𝑘, então
𝛿𝑛 (𝐿𝑘 ) = 1 ≤ 1 = 𝛿𝑚 (𝐿𝑘 ).
Caso 2: Suponha 𝑚 < 𝑘 < 𝑛, então
𝛿𝑛 (𝐿𝑘 ) = 0 ≤ 1 = 𝛿𝑚 (𝐿𝑘 ).
Caso 3: Suponha 𝑘 < 𝑚 < 𝑛, então
𝛿𝑛 (𝐿𝑘 ) = 0 ≤ 0 = 𝛿𝑚 (𝐿𝑘 ).
Em qualquer situação, ∀ inferior 𝐿, temos
𝛿𝑛 (𝐿) ≤ 𝛿𝑚 (𝐿),
que implica em 𝛿𝑚 ≺ 𝛿𝑛 .
O Lema 5 está provado.
Lema 6 Seja 𝑃 um 𝒩 -operador local. Então,
(︀
)︀
(︀
)︀
𝑃 é monótono ⇐⇒ ∀ 𝑚, 𝑛 ∈ Z+ : 𝑚 < 𝑛 =⇒ 𝛿𝑚 𝑃 ≺ 𝛿𝑛 𝑃 .
Prova. Vamos provar na direção (⇒). Se 𝑃 é monótono, então ∀ 𝜇, 𝜈 com 𝜇 ≺ 𝜈,
temos que 𝜇𝑃 ≺ 𝜈𝑃. Como por hipótese 𝑚 < 𝑛, segue do Lema 5 que 𝛿𝑚 ≺ 𝛿𝑛 .
23
Então, fazendo 𝜇 = 𝛿𝑚 e 𝜈 = 𝛿𝑛 , temos que 𝛿𝑚 𝑃 ≺ 𝛿𝑛 𝑃 e segue o resultado nesta
direção. Agora na outra direção (⇐).
Seja (𝜇, 𝜈) um par local. De acordo com o Lema 4, se 𝜇 ≺ 𝜈, então existe uma
sequ^encia de medidas, 𝜋1 , . . . , 𝜋𝑛 tal que
𝜇 = 𝜋1 ≺ 𝜋2 ≺ . . . ≺ 𝜋𝑛−1 ≺ 𝜋𝑛 = 𝜈 e 𝜋𝑖+1 − 𝜋𝑖 é um passo.
(2.9)
Vamos provar que 𝜇𝑃 ≺ 𝜋2 𝑃 ≺ . . . ≺ 𝜋𝑛−1 𝑃 ≺ 𝜈𝑃. Observe que, para qualquer
passo, existe um inteiro 𝑛, para o qual este passo pode ser escrito como
passo = 𝑝 (𝛿𝑛+1 − 𝛿𝑛 ) ,
sendo 𝑝 um número real não negativo. Da hipótese 𝑚 < 𝑛, temos que 𝛿𝑚 𝑃 ≺ 𝛿𝑛 𝑃,
e assim podemos escrever o seguinte
(𝑝 𝛿𝑛 ≺ 𝑝 𝛿𝑛+1 ) =⇒ (Ø ≺ −𝑝 𝛿𝑛 𝑃 + 𝑝 𝛿𝑛+1 𝑃 ) =⇒ (Ø ≺ (passo)𝑃 ).
(2.10)
Combinando (2.10) com o fato de que a sequ^encia (2.9) é tal que 𝜋𝑖+1 − 𝜋𝑖 é um
passo, segue
(Ø ≺ (𝜋𝑖+1 − 𝜋𝑖 )𝑃 ) =⇒ (Ø ≺ 𝜋𝑖+1 𝑃 − 𝜋𝑖 𝑃 ).
O Lema 6 está provado.
É claro que, a operação ≺ estabelece uma ordem parcial sobre o conjunto
de medidas locais em Z+ . Assim, é natural obter condições sob as quais uma
aplicação preserve esta ordem. Tais aplicações são conhecidas como aplicações
que preservam ordem (vide p.21 em [6]). O Lema 6 fornece condições suficientes
para que um 𝒩 -operador 𝑃, agindo sobre todas as medidas locais, preserve ordem.
Dados os 𝒩 -operadores 𝑃 e 𝑄, dizemos que 𝑃 precede 𝑄 e escrevemos 𝑃 ≺ 𝑄
se 𝜇 𝑃 ≺ 𝜇 𝑄 para todo 𝜇 ∈ 𝒩 .
24
Lema 7 Considere 𝑃 e 𝑄 dois 𝒩 -operadores locais. Então,
(︀
)︀
(︀
)︀
𝑃 ≺ 𝑄 ⇐⇒ ∀ 𝑛 ∈ Z+ : 𝛿𝑛 𝑃 ≺ 𝛿𝑛 𝑄 .
Prova. Em uma direção (⇒) é evidente. Para provar na outra direçao(⇐), é
suficiente lembrar que 𝑃 e 𝑄 são lineares e podemos escrever 𝜇 como segue
𝜇=
𝑛
∑︁
𝑎𝑘 𝛿𝑥+𝑘 ,
𝑘=0
em que todos os 𝑎𝑘 são não negativos, somam 1 e
𝑥 = min{𝑛 ∈ Z+ | 𝜇(𝑛) > 0}; 𝑦 = max{𝑛 ∈ Z+ | 𝜇(𝑛) > 0} e 𝑛 = 𝑦 − 𝑥.
Temos para todo 𝑘 = 0, . . . , 𝑛 que
(︀
)︀
(︀
)︀
𝛿𝑥+𝑘 𝑃 ≺ 𝛿𝑥+𝑘 𝑄 ⇒ (𝑎𝑘 𝛿𝑥+𝑘 )𝑃 ≺ (𝑎𝑘 𝛿𝑥+𝑘 )𝑄 .
Agora, usando o Lema 2, temos
(︃ 𝑛
∑︁
(𝑎𝑘 𝛿𝑥+𝑘 )𝑃 ≺
𝑘=0
𝑛
∑︁
)︃
(𝑎𝑘 𝛿𝑥+𝑘 )𝑄
⇒ (𝜇𝑃 ≺ 𝜇𝑄) .
𝑘=0
O Lema 7 está provado.
Lema 8 Considere os 𝒩 -operadores monótonos 𝑃1 , 𝑃2 e 𝑄, tais que 𝑃1 ≺ 𝑃2 .
Então, 𝑃1 𝑄 ≺ 𝑃2 𝑄 e 𝑄𝑃1 ≺ 𝑄𝑃2 .
Prova. Vamos provar que 𝑃1 𝑄 ≺ 𝑃2 𝑄. Por definição podemos escrever
(︀
)︀
(︀
)︀
𝑃1 ≺ 𝑃2 =⇒ ∀𝜇 ∈ 𝒩 : 𝜇𝑃1 ≺ 𝜇𝑃2 .
Como 𝑄 é monótono, então ∀𝜇 ∈ 𝒩
(︀
)︀
(︀
)︀
𝜇𝑃1 ≺ 𝜇𝑃2 =⇒ 𝜇𝑃1 𝑄 ≺ 𝜇𝑃2 𝑄 .
25
Agora a prova para 𝑄𝑃1 ≺ 𝑄𝑃2 . Como 𝑃1 ≺ 𝑃2 , quer dizer que ∀𝜇 ∈ 𝒩 : 𝜇𝑃1 ≺
𝜇𝑃2 . Tomando 𝜇 = 𝜈𝑄, podemos escrever
(︀
)︀
(︀
)︀
(︀
)︀
(︀
)︀
𝜈𝑄 𝑃1 ≺ 𝜈𝑄 𝑃2 =⇒ 𝜈 𝑄𝑃1 ≺ 𝜈 𝑄𝑃2
e segue-se o resultado.
O Lema 8 está provado.
Lema 9 Dados 𝑃1 , . . . , 𝑃𝑛 e 𝑄1 , . . . , 𝑄𝑛 , 𝒩 -operadores monótonos locais tais que
𝑃1 ≺ 𝑄1 , . . . , 𝑃𝑛 ≺ 𝑄𝑛 . Então,
𝑃1 ∘ 𝑃2 ∘ · · · ∘ 𝑃𝑛 ≺ 𝑄1 ∘ 𝑄2 ∘ · · · ∘ 𝑄𝑛 .
Prova. Será por indução.
Base de indução: 𝑃1 ≺ 𝑄1 é dado.
Hipótese de indução:
𝑃1 ∘ · · · ∘ 𝑃𝑛−1 ≺ 𝑄1 ∘ · · · ∘ 𝑄𝑛−1 .
Passo de indução. É claro que
𝑃𝑛 ∘ (𝑃1 ∘ · · · ∘ 𝑃𝑛−1 ) ≺ 𝑄𝑛 ∘ (𝑃1 ∘ · · · ∘ 𝑃𝑛−1 ).
Ainda, temos que
(︀
𝑃1 ∘ · · · ∘ 𝑃𝑛−1
)︀
é um 𝒩 -operador monótono.
(2.11)
Assim,
usando o Lema 8, podemos reescrever (2.11) como segue
(︀
)︀
(𝑃1 ∘ · · · ∘ 𝑃𝑛−1 ) ∘ 𝑃𝑛 ≺ (𝑃1 ∘ · · · ∘ 𝑃𝑛−1 ) ∘ 𝑄𝑛 .
(2.12)
Agora, da hipótese de indução e monotonicidade de 𝑄𝑛
(𝑃1 ∘ · · · ∘ 𝑃𝑛−1 ) ∘ 𝑄𝑛 ≺ (𝑄1 ∘ · · · ∘ 𝑄𝑛−1 ) ∘ 𝑄𝑛 .
(2.13)
26
Portanto, o Lema 9 segue de (2.12) e (2.13).
O Lema 9 está provado.
Lema 10 Seja 𝜈 ∈ 𝒩 e 𝐿 = {𝑛 : 𝑛 ≤ 𝑛0 }. Então,
𝜈 Murder(𝐿) =
=
𝜈(𝐿) + 𝛼 · 𝜈(𝑛 = 𝑛0 + 1)
(2.14)
(1 − 𝛼) · 𝜈(𝐿) + 𝛼 · 𝜈(𝑛 ≤ 𝑛0 + 1).
(2.15)
Prova. Para encontrarmos (2.15), adicionamos e subtraı́mos 𝜈(𝐿) no segundo
membro da equação (2.14) como segue
𝜈 Murder(𝐿) =
𝜈(𝐿) + 𝛼 · 𝜈(𝑛 = 𝑛0 + 1)
=
𝜈(𝐿) − 𝛼𝜈(𝐿) + 𝛼𝜈(𝐿) + 𝛼 · 𝜈(𝑛 = 𝑛0 + 1)
=
(1 − 𝛼) · 𝜈(𝐿) + 𝛼 · 𝜈(𝑛 ≤ 𝑛0 + 1).
O Lema 10 está provado.
Lema 11 O 𝒩 -operador Murder é local e monótono para todo 𝛼.
Prova. Vamos provar que Murder é local.
Dizer que o conjunto {𝑛 ∈ Z+ : 𝜇(𝑛) ̸= 0} é finito, significa dizer que existe uma
sequ^encia finita de inteiros 𝑥1 , 𝑥2 , . . . , 𝑥𝑛 , tal que
𝜇(𝑥𝑖 ) ̸= 0, em que 𝑖 = 1, . . . , 𝑛.
Portanto, pela defição do 𝒩 -operador Murder, podemos verificar que o conjunto
{𝑛 ∈ Z+ : 𝜇(𝑥𝑖 ) Murder(𝑦 𝑥𝑖 ) ̸= 0} = {𝑥𝑖−1 , 𝑥𝑖 }
27
é finito. Agora, provaremos que o operador Murder é monótono. Sejam 𝜇, 𝜈 ∈
𝒩 , 𝜇 ≺ 𝜈 e 𝐿 = {𝑛 : 𝑛 ≤ 𝑛0 }. Da definição de Murder segue
𝜈 Murder(𝐿) = 𝜈(𝐿) + 𝛼 𝜈(𝑛 = 𝑛0 + 1).
Desta igualdade, juntamente com o Lema 10, temos
𝜈 Murder(𝐿) =
(1 − 𝛼) 𝜈(𝐿) + 𝛼 𝜈(𝑛 ≤ 𝑛0 + 1) ≤
(1 − 𝛼) 𝜇(𝐿) + 𝛼 𝜇(𝑛 ≤ 𝑛0 + 1) = 𝜇 Murder(𝐿).
Portanto, concluı́mos que
𝜇 Murder ≺ 𝜈 Murder.
O Lema 11 está provado.
Lema 12 Seja 𝑧 ∈ Z+ . Então,
(a) 𝛿𝑧 Birth(𝑛 = 𝑦) = 0 quando 𝑦 < 𝑧;
(︂
)︂
𝑧+1
(b) 𝛿𝑧 Birth(𝑛 = 𝑦) =
𝛽 𝑦−𝑧 (1 − 𝛽)2𝑧+1−𝑦 se 𝑧 ≤ 𝑦 ≤ 2𝑧 + 1;
𝑦−𝑧
(c) 𝛿𝑧 Birth(𝐿) =
𝑛0
∑︁
𝛿𝑧 Birth(𝑛 = 𝑦) = 1 se 𝑛0 ≥ 2𝑧 + 1.
𝑦=0
Prova. Seja 𝑦, 𝑥 ∈ Z+ . É suficiente observar da definição (1.15) de Birth que
∀ 𝑦 ∈ Z+ : 𝜈 Birth(𝑛 = 𝑦) =
∑︁
𝜈(𝑥) Birth(𝑦|𝑥).
𝑥∈Z+
Agora, assuma 𝜈 = 𝛿𝑧 , e segue a prova do Lema 12.
O Lema 12 está provado.
28
Vamos usar a bem conhecida notação Bin (𝑧 + 1, 𝛽), para a distribuição binomial. Seja 𝑋 uma variável aleatória com a distribuição Bin (𝑧 + 1, 𝛽).
Do Lema 12 concluı́mos que
{︃
𝛿𝑧 Birth(𝑛 = 𝑧 + 𝑘) =
IP(𝑋 = 𝑘)
se 0 ≤ 𝑘 ≤ 𝑧 + 1;
0
em todos os outros casos.
(2.16)
Lema 13 Sejam 𝑛1 , 𝑛2 ∈ Z+ e 𝑛1 < 𝑛2 ; sejam 𝑋1 e 𝑋2 variáveis aleatórias com
distribuições Bin (𝑛1 , 𝛽) e Bin (𝑛2 , 𝛽), respectivamente. Então,
𝑋 1 ≺ 𝑋2 .
Prova. Para provar o Lema 13 usaremos o seguinte resultado (provado em [23]
p.5): sejam 𝑋, 𝑌 variáveis aleatórias com distribuições 𝜇, 𝜈 ∈ 𝒩 , respectivamente.
Então,
𝜇 ≺ 𝜈 ⇐⇒ 𝑋 ≤ 𝑌 quase certamente.
Como sempre, denotamos a cardinalidade de um conjunto 𝐴 por #𝐴. Sejam
𝑈1 , . . . , 𝑈𝑛1 , . . . , 𝑈𝑛2 variáveis aleatórias i.i.d., cada uma destas distribuı́da uniformemente em [0, 1]. Denotemos
𝑋𝑖 = #{𝑘 : 𝑈𝑘 < 𝛽} para 𝑘 = 1, . . . , 𝑛𝑖 .
Então, 𝑋1 < 𝑋2 quase certamente. O Lema 13 está provado.
Lema 14 O 𝒩 -operador Birth é local e monótono para todo 𝛽.
Prova. Pela definição (1.15), Birth é local. Agora vamos provar sua monotonicidade. Sejam 𝑥, 𝑦 ∈ Z+ . Se assumimos que 𝑥 < 𝑦, então é evidente que 𝛿𝑥 ≺ 𝛿𝑦 .
Do Lema 7, isto é equivalente a
∀ 𝑥, 𝑦 : 𝑥 < 𝑦 =⇒ 𝛿𝑥 Birth ≺ 𝛿𝑦 Birth.
(2.17)
29
A partir de (2.16), concluı́mos que (2.17) é equivalente a
(𝑥 < 𝑦) =⇒
(︀
)︀
Bin (𝑥 + 1, 𝛽) ≺ Bin (𝑦 + 1, 𝛽) ,
que segue do Lema 13.
O Lema 14 está provado.
2.1.4
Os 𝒩 -operadores Sing e Sing 𝑟
Vamos definir outro 𝒩 -operador local denominado sing e denotado por Sing , cujo
comportamento é similar àquele de Single , porém mais simples:
⎧
2/3
⎪
⎪
⎪
⎪
⎪
⎪
⎪
1/3
⎪
⎪
⎨
𝛾
Sing (𝑦 𝑥) =
⎪
⎪
⎪
⎪
⎪
1−𝛾
⎪
⎪
⎪
⎪
⎩
1−𝛾
se 𝑞 ≤ 𝑥 e 𝑦 = 𝑥 + 1;
se 𝑞 ≤ 𝑥 e 𝑦 = 𝑥 − 1;
se 𝑥 < 𝑞 e 𝑦 = 𝑥 + 1;
se 0 < 𝑥 < 𝑞 e 𝑦 = 𝑥 − 1;
se 𝑥 = 𝑦 = 0.
Aqui o número natural 𝑞 e o número real 𝛾 são par^ametros, que vamos escolher
de uma forma apropriada. Antes, considere o seguinte lema.
Lema 15 Seja 𝛽 ∈ (0, 1) fixo. Então, IP(Δ𝑏𝑖𝑟𝑡ℎ ≤ 1) tende a zero quando 𝑥 → ∞.
Prova. Note que
IP(Δ𝑏𝑖𝑟𝑡ℎ ≤ 1) = (1 − 𝛽)𝑥+1 + (𝑥 + 1) 𝛽 (1 − 𝛽)𝑥 .
(2.18)
Quando 𝑥 → ∞, a primeira parcela do segundo membro de (2.18) vai para zero.
Agora, devemos mostrar que a segunda parcela também vai para zero. Note,
também, que
𝛽(𝑥 + 1)
.
𝑥→∞ 1/(1 − 𝛽)𝑥
lim [𝛽(𝑥 + 1)(1 − 𝛽)𝑥 ] = lim
𝑥→∞
30
Logo, por L’H^opital, o último limite fica assim
𝛽
𝛽(1 − 𝛽)𝑥
=
lim
= 0.
𝑥→∞ log(1 − 𝛽)/(1 − 𝛽)𝑥
𝑥→∞ log(1 − 𝛽)
lim
O Lema 15 está provado.
Levando em conta o Lema 15,
escolhemos 𝑞 como o menor número inteiro tal que
}︃
IP(Δ𝑏𝑖𝑟𝑡ℎ ≤ 1) ≤ 1/3 para todo 𝑥 ≥ 𝑞.
(2.19)
Tendo escolhido 𝑞, definimos 𝛾 como segue:
}︀)︀
(︀
{︀
𝛾 = min 𝛽(1 − 𝛼), min 𝑃 𝑟𝑜𝑏(Δ𝑏𝑖𝑟𝑡ℎ ≥ 2) 0 < 𝑥 < 𝑞 .
(2.20)
Dessa forma, Sing está definido.
Para considerar cadeias de Markov finitas ao invés de infinitas, para cada natural 𝑟 maior do que 𝑞, definimos um 𝒩 -operador, que denotamos por Sing 𝑟 . Como
uma cadeia de Markov, Sing 𝑟 tem {0, . . . , 𝑟} como seu conjunto de estados. Esta
é a fórmula de suas transições:
Sing 𝑟 (𝑦 𝑥) =
⎧
⎪
Sing (𝑦 𝑥)
⎪
⎪
⎪
⎪
⎨2/3
⎪
1/3
⎪
⎪
⎪
⎪
⎩
0
se 0 ≤ 𝑥 < 𝑟,
se 𝑥 = 𝑦 = 𝑟,
se 𝑥 = 𝑟 e 𝑦 = 𝑟 − 1,
(2.21)
em todos os outros casos.
A Figura 2.1 nos mostra o comportamento de Sing 𝑟 para alguns valores de 𝑞 e
𝑟 em escala logarı́tmica.
31
∙
@
@
@
@
@
@
∙
@
@
@
@
@
@
∙````
0
1
2
``
∙
𝑞=3
∙
4
∙
5
∙
6
∙
7
∙
𝑟=8
Figura 2.1: Os cı́rculos pretos mostram os valores de 𝜆𝑟 que é a medida invariante normalizada do
𝒩 -operador Sing 𝑟 para o caso 𝑞 = 3 e 𝑟 = 8 em escala logarı́tmica. As linhas ligando os pontos
pretos são apenas para auxiliar a impressão visual. A parte esquerda do gráfico com números de
zero até 𝑞 − 1 representa a garrafa onde o g^enio do folclore árabe foi inicialmente capturado. Leva
muito tempo para ele alcançar o gargálo 𝑞, mas uma vez que ele o atinge, ele facilmente cresce
exponencialmente.
32
Lema 16 Para 𝑞 e 𝛾 definidos em (2.19) e (2.20), respectivamente, e para qualquer 𝑟 > 𝑞:
(a) Sing 𝑟 , Sing e Single são locais e monótonos e
(b) Sing 𝑟 ≺ Sing ≺ Single .
Prova de (a): A localidade de todos estes operadores é evidente. Vamos provar a monotonicidade de Single . O 𝒩 -operador Single é monótono para todo
𝛼 e 𝛽, pois ele é uma composição de Birth e Murder, ambos monótonos. Agora, a
monotonicidade de Sing . Do Lema 6, é suficiente provar que
(︀
)︀
(𝑚 < 𝑛) =⇒ 𝛿𝑚 Sing ≺ 𝛿𝑛 Sing .
(2.22)
A equação (2.22) é evidente quando 𝑞 ≤ 𝑚 < 𝑛 ou 𝑚 < 𝑛 < 𝑞 ou 𝑚 < 𝑞 < 𝑛.
Resta-nos fazer o caso 𝑚 = 𝑞 − 1 e 𝑛 = 𝑞. Neste caso, (2.22) segue da inequação
𝛾 ≤ 2/3, vide (2.20). A monotonicidade de Sing 𝑟 segue de sua definição. Então,
item (a) do Lema 16 está provado.
Agora vamos provar o item (b). Provemos que Sing ≺ Single , a prova do outro
caso segue das definições de Sing 𝑟 e Sing . Do Lema 7, segue-se que
∀𝑛 ∈ Z+ : 𝛿𝑛 Sing ≺ 𝛿𝑛 Single .
(2.23)
Vamos considerar dois casos.
Caso 𝑛 ≥ 𝑞 : De (2.19) é suficiente notar que para todo 𝑥 ≥ 𝑞 a probabilidade
que o número cresça no mı́nimo por um como um resultado da aplicação do 𝒩 operador Single não é menor que 2/3. Neste caso (2.23) está provada.
Caso 𝑛 < 𝑞 : (2.23) é uma consequ^encia direta de (2.20), a definição de 𝛾.
O Lema 16 está provado.
33
Lema 17 Considere uma cadeia de Markov finita irredutı́vel com um conjunto
de estados 𝑆 = 𝐴 ∪ 𝐵, onde 𝐴 ∩ 𝐵 é vazio. Para todo 𝑥, 𝑦 ∈ 𝑆 denotamos
por 𝑝(𝑦 𝑥) a probabilidade de transição de 𝑥 a 𝑦. Estas probabilidades formam
a matriz de transição. É bem conhecido que, sob estas condições, uma cadeia de
Markov tem uma única medida invariante, a qual vamos denotar por 𝜇. Vamos
fixar dois estados 𝑎 ∈ 𝐴 e 𝑏 ∈ 𝐵, e assumir que 𝑝(𝑦 𝑥) = 𝑝(𝑥 𝑦) = 0 para todo
𝑥 ∈ 𝐴 e 𝑦 ∈ 𝐵 exceto o caso em que 𝑥 = 𝑎, 𝑦 = 𝑏. Então,
𝜇(𝑎) 𝑝(𝑏 𝑎) = 𝜇(𝑏) 𝑝(𝑎 𝑏).
(2.24)
Prova. Note que
∑︁
(︀ )︀ ∑︁
𝜇(𝑦) 𝑝(𝑥 𝑦).
∀𝑥∈𝑆: 𝜇 𝑥 =
𝜇(𝑦) 𝜇(𝑥 𝑦) =
𝑦∈𝑆
𝑦∈𝑆
Portanto,
∑︁
𝑥∈𝐴
𝜇(𝑥) =
∑︁ ∑︁
𝜇(𝑦) 𝑝(𝑥 𝑦) =
𝑥∈𝐴 𝑦∈𝑆
∑︁ ∑︁
𝑥∈𝐴 𝑦∈𝐴
𝜇(𝑦) 𝑝(𝑥 𝑦) +
∑︁ ∑︁
𝜇(𝑦) 𝑝(𝑥 𝑦).
𝑥∈𝐴 𝑦∈𝐵
Aqui, a segunda soma tem apenas um termo diferente de zero, isto é, o termo
que tem 𝑥 = 𝑎 e 𝑦 = 𝑏. Portanto, a segunda soma é igual a 𝜇(𝑏) 𝑝(𝑎 𝑏).
34
A primeira soma é igual a
∑︁ ∑︁
𝜇(𝑦) 𝑝(𝑥 𝑦) =
𝑦∈𝐴 𝑥∈𝐴
∑︁ ∑︁
𝜇(𝑦) 𝑝(𝑥 𝑦) −
∑︁ ∑︁
𝜇(𝑦) 𝑝(𝑥 𝑦).
𝑦∈𝐴 𝑥∈𝐵
𝑦∈𝐴 𝑥∈𝑆
Aqui, o minuendo é igual a
∑︁
𝜇(𝑦)
𝑦∈𝐴
∑︁
𝑝(𝑥 𝑦) =
𝑥∈𝑆
∑︁
𝜇(𝑦) =
𝑦∈𝐴
∑︁
𝜇(𝑥).
𝑥∈𝐴
O subtraendo tem apenas um termo diferente de zero, isto é, aquele que tem 𝑦 = 𝑎
e 𝑥 = 𝑏. Portanto, ele é igual a 𝜇(𝑎) 𝑝(𝑏 𝑎). Assim,
∑︁
𝑥∈𝐴
𝜇(𝑥) =
∑︁
𝜇(𝑥) + 𝜇(𝑏) 𝑝(𝑎 𝑏) − 𝜇(𝑎) 𝑝(𝑏 𝑎)
𝑥∈𝐴
e (2.24) segue. O Lema 17 está provado.
2.1.5
A medida invariante de Sing 𝑟
Sing 𝑟 é uma cadeia de Markov finita e irredutı́vel qualquer que seja 𝑟. Sendo assim,
ela tem exatamente uma medida invariante normalizada, que vamos denotar por
𝜆𝑟 .
Lema 18 A sequ^encia (𝜆𝑟 ) cresce completamente quando 𝑟 → ∞.
Prova. Provaremos o Lema 18 ao escrever explicitamente a medida 𝜆𝑟 .
Podemos representar Sing 𝑟 como uma matriz, que a denotaremos por M.
Então, 𝜆𝑟 é a solução normalizada da equação
𝜆𝑟 ( M - I ) = 0 ,
(2.25)
35
em que I é a matriz identidade de ordem 𝑟 + 1 e 0 é a matriz nula com 𝑟 + 1
colunas.
Note que as únicas probabilidades de transição não nulas de Sing 𝑟 são aquelas
que de qualquer 𝑠 vão a 𝑠 − 1, 𝑠 ou 𝑠 + 1. Esse fato permite usar o Lema 17 para
concluir que a medida invariante 𝜆𝑟 de Sing 𝑟 satisfaz as seguintes condições:
⎫
𝛾 𝜆𝑟 (𝑠) = (1 − 𝛾) 𝜆𝑟 (𝑠 + 1) para 𝑠 = 0, . . . , 𝑞 − 2, ⎪
⎪
⎪
⎪
⎪
⎪
⎬
1
𝜆𝑟 (𝑞),
𝛾 𝜆𝑟 (𝑞 − 1) =
3
⎪
⎪
⎪
⎪
⎪
1
2
⎪
⎭
𝜆𝑟 (𝑠) =
𝜆𝑟 (𝑠 + 1) para 𝑠 = 𝑞, . . . , 𝑟 − 1.
3
3
(2.26)
De acordo com (2.26), para todo 𝑠 ∈ [0, 𝑟], podemos escrever
⎧
(︂
)︂𝑞−𝑠
⎪
1
1
−
𝛾
⎪
⎨𝜆𝑟 (𝑞)
3𝛾
𝛾
𝜆𝑟 (𝑠) =
⎪
⎪
⎩𝜆𝑟 (𝑞) 2𝑠−𝑞
para 0 ≤ 𝑠 < 𝑞,
para 𝑞 ≤ 𝑠 ≤ 𝑟,
em que 𝜆𝑟 (𝑞) é um par^ametro que ainda precisamos escolher. Usando a fórmula
da soma de uma progressão geométrica, temos que
𝑟
∑︁
𝜆𝑟 (𝑠) = 𝜆𝑟 (𝑞) (2𝑟−𝑞+1 − 1).
𝑠=𝑞
Para calcular a soma de 𝜆𝑟 (𝑠), que vai de 𝑠 = 0 a 𝑠 = 𝑞 − 1, é melhor enumerar os
estados na ordem inversa. Então, temos uma progressão geométrica com 𝑞 termos,
na qual o primeiro termo é
𝜆𝑟 (𝑞 − 1) = 𝜆𝑟 (𝑞)
e o coeficiente é
1−𝛾
. Desse modo,
𝛾
1 1−𝛾
3𝛾 𝛾
36
𝑞−1
∑︁
)︀
1 (︀
1 𝜑(𝜑𝑞 − 1)
𝑞−1
𝜆𝑟 (𝑠) =
1 + ··· + 𝜑
= 𝜆𝑟 (𝑞)
,
3𝛾
3𝛾
𝜑
−
1
𝑠=0
1−𝛾
1 𝜑(𝜑𝑞 − 1)
. Também, denotamos Φ =
.
𝛾
3𝛾 𝜑 − 1
𝑟
∑︁
(︀
)︀
Então,
𝜆𝑟 (𝑠) = 𝜆𝑟 (𝑞) Φ + (2𝑟−𝑞+1 − 1) .
em que 𝜑 =
𝑠=0
Para normalizar a medida 𝜆𝑟 , assumimos
𝜆𝑟 (𝑞) =
1
Φ + (2𝑟−𝑞+1 − 1)
.
Portanto, para qualquer 𝑟′ ∈ [𝑞, 𝑟]
′
𝑟
∑︁
′
Φ + (2𝑟 −𝑞+1 − 1)
𝜆𝑟 (𝑠) =
.
𝑟−𝑞+1 − 1)
Φ
+
(2
𝑠=0
O valor desta fração tende a zero quando 𝑟 tende a ∞, com todos os outros
par^ametros, incluindo 𝑟′ , mantidos fixos. Assim, a sequ^encia 𝜆𝑟 cresce completamente quando 𝑟 → ∞. O Lema 18 está provado.
Agora vamos provar (2.5). Do Lema 18, a sequ^encia (𝜆𝑟 ) cresce completamente quando 𝑟 → ∞. Em outras palavras,
∀ 𝑟1 : 𝜆𝑟 [0, 𝑟1 ] → 0 quando 𝑟 → ∞,
em que [0, 𝑟1 ] é o segmento com extremos em 0 e 𝑟1 . O mesmo em mais detalhes:
(︀
)︀
∀ 𝑟1 ∀ 𝜀 > 0 ∃ 𝑟0 ∀ 𝑟 ≥ 𝑟0 : 𝜆𝑟 [0, 𝑟1 ] < 𝜀/2 .
Por outro lado, uma vez que Sing 𝑟 é irredutı́vel,
𝛿0 ( Sing 𝑟 )𝑡 → 𝜆𝑟 quando 𝑡 → ∞.
(2.27)
37
Em particular
∀ 𝑟1 : 𝛿0 ( Sing 𝑟 )𝑡 [0, 𝑟1 ] → 𝜆𝑟 [0, 𝑟1 ] quando 𝑡 → ∞.
Em mais detalhes
∀ 𝑟1 , ∀ 𝜀 > 0 ∃ 𝑟0 , ∃ 𝑡0 ∀ 𝑟 ≥ 𝑟0 , ∀ 𝑡 ≥ 𝑡0 :
𝛿0 ( Sing 𝑟 )𝑡 [0, 𝑟1 ] − 𝜆𝑟 [0, 𝑟1 ] ≤ 𝜀/2.
(2.28)
Agora, combinando (2.27) e (2.28), temos que
∀ 𝑟1 ∀ 𝜀 > 0 ∃ 𝑟0 ∃ 𝑡0 ∀ 𝑟 ≥ 𝑟0 , ∀ 𝑡 ≥ 𝑡0 : 𝛿0 ( Sing 𝑟 )𝑡 [0, 𝑟1 ] ≤ 𝜀.
Portanto, pelo Lema 9, uma vez que Sing 𝑟 ≺ Sing ≺ Single , temos
∀ 𝑟1 ∀ 𝜀 > 0 ∃ 𝑡0 ∀ 𝑡 ≥ 𝑡0 : 𝛿0 ( Single )𝑡 [0, 𝑟1 ] ≤ 𝜀.
Portanto, segue (2.5), que implica na fórmula (2.1), que é nosso resultado principal. O teorema principal está provado.
Capı́tulo 3
Aproximação do caos
Como anteriormente, ℳ𝒜 é o conjunto de medidas normalizadas invariantes por
translação sob 𝒜Z . Chamamos de operador caótico e denotamos por 𝒞 : ℳ𝒜 −→
ℳ𝒜 , o operador aleatório estudado em [15, 17], que a cada passo de tempo mistura
aleatoriamente todas as componentes do processo. Formalmente, para cada 𝜇 ∈
ℳ𝒜 , a medida 𝜇𝒞 é uma medida produto com as mesmas frequ^encias que há na
medida 𝜇, ou seja,
𝜇(⊕) = 𝜇𝒞(⊕) e 𝜇(⊖) = 𝜇𝒞(⊖),
observando que, em nosso caso, 𝒜 = {⊖, ⊕}. O operador caótico possibilita
aproximarmos um dado processo 𝜇(𝑃 )𝑡 , sobre o espaço configuracional 𝒜Z , por
um outro processo 𝜇(𝒞𝑃 )𝑡 sobre o mesmo espaço (a cada passo de tempo aplicamos
primeiro 𝒞 e depois 𝑃 ). A esta aproximação denominamos de aproximação do caos.
A aproximação do caos lida com a evolução da densidade das letras pertencentes ao
alfabeto. Neste caso, vamos considerar como par^ametros as frequ^encias relativas
das letras do alfabeto. Como a soma das frequ^encias relativas dessas letras é igual
a um, o número de par^ametros independentes na aproximação do caos é igual ao
número de letras no alfabeto menos um. Sendo assim, em nossa aproximação do
caos, vamos lidar apenas com um par^ametro e para tal vamos escolher a densidade
da letra ⊕.
38
39
Seja 𝑥𝑡 a frequ^encia relativa de ⊕ no tempo 𝑡 e 𝑓 (𝑥𝑡 ) = 𝑥𝑡+1 . Seja 𝑓 de [0, 1] em
[0, 1] uma função contı́nua tal que 𝑓 𝑡 significa a 𝑡–ésima iteração de 𝑓 . Denotamos
𝑥 um ponto fixo de 𝑓 , se 𝑓 (𝑥) = 𝑥. Dessa maneira, o estudo da aproximação do
caos resume–se a estudar um sistema din^amico discreto, o qual por sua vez será
denominado ergódico se ele tiver um único ponto fixo, denotado por 𝑥𝑓 𝑖𝑥𝑜 , e se
∀ 𝑥 ∈ [0, 1]
lim 𝑓 𝑡 (𝑥) = 𝑥𝑓 𝑖𝑥𝑜 .
𝑡→∞
(3.1)
Caso contrário, o sistema din^amico é dito não ergódico . A seguir vamos fazer
uma aproximação do caos para o processo de Stavskaya clássico (PSC).
3.1
Aproximação do caos para o PSC
Conforme foi obtido e analisado em [15], nosso trabalho nesta seção segue as
mesmas análises para aproximação do caos do PSC.
O PSC é definido a partir da superposição Stav Flip 𝛽 aplicada interativamente
a uma medida inicial. O operador de interação stav é determinı́stico e definido
conforme (1.8), enquanto que o operador de interação flip transforma cada ⊖ em ⊕
com probabilidade 𝛽, independentemente do que ocorre nas outras componentes.
Assim, pela definição do operador caótico e do operador de interação stav podemos
escrever
𝜇𝑡 (𝒞 Stav )(⊕) = (𝜇𝑡 𝒞(⊕))2 .
(3.2)
40
Usando (3.2), a aplicação do operador de caos em uma interação do PSC é:
𝜇𝑡 (𝒞 Stav Flip 𝛽 )(⊕) = 𝜇𝑡 (𝒞 Stav )(⊕) + 𝛽(𝜇𝑡 (𝒞 Stav )(⊖))
= 𝜇𝑡 (𝒞 Stav )(⊕) + 𝛽(1 − 𝜇𝑡 (𝒞 Stav )(⊕))
= 𝜇𝑡 (𝒞 Stav )(⊕) + 𝛽 − 𝛽(𝜇𝑡 (𝒞 Stav )(⊕))
= 𝛽 + (1 − 𝛽)(𝜇𝑡 (𝒞 Stav )(⊕))
= 𝛽 + (1 − 𝛽)(𝜇𝑡 𝒞(⊕))2 .
(3.3)
Assim, (3.3) pode ser interpretado como:
𝑥𝑡+1 = 𝑓 (𝑥𝑡 ),
sendo 𝑓 (𝑥𝑡 ) a frequ^encia relativa de ⊕ após a aplicação de uma interação da
aproximação do caos. Por simplicidade, fazendo 𝑥𝑡 = 𝑥, temos
𝑓 (𝑥) = 𝛽 + (1 − 𝛽)𝑥2 .
(3.4)
Resolvendo a equação 𝑓 (𝑥) = 𝑥, obtemos os seguintes pontos fixos de 𝑓 :
𝑝1 = 1 e 𝑝2 =
𝛽
,
1−𝛽
que são análogos às possı́veis medidas invariantes do PSC. Quando 𝛽 > 1/2, o
ponto 𝑝2 é maior que um. Logo, 𝑝1 é o único ponto fixo neste caso. Por outro
lado, para 𝛽 < 1/2, temos associado uma situação de não ergodicidade por haver
mais do que um ponto fixo. Ou seja, temos dois comportamentos diferentes para
𝑓 𝑡 . O primeiro ocorre quando 𝛽 > 1/2, o qual esperamos que no limite as iteradas
de 𝑓 convirjam a 𝑝1 a partir de qualquer ponto inicial uma vez que só existe um
ponto fixo, sugerindo que o PSC é ergódico. O segundo, quando 𝛽 < 1/2, tem
pelo menos dois pontos fixos, sugerindo que o PSC é não ergódico. Em [29] foi
41
demonstrado a exist^encia de um valor crı́tico não trivial 𝛽 * ∈ [1/54, 1/2] para o
PSC. Assim, o resultado obtido neste exemplo, que é 𝛽 * = 1/2, vem confirmar
a reprodução do comportamento obtido do processo real. Em outras palavras, a
aproximação do caos realizada para o PSC se comporta qualitativamente similar
a este processo, inclusive no que se refere ao seu valor crı́tico.
Na Figura 3.1a e 3.1b temos 10 iteraçoes da equação (3.4) quando 𝛽 = 0.25,
mostrando que o sistema din^amico discreto converge para 21 . O mesmo sistema
din^amico converge para 1 quando 𝛽 = 0.7, como pode ser verificado na Figura
3.1c. Estimações mais precisas obtidas em [27] mostraram que 𝛽 * > 0, 09.
42
1.04
y
1.04
0.78
0.78
0.52
0.52
0.26
0.26
y
x
0.26
0.52
0.77
x
1.03
0.26
(a) 𝑥0 = 0 e 𝛽 = 0.25
1.04
0.52
0.77
1.03
(b) 𝑥0 = 0.7 e 𝛽 = 0.25
y
0.78
0.52
0.26
x
0.26
0.52
0.77
1.03
(c) 𝑥0 = 0 e 𝛽 = 0.70
Figura 3.1: Comportamento limite para a aproximação do caos no PSC.
43
3.2
Aproximação do caos para o PSCV
O estudo do operador de interação Birth inter Murder inter é substituı́do por um
estudo do operador caótico 𝒞 Birth inter Murder inter , que, por sua vez, se resume
no estudo do sistema din^amico 𝑓 : [0, 1] → [0, 1] com par^ametros 𝛼, 𝛽 ∈ [0, 1].
Note-se que o PSCV tem comprimento variável e em (1.14) vamos tomar 𝜇𝑖𝑛𝑖𝑐 = 𝛿⊖ ,
ou seja, vamos estudar
𝜇𝑡 = 𝛿⊖ ( Birth inter ∘ Murder inter )𝑡 .
(3.5)
Fazendo a aproximação do caos para nossos operadores de interação definidos por
(1.12) e (1.13), temos
𝜇(𝒞 Birth inter )(⊕) =
𝑥+𝛽
e
1+𝛽
(3.6)
𝑦 − 𝛼𝑦(1 − 𝑦)
,
(3.7)
1 − 𝛼𝑦(1 − 𝑦)
observando que 𝑥 = 𝜇(⊕) = 𝑦. A composição destes operadores de interação,
𝜇(𝒞 Murder inter )(⊕) =
conforme ap^endice A, será denotada por 𝑓 (𝑥) e é dada por:
𝑓 (𝑥) =
(𝑥 + 𝛽)(1 + 𝛽 − 𝛼(1 − 𝑥))
.
(1 + 𝛽)2 − 𝛼(𝑥 − 𝑥2 + 𝛽 − 𝛽𝑥)
(3.8)
𝛼
, com 𝛼 > 0. A aproximação do caos em (3.8)
4−𝛼
possui um ponto fixo se 𝛽 > 𝛽 * (𝛼), dois pontos fixos se 𝛽 = 𝛽 * (𝛼) e tr^es pontos
Lema 19 Seja 𝛽 * (𝛼) =
fixos se 𝛽 < 𝛽 * (𝛼).
Prova. Vamos inicialmente considerar que 0 < 𝛽 < 1. Seja 𝑓 como definido
em (3.8). Resolvendo 𝑓 (𝑥) = 𝑥 encontramos os seguintes pontos fixos, os quais
44
denotamos por 𝑝1 , 𝑝2 e 𝑝3 , isto é,
𝛼(1 − 𝛽) −
𝑝1 =
2𝛼
√︀
ℎ(𝛽)
,
𝛼(1 − 𝛽) +
𝑝2 =
2𝛼
√︀
ℎ(𝛽)
e 𝑝3 = 1,
sendo
ℎ(𝛽) = 𝛽 2 (𝛼2 − 4𝛼) + 𝛽(2𝛼2 − 4𝛼) + 𝛼2 .
(3.9)
Não é difı́cil verificar que
0 < 𝑝1 ≤ 𝑝2 < 𝑝3 = 1.
Por (3.9), ℎ(𝛽) é uma função quadrática de 𝛽 cujo coeficiente do termo de segundo
grau é negativo,
𝑔(𝛼) = 𝛼2 − 4𝛼 < 0
∀ 𝛼 > 0. Vamos denotar as raı́zes de (3.9) por 𝛽 = 𝛽1 (𝛼) e 𝛽 = 𝛽2 (𝛼), em que
𝛽1 (𝛼) = −1 e 𝛽2 (𝛼) =
𝛼
4−𝛼
(3.10)
e observe que 𝛽2 (𝛼) em (3.10) é o nosso 𝛽 * (𝛼). ℎ(𝛽) é negativo quando 𝛽 < 𝛽1 (𝛼)
ou 𝛽 > 𝛽2 (𝛼) e positivo quando 𝛽 está entre 𝛽1 (𝛼) e 𝛽2 (𝛼). Também, podemos
verificar que
𝛽1 (𝛼) < 0 < 𝛽2 (𝛼) < 1
∀ 𝛼 > 0. Assim, se 𝛽 < 𝛽 * (𝛼), então ℎ(𝛽) > 0 e nosso sistema din^amico tem
tr^es pontos fixos diferentes 𝑝1 , 𝑝2 e 𝑝3 . Se 𝛽 = 𝛽 * (𝛼), então ℎ(𝛽) = 0 e o sistema
din^amico tem dois pontos fixos distintos 𝑝1 = 𝑝2 e 𝑝3 . Se 𝛽 > 𝛽 * (𝛼), ℎ(𝛽) < 0 e
assim 𝑓 tem um único ponto fixo 𝑝3 = 1.
O Lema 19 está provado.
45
Proposição 1 A aproximação do caos em (3.8) é ergódica se 𝛽 > 𝛽 * (𝛼) e não
ergódica se 𝛽 ≤ 𝛽 * (𝛼), sendo
{︃
𝛽 * (𝛼) =
𝛼
, se 𝛼 > 0
4−𝛼
0,
se 𝛼 = 0.
(3.11)
Prova.
Primeiro seja 𝛼 = 0. É fácil verificar que, neste caso, nosso sistema din^amico
é ergódico para todo 𝛽 > 0 e não ergódico para 𝛽 = 0. Assim, a Proposição 1 é
verdadeira. Ainda, se 𝛽 = 0 ou 𝛽 = 1, a proposição 1 é evidente. Agora, vamos
assumir que 0 < 𝛽 < 1. Note que, se 𝑥0 ∈ [0, 1], então pelo Lema 19, uma forma
equivalente de reescrever a proposição 1 é a seguinte:
Se ℎ(𝛽) < 0, então lim 𝑓 𝑡 (𝑥0 ) = 𝑝3 = 1 para todo 𝑥𝑜 .
𝑡→∞
{︂
𝑝1 = 𝑝2 , se 𝑥0 ≤ 𝑝1 = 𝑝2 ,
Se ℎ(𝛽) = 0, então lim 𝑓 𝑡 (𝑥0 ) =
𝑡→∞
𝑝3 = 1, se 𝑥0 > 𝑝1 = 𝑝2 .
⎧
se 𝑥0 < 𝑝2 ,
⎨ 𝑝1 ,
𝑡
𝑝,
se 𝑥0 = 𝑝2 ,
Se ℎ(𝛽) > 0, então lim 𝑓 (𝑥0 ) =
𝑡→∞
⎩ 2
𝑝3 = 1, se 𝑥0 > 𝑝2 .
(3.12)
(3.13)
(3.14)
De fato, quando 𝛽 < 𝛽 * (𝛼) ou 𝛽 = 𝛽 * (𝛼), nosso sistema din^amico tem tr^es
pontos fixos distintos (𝑝1 , 𝑝2 e 𝑝3 ) ou dois pontos fixos (𝑝1 = 𝑝2 e 𝑝3 ), respectivamente, isto é, em ambos os casos ele é não ergódico. Quando 𝛽 > 𝛽 * (𝛼), (3.8)
tem um único ponto fixo 𝑝3 = 1. Assim, vamos nos concentrar em provar (3.12),
(3.13) e (3.14). Primeiro (3.12), que equivale a ergodicidade. Note que, 𝑓 definido
em (3.8), é contı́nua em [0, 1] e assim 𝑠(𝑥) = 𝑓 (𝑥) − 𝑥, também, é contı́nua nesse
mesmo intervalo. É fácil verificar que 𝑠(0) > 0 e, além disso, 𝑠 é contı́nua e igual
a zero apenas no ponto 𝑥 = 1. Concluı́mos que 𝑠(𝑥) > 0, ∀ 𝑥 < 1. Portanto,
46
𝑥 < 𝑓 (𝑥), ∀ 𝑥 < 1. Desse fato podemos escrever, também, que:
𝑓 (𝑥) < 𝑓 2 (𝑥),
∀𝑓 (𝑥) < 1.
𝑓 2 (𝑥) < 𝑓 3 (𝑥),
∀𝑓 2 (𝑥) < 1.
........................
Assim,
𝑥 < 𝑓 (𝑥) < 𝑓 2 (𝑥) < 𝑓 3 (𝑥) < . . . < 1.
Logo, se definirmos 𝑎𝑛 = 𝑓 𝑡 (𝑥) com 𝑎0 = 𝑥, temos que 𝑎𝑡 é uma sequ^encia
monótona crescente limitada por 1.
Como o 𝑠𝑢𝑝 de 𝑎𝑛 é 1 concluı́mos que
lim 𝑓 𝑡 (𝑥0 ) = 1 e (3.12) está provada. Agora, a prova para (3.13). Vamos justifi-
𝑡→∞
car a primeira parte de (3.13). Com esse objetivo, vamos reescrev^e-la da seguinte
forma:
Se ℎ(𝛽) = 0, então lim 𝑓 𝑡 (𝑥0 ) =
𝑡→∞
{︂
𝑝1 = 𝑝2 , se 𝑥0 ∈ [0, 𝑝1 ],
𝑝3 = 1, se 𝑥0 ∈ (𝑝1 , 1].
Note-se que se ℎ(𝛽) = 0, então nosso sistema din^amico possui dois pontos fixos
e, além disso, 0 < 𝑝1 ≤ 𝑝2 < 𝑝3 = 1. Agora, note também que 𝑓 é contı́nua em
[0, 𝑝1 ], pois [0, 𝑝1 ] ⊂ [0, 1]. A partir daqui a prova segue análoga aquela feita
para (3.12) e assim 𝑓 𝑡 (𝑥0 ) −→ 𝑝1 quando 𝑡 → ∞. A prova para a segunda parte de
(3.13) é análoga à prova que foi feita para sua primeira parte, notando que agora
vamos querer mostrar o comportamento limite em (𝑝1 , 1]. A prova para (3.14) é
análoga a que fizemos para (3.13). A Proposição 1 está provada.
A Figura 3.2 apresenta exemplos para o comportamento limite desses pontos
fixos.
47
1.04
y
1.82
y
1.56
0.78
1.30
1.04
0.52
0.78
0.52
0.26
0.26
x
x
0.26
0.52
0.77
0.26
1.03
(a) 𝑥0 = 0; 𝛼 = 0, 2 e 𝛽 = 0, 2
0.52
0.77
1.03
1.29
1.55
1.80
(b) 𝑥0 = 1, 5; 𝛼 = 0, 2 e 𝛽 = 0, 2
1.04
y
y
1.04
0.78
0.78
0.52
0.52
0.26
0.26
x
x
0.26
0.52
0.77
1.03
(c) 𝑥0 = 0; 𝛼 = 0, 6 e 𝛽 = 0.1
0.26
0.52
0.77
1.03
(d) 𝑥0 = 0, 8; 𝛼 = 0, 6 e 𝛽 = 0.1
Figura 3.2: Comportamento limite para a aproximação do caos no PSCV.
Capı́tulo 4
Simulação de Monte Carlo do processo
Singular
Segundo Sobol [24], o método de Monte Carlo é um método numérico capaz de
resolver problemas matemáticos por meio de simulação de variáveis aleatórias.
O artigo intitulado The Monte Carlo Method (O Método de Monte Carlo) publicado em 1949 (Journal of the American Statistical Association) pelos matemáticos
norte-americanos N. Metropolis e S. Ulam, marca o nascimento do método Monte
Carlo, apesar de sua base teórica ser conhecida há muito tempo conforme em [24].
A primeira refer^encia do método de Monte Carlo é devido ao naturalista franc^es
George Louis Leclerc, Conde de Buffon, que em 1777 enunciou e resolveu àquele
que ficou conhecido como o problema da agulha de Buffon. Este problema é
um estudo probabilı́stico do lançamento aleatório de uma agulha num plano com
infinitas linhas paralelas.
A real utilização do método de Monte Carlo se deu como ferramenta de pesquisa
no Projeto Manhattan para construção da bomba at^omica na segunda guerra
mundial, envolvendo simulação direta de problemas probabilı́sticos, preocupandose com a difusão aleatória de n^eutrons em material fı́ssil, conforma consta em
[5].
48
49
Agora, vamos fazer uma simulação Monte Carlo, cuja discrep^ancia com o nosso
resultado teórico é realmente surpreendente. Baseado em nosso lema principal, ao
invés de simular o processo VarStav , vamos simular o processo Single , o qual é
mais fácil de realizar. Vamos descrever um procedimento, denominado Imitação
e que é uma imitação de Monte Carlo de nosso processo. Lembre-se que S𝑡 é
uma variável aleatória com distribuição 𝛿0 ( Single )𝑡 . Este procedimento gera uma
sequ^encia de variáveis aleatórias na seguinte forma indutiva.
Base de indução: 𝑆0 = 0.
𝑡−ésimo passo de indução:
• Fixe 𝛼 e 𝛽 no intervalo [0, 1].
• Dado 𝑆𝑡+1 , com 𝑡 = 1, 2, 3, . . . , realize dois procedimentos:
Primeiro procedimento imitando Birth:
• Gere uma variável aleatória Δ𝑏𝑖𝑟𝑡ℎ com distribuição binomial, Bin (𝑆𝑡 + 1, 𝛽).
• Faça 𝑌 = 𝑆𝑡 + Δ𝑏𝑖𝑟𝑡ℎ .
Segundo procedimento imitando Murder:
Gere uma variável aleatória 𝑈 distribuida uniformemente no intervalo [0, 1].
Assim, o que ocorre é um dos tr^es casos seguintes:
• 𝑆𝑡+1 = 𝑌 − 1, se 𝑈 < 𝛼 e 𝑌 > 0;
• 𝑆𝑡+1 = 𝑌, se 𝑈 > 𝛼 e 𝑌 > 0;
• 𝑆𝑡+1 = 𝑌, se 𝑌 = 0.
Condição de parada: dada uma constante 𝑇 = 1000000, paramos quando
𝑡 = 𝑇 ou 𝑆𝑡 > 10000.
50
Assim, define-se Imitação. Neste momento, devemos prestar atenção ao fato
que dado um par (𝛼, 𝛽), se realizamos Imitação 𝑛 vezes independentemente, o
resultado será o mesmo como se simulássemos o processo original VarStav com a
condição inicial “todos menos”.
Seja 𝐸 uma variável binária que significa ergodicidade e assume o valor sim, se
𝑆𝑡 > 10000; caso contrário, 𝐸 assume o valor não. Se 𝐸 = 𝑠𝑖𝑚, vamos interpretar
isso como uma sugestão de que o PSCV, com seus respectivos valores de 𝛼 e 𝛽,
é ergódico. Por outro lado, 𝐸=não é assumido como uma sugestão de que nosso
processo é não ergódico.
Sendo assim, vamos usar Imitação dentro de um ciclo crescente de 𝛽: Iniciamos com 𝛽 = 0 e iterativamente realizamos Imitação para cada aumento de um
milésimo de 𝛽. Repetimos o procedimento até 𝛽 atingir o valor 1 ou 𝐸 assumir
o valor 𝑠𝑖𝑚, que é como ergodicidade é sugerida. Assim, obtemos um valor de 𝛽.
Na verdade, realizamos este ciclo 10 vezes e guardamos a média aritmética dos 10
valores de 𝛽 assim obtidos.
Devemos lembrar que tudo isso foi feito para um certo valor de 𝛼. Na verdade,
consideramos 1000 valores de 𝛼, isto é, 𝛼𝑖 = 0, 001 𝑖, para 𝑖 = 1, . . . , 1000. O
correspondente valor guardado de 𝛽 foi denotado por 𝛽𝑖 . Assim, obtemos 1000
pares da forma (𝛼𝑖 , 𝛽𝑖 ) que nos ajudará a construir uma pseudo-curva denotada
por “curva” de Monte Carlo (M.C.). A curva de Monte Carlo vai nos dar uma
ideia do comportamento do nosso processo. Na Figura 4.1 mostramos a curva
M.C., juntamente com a curva obtida pela aproximação do caos, dada por 𝛽 * (𝛼)
e encontrada em (3.11), a qual denotamos por caos.
Cada uma dessas curvas estima a linha de separação entre ergodicidade e não
ergodicidade de nosso processo.
51
probabilidade de Nascimento, β
0.35
0.3
caos
0.25
0.2
0.15
0.1
M.C.
0.05
0
0
0.2
0.4
0.6
probabilidade de Matança, α
0.8
1
Figura 4.1: Estimação das linhas de transição entre ergodicidade e não ergodicidade para PSCV,
obtidas pela aproximação do caos (caos) e Método de Monte Carlo (M.C.)
4.1
̂︀
Simulação de IE(𝑚𝑎𝑥(𝑆
𝑡 ))
A partir de agora, vamos falar sobre outro tipo de experimento computacional.
Para o processo Single foi realizado o seguinte experimento computacional: fixamos 𝛼 = 0, 1 𝑖, 𝑖 = 1, 2, . . . , 9 e 𝛽 variando de 0 até 0, 13 com incremento de 0, 001.
Para cada par, executamos o procedimento imitação, definido anteriormente. Se
no término de imitação for sugerido não-ergodicidade, 𝐸=não, salvamos o valor
máximo que 𝑆𝑡 tem alcançado no processo. Da mesma forma, se no término de
imitação for sugerido ergodicidade, 𝐸 = 𝑠𝑖𝑚, salvamos o valor máximo que 𝑆𝑡
52
assumiu. Este valor máximo será denotado por 𝑚𝑎𝑥(𝑆𝑡 ). Em outras palavras,
dado um par (𝛼, 𝛽),
max(𝑆𝑡 ) = max{𝑆𝑡 : 𝑡 = 0, . . . , 100000}.
Para cada par, este experimento foi repetido 100 vezes. Assim, teremos 100 valores
de máximo, 𝑚𝑎𝑥𝑖 (𝑆𝑡 ), 𝑖 = 1, 2, . . . , 100, obtidos de cada experimento. Calculamos
̂︀
a média desses 100 valores de máximo, a qual denotamos por IE(𝑚𝑎𝑥(𝑆
𝑡 )) e definimos como
100
1 ∑︁
̂︀
IE(𝑚𝑎𝑥(𝑆
))
=
𝑚𝑎𝑥𝑖 (𝑆𝑡 ).
𝑡
100 𝑖=1
̂︀
Os gráficos na Figura 4.2, nos mostram os valores de IE(𝑚𝑎𝑥(𝑆
𝑡 )), no eixo das
ordenadas, versus a probabilidade 𝛽, no eixo das abscissas. Para uma visualização
̂︀
ampliada, a localização dos valores de IE(𝑚𝑎𝑥(𝑆
𝑡 )), foi dada segundo uma escala
logarı́tmica. Em cada gráfico dessa figura foi mostrado um subgráfico (subjanelas)
de trechos ampliados dos gráficos maiores, evidenciando saltos ocorridos em cada
gráfico. Saltos como estes, tradicionalmente, sugerem o fen^omeno de transição de
fase em um certo sentido, que pode ser clássico ou de velocidade de crescimento.
Observamos que, tanto em cada gráfico da Figura 4.2, quanto conjuntamente, em
média, os valores máximos de 𝑆𝑡 tendem a crescer para valores crescentes de 𝛽 e
que próximo à linha de transição existe um aumento abrupto.
53
10000
100000
10000
10000
10000
1000
1000
1000
E[max(St)]
E[max(St)]
100
10
100
1
0.006
0.0075
0.009
1000
100
0.015 0.016 0.017 0.018 0.019
100
0.02
10
10
1
1
0
0.002
0.004
0.006
0.008
probabilidade de Nascimento, β
0.01
0.012
0
0.005
0.01
0.015
probabilidade de Nascimento, β
(a) 𝛼 = 0, 1
0.02
0.025
(b) 𝛼 = 0, 2
100000
100000
10000
10000
10000
10000
1000
1000
E[max(St)]
10
1
0.02
100
100
1000
0.025
0.03
10
100
1
0.03
0.035
0.04
10
10
1
1
0.1
0
0.005
0.01
0.015
0.02
0.025
0.03
probabilidade de Nascimento, β
0.035
0
0.005
0.01
0.015
0.02
0.025
(d) 𝛼 = 0, 4
100000
10000
10000
1000
100
1000
10
1
0.03
100
0.032 0.034 0.036 0.038
0.04
10
1
0
0.01
0.02
0.03
0.04
probabilidade de Nascimento, β
(e) 𝛼 = 0, 5
0.03
0.035
probabilidade de Nascimento, β
(c) 𝛼 = 0, 3
E[max(St)]
E[max(St)]
100
1000
0.05
0.06
0.04
0.045
54
100000
100000
10000
10000
10000
10000
1000
100
100
1000
E[max(St)]
1000
E[max(St)]
1000
10
100
1
0.045
0.05
0.055
10
100
1
0.055
10
10
1
1
0.1
0.06
0.1
0
0.01
0.02
0.03
0.04
0.05
0.06
probabilidade de Nascimento, β
0.07
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
probabilidade de Nascimento, β
(f) 𝛼 = 0, 6
0.08
0.09
(g) 𝛼 = 0, 7
100000
100000
10000
10000
10000
10000
1000
1000
100
100
1000
E[max(St)]
1000
E[max(St)]
0.065
10
100
1
0.075
0.08
0.085
10
100
1
0.085
10
10
1
1
0.1
0.09
0.095
0.1
0.1
0
0.02
0.04
0.06
probabilidade de Nascimento, β
(h) 𝛼 = 0, 8
0.08
0.1
0
0.02
0.04
0.06
0.08
0.1
probabilidade de Nascimento, β
0.12
(i) 𝛼 = 0, 9
Figura 4.2: Comportamento da estimativa da média de 𝑚𝑎𝑥(𝑆𝑡 ), para 𝛼 = 0, 1 𝑖, 𝑖 = 1, 2, . . . , 9 e 𝛽
variando de 0 até 0, 13. Para cada par de 𝛼 e 𝛽, foram realizados 100 experimentos independentes.
55
A Figura 4.3 ilustra os valores que 𝑆𝑡 assume para 𝛼 = 0, 9 e 𝛽 = 0, 05. Esta
figura sugere que, para todo 𝑡, a “trajetória” de 𝑆𝑡 fica intensamente concentrada nos valores {0, 1} e muito suavemente concentrada no valor 2, sugerindo,
inicialmente que, para esses valores de 𝛼 e 𝛽, 𝛿⊖ ( VarStav )𝑡 não tende para 𝛿⊕ ,
contrariando nosso teorema principal.
6
5
St
4
3
2
1
0
0
250000
500000
750000
1e+006
Passo de tempo t
Figura 4.3: Gráfico que mostra, para 𝛼 = 0, 5 e 𝛽 = 0, 02, os valores de 𝑆𝑡 , na simulação do
processo Singular
Capı́tulo 5
Conclusões
Introduzimos neste trabalho o processo de Stavskaya com comprimento variável
(PSCV), inspirado no bem conhecido processo de Stavskaya clássico. Nosso estudo
está dividido em aproximação do caos, resultados teóricos e simulação de Monte
Carlo, não necessariamente nesta ordem. O maior resultado teórico, dado pelo
teorema principal só foi possı́vel por que o operador de interação VarStav , que é
não linear, p^ode ser reduzido ao operador Single , que por sua vez é linear.
Este teorema nos mostrou que 𝛿⊖ ( VarStav )𝑡 tem comportamento ergódico, uma
vez que, para todo 𝛼 < 1 e 𝛽 > 0, este processo tende para 𝛿⊕ . Tanto a aproximação do caos, quanto a simulação de Monte Carlo se mostraram, surpreendentemente, em outra direção com respeito ao nosso resultado teórico, pois estes
métodos sugeriram a exist^encia de uma linha de separação entre ergodicidade e
não ergodicidade de nosso processo, de acordo com a Figura 4.1. Investigando um
pouco mais a questão, vimos que, quando simulamos 𝑆𝑡 para os valores 𝛼 = 0, 9 e
𝛽 = 0, 05, sua trajetória fica intensamente concentrada em {0, 1} e esparsamente
concentrada nos outros valores (vide Figura 4.3), sugerindo que nosso processo não
tende para 𝛿⊕ . Isto constitui um exemplo de um novo tipo: um processo de comprimento variável, para ilustrar um aparente conflito entre simulação computacional
de processos aleatórios e seu estudo teórico.
56
57
Notamos entretanto que, a simulação de Monte Carlo e a aproximação do caos,
se comportam como se 𝛿⊖ ( VarStav )𝑡 tendesse para 𝛿⊕ , de forma muito mais lenta
para alguns valores de 𝛼, 𝛽 ∈ (0, 1), do que para outros. Isto nos faz acreditar
na seguinte conjectura: VarStav tem fase, porém, não no sentido simples como
acontece no processo clássico de Stavskaya.
Na verdade, podemos estudar ainda mais nosso processo à luz da teoria dos
operadores de substituição vistos em [33]. Por exemplo, neste mesmo trabalho, o
𝜌
operador de substituição básico, denominado inserção e representado por Λ −→ ℎ,
em que ℎ é uma letra de algum alfabeto, coincide com o nosso operador de interação
Birth inter , quando fazemos ℎ = ⊕ e 𝜌 = 𝛽. Apesar de não ser obtido diretamente
dos operadores de substituição básicos vistos em [33], o operador de interação
Murder inter pode ser obtido na Seção 1.7 deste trabalho, voltada a composição
dos operadores de substituição.
Por fim, vale ressaltar que esta tese utilizou os principais resultados do artigo intitulado Variable-Length Analog of Stavskaya Process: A New Example of
Misleading Simulation, recentemente submetido ao Journal of Statistical Physics.
Ap^
endice A
Cálculos da aproximação do caos para o
PSCV
Note-se que a aproximação do caos para os nossos operadores é dada por (3.6) e
(3.7). Substituindo 𝑦 por (𝜇(𝒞 Birth inter )(⊕)) em (3.7), obtemos que a composição
destes operadores é
𝜇𝒞 Birth inter Murder inter (⊕) =
=
=
=
=
[𝜇(𝒞 Birth inter )(⊕)][1 − 𝛼(1 − (𝜇(𝒞 Birth inter )(⊕)))]
1 − 𝛼(𝜇(𝒞 Birth inter )(⊕))(1 − (𝜇(𝒞 Birth inter )(⊕)))
(︂
)︂
𝑥+𝛽
𝑥+𝛽
𝑥+𝛽
−𝛼
1−
1+𝛽
1+𝛽
1+𝛽
(︂
)︂
𝑥+𝛽
𝑥+𝛽
1−𝛼
1−
1+𝛽
1+𝛽
(1 + 𝛽)(𝑥 + 𝛽) − 𝛼(𝑥 + 𝛽)[1 + 𝛽 − (𝑥 + 𝛽)]
(1 + 𝛽)2 − 𝛼(𝑥 + 𝛽)[1 + 𝛽 − (𝑥 + 𝛽)]
(1 + 𝛽)(𝑥 + 𝛽) − 𝛼(𝑥 + 𝛽)(1 − 𝑥)
(1 + 𝛽)2 − 𝛼(𝑥 + 𝛽)(1 − 𝑥)
(𝑥 + 𝛽)(1 + 𝛽 − 𝛼(1 − 𝑥))
.
(1 + 𝛽)2 − 𝛼(𝑥 − 𝑥2 + 𝛽 − 𝛽𝑥)
Assim, a densidade de ⊕ na medida 𝜇𝒞 Birth inter Murder inter depende apenas da
densidade de ⊕ na medida 𝜇. Fazendo
𝑓 (𝑥) = 𝜇𝒞 Birth inter Murder inter (⊕),
58
59
temos que
𝑓 (𝑥) =
(𝑥 + 𝛽)(1 + 𝛽 − 𝛼(1 − 𝑥))
.
(1 + 𝛽)2 − 𝛼(𝑥 − 𝑥2 + 𝛽 − 𝛽𝑥)
Refer^
encias Bibliográficas
[1] A. Busic, J. Maitresse and I. Marcovici. Probabilistic cellular automata, invariant measures, and perfect sampling. STACS 2011, pp. 296-307.
[2] J. Depoorter and C. Maes. Stavskaya’s Measure Is Weakly Gibbsian. Markov
Processes and Related Fields, vol. 12 (2006), pp. 791-804.
[3] R. Fernandez, P. A. Ferrari, N. Garcia. Perfect simulation for interacting
point processes, loss networks, and Ising models. Stoch. Process. Appl., vol.
102 (2002), n. 1, pp. 63-88.
[4] L. Gray. A mathematician looks at Stephen Wolfram’s New Kind of Science.
Notices of the AMS, vol. 50 (February 2003), n. 2, pp. 200-211.
[5] J. M. Hammersley, D. C. Handscomb. Monte Carlo Methods. Chapman and
Hall, London, 1964.
[6] A. N. Kolmogorov and S. V. Fomin. Introductory real analysis. Translated and
Edited by Richard A. Silverman Dover publications, Inc, New York (1970).
[7] G. L. Kurdyumov. An algorithm-theoretic method for the study of homogeneous random networks. Adv. Probab, vol. 6 (1980), pp. 471-504.
[8] T. M. Liggett. Interacting Particle Systems. Springer, 1985.
60
61
[9] T. M. Liggett. Stochastic Intracting Systems: Contact, Voter, and Exclusion
Processes. Springer, 1999.
[10] C. Maes. New Trends in Interacting Particle Systems. Markov Proc. Rel.
Fields, vol. 11 (2005), n. 2, pp. 283-288.
[11] V. Malyshev. Quantum Grammars. Journal of Mathem. Physics, vol. 41
(2000), n. 7, pp. 4508-4520.
[12] V. Malyshev. Quantum Evolution of Words. Theoretical Computer Science
(2002). Avaliable at
http://www-rocq.inria.fr/\%7Emalyshev/Malyshev/papers.htm.
[13] I. Narsky. Estimation of Goodness-of-Fit in Multidimensional Analysis Using
Distance to Nearest Neighbor. arXiv: physics/0306171v1.
[14] N. V. Petri. Unsolvability of the recognition problem for annihilating iterative
networks. Selecta Mathematica Sovietica, vol. 6 (1987), pp. 355-363.
[15] A. D. Ramos. Particle process with variable length. Ph.D. Thesis. Federal
University of Pernambuco, Departament of Statistics, Recife, Pernambuco,
Brazil (2007). (In Portuguese with an abstract in English). Available at
http://de.ufpe.br/~toom/ensino/doutorado/alunos/index.htm.
[16] A. D. Ramos and A. Toom. An error correction. Letter to the editor. Journal
of Statistical Physics, vol. 131, number 1 (april 2008), pp 167-168.
[17] A. D. Ramos and A. Toom. Chaos and Monte-Carlo approximations of the
Flip-Annihilation process. Journal of Statistical Physics, vol. 133 (2008), n. 4,
pp. 761-771.
62
[18] A. D. Ramos and A. Toom. Non-ergodicity and growth are compatible for
1-D local interaction. Brazilian Journal of Probability and Statistics, vol. 24
(2010), n. 2, pp.400-412.
[19] A. D. Ramos and A. Toom. Trajectories in Random Monads. Journal of Statistical Physics, vol. 142 (2011), n. 1, pp. 201-219.
[20] A. V. Rocha, A. B. Simas and A. Toom. Substitution Operators. Journal of
Statistical Physics, vol. 143, (2011), n. 3, pp. 585-618.
[21] O. Stavskaya. Gibbs invariant measures for Markov chains on finite lattices
with local interaction. Mat. Sbornik, vol. 21 (1973), pp. 395. (Em russo.)
[22] O. Stavskaya and I. Piatetski-Shapiro. On homogeneous nets of spontaneously
active elements. Systems Theory Res., vol. 20 (1971), pp. 75-88.
[23] M. Shaked and J. G. Shanthikumar. Stochastic orders. Springer Series in
Statistics. Springer, New York, 2007.
[24] M. I. Sobol. A Primer for the Monte Carlo Method. London: CRC Press,
1994.
[25] A. Toom. A Family of Uniform Nets of Formal Neurons. Soviet Math. (Doklady), 1968, vol.9 n.6, pp. 1338-1341.
[26] A. Toom. On invariant measures in non-ergodic random media. Probabilistic
Methods of Investigation, issue 41. Ed. by A. Kolmogorov. Moscow University
Press, Moscow, pp.43-51, 1972. (Em Russo).
[27] A. Toom, N. Vasilyev, O. Stavskaya, L. Mityushin, G. Kurdyumov and S.
Pirogov. Discrete local Markov systems. Stochastic Cellular Systems : ergodicity, memory, morphogenesis. Ed. by R. Dobrushin, V. Kryukov and A.
63
Toom. Nonlinear Science: theory and applications, Manchester University
Press, 1990, pp. 1-182.
[28] A. Toom. Cellular Automata with Errors: Problems for Students of Probability. Topics in Contemporary Probability and its Applications. Ed. J. Laurie
Snell. Series Probability and Stochastics ed. by Richard Durrett and Mark
Pinsky. CRC Press, 1995, pp. 117-157.
[29] A. Toom. Contours, convex sets, and cellular automata. Text of a course at
the 23-th Colloquium of Brazilian mathematicians. Translated from English
into Portugues by Andréa Vanessa Rocha and Pedro Ferreira de Lima. IMPA,
2001.
[30] A. Toom. Particle systems with variable length. Bulletin of the Brazilian
Mathematical Society, vol. 33, n. 3, November 2002, pp. 419-425.
[31] A. Toom. Non-ergodicity in a 1-D particle process with variable length. Journal
of Statistical Physics, vol. 115 (2004), nn. 3/4, pp. 895-924.
[32] A. Toom. Every continuous operator has an invariant measure. Journal of
Statistical Physics, vol. 129 (2007), pp. 555-566.
[33] A. Toom, A. Ramos, A. Rocha e A. Simas. Processos Aleatórios com Comprimento Variável. Text of a course at the 28-th Colloquium of Brazilian
mathematicians. IMPA, 2011.