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 medidos ao longo do tempo. Dentro destes um grande número tem resultados aleatórios, ou seja, são
resultados imprevisı́veis. Estes processos são chamados de processos estocásticos e são estudados 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 veı́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) Ruı́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 perı́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, daı́, o problema iniciado recai na álgebra linear onde teremos que
utilizar as ferramentas desta área da matemática para encontrar tal autovetor.
Capı́tulo 1
Definições
Este capı́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 determinadas 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 ) = P r[X1 = i1 ; X2 = i2 ; . . . ; Xn = in ]
ou
F (x1 , x2 , . . . , xn ) = P r[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
(1)
p(i1 , i2 , . . . , in )
= pX1 , X2 , ..., Xn−1 (i1 , i2 , . . . , in−1 )p(in |i1 , i2 , . . . , in−1 )
= ...
..
.
p(i1 , i2 , . . . , in )
= pi1 p(i2 |i1 )p(i3 |i1 , i2 ) . . . p(in |i1 , i2 , . . . , in−1 ),
(1)
(1)
onde pi1 é a função densidade de X1 , ou seja, pi1 = P r[X1 = i1 ], e o significado de cada uma
das outras probabilidades condicionais é natural. Desta forma a equação anterior se torna
P r[X1 = i1 ; X2 = i2 ; . . . ; Xn = in ] = P r[X1 = i1 ]P r[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 disponı́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.

Os termos da diagonal de A = 
carro novo da marca.

A2 = 
59
100
11
25
12
25
7
25
39
100
9
25
13
100
17
100
4
25
J
0, 7
0, 3
0, 4
J
P
U
De
7
10
3
10
4
10
P ara
P
0, 2
0, 5
0, 4
2
10
5
10
4
10
1
10
2
10
2
10
U
0, 1
0, 2
0, 2

dão a probabilidade aii de se comprar um

. 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
Daı́, a11 =
7
10
→
7
10
·
7
10
7
10
J
+
→
2
10
·
3
10
J
+
1
10
2
10
J
·
4
10
→
=
P
3
10
→
J
J
1
10
→
U
4
10
→
J
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
Daı́, 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
Daı́, a13 =
7
10
→
7
10
·
1
10
J
1
10
+
→
2
10
·
2
10
U
+
1
10
2
10
J
·
4
10
→
=
P
2
10
→
U
J
1
10
→
U
2
10
→
U
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
Daı́, a21 =
3
10
→
3
10
·
7
10
J
7
10
+
→
5
10
·
3
10
J
+
2
10
5
10
P
·
4
10
→
=
P
3
10
→
J
P
2
10
→
U
4
10
→
J
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
Daı́, a22 =
3
10
→
3
10
·
2
10
J
2
10
+
→
5
10
·
5
10
P
+
5
10
P
2
10
·
4
10
→
=
P
5
10
→
P
P
2
10
→
U
4
10
→
P
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
Daı́, a23 =
3
10
→
7
10
·
1
10
J
2
10
+
→
2
10
·
5
10
U
+
5
10
P
1
10
·
4
10
→
=
P
2
10
→
U
P
2
10
→
U
2
10
→
U
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
Daı́, a31 =
4
10
→
4
10
·
7
10
J
7
10
+
→
4
10
·
3
10
J
+
2
10
4
10
U
·
4
10
→
=
P
3
10
→
J
U
2
10
→
U
4
10
→
J
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
Daı́, a32 =
4
10
→
4
10
·
2
10
J
2
10
+
→
4
10
·
5
10
P
+
4
10
U
2
10
·
4
10
→
=
P
5
10
→
P
U
2
10
→
U
4
10
→
P
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
Daı́, a33 =
4
10
→
4
10
·
1
10
J
1
10
+
→
4
10
·
2
10
U
+
4
10
U
2
10
·
2
10
→
=
16
.
100
P
2
10
→
U
U
2
10
→
U
2
10
→
U
2. Seja {XN } uma cadeia de Markov com espaço dos estados {0, 1, 2}, vetor de probabilidade
inicial p(0) = ( 14 , 12 , 41 ) e matriz de transição de 1 passo P :

P = 
1
4
1
3
3
4
1
3
1
4
0
0
1
3
3
4


(a) Calcule p(0, 1, 1) = P r[X0 = 0, X1 = 1, X2 = 1].
(b) Mostre que P [X1 = 1 e X2 = 1|X0 = 0] = p01 p11 .
(2)
(3)
(c) Calcule p01 , pij para i, j = 0, 1, 2.
RESPOSTAS:
(a) p(0, 1, 1) = P r[X0 = 0, X1 = 1, X2 = 1] =
= P r[X0 = 0] · [X1 = 1|X0 = 0] · P r[X2 = 1|X1 = 1, X0 = 0] =
= P r[X0 = 0] · [X1 = 1|X0 = 0] · P r[X2 = 1|X1 = 1] =
1
4
· 34 ·
1
3
=
1
.
16
(b)
1
4
0
→
1
3
4
→
1
Ou seja, P [X1 = 1 e X2 = 1|X0 = 0] = p01 p11 .
(2)
(c) Calcule p01 = a probabilidade de passar do estado 0 ao estado 1 depois de 2 passos.
0
(2)
Daı́, p01 =
1
4
→
1
4
0
3
4
→
1
· 34 + 43 · 13 + 0 ·
3
4
0
1
4
=
→
1
1
3
→
1
0
0
→
2
1
4
→
1
7
.
16
O mesmo resultado pode ser obtido calculando o elemento a12 da 2a potência da
matriz de transição:
  1 3
  5 7 1 
 1 3
0
0
4
4
4
4
16
16
4
 1 1 1  ·  1 1 1  =  7 4 13 
3
3
3
3
3
3
36
9
36
1
13
31
0 14 34
0 14 34
12
48
48

P (3) = 
(3)
43
192
85
432
1
9
85
192
83
216
181
576
1
3
181
432
331
576


Os termos pij são as entradas da 3a potência da matriz de transição P .
3. Um sistema de comunicação tem uma probabilidade tal que, se um sı́mbolo é transmitido
corretamente, a probabilidade de que o sı́mbolo seguinte seja correto é de 0,9. Se, no entanto, um sı́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 sı́mbolo for transmitido corretamente, Xi = 0 se
o i-ésimo sı́mbolo for incorreto. Suponha que a probabilidade de que o primeiro sı́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 P r[X3 = 1].
(d) Se o k-ésimo sı́mbolo for correto, Xk = 1, qual a probabilidade de que (k + 2)-ésimo
sı́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) :
9
10
5
10
1
10
5
10
43
50
7
10
7
50
3
10
A=
2
A =
(b) p(i1 , i2 , · · · , in ) = p(i1 ) · p(i2 , i1 ) · · · p(in , in−1 ).
(c) P r[X3 = 1] =
7
10
· p11 · p11 +
7
10
· p12 · p21 +
3
10
· p21 · p11 +
3
10
· p22 · p21 .
(d) Se o k-ésimo sı́mbolo for correto, Xk = 1, a probabilidade de que (k + 2)-ésimo
(2)
sı́mbolo seja correto, isto é, Xk+2 = 1 é p11 = 43
.
50
Definição 1.3. Uma sequência X1 , X2 , . . . , Xn é dita uma Sequência de Variáveis Aleatórias
Independentes se
(n)
p(in |i1 , i2 , . . . , in−1 ) = pin
e
(1) (2)
(n)
p(i1 , i2 , . . . , in ) = pi1 pi2 . . . pin
Se, além disto, todas as variáveis aleatórias tem a mesma função distribuição, ou seja,
(j)
pi = 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 ) = P r[Xn = in |X1 = i1 , X2 = i2 , . . . , Xn−1 = in−1 ].
Isto significa que
p(in |i1 , i2 , . . . , in−1 ) = p(in |in−1 )
ou
P r(Xn = in |X1 = i1 , X2 = i2 , . . . , Xin−1 = in−1 ) = P r[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
especı́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 )
=
=
=
=
P r[Yn = in |Yn−1 = in−1 ]
P r[Yn−1 + Xn = in |Yn−1 = in−1 ]
P r[in−1 + Xn |Yn−1 = in−1 ]
P r[Xn = in − in−1 ]
Uma vez que Xn é independente de X1 , X2 , . . . , Xn−1 e, consequentemente de Yn−1 , seque
que

 p, se in = in−1 + 1
q, se in = in−1 − 1
p(in |in−1 ) =

0, para qualquer outro valor
Assim, observa-se que a sequência tem probabilidade de transição estacionária

 p, se j = in−1 + 1
q, se j = in−1 − 1
pij =

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
P
X1 , X2 , · · · , Xn tem densidade conjunta p(i1 , i2 , · · · , ik ) = pt q n−t onde t = nk=1 ik .
Considere Sk =
Pk
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α q 1−α para α = 0 ou 1
0
(b) Seja {X1 , X2 , · · · } uma seqüência de variáveis aleatórias discretas independentes.
Seja
Sk =
k
X
Xi para k = 1, 2, · · ·
i=1
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 - ganharã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
X
Xi para k = 1, 2, · · ·
i=1
{S1 , S2 , · · · }
é uma seqüência markoviana dependente que pode modelar um problema de ruı́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 ,
X1 + X2
Y2 =
,
2
..
.
X1 + X2 + · · · + Xn
Yn =
n
.
(c) Identifique a seqüência {Yn }. Trata-se de uma seqüência independente? Uma
seqüência de Markov? Um problema da Ruı́na de Jogador?
EXEMPLOS DE 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 ,
X1 + X2
Z2 =
,
2
..
.
Xn + Xn+1
Zn+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
h
r
d×d
1
0
0
r×r
0
0
1
d×r
0
1
0
d×h
0,5
0,5
0
r×h
0
0,5
0,5




(2)
pd
(2)
ph
(2)
pr

 

1 0 0 0, 5 0 0, 25

 
 = 0 0 1 0, 5 0, 5 0, 5  · 


0 1 0 0 0, 5 0, 25





 

1 0 0 0, 5 0 0, 25

=  0 0 1 0, 5 0, 5 0, 5  · 


0 1 0 0 0, 5 0, 25


h×h
0,25
0,5
0,25
(1)
(1)
pd · pd
(1)
(1)
pr · pr
(1)
(1)
2 · pd · pr
(1)
(1)
2 · pd · ph
(1)
(1)
2 · pr · ph
(1)
(1)
ph · ph
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, 25

 =  0, 5 


0, 25

(1)
pd : porcentagem de indivı́duos dominantes.
(1)
ph : porcentagem de indivı́duos hibridos.
(1)
pr : porcentagem de indivı́duos recessivos.
(3)
(2)
(3)
(2)
(3)
Obs: pd = pd , ph = ph , pr
(2)
= pr . 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 é,
(n)
vj = lim pj
n→∞
Neste caso vj recebe o nome de Probabilidade de Estado Permanente. Em termos razoáveis
pode-se esperar que, ao longo de um grande perı́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
(n)
interpretado como limite das probabilidades de transição de n passos pij , vj = lim pij ,
n→∞
(n)
já que pij é 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
(n)
matriz P(n) = (pij ), 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?
P
Se existitrem, formam uma distribuição de probabilidade? Isto é, somam 1,
vj = 1?
Como se pode calcular os vj ?
(n)
se os limites vj = lim pij existem e não dependem do estado inicial, então, fazendo
n→∞
n → ∞ na identidade
(n)
pj
=
X
(n−1)
pk
pkj
k
obtem-se
vj =
X
k
ou, equivalentemente,
vk pkj , com j = 0, 1, 2, . . .,
v =v·P
Qualquer vetor x = (x0 , x1 , x2 , . . .), com xi ≥ 0 tal que
xj =
X
P
xi = 1, que satisfaça
xk pkj , com j = 0, 1, 2, . . . ou x = x · P
k
é chamado de Vetor de Probabilidade Estacionária.
(n)
Teorema 1.1. Em qualquer cadeia aperiódica de Markov todos os limites vj = lim pj
n→∞
existem.
(n)
Teorema 1.2. Em qualquer cadeia aperiódica de Markov todos os limites vj = lim pj
n→∞
(n)
= lim pij
n→∞
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,
(n)
a matriz P(n) = (pij ) tende à uma matriz que tem todas sua linhas iguais, sendo cada
uma delas id entica ao vetor estacionário, ou seja,



lim P(n) = 
n→∞

v
v
..
.


 
 
=
 
v
v0
v0
..
.
v1
v1
..
.
v2
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

p00
P =  p10
p20
p01
p11
p21
 
p02
0, 8
p12  =  0, 1
p22
0, 6

0, 1 0, 1
0, 6 0, 2 
0 0, 4
Assim, por exemplo, p01 = 0, 1significa que a probabilidade de que uma máquina ocupada 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
P
xi = 1. Assim,

 x0
x1

x2
= (0, 8)x0
= (0, 1)x0
= (0, 1)x0
+ (0, 2)x1
+ (0, 6)x1
+ (0, 2)x1
+
(0, 6)x2
+
(0, 4)x2
ou


(0, 2)x0
−(0, 1)x0

−(0, 1)x0
− (0, 2)x1
+ (0, 4)x1
− (0, 2)x1
− (0, 6)x2
+
(0, 6)x2
= 0
= 0
= 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
P
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, 1)x0

x0
− (0, 2)x1
+ (0, 4)x1
+
x1
− (0, 6)x2
+
x2
= 0
= 0
= 1
1
1
Das duas primeiras equações do sistemas, verifica-se que x1 = x0 , x2 = x0 , e substi4
4
tuindo na última equação, obtem-se
1
1
x2 =
6
6
2 1 1
, ,
, e isso oferece as proporções de
Assim, o vetor da probabilidade limite é v =
3 6 6
tempo, a longo prazo, que o sistema gasta nestes estados.
x0 =
2
3
x1 =
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 21 , 15 e
de ser derrotado são
3 3
,
10 10
3
10
respectivamente; e depois
e 25 , respectivamente; e depois de empatar são 51 , 25 e 52 ,
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,2
0,3
P
0,3
0,3
0,4
E
0,2
0,4
0,4
Como a matriz das probabilidades é regular, podemos aplicar o teorema (1.5.4)[1]:


 

pG
0, 5 0, 3 0, 2
pG
 −0, 5pG + 0, 3pP + 0, 2pE = 0
 0, 2 0, 3 0, 4   pP  =  pP  ⇔
0, 2pG − 0, 7pP + 0, 4pE = 0

0, 3pG + 0, 4pP − 0, 6pE = 0
pE
0, 3 0, 4 0, 4
pE

.
Além disso, sabemos que pG + pP + pE = 1. Daı́, 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 probabilidade 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 termos S ou I?
S
0,4
0,6
RESPOSTA: S
I
I
0,2
0,8
Para o item b)Como a matriz das probabilidades é regular, podemos aplicar o teorema (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
.
1
4
Além disso, pS + pI = 1. Daı́, pS =
Para o item a)
I
4
5
I
4
5
I
1
5
S
1
5
S
→
I
→
I
→
I
→
e pI = 43 .
4
5
I
1
5
S
3
5
I
2
5
S
→
→
→
→
1
5
S
2
5
S
1
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 3a potência da
matriz de transição:
0, 4 0, 2
0, 4 0, 2
0, 4 0, 2
·
·
=
0, 6 0, 8
0, 6 0, 8
0, 6 0, 8
32
125
93
125
31
125
94
125
(c) Considere duas companhias de comidas prontas, M e N. Cada ano, a companhia
M conserva 13 de seus fregueses, enquanto que 23 se transferem para N. Cada ano,
N conserva
1
2
1
2
de seus fregueses, enquanto
transferem-se para M. Suponha que a
distribuição inicial do mercado é dada por
1
3
2
3
X0 =
i. Ache a distribuição do mercado após 1 ano.
Um ano mais tarde, a distribuição do mercado é
M
1
1
2
1
2
3
2
3
A =
X1 = AX0 =
N
1
3
2
3
M
N
1
2
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 13 de seus
fregueses e ganha
tem
2
3
· ( 13 k) + 12 ·
1
de N, ou seja, M tem 13
2
( 23 k) = 59 k fregueses.
· ( 31 k) + 12 · ( 23 k) = 49 k fregueses e S
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
2
3
1
2
1
2
pM
pN
=
pM
pN
⇔
−4pM + 3pN = 0
4pM − 3pN = 0
Além disso, temos que pM + pN = 1. Daı́, podemos concluir que pM =
pN =
4
.
7
3
7
e
(d) Suponha que somente duas companhias rivais, R e S, manufaturam um certo produto. Cada ano, a companhia R retém 13 dos seus fregueses, enquanto que 32 passam
3
5
a ser fregueses de S. Cada ano, S mantém
se seus fregueses, enquanto que
2
5
se
transfere para R. Estas informações podem ser mostradas sob a forma matricial
como
R1
S
2
5
3
5
3
2
3
A =
Ao se iniciar a manufatura, R tem
2
3
R
S
do mercado (o mercado é composto pelo
1
3
número total de fregueses), enquanto que S tem
distribuição inicial do mercado por
X0 =
2
3
1
3
do mercado. Representamos a
Um ano mais tarde, a distribuição do mercado é
X1 = AX0 =
1
3
2
3
2
5
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
ses e ganha 25 de S, ou seja, R tem
2
29
· ( 32 k) + 35 · ( 31 k) = 45
k fregueses.
3
1
3
· ( 23 k) +
2
5
· ( 31 k) =
16
k
45
1
3
de seus fregue-
fregueses e S tem
Como a matriz A é regular, segue pelo teorema da Cadeia de Markov que as probabilidades pR e pS a longo prazo satisfazem o seguinte sistema linear:
1
3
2
3
2
5
3
5
pR
pS
=
pR
pS
⇔
−5pR + 3pS = 0
5pR − 3pS = 0
.
Além disso, temos que pR + pS = 1. Daı́, podemos concluir que pR =
3
8
e pS = 58 .
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; Brası́lia, Ed. Universidade de Brası́lia, 1973.
(d) KOLMAN, Bernard. Traduzido por: João Pitombeira de Carvalho. Álgebra
Linear. 3a edição. Editora: Guanabara.