Introdução às Cadeias de Markov

Prévia do material em texto

VI SEMANA DE MATEMÁTICA DA UESC
Introdução à Cadeias de Markov: Processos Markovianos de
parâmetro discreto
Autores: Msc. Cláudia Ribeiro Santana
Phd. Enio G. Jelihovschi
Msc. Pedro Carlos Elias Ribeiro Junior
Ilhéus - BA
Outubro de 2007
Resumo
Uma grande quantidade de processos estudados na atualidade, são resultados que são medi-
dos ao longo do tempo. Dentro destes um grande número tem resultados aleatórios, ou seja, são
resultados impreviśıveis. Estes processos são chamados de processos estocásticos e são estuda-
dos usando a teoria das probabilidades. Como exemplos temos: 1) a variação de tráfego em um
certo cruzamento que envolvem a formação e a dissipação de congestionamentos de véıculos. 2)
Quantidade de pessoas que chegam ao longo do dia para fazer transações bancárias nos caixas
eletrônicos dentro de um banco e um problema seria de como encontrar o número de caixas
eletrônicos para que os clientes passem menos tempo nas filas e não haja muitos caixas ociosos
durante o dia. 3) Rúına do jogador; um jogador joga uma seqüência de jogos independentes
contra um oponente, qual será a probabilidade de um dos jogadores se arruinar se iniciar com
um capital N? 4) Mutações genéticas; qual é a probabilidade de uma mutação desaparecer,
continuar numa pequena proporção da população, ou tomar conta de toda a população depois
de um certo peŕıodo de tempo?
Um dos modelos que melhor explica uma quantidade importante destes processos, é chamado
de Cadeias de Markov, que são processos aleatórios cujo resultado no estágio n depende somente
do que aconteceu no estágio n− 1 e não dos resultados anteriores a n− 1, ou seja, um Processo
Markoviano de parâmetro discreto será uma seqüência aleatória que satisfaz a identidade:
Pr(jk | j0, j2,..., jk−1) = Pr[Xk = jk | Xk−1 = jk−1] = p( jk | jk−1)
para cada k e para cada seqüência j0, j2,..., jk de estados, onde Xk são variáveis aleatórias que
definem o resultado do processo no estágio k.
Sabe-se que uma cadeia aperiódica, irredut́ıvel, finita de Markov se estaciona, ou seja, entra
em um estado permanente e o vetor limite é o único vetor de probabilidade estacionária do
processo. Na verdade este vetor é um autovetor associado à matriz (regular) de probabilidades
de transição do processo, dáı, o problema iniciado recai na álgebra linear onde teremos que
utilizar as ferramentas desta área da matemática para encontrar tal autovetor.
Caṕıtulo 1
Definições
Este caṕıtulo se dedica a definir alguns conceitos que são necessários para o restante do estudo
desejado.
Muitas das situações investigadas no nosso estudo diz respeito à uma experiência aleatótia
que não conduz a uma única variável aletaória, mas a toda uma seqência de variáveis aleatórias.
Sequência de variáveis aleatórias tem uma ampla aplicação em diversos casos, a saber:
pedidos comerciais, avarias de máquinas, tempo de vida útil de um componente eletrônico,
sistemas de comunicação, cintagem de part́ıculas subatômicas, epidimias, sistemas genéticos, e
outros.
Qualquer sistema que varie de forma aleatória com o tempo e seja observado em determi-
nadas sequências de tempos segue este padrão.
Definição 1.1. Uma sequência de variáveis aleatórias definidas no mesmo espaço amostral é
denominada uma Sequência Aleatória ou um Processo Aleatório de Parâmetro Discreto.
Observação 1.1. O termo Parâmetro Discreto se refere ao ı́ndice i na sequência Xi com
i = 1, 2, . . . , n, . . .
Os contradomı́nios das variáveis alatórias podem ser conjuntos cont́ınuos ou discretos. Nosso
caso é aquele em que o contradomı́nio é um conjunto discreto, que tem grande vairedade de
aplicações.
Definição 1.2. Dizemos que as variáveis aleatórias na sequência {X1, X2, . . . , Xn, . . .} sejam
Discretas se seus contradomı́nios consistem de conjuntos de elementos Inteiros. Nesta caso
pode-se afirmar que a j-ésima variável aleatória tem valor m, ou seja Xj = m, ou então, diz-se
que o sistema está no estado m no j-ésimo estágio, e também, o sistema está no estado m no
tempo j.
1
O problema consiste em responder alguns questionamentos sobre a função densidade da
probabilidade conjunta ou da função distribuição de X1, X2, . . . , Xn, ou seja, quanto à
p(i1, i2, . . . , in) = Pr[X1 = i1; X2 = i2; . . . ; Xn = in]
ou
F (x1, x2, . . . , xn) = Pr[X1 ≤ x1; X2 ≤ x2; . . . ; Xn ≤ xn]
quando n é um número suficientemente grande, ou investigar sobre tais questões no caso do
limite emq ue n tende ao infinito.
Uma forma de de se conhecer tais probabilidades e através do emprego repetido da fórmula
para a probabilidade da intersecção p(A ∩B) = p(A) · p(B|A), obtendo que
p(i1, i2, . . . , in) = pX1, X2, ..., Xn−1(i1, i2, . . . , in−1)p(in|i1, i2, . . . , in−1)
= . . .
...
p(i1, i2, . . . , in) = p
(1)
i1
p(i2|i1)p(i3|i1, i2) . . . p(in|i1, i2, . . . , in−1),
onde p
(1)
i1
é a função densidade de X1, ou seja, p
(1)
i1
= Pr[X1 = i1], e o significado de cada uma
das outras probabilidades condicionais é natural. Desta forma a equação anterior se torna
Pr[X1 = i1; X2 = i2; . . . ; Xn = in] = Pr[X1 = i1]Pr[X2 = i2|X1 = i1] . . .
P r[Xn = in|X1 = i1; X2 = i2; . . . ; Xn−1 = in−1]
EXEMPLOS
1. Existem três marcas de automóveis dispońıveis no mercado: o Jacaré, o Piranha e o
Urubu. O termo aij da matriz A abaixo é a propabilidade de que um dono de carro da
linha i mude para o carro da coluna j, quando comprar um carro novo.
De
J
P
U
J
0, 7
0, 3
0, 4
Para
P
0, 2
0, 5
0, 4
U
0, 1
0, 2
0, 2
Os termos da diagonal de A =
 710 210 1103
