alana-deyvison

Prévia do material em texto

1/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Cadeias de Markov e Random Walks
Alana de Santana Correia
Deyvison N. Rodrigues
IC - Unicamp
06/2019
2/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Sumário
1 Introdução
2 Definições e Conceitos
3 Classificação de Estados
4 Distribuições Estacionárias
5 Random Walks
6 Paradoxo de Parrondo
3/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Introdução
Um Processo Estocástico é uma coleção de variáveis aleatórias
(Xt), que são indexadas por um índice t, sendo que esse índice
geralmente é o tempo.
4/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Introdução
Exemplo de Processo Estocástico: Condição do solo no início
de cada mês durante o período de um ano.
Xt =

1, muitobom
2, regular
3, ruim
(1)
t = 1, 2, 3, ... (2)
Temos um processo estocástico X0,X1,X1, ...,X12 quando a cada
instante de tempo a variável aleatória pode assumir valores
diferentes.
5/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Introdução
Classificação de Processos Estocásticos:
Discreto Contínuo
Estado
os valores de Xt são
enumeráveis ou finitos
caso contrário
Parâmetro t t é finito ou enumerável caso contrário
Exemplos:
1 Número de usuários em uma fila de banco: Estado Discreto e
Tempo contínuo.
6/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Introdução
Várias aplicações:
1 Física
2 Química
3 Reconhecimento de Fala
4 Teoria de Filas
5 Aplicações de internet
6 Economia e finanças
7 Biologia
8 Genética
9 Jogos
7/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Introdução
Alguns tipos de Processos Estocásticos:
1 Processo Independente
2 Processo de Poisson
3 Processos de Markov
8/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Processos de Markov
Propriedade da perda de memória (propriedade de Markov);
Definição 7.1
Dada uma sequência de variáveis aleatórias X0,X1,X2, ...,Xt um
processo é markoviano se
Pr = (Xt = at |Xt−1 = at−1,Xt−2 = at−2,Xt−3 = at−3, ...,X0 =
a0) = Pr(Xt = at |Xt−1 = at−1) = Pat−1,at
Se o tempo é discreto esse processo é chamado de cadeia de
markov;
A propriedade de Markov não implica que Xt é independente
da sequência de variáveis aleatórias X0,X1,X2, ...,Xt−2;
9/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Processos de Markov
Representação das cadeias de Markov
1
2 3
0.5
0.5 10.5
0.2
0.3
10/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Processos de Markov
Representação Matemática:
Matriz de Transição: P =

P0,0 P0,1 ... P0,j ...
P1,0 P1,1 ... P1,j ...
...
...
. . .
...
...
Pi ,0 Pi ,1 ... Pi ,j ...
...
...
. . .
...
. . .

Vetor de Probabilidade: p̂(t) = (p0(t), p1(t), p2(t), ...)
11/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Processos de Markov
1
2 3
0.5
0.5 10.5
0.2
0.3
Matriz de Transição: P =
0.2 0.5 0.30 0.5 0.5
0 0 1

Vetor de Probabilidade: p̂(0) = (1, 0, 0)
12/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Processos de Markov
Predições futuras utilizando a representação gráfica
Qual a probabilidade da condição do solo ser boa no mês três
sabendo que inicialmente p̂(0) = (1, 0, 0)?
1
2 3
0.5
0.5 10.5
0.2
0.3
Só existe um caminho possível: 1-1-1
p̂1(3) = 1 ∗ 0.2 ∗ 0.2 ∗ 0.2 = 0.0080
13/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Processos de Markov
Qual seria a condição do solo no mês 4?
p(1) = p(0)P
p(2) = p(1)P
p(3) = p(2)P
p(4) = p(3)P
...
p(4) = p(0)P4
Para estimar a condição futura de um sistema modelado por uma
cadeia de Markov é suficiente conhecer apenas a distribuição de
probabilidade inicial e a matriz de transição.
p̂(t + m) = p̂(t)Pm
14/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Simplificação do algoritmo SAT (NP-difícil);
Algoritmo SAT
Determinar se existe um conjunto de valores para variáveis boolea-
nas de uma determinada fórmula booleana tal que esse conjunto de
valores satisfaça uma fórmula booleana do tipo:
(x1 ∨ x3 ∨ x4... ∨ xn) ∧ (x2 ∨ x4 ∨ x5... ∨ xn)
As variáveis booleanas são literais
Uma disjunção de literais é chamada cláusula
Algoritmo 2-SAT
A entrada possui apenas 2 literais por cláusula:
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x1 ∨ x2) ∧ (x4 ∨ x3) ∧ (x4 ∨ x1)
15/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
1 início
2 u ← atribuição arbitrária
3 para j ← 1 até 2mn2 faça
4 se u satisfaz φ então
5 retorna o algoritmo é satisfatível
6 fim
7 Escolhe uma cláusula de φ não satisfeita por u
8 Escolhe com probabilidade uniforme um dos literais da
cláusula não satisfeita u(x)← u(x)
9 fim
10 se u satisfaz φ então
11 retorna o algoritmo é satisfatível
12 fim
13 senão
14 retorna o algoritmo não é satisfatível
15 fim
16 fim
16/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Lemma 7.1
Supondo que uma fórmula 2-SAT com n variáveis tenha uma atri-
buição satisfatória e que o algoritmo 2-SAT possa ser executado até
encontrar essa atribuição. Então, o número esperado de passos
até que o algoritmo encontre uma atribuição é no máximo n2.
17/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Modelar o problema como uma cadeia de Markov:
Xi =

0 nenhuma variável e igual conjunto S
1 uma variável e igual conjunto S
...
...
n todas as variáveis são iguais ao conjunto S
0 1
...
p = ???
p = ???
2
p = ???
p = ???
n
p = ???p = ???
p = ???
18/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Modelar o problema como uma cadeia de Markov:
Conjunto S
Definir as probabilidades condicionais
Primeiro caso (Xi = 0): Pr(Xi+1 = 1|X0 = 0) = 1
Segundo caso (Xi > 0):
Pr(Xi+1 = j + 1|Xi = j) > 12
Pr(Xi+1 = j − 1|Xi = j) 6 12
Problema não é completamente Markoviano
19/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Geração de uma versão pessimista do processo estocástico X0,X1,X2, ...:
Y0 = X0
Pr(Yi+1 = 1|Y0 = 0) = 1
Pr(Yi+1 = j + 1|Yi = j) = 12
Pr(Yi+1 = j − 1|Yi = j) = 12
20/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
O que queremos encontrar é o número esperado de passos do algo-
ritmo saindo de um estado j até o estado n (hj).
hn = 0
h0 = h1 + 1
E [Zj ] = E [
1
2(1 + Zj−1) +
1
2(1 + Zj+1)]
hj =
hj−1+1
2 +
hj+1+1
2 =
hj−1
2 +
hj+1
2 + 1
21/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Resolvendo o sistema de equações para hj .
hj =
n2−(j−1)2
2 +
n2−(j+1)2
2 + 1 = n
2 − j2
h0 = (n
2 − 1) + 1 = n2
22/58
Introdução Definiçõese Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Teorema 7.2
O algoritmo 2-SAT sempre retorna uma resposta correta quando
a fórmula é insatisfatível. Se a fórmula é satisfatível, então com
probabilidade de pelo menos 1−2m que a fórmula é satisfatível. Caso
contrário, ele retorna incorretamente que a fórmula é insatisfatível.
23/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
ALGORITMO 2-SAT
Usando a desigualdade de Markov:
Pr(Z > 2n2) 6 n
2
2n2 =
1
2
Então a probabilidade do algoritmo falhar após m iterações é
(1
2
)m.
24/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Analisar o comportamento a longo prazo;
Definição 7.2
O estado j é acessível a partir do estado i , se para algum n > 0,
temos que Pni ,j > 0. Se dois estados i e j são acessíveis um ao outro,
dizemos que eles se comunicam (i ↔ j)
25/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Comunicação define uma relação de equivalência;
1 Reflexivo: Para qualquer estado i , temos que i ↔ i ;
2 Simétrico: Se i ↔ j , então j ↔ i ;
3 Transitivo: Se i ↔ j e j ↔ k , então i ↔ k ;
A relação de comunicação particiona os estados em classes de
equivalências disjuntas.
26/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Definição 7.3
Uma cadeia de Markov é irredutível se todos os estados pertence a
uma classe de comunicação.
Fortemente conexo;
A partir de um estado, posso chegar em qualquer outro da
mesma classe.
27/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Seja r ti ,j a probabilidade de que iniciando no estado i , a
primeira transição para o estado j , ocorra no tempo t.
r ti ,j = Pr(Xt = j , e para 1 ≤ s ≤ t − 1,Xs 6= j | X0 = 1)
28/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Definição 7.4
Um estado i é recorrente se
∑
t≥1
r ti ,i = 1;
Um estado i é transiente se
∑
t≥1
r ti ,i < 1;
28/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Definição 7.4
Um estado i é recorrente se
∑
t≥1
r ti ,i = 1;
Um estado i é transiente se
∑
t≥1
r ti ,i < 1;
28/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Definição 7.4
Um estado i é recorrente se
∑
t≥1
r ti ,i = 1;
Um estado i é transiente se
∑
t≥1
r ti ,i < 1;
Se um estado em uma classe de comunicação é
transiente(respectivamente recorrente), então todos os estados
daquela classe são transiente(respectivamente recorrente).
29/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Seja hi ,j o tempo esperado alcançar j de um estado i ;
hi ,j =
∑
t≥1
t · r ti ,j
Definição 7.5
Um estado recorrente i é positivo recorrente se hi ,i < ∞. Caso
contrário é nulo recorrente.
30/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Estados são os positivos inteiros;
O estado i tem probabilidade de ir para o estado i + 1 de ii+1 ;
O estado i tem probabilidade de ir para o estado 1 de 1i+1 .
1 2 3 4 ...
1
2
2
3
3
4
1
2 13
1
4
31/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
A probabilidade de não ter voltado para o estado 1 em t passos:
t∏
j=1
j
j + 1
=
1
t + 1
então temos que o estado 1 é recorrente:
r t1,1 =
1
t(t + 1)
32/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Classificação de Estados
Número esperados de passos até retornar para o estado 1 é:
ht1,1
∞∑
t=1
t · r t1,1 =
∞∑
t=1
1
t + 1
,
que é ilimitado, logo o estado 1 é recorrente nulo.
Lema 7.5: Em uma cadeia finita de Markov
1 Ao menos um estado é recorrente;
2 Todos os estados recorrentes são positivos recorrentes.
33/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Exemplo: Ruína do Jogador
Quando se tem mais de uma classe de estados recorrente, estamos
interessados em na probabilidade do processo entrar e ser absorvido
em uma dada classe de comunicação.
Jogo de apostas justas entre dois jogadores;
Estados do jogador 1 no tempo t;
L1 e L2;
estado inicial é 0;
−L1 e L2 são estados recorrentes;
34/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Exemplo: Ruína do Jogador
lim
t→∞
Pti = 0, ∀i : −L1 < i < L2
Seja q a probabilidade do jogador 1 vencer o jogo, então:
lim
t→∞
PtL2 = q.
Seja W t o ganho do jogador 1 após t passos, então temos que:
E [W t ] = 0; e
lim
t→∞
E [W t ] = L2q − L1(1− q); ento
q =
L1
L1 + L2
35/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Dada a matriz Pn para m = 1.
P1 =

0.080 0.184 0.368 0.368
0.632 0.368 0 0
0.264 0.368 0.368 0
0.080 0.184 0.368 0.368

36/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Dada a matriz Pn para m = 2.
P2 =

0.249 0.286 0.300 0.165
0.283 0.252 0.233 0.097
0.351 0.319 0.233 0.097
0.249 0.286 0.300 0.165

37/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Dada a matriz Pn para m = 8.
P8 =

0.286 0.285 0.264 0.166
0.286 0.285 0.264 0.166
0.286 0.285 0.264 0.166
0.286 0.285 0.264 0.166

38/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Figura 1: Comportamento do vetor de probabilidade dos estados.
39/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Definição
Uma distribuição estacionária (também chamada de distribuição de
equiblíbrio) π̂ ocorre quando
π̂(t + 1) = π̂(t)P = π̂(t)
40/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Teorema
Se a cadeia de Markov é finita, irredutível e ergódica ela apresenta
as seguintes propriedades:
a cadeia apresenta uma única distribuição estacionária
π̃ = (π0, π1, π2, ..., πn);
Para todo j e i o limt→∝Ptj ,i existe e ela é independente de j;
πi = limt→∝P
t
j ,i =
1
hi,i
41/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Modelo On-Off
A distribuição é estacionária?
1 2
1-p
p
1-q
q
42/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Modelo On-Off
A distribuição é estacionária?
πi =
∑
j πjPj ,i∑
i πi = 1
π1 = π1P1,1 + π2P2,1 = (1− p)π1 + qπ2
π2 = π1P1,2 + π2P2,2 = pπ1 + (1− q)π2
π1 + π2 = 1
π1 =
q
q+p , π2 =
p
q+p
43/58
Introdução Definições e Conceitos Classificação de Estados DistribuiçõesEstacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Modelo On-Off
A distribuição é estacionária?
π1P1,2 = π2P2,1
qp
q+p =
pq
q+p
44/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Reversibilidade no tempo
Teorema
Seja S um conjunto de estados de uma cadeia de Markov finita,
irredutível e aperiódica. Na distribuição estacionária, a probabilidade
de que a cadeia saia do conjunto S é igual à probabilidade de entrar
em S.
45/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Distribuições Estacionárias
Teorema
Considerando uma cadeia de Markov finita, irredutível e ergódica
com uma matriz de transição P. Se π = (π0, π1, ..., πn) é um vetor
não negativo, tal que
∑n
i=0 = 1, para qualquer par de estados i, j
πiPi ,j = πjPj ,i
a distribuição πi é estacionária.
46/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Random Walks
Seja G = (V ,E ) um grafo finito, não direcionado e conectado.
Um Random Walk (passeio aleatório) em G é uma cadeia de
Markov definida pela sequência de movimentos de uma
partícula entre os vértices de G;
Neste processo, o lugar da partícula em um dado intervalo de
tempo é o estado do sistema.
Se o vértice i tem grau d(i), então a probabilidade da partícula
utilizar a aresta (i , j) e mover-se até o estado j é de 1d(i) .
47/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Random Walks
Teorema 7.13
Um Random Walk em G convergem em um estado estacionário com
π̃, onde :
πv =
d(v)
2|E |
48/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Random Walks
Prova: Como
∑
v∈V d(v) = 2|E |∑
v∈V
πv =
∑
v∈V
d(v)
2|E |
= 1
Seja P a matriz de probabilidade de transição de uma cadeia de
Markov, Seja N(v) representando os vizinhos de v . A relação
π̃ = π̃P é equivalente a:
πv =
∑
v∈N(v)
d(u)
2|E |
1
d(u)
=
d(v)
2|E |
49/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Random Walks
hu,v Tempo de atingir v a partir de u;
hu,v + hv ,u Tempo de comutação entre u e v ;
Tempo de cobertura.
Definition 7.10
O tempo de cobertura em um grafo G = (V ,E ) é, entre todos os
vértices v ∈ V , o maior valor esperado para visitar todos os outros
vértices por um Random Walk a partir de v .
50/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Random Walks
Lema 7.15
O tempo de cobertura de um G = (V ,E ) é limitado por cima
por 2|E |(V − 1).
(Ideia) Cria uma Arvore geradora, e olha os ciclos Eulerianos.
Lema 7.16
O tempo de cobertura de um G = (V ,E ), com n vértcies é limitado
por cima por H(n − 1).
(Ideia) Semelhante ao coletor de cupons.
51/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
s-t Conectividade
Dado um grafo G = (V ,E ) e dois vértices s e t, queremos
determinar se existe caminho entre s e t Conectividade entre s e t.
BFS;
DFS;
Ω(n) espaço;
52/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
s-t Conectividade
Algoritmo 1: Algoritmo s-t conectividade
1 início
2 Inicia um Random Walk em s
3 Se o passeio alcançar t, em 2n3 retorna que existe um caminho,
Caso contrário retorne que não existe caminho.
4 fim
O(log n) de bits de memória;
Usa o lema 7.16 para limitar o número de passos.
53/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Paradoxo de Parrondo
Contradiz o ditado que dois erros não formam um acerto;
Demonstra que dois jogos perdedores podem ser combinados
para formar um jogo vencedor.
Jogo A, joga uma moeda a não justa, que torna cara com
probabilidade pa < 12
O jogador ganha um Dollar se a moeda se tornar cara;
54/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Paradoxo de Parrondo
Jogo B , jogador tem duas moedas, b e c ;
A moeda jogada, depende de como você está indo no jogo;
w e l o número de vitórias e derrotas, respectivamente;
w − l representa o lucro;
Se o lucro é um múltiplo de 3, então joga a moeda b, com
probabilidade pb, caso contrário joga a moeda c com
probabilidade pc ;
55/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Paradoxo de Parrondo
A moeda b dá cara com pb = 0.09 e a moeda c dá cara com
pc = 0.74;
No primeiro olhar, parece que o jogo é vantajoso;
w =
1
3
+
9
100
+
2
3
74
100
=
157
300
>
1
2
.
56/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Paradoxo de Parrondo
A moeda b NÃO é usada 1/3 do tempo !
−3 −2 −1 0 +1 +2 +3
Também é um jogo desvantajoso para o jogador;
57/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Paradoxo de Parrondo
Se combinar os dois jogos (ABBABB . . . ) temos
paradoxalmente, um jogo vencedor;
Combinando os dois jogos para que mude para o joga A
quando for múltiplo de 3;
Linearidade da esperança ainda é válida.
58/58
Introdução Definições e Conceitos Classificação de Estados Distribuições Estacionárias Random Walks Paradoxo de Parrondo
Pergunta
Qual a propriedade necessária para que um processo estocástico
seja considerado um processo markoviano? Explique.
	Introdução
	Definições e Conceitos
	Classificação de Estados
	Distribuições Estacionárias
	Random Walks
	Paradoxo de Parrondo