29/05/2014
Tratamento de Incertezas
TIC-00.176
Aula 17
Conteúdo
Cadeias de Markov
Professor Leandro Augusto Frata Fernandes
[email protected]
Material disponível em
http://www.ic.uff.br/~laffernandes/teaching/2014.1/tic-00.176
Tópicos da Aula
•
•
Revisão
Absorção
 Probabilidades de absorção
 Tempo esperado para absorção
•
Tempo para atingir um estado recorrente
 Tempo médio para primeira visita
 Tempo médio de recorrência
Leitura
Bertsekas and Tsitsiklis, 2nd ed., 2008, Seção 7.4
TIC-00.176 Tratamento de Incertezas
2
TIC-00.176 Tratamento de Incertezas
3
Cadeias de Markov
Revisão
1
29/05/2014
Classificação de Estados
•
Acessibilidade
 Estado é ou não é acessível
a partir de
•
Recorrência
 Estado é recorrente ou transiente
 Classe recorrente de estados
Classe 2
Classe 1
TIC-00.176 Tratamento de Incertezas
4
Teorema de Convergência
•
Válido para cadeias de Markov com uma classe recorrente
não periódica
•
Propriedades
1)
Para cada , temos lim
2)
Os valores são as únicas soluções para o sistema
formado pelas equações
para todo
,
→
,
, para
1, ⋯ ,
1
3)
Temos
Temoe
Equações de
Balanço
Equação de
Normalização
0 para todo estado transiente
0 para todo estado recorrente
TIC-00.176 Tratamento de Incertezas
5
TIC-00.176 Tratamento de Incertezas
6
Cadeias de Markov
Absorção
2
29/05/2014
Absorção
•
Absorção é o evento caracterizado pela
transição do processo para uma classe recorrente
≡
Legenda de Estados: Transientes, Recorrentes, Absorventes
TIC-00.176 Tratamento de Incertezas
7
Probabilidades de Absorção
•
Dado um estado absorvente , a probabilidade de
absorção é a probabilidade do processo atingir
o estado partindo do estado para qualquer
tempo
0
para todo absorvente e
,
para todo transiente
TIC-00.176 Tratamento de Incertezas
8
Probabilidades de Absorção
Exemplo
Qual a probabilidade do processo se instalar no
estado
4, dado que o estado inicial é ?
1
0,8
0,6
2
0,2
1
0,4
0,7
5
1
4:
Para
5:
3
0,3
4
Para
Para
1:
Para
2:
Para
3:
TIC-00.176 Tratamento de Incertezas
9
3
29/05/2014
Tempo Esperado para Absorção
•
Dado um estado inicial , o tempo esperado para
absorção é a quantidade de transições que se
espera ter até atingir um estado absorvente
para todo recorrente
min
1
0
,
|
para transiente
TIC-00.176 Tratamento de Incertezas
10
Tempo Esperado para Absorção
Exemplo 1
Encontre a quantidade de transições esperada ( )
até o processo atingir um estado absorvente, dado
que o estado inicial é ?
1
0,8
0,6
2
0,2
1
0,4
0,7
5
1
4:
5:
3
0,3
4
Para
Para
Para
1:
Para
2:
Para
3:
TIC-00.176 Tratamento de Incertezas
11
Tempo Esperado para Absorção
Exemplo 2
Considere a seguinte versão simplificada do jogo clássico “Serpentes e Escadas”.
Qual o número esperado de turnos para o jogador vencer?
Regras:
1. O jogador começa na casa 1 e vence se
alcançar a casa 9.
2. A cada turno, ele lança uma moeda não
viciada. Se o resultado for cara, avança
uma casa. Caso contrário, avança duas.
3. Sempre que alcançar a base de uma escada,
o jogador é transportado para o topo.
4. Sempre que alcançar a cabeça de uma
serpente, o jogador escorregar até a ponta
de sua cauda.
TIC-00.176 Tratamento de Incertezas
12
4
29/05/2014
Cadeias de Markov
Tempo para Atingir um
Estado Recorrente
TIC-00.176 Tratamento de Incertezas
13
Tempo Médio para Primeira Visita
•
Dado um estado recorrente e um estado inicial ,
o tempo médio para primeira visita à é
min
0
1
,
|
para todo
TIC-00.176 Tratamento de Incertezas
14
Tempo Médio de Recorrência
•
Tempo médio de recorrência ∗ é a variação do
tempo médio para primeira visita onde
1e
é tanto o estado inicial quanto o estado final
∗
min
1
1
,
|
TIC-00.176 Tratamento de Incertezas
15
5
29/05/2014
Tempo para Atingir um Estado Recorrente
Exemplo
0,5
0,8
0,5
1
2
1: online
2: off-line
0,2
Seja
1
Para
1:
Para
2:
∗
TIC-00.176 Tratamento de Incertezas
16
6