10
5
10
2
10
4
10
4
10
2
10
dão a probabilidade aii de se comprar um
carro novo da marca.
A2 =
 59100 725 1310011
25
39
100
17
100
12
25
9
25
4
25
. Os termos de A2, aij, significam mudar da marca i para a marca
j depois de duas compras:
De fato: a11 = probabilidade de tendo inicialmente um carro da marca J mudar para um
outro carro desta mesma marca, ou seja, J , depois de duas compras.
J
7
10
→ J
7
10
→ J J
2
10
→ P
3
10
→ J J
1
10
→ U
4
10
→ J
Dáı, a11 =
7
10
· 7
10
+ 2
10
· 3
10
+ 1
10
· 4
10
= 59
100
.
a12 = probabilidade de tendo inicialmente um carro da marca J mudar para um outro
carro da marca P depois de duas compras.
J
7
10
→ J
2
10
→ P J
2
10
→ P
5
10
→ P J
1
10
→ U
4
10
→ P
Dáı, a12 =
7
10
· 2
10
+ 2
10
· 5
10
+ 1
10
· 4
10
= 28
100
.
a13 = probabilidade de tendo inicialmente um carro da marca J mudar para um outro
carro da marca U depois de duas compras.
J
7
10
→ J
1
10
→ U J
2
10
→ P
2
10
→ U J
1
10
→ U
2
10
→ U
Dáı, a13 =
7
10
· 1
10
+ 2
10
· 2
10
+ 1
10
· 4
10
= 13
100
.
a21 = probabilidade de tendo inicialmente um carro da marca P mudar para um outro
carro da marca J depois de duas compras.
P
3
10
→ J
7
10
→ J P
5
10
→ P
3
10
→ J P
2
10
→ U
4
10
→ J
Dáı, a21 =
3
10
· 7
10
+ 5
10
· 3
10
+ 2
10
· 4
10
= 44
100
.
a22 = probabilidade de tendo inicialmente um carro da marca P mudar para um outro
carro desta mesma marca, ou seja, P , depois de duas compras.
P
3
10
→ J
2
10
→ P P
5
10
→ P
5
10
→ P P
2
10
→ U
4
10
→ P
Dáı, a22 =
3
10
· 2
10
+ 5
10
· 5
10
+ 2
10
· 4
10
= 39
100
.
a23 = probabilidade de tendo inicialmente um carro da marca P mudar para um outro
carro da marca U depois de duas compras.
P
3
10
→ J
1
10
→ U P
5
10
→ P
2
10
→ U P
2
10
→ U
2
10
→ U
Dáı, a23 =
7
10
· 2
10
+ 2
10
· 5
10
+ 1
10
· 4
10
= 16
100
.
a31 = probabilidade de tendo inicialmente um carro da marca U mudar para um outro
carro da marca J depois de duas compras.
U
4
10
→ J
7
10
→ J U
4
10
→ P
3
10
→ J U
2
10
→ U
4
10
→ J
Dáı, a31 =
4
10
· 7
10
+ 4
10
· 3
10
+ 2
10
· 4
10
= 48
100
.
a32 = probabilidade de tendo inicialmente um carro da marca U mudar para um outro
carro da marca P depois de duas compras.
U
4
10
→ J
2
10
→ P U
4
10
→ P
5
10
→ P U
2
10
→ U
4
10→ P
Dáı, a32 =
4
10
· 2
10
+ 4
10
· 5
10
+ 2
10
· 4
10
= 36
100
.
a33 = probabilidade de tendo inicialmente um carro da marca U mudar para um outro
carro da marca U depois de duas compras.
U
4
10
→ J
1
10
→ U U
4
10
→ P
2
10
→ U U
2
10
→ U
2
10
→ U
Dáı, a33 =
4
10
· 1
10
+ 4
10
· 2
10
+ 2
10
· 2
10
= 16
100
.
2. Seja {XN} uma cadeia de Markov com espaço dos estados {0, 1, 2}, vetor de probabilidade
inicial p(0) = (1
4
, 1
2
, 1
4
) e matriz de transição de 1 passo P :
P =
 14 34 01
3
1
3
1
3
0 1
4
3
4

(a) Calcule p(0, 1, 1) = Pr[X0 = 0, X1 = 1, X2 = 1].
(b) Mostre que P [X1 = 1 e X2 = 1|X0 = 0] = p01p11.
(c) Calcule p
(2)
01 , p
(3)
ij para i, j = 0, 1, 2.
RESPOSTAS:
(a) p(0, 1, 1) = Pr[X0 = 0, X1 = 1, X2 = 1] =
= Pr[X0 = 0] · [X1 = 1|X0 = 0] · Pr[X2 = 1|X1 = 1, X0 = 0] =
= Pr[X0 = 0] · [X1 = 1|X0 = 0] · Pr[X2 = 1|X1 = 1] = 14 ·
3
4
· 1
3
= 1
16
.
(b)
0
1
4
→ 1
3
4
→ 1
Ou seja, P [X1 = 1 e X2 = 1|X0 = 0] = p01p11.
(c) Calcule p
(2)
01 = a probabilidade de passar do estado 0 ao estado 1 depois de 2 passos.
0
1
4
→ 0
3
4
→ 1 0
3
4
→ 1
1
3
→ 1 0
0
→ 2
1
4
→ 1
Dáı, p
(2)
01 =
1
4
· 3
4
+ 3
4
· 1
3
+ 0 · 1
4
= 7
16
.
O mesmo resultado pode ser obtido calculando o elemento a12 da 2
a potência da
matriz de transição: 14 34 01
3
1
3
1
3
0 1
4
3
4
 ·
 14 34 01
3
1
3
1
3
0 1
4
3
4
 =
 516 716 147
36
4
9
13
36
1
12
13
48
31
48

P (3) =
 43192 85192 1385
432
83
216
181
432
1
9
181
576
331
576

Os termos p
(3)
ij são as entradas da 3
a potência da matriz de transição P .
3. Um sistema de comunicação tem uma probabilidade tal que, se um śımbolo é transmitido
corretamente, a probabilidade de que o śımbolo seguinte seja correto é de 0,9. Se, no en-
tanto, um śımbolo for transmitido incorretamente, a probabilidade de o próximo também
o seja é de 0,5. A trasmissão pode ser modelada pela seqüência markoviana dependente,
{X1, X2, · · · } onde Xi = 1 se o i-ésimo śımbolo for transmitido corretamente, Xi = 0 se
o i-ésimo śımbolo for incorreto. Suponha que a probabilidade de que o primeiro śımbolo
seja transmitido corretamente seja de 0,7.
(a) Calcule as probabilidades de transmissão p(in, in−1).
(b) Calcule p(i1, i2, · · · , in).
(c) Calcule Pr[X3 = 1].
(d) Se o k-ésimo śımbolo for correto, Xk = 1, qual a probabilidade de que (k + 2)-ésimo
śımbolo seja correto, isto é, Xk+2 = 1
RESPOSTAS
(a) as probabilidades de transmissão p(in, in−1) são as entradas da seguinte matriz (de
transição) :
A =
[
9
10
1
10
5
10
5
10
]
A2 =
[
43
50
7
50
7
10
3
10
]
(b) p(i1, i2, · · · , in) = p(i1) · p(i2, i1) · · · p(in, in−1).
(c) Pr[X3 = 1] =
7
10
· p11 · p11 + 710 · p12 · p21 +
3
10
· p21 · p11 + 310 · p22 · p21.
(d) Se o k-ésimo śımbolo for correto, Xk = 1, a probabilidade de que (k + 2)-ésimo
śımbolo seja correto, isto é, Xk+2 = 1 é p
(2)
11 =
43
50
.
Definição 1.3. Uma sequência X1, X2, . . . , Xn é dita uma Sequência de Variáveis Aleatórias
Independentes se
p(in|i1, i2, . . . , in−1) = p(n)in
e
p(i1, i2, . . . , in) = p
(1)
i1
p
(2)
i2
. . . p
(n)
in
Se, além disto, todas as variáveis aleatórias tem a mesma função distribuição, ou seja,
p
(j)
i = pi, para cada j, a sequência é dita Sequência de Variáveis Aleatórias Independentes
com Mesma Distribuição.
EXEMPLO
4. Arremessa-se uma moeda 50 vezes e seja Xn = −1 se uma cara aparecer e Xn = +1 se
uma coroa aparecer.
Definição 1.4. A sequência aleatória {X1, X2, . . . , Xn} é dita Serquência Dependente
de Markov, ou um Processo de Markov caso a probabilidade condicional
p(in|i1, i2, . . . , in−1) = Pr[Xn = in|X1 = i1, X2 = i2, . . . , Xn−1 = in−1].
Isto significa que
p(in|i1, i2, . . . , in−1) = p(in|in−1)
ou
Pr(Xn = in|X1 = i1, X2 = i2, . . . , Xin−1 = in−1) = Pr[Xn = in|Xn−1 = in−1].
Exemplo 1.1. Considere uma seuqência independente {X1, X2, . . . , Xm, . . .}, onde cada
Xi = +1 ou Xi = −1, com probabilidade p e q, respectivamente. Agora defina a sequência
Yn = X1 + X2 + . . . + Xn,
para n = 1, 2, . . . , e considere a sequência
{Y1, Y2, . . . , Ym, . . .},
Se a sequência X representa uma sequência independentede passos da unidade de +1
ou −1no eixo real, então Yn representa a posição depois de n passos. Por esta razão a
sequência {Y1, Y2, . . . , Ym, . . .} é chamado de caminho aleatório. sta sequência aleatória
espećıfica é extremamente importante, tnato teoricamente, como em estudos de ordem
prática. O estudo de suas propriedades, e determinadas generalizações ocupa grande parte
da teoria de probabilidade. Aqui só se destaca o fato de que a sequência {Y1, Y2, . . . , Ym, . . .}
náo é uma sequência independente, a despeito do fato de ser proveniente de uma sequência
independente {X1, X2, . . . , Xm, . . .}. Note que
Yn − Yn−1 = Xn =⇒ Yn = Yn−1 + Xn
Assim, se Yn−1 for dado, Yn dependerá somente de Xn, que é independente de qualquer
X ‘e e Y ‘s anteriores. Desta forma
p(in|in−1) = Pr[Yn = in|Yn−1 = in−1]
= Pr[Yn−1 + Xn = in|Yn−1 = in−1]
= Pr[in−1 + Xn|Yn−1 = in−1]
= Pr[Xn = in − in−1]
Uma vez que Xn é independente de X1, X2, . . . , Xn−1e, consequentemente de Yn−1, seque
que
p(in|in−1) =

p, se in = in−1 + 1
q, se in = in−1 − 1
0, para qualquer outro valor
Assim, observa-se que a sequência tem probabilidade de transição estacionária
pij =

p, se j = in−1 + 1
q, se j = in−1 − 1
0, para qualquer outro valor
para i, j = 0, ±1, ±2, . . .
EXERCÍCIOS PROPOSTOS
(a) Seja {X1, X2, · · · } uma seqüência aleatória independente onde cada Xi, assume
somente os valores 1 e 0 com probabilidades p e q, p + q = 1. Mostre que
X1, X2, · · · , Xn tem densidade conjunta p(i1, i2, · · · , ik) = ptqn−t onde t =
∑n
k=1 ik.
Considere Sk =
∑k
i=1 Xi para k = 1, 2, · · ·
i. Mostre que a seqüência {S1, S2, · · · } é uma seqüência dependente de Markov.
ii. Mostre que as probabilidades de transição são dadas a seguir onde α = in−in−1:
p(in, in−1) =
{
pαq1−α para α = 0 ou 1
0
(b) Seja {X1, X2, · · · } uma seqüência de variáveis aleatórias discretas independentes.
Seja
Sk =
k∑
i=1
Xi para k = 1, 2, · · ·
Mostre que {S1, S2, · · · } é uma seqüência markoviana dependente.
RUÍNA DO JOGADOR
EXERCÍCIOS PROPOSTOS
(a) Um jogador joga um ”jogo limpo”na qual as chances são 2 contra 1. Em outras
palavras em cada jogo ele tem 1
3
de probabilidade de ganhar e 2
3
de perder. Se gan-
har, ganhará R$2,00. Se perder, perderá R$1,00. Suponha que os recursos totais
em dólar do jogador e do seu oponente sejam N dólares. Se o capital de qualquer
um dos jogadores cair abaixo do ponto em que eles pudessem pagar caso perdessem
o jogo seguinte, o jogo termina. Que Xn representa o caapital do primeiro jogador
após n jogadas.
i. Determine a matriz de transição de 1 passo da cadeia de Markov {Xn}.
ii. Suponha que os dois jogadores concordem em que se o capital de qualquer um
dos dois cair para R$1,00, eles farão o próximo jogo com chances iguais - gan-
harão ou perderão com igual probabilidade. Determine a matriz de transição
de 1 passo para esse caso.
Obs: Considere o seguinte experimento:
Arremessa-se uma moeda 50 vezes e seja Xn = −1 se uma cara aparecer e Xn = +1
se uma coroa aparecer. Seja {X1, X2, · · · } uma seqüência de variáveis aleatórias
discretas independentes. Seja
Sk =
k∑
i=1
Xi para k = 1, 2, · · ·
{S1, S2, · · · }
é uma seqüência markoviana dependente que pode modelar um problema de rúına
de Jogador Clássico onde se ganha R$1,00 e perde R$1,00.
(b) Arremessa-se uma moeda 50 vezes e seja Xn = −1 se uma cara aparecer e Xn = +1
se uma coroa aparecer. Defina uma nova seqüência {Yn}, onde a seqüência {Xn},
da seguinte maneira:
Y1 = X1,
Y2 =
X1 + X2
2
,
...
Yn =
X1 + X2 + · · ·+ Xn
n
.
(c) Identifique a seqüência {Yn}. Trata-se de uma seqüência independente? Uma
seqüência de Markov? Um problema da Rúına de Jogador?
EXEMPLOSDE MODELOS NÃO-MARKOVIANOS
(a) Arremessa-se uma moeda 50 vezes e seja Xn = −1 se uma cara aparecer e Xn = +1
se uma coroa aparecer. Defina uma nova seqüência {Zn}, da seguinte maneira:
Z1 = X1,
Z2 =
X1 + X2
2
,
...
Zn+1 =
Xn + Xn+1
2
.
Com n=1, · · · , 49.
(b) Explique porque {Zn} dada acima não é um modelo Markoviano?
(c) Numa ilha maravilhosa verificou-se que a cor azul ocorre em borboletas de genótipo
aa, e não ocorre em Aa e AA. Suponha que a proporção de borboletas azuis seja
1
4
. Depois de algumas gerações, qual será a porcentagem das borboletas não azuis,
mas capazes de ter filhotes azuis?
RESPOSTA:
Denotando por d, dominante, r, recessivo e h, h́ıbrido, e os repectivos cruzamentos
por d× d, d× r, d× h, colocando as probabilidaddes em colunas, podemos montar
a seguinte matriz de transição:
d× d r × r d× r d× h r × h h× h
d 1 0 0 0,5 0 0,25
h 0 0 1 0,5 0,5 0,5
r 0 1 0 0 0,5 0,25
 p
(2)
d
p
(2)
h
p
(2)
r
 =
 1 0 0 0, 5 0 0, 250 0 1 0, 5 0, 5 0, 5
0 1 0 0 0, 5 0, 25
 ·

p
(1)
d · p
(1)
d
p
(1)
r · p(1)r
2 · p(1)d · p
(1)
r
2 · p(1)d · p
(1)
h
2 · p(1)r · p(1)h
p
(1)
h · p
(1)
h

=
=
 1 0 0 0, 5 0 0, 250 0 1 0, 5 0, 5 0, 5
0 1 0 0 0, 5 0, 25
 ·

0, 25 · 0, 25
0, 25 · 0, 25
2 · 0, 25 · 0, 25
2 · 0, 25 · 0, 5
2 · 0, 25 · 0, 5
0, 5 · 0, 5
 =
 0, 250, 5
0, 25

p
(1)
d : porcentagem de indiv́ıduos dominantes.
p
(1)
h : porcentagem de indiv́ıduos hibridos.
p
(1)
r : porcentagem de indiv́ıduos recessivos.
Obs: p
(3)
d = p
(2)
d , p
(3)
h = p
(2)
h , p
(3)
r = p
(2)
r . Isto não é casualidade. Existe uma ”lei
em genética”muito conhecida, que estabelece sob condições ideais que depois da
segunda geração, a distribuição entre os genótipos permanece a mesma.
APLICAÇÕES DA ÁLGEBRA LINEAR EM CADEIAS DE MARKOV
Frequêntemente se deseja estudar a cadeia de Markov que tenha estado em funcionamento
há alguma tempo, ou seja, investigar sobre o comportamento das probabilidades de estado
n, com n bem grande, isto é,
vj = lim
n→∞
p
(n)
j
Neste caso vj recebe o nome de Probabilidade de Estado Permanente. Em termos razoáveis
pode-se esperar que, ao longo de um grande peŕıodo de tempo, a influência do estado
inicial no qual o processo começou pode esmorecer e, assim, as probabilidades limites vj
podem não depender do estado inicial. Se for este o caso, então vj também pode ser
interpretado como limite das probabilidades de transição de n passos pij, vj = lim
n→∞
p
(n)
ij ,
já que p
(n)
ij é a probabilidade do porcesso estar no estado j após n passos, dado que
inicialmente estava no estado i. Se realmente cada vj não depende do estado inicial, a
matriz P(n) = (p(n)ij ), convergirá para uma matriz V conforme n → ∞, e cada linha será
identica ao vetor v, com componetes vj,
P(n) → V =

v
v
...
v
,
quando n →∞, onde v = (v0, v1, . . . , vj, . . .)
Deve-se estar atento ás algumas perguntas, tais como: os limites que definen vj existem?
Se existitrem, formam uma distribuição de probabilidade? Isto é, somam 1,
∑
vj = 1?
Como se pode calcular os vj?
se os limites vj = lim
n→∞
p
(n)
ij existem e não dependem do estado inicial, então, fazendo
n →∞ na identidade
p
(n)
j =
∑
k
p
(n−1)
k pkj
obtem-se
vj =
∑
k
vkpkj, com j = 0, 1, 2, . . .,
ou, equivalentemente,
v = v · P
Qualquer vetor x = (x0, x1, x2, . . .), com xi ≥ 0 tal que
∑
xi = 1, que satisfaça
xj =
∑
k
xkpkj, com j = 0, 1, 2, . . . ou x = x · P
é chamado de Vetor de Probabilidade Estacionária.
Teorema 1.1. Em qualquer cadeia aperiódica de Markov todos os limites vj = lim
n→∞
p
(n)
j
existem.
Teorema 1.2. Em qualquer cadeia aperiódica de Markov todos os limites vj = lim
n→∞
p
(n)
j = lim
n→∞
p
(n)
ij
não dependem da distribuição inicial.
Teorema 1.3. Em qualquer cadeia aperiódica irredut́ıvel e finita de Markov, o vetor
limite v = (v0, v1, v2, . . .) é o único vetor da probabilidade estacionária do processo.
Este último teorema implica que, para ca cadeia aperiódica, irredut́ıvel e finita de Markov,
a matriz P(n) = (p(n)ij ) tende à uma matriz que tem todas sua linhas iguais, sendo cada
uma delas id entica ao vetor estacionário, ou seja,
lim
n→∞
P(n) =

v
v
...
v
 =

v0 v1 v2 . . .
v0 v1 v2 . . .
...
...
...
...
v0 v1 v2 . . .

Exemplo 1.2. Suponha que um equipamento tanto possa estar ocupado como inoperante,
e que, se estiver inoperante, possa estar parado para reparos, como aguardando mais
trabalho. Indiqueos estados ocupado, em reparo, e aguardando mais trabalho por 0, 1 e 2.
Observe o estado do sistema em uma sequência de dias sucessivos, e suponha que haja
suficiente falta de memóriano sistema, de forma que possa ser aproximado por uma cadeia
de Markov com matriz de transição de 1 passo
P =
 p00 p01 p02p10 p11 p12
p20 p21 p22
 =
 0, 8 0, 1 0, 10, 1 0, 6 0, 2
0, 6 0 0, 4

Assim, por exemplo, p01 = 0, 1significa que a probabilidade de que uma máquina ocu-
pada quebre é de 0, 1, p11 = 0, 6 significa que a probabilidade de que uma máquina em
reparo hoje ainda esteja em reparo amanhã é de 0, 6, p21 = 0 significa que uma máquina
inoperente não se quebra.
Se estiver interessado nas proporções de tmepo à longo prazo que o equipamento gasta
em três estados, a distribuição limite deverá ser calculada. O sistema é, claramente,
irredut́ıvel (cada estado por ser alcaçado partindo de cada outro estado, embora não
necessariamente em um único passo, pois leva-se, ao menos, 2 passos para ir do estado
2 para o estado 1). É também finito e aperiódico. De acordo com o teorema 1.3 só se
precisa encontrar o único vetor de probabilidade estacionária, resolvendo-se x = xP, com∑
xi = 1. Assim, 
x0 = (0, 8)x0 + (0, 2)x1 + (0, 6)x2
x1 = (0, 1)x0 + (0, 6)x1
x2 = (0, 1)x0 + (0, 2)x1 + (0, 4)x2
ou 
(0, 2)x0 − (0, 2)x1 − (0, 6)x2 = 0
−(0, 1)x0 + (0, 4)x1 = 0
−(0, 1)x0 − (0, 2)x1 + (0, 6)x2 = 0
Já que a terceira equação pode ser obtida somando as duas primeiras e multiplicando
por −1, a terceira não oferece nenhuma informação adicional, podendo ser eliminada. As
duas primeiras equações aliadas ao fato de que
∑
xi = 1, determinarão a única solução,
que será do sistema
(0, 2)x0 − (0, 2)x1 − (0, 6)x2 = 0
−(0, 1)x0 + (0, 4)x1 = 0
x0 + x1 + x2 = 1
Das duas primeiras equações do sistemas, verifica-se que x1 =
1
4
x0, x2 =
1
4
x0, e substi-
tuindo na última equação, obtem-se
x0 =
2
3
x1 =
1
6
x2 =
1
6
Assim, o vetor da probabilidade limite é v =
(
2
3
,
1
6
,
1
6
)
, e isso oferece as proporções de
tempo, a longo prazo, que o sistema gasta nestes estados.
EXERCÍCIOS RESOLVIDOS
(a) É observado que as probabilidades de um time de futebol ganhar, perder e empatar
uma partida depois de conseguir uma vitória são 1
2
, 1
5
e 3
10
respectivamente; e depois
de ser derrotado são 3
10
, 3
10
e 2
5
, respectivamente; e depois de empatar são 1
5
, 2
5
e 2
5
,
respectivamente. Se o time não melhorar nem piorar, conseguirá mais vitórias que
derrotas a longo prazo?
RESPOSTA:
G P E
G 0,5 0,3 0,2
P 0,2 0,3 0,4
E 0,3 0,4 0,4
Como a matriz das probabilidades é regular, podemos aplicar o teorema (1.5.4)[1]:
 0, 5 0, 3 0, 20, 2 0, 3 0, 4
0, 3 0, 4 0, 4
 pGpP
pE
 =
 pGpP
pE
 ⇔

−0, 5pG + 0, 3pP + 0, 2pE = 0
0, 2pG − 0, 7pP + 0, 4pE = 0
0, 3pG + 0, 4pP − 0, 6pE = 0
.
Além disso, sabemos que pG + pP + pE = 1. Dáı, pG =
26
79
, pP =
24
79
e pE =
29
79
.
(b) Numa cidade industrial, os dados sobre a qualidade do ar são classificados como
satisfatório (S) e insatisfatório (I). Assuma que, se um dia é registrado S, a prob-
abilidade de se ter S no dia seguinte é 2
5
e que, uma vez registrado I, tem-se 1
5
de
probabilidade de ocorrer S no dia seguinte.
i. Qual é a probabilidade do quarto dia ser S, se o primeiro dia é I?
ii. O que se pode dizer a longo prazo sobre a probabilidade de termosS ou I?
RESPOSTA:
S I
S 0,4 0,2
I 0,6 0,8
Para o item b)Como a matriz das probabilidades é regular, podemos aplicar o teo-
rema (1.5.4)[1]:[
0, 4 0, 2
0, 6 0, 8
] [
pS
pI
]
=
[
pS
pI
]
⇔
{
−0, 6pS + 0, 2pI = 0
0, 6pS − 0, 2pI = 0
.
Além disso, pS + pI = 1. Dáı, pS =
1
4
e pI =
3
4
.
Para o item a)
I
4
5
→ I
4
5
→ I
1
5
→ S
I
4
5
→ I
1
5
→ S
2
5
→ S
I
1
5
→ S
3
5
→ I
1
5
→ S
I
1
5
→ S
2
5
→ S
2
5
→ S
Portanto, a probabilidade de ocorrer S no quarto dia tendo ocorrido I no primeiro
dia é igual a 16
125
+ 8
125
+ 3
125
+ 4
125
= 31
125
.
O mesmo resultado pode ser obtido calculando o elemento a12 da 3
a potência da
matriz de transição:[
0, 4 0, 2
0, 6 0, 8
]
·
[
0, 4 0, 2
0, 6 0, 8
]
·
[
0, 4 0, 2
0, 6 0, 8
]
=
[
32
125
31
125
93
125
94
125
]
(c) Considere duas companhias de comidas prontas, M e N. Cada ano, a companhia
M conserva 1
3
de seus fregueses, enquanto que 2
3
se transferem para N. Cada ano,
N conserva 1
2
de seus fregueses, enquanto 1
2
transferem-se para M. Suponha que a
distribuição inicial do mercado é dada por
X0 =
[
1
3
2
3
]
i. Ache a distribuição do mercado após 1 ano.
Um ano mais tarde, a distribuição do mercado é
M N
A =
[
1
3
1
2
2
3
1
2
]
M
N
X1 = AX0 =
[
1
3
1
2
2
3
1
2
] [
1
3
2
3
]
De fato, suponhamos que o mercado inicial consiste em k pessoas, e que este
número não varia com o tempo. Ao fim do primeiro ano, M mantém 1
3
de seus
fregueses e ganha 1
2
de N, ou seja, M tem 1
3
· (1
3
k) + 1
2
· (2
3
k) = 4
9
k fregueses e S
tem 2
3
· (1
3
k) + 1
2
· (2
3
k) = 5
9
k fregueses.
ii. Ache a distribuição estável do mercado.
Como a matriz A é regular, segue pelo teorema da Cadeia de Markov que as
probabilidades pM e pN a longo prazo satisfazem o seguinte sistema linear:[
1
3
1
2
2
3
1
2
] [
pM
pN
]
=
[
pM
pN
]
⇔
{
−4pM + 3pN = 0
4pM − 3pN = 0
Além disso, temos que pM + pN = 1. Dáı, podemos concluir que pM =
3
7
e
pN =
4
7
.
(d) Suponha que somente duas companhias rivais, R e S, manufaturam um certo pro-
duto. Cada ano, a companhia R retém 1
3
dos seus fregueses, enquanto que 2
3
passam
a ser fregueses de S. Cada ano, S mantém 3
5
se seus fregueses, enquanto que 2
5
se
transfere para R. Estas informações podem ser mostradas sob a forma matricial
como
R S
A =
[
1
3
2
5
2
3
3
5
]
R
S
Ao se iniciar a manufatura, R tem 2
3
do mercado (o mercado é composto pelo
número total de fregueses), enquanto que S tem 1
3
do mercado. Representamos a
distribuição inicial do mercado por
X0 =
[
2
3
1
3
]
Um ano mais tarde, a distribuição do mercado é
X1 = AX0 =
[
1
3
2
5
2
3
3
5
] [
2
3
1
3
]
De fato, suponhamos que o mercado inicial consiste em k pessoas, e que este número
não varia com o tempo. Ao fim do primeiro ano, R mantém 1
3
de seus fregue-
ses e ganha 2
5
de S, ou seja, R tem 1
3
· (2
3
k) + 2
5
· (1
3
k) = 16
45
k fregueses e S tem
2
3
· (2
3
k) + 3
5
· (1
3
k) = 29
45
k fregueses.
Como a matriz A é regular, segue pelo teorema da Cadeia de Markov que as prob-
abilidades pR e pS a longo prazo satisfazem o seguinte sistema linear:[
1
3
2
5
2
3
3
5
] [
pR
pS
]
=
[
pR
pS
]
⇔
{
−5pR + 3pS = 0
5pR − 3pS = 0
.
Além disso, temos que pR + pS = 1. Dáı, podemos concluir que pR =
3
8
e pS =
5
8
.
BIBLIOGRAFIA
(a) BOLDRINE, José Luiz. COSTA, Suelli I. Rodrigues. FIGUEREDO, Vera
Lúcia. WETZLER, Henry G. Álgebra Linear. 3a edição. Editora: HARBRA
ltda.
(b) CLARKE, A. Bruce. Disney, Ralph L. Traduzido por: Gildásio Amado Filho.
Probabilidade e Processos Estocásticos. -Rio de Janeiro: Livros Técnicos e Cient́ıficos,
1979.
(c) FERNANDEZ, Pedro Jesus. Introdução à Teoria das Probabilidades. Rio de
Janeiro, Livros Técnicos e Cient́ıficos; Braśılia, Ed. Universidade de Braśılia, 1973.
(d) KOLMAN, Bernard. Traduzido por: João Pitombeira de Carvalho. Álgebra
Linear. 3a edição. Editora: Guanabara.