AD2 2021-2 Algebra Linear CEDERJ

Prévia do material em texto

Fundação Centro de Ciências e Educação Superior a Distância do Estado do Rio de Janeiro 
Centro de Educação Superior a Distância do Estado do Rio de Janeiro 
AD2 – Álgebra Linear EPR – 2/2021 
Código da disciplina EAD01074 
 
Cadeias de Marcov 
Modelos matemáticos podem ser determinísticos quando as condições sob as quais o 
experimento é realizado determinam o resultado do experimento, e não determinísticos 
quando não é possível prever de antemão seus resultados. Neste último caso diz-se que o 
experimento é aleatório. 
Um dos objetivos do estudo de probabilidade é estudar os experimentos aleatórios. O cálculo 
da probabilidade envolve além do conceito de experimento aleatório, os conceitos de espaço 
amostral e evento. 
Um Espaço amostral é definido como sendo o conjunto formado por todos os resultados 
possíveis de um experimento aleatório. 
Por exemplo ao lançarmos uma moeda uma vez, temos que o espaço amostral é 
{𝑐𝑎𝑟𝑎; 𝑐𝑜𝑟𝑜𝑎}, se jogar um dado convencional de seis faces, o espaço amostral vai ser 
{1 ,2 ,3 ,4 ,5 ,6} 
Um subconjunto de um espaço amostral é denominado evento. 
Por exemplo no caso do dado, se o evento for sair um número ímpar. 
Neste caso o espaço amostral 𝑈 = {1 ,2 ,3 ,4 ,5 ,6} e o evento é o conjunto 𝐴 = {1,3,5} 
Seja 𝑈 um espaço amostral e 𝐴 ⊂ 𝑈, um evento. A probabilidade de ocorrer o evento 𝐴 é 
denida por 
𝑃(𝐴) =
𝑛(𝐴)
𝑛(𝑈)
 
 onde 𝑛(𝑈) é o número de elementos contido espaço amostral 𝑈, e 𝑛(𝐴) é o número de 
elementos contido evento 𝐴. 
Voltando ao nosso exemplo do dado de 6 faces, onde o espaço amostral 𝑈 = {1 ,2 ,3 ,4 ,5 ,6} e 
o evento é o conjunto 𝐴 = {1,3,5} e a probabilidade de ocorrer 𝐴 em um lançamento é: 
𝑃(𝐴) =
3
6
=
1
2
 
Andrei Andreyevich Markov nasceu em 14 de junho de 1856 em Ryazan, Russia. Graduou-se na 
Universidade de São Petersburgo (1878) e começou a atuar como professor na mesma 
Universidade em 1886. As Cadeias de Markov apareceram em um trabalho onde em um certo 
texto ele estudava a probabilidade de uma consoante ocorrer em uma determinada posição de 
uma palavra qualquer. Como hipótese, ele supôs que a probabilidade deveria depender 
apenas se a letra precedente à consoante seria uma vogal ou outra consoante. A teoria geral 
dos processos de Markov foi estabelecida em 1930 por Andrei Kolmogorov. Em 20 julho de 
1922 Andrei A. Markov faleceu na então cidade de Petrogrado, hoje São Petersburgo, na 
Rússia. 
Muitos fenômenos que ocorrem na natureza e na sociedade podem ser estudados, pelo 
menos em uma primeira aproximação, como se os fenômenos passassem a partir de um 
estado inicial, por uma sequência de estados, onde a transição de um estado para o seguinte, 
ocorre segundo uma certa probabilidade. No caso em que esta probabilidade de transição 
depende apenas do estado em que o fenômeno se encontra e do estado a seguir, o processo é 
denominado de Processo de Markov e uma sequência de estados envolvida nesse processo é 
denominada de Cadeia de Markov. 
Para saber mais: https://www.youtube.com/watch?v=k6FAZJGTZJo 
Cadeias de Markov e Matrizes (ou diagramas de tranzição) 
O diagrama de transição é uma representação gráfica de uma Cadeia de Markov. Vamos 
representar os estados e as probabilidades de transição, respectivamente, por 𝐸𝑖 e 𝑝𝑖𝑗 , onde 
𝑝𝑖𝑗 representa a probabilidade de haver uma transição do estado 𝐸𝑖 para o estado 𝐸𝑗 . 
 
Neste caso, a matriz de transição será dada por 
https://www.youtube.com/watch?v=k6FAZJGTZJo
𝑃 = [
𝑝11 𝑝12 𝑝13
𝑝21 𝑝22 𝑝23
𝑝31 𝑝32 𝑝33
] 
Note que isto poderia ser facilmente generalizado, para uma matriz de 𝑘 estados, onde 𝑃 =
[𝑝𝑖𝑗]𝑘×𝑘
 e cada elemento 𝑝𝑖𝑗 é um número real tal que 0 ≤ 𝑝𝑖𝑗 ≤ 1, com 𝑖, 𝑗 ∈ {1, ⋯ , 𝑘} o qual 
representa a probabilidade do sistema mudar do 𝑗-ésimo estado para o 𝑖-ésimo estado. Na 
literatura a matriz 𝑃 também é denominada de matriz estocástica ou matriz de Markov. 
 
Exemplo: 
Determinar a matriz de transição da Cadeia de Markov do seguinte problema: 
Conferindo os registros de doações recebidas, uma certa entidade filantrópica observa que 
80% dos seus associados que contribuem ao fundo da entidade em um certo ano, também 
contribuem no ano seguinte e que 30% dos que não contribuem em um certo ano, contribuem 
no ano seguinte. 
Solução: 
Isto pode ser visto como uma Cadeia de Markov de dois estados. 
O primeiro estado 𝐸1 corresponde a um associado que contribui em um ano qualquer e o 
segundo 𝐸2 estado corresponde a um associado que não contribui naquele ano. 
𝑝11 = contribui e vai continuar contribuindo 0,8 
𝑝21 = não contribui e vai contribuir 0,3 
𝑝12 = contribui, mas não vai contribuir 0,2 
𝑝22 = não contribui e não vai contribuir 0,7 
Assim, 
𝑃 = [
0,8 0,2
0,3 0,7
] 
Note que: 
• Todos os elementos da matriz 𝑃 é não negativo. 
• A soma dos elementos de cada coluna é 1 
Essas são condições necessárias para uma matriz de transição. No caso geral, se 𝑃 = [𝑝𝑖𝑗], é a 
matriz de transição de uma Cadeia de Markov com 𝑘 estados, deve-se ter que 
𝑃𝑖 = ∑ 𝑝𝑖𝑗
𝑘
𝑗=1
= 1 
Para todo 𝑖 = 1 ⋯ 𝑘. 
Em geral, numa observação arbitrária, não se pode determinar com certeza o estado de um 
sistema em uma Cadeia de Markov. O melhor que se pode fazer é especificar as probabilidades 
para cada um dos estados possíveis. 
Podemos descrever o estado possível do sistema, em uma certa observação em uma Cadeia de 
Markov com 𝑘 estados, por um vetor linha 
𝑥 = [𝑥1 ⋯ 𝑥𝑘] 
onde 𝑥1 é a probabilidade do sistema estar no primeiro estado, 𝑥2 é a probabilidade de estar 
no segundo estado e 𝑥𝑘 é a probabilidade do sistema estar no 𝑘 −ésimo estado. 
Definimos então, o vetor estado (ou vetor de probabilidade) de uma observação de uma 
Cadeia de Markov com 𝑘 estados é um vetor coluna 𝑥 cuja 𝑖 −ésima componente 𝑥𝑖 é a 
probabilidade do sistema estar no 𝑖 −ésimo estado naquela observação. Além disso, como 
estamos falando de probabilidades, temos que, em um vetor de estado deve ocorrer: 
• 𝑥𝑖 ≥ 0 para todo 𝑖 = 1 ⋯ 𝑘 
• 𝑥1 + ⋯ + 𝑥𝑘 = 1 
A seguir, denotamos por 𝑥(𝑖) o vetor estado na 𝑖 −ésima observação de uma Cadeia de 
Markov. Suponhamos agora, que seja conhecido o vetor estado 𝑥(0) de uma Cadeia de Markov 
numa observação inicial, Então podemos determinar os estados das observações 
subsequentes na Cadeia de Markov, a partir do seguinte resultado: 
• Se 𝑃 é a matriz de transição de uma Cadeia de Markov e 𝑥(𝑛) é o vetor estado na 
𝑛 −ésima observação (ou de passo n), então 
𝑥(𝑛+1) = 𝑥(𝑛) ⋅ 𝑃 
• Se conhecemos 𝑥(0), então 
𝑥(𝑛) = 𝑥(0) ⋅ 𝑃𝑛 
A matriz 𝑃𝑛 é também chamada de matriz de transição de passo n 
Voltando ao exemplo: 
𝑃 = [
0,8 0,2
0,3 0,7
] 
Para determinar um registro futuro provável de contribuição de um novo associado que não 
contribuiu para este ano de 2017, o qual vamos considerar como o ano inicial das 
contribuições. Para esse associado o sistema está inicialmente no segundo estado, de modo 
que o vetor estado inicial é 
𝑥(0) = [0 1] 
Neste caso ele não contribuiu, assim 𝑥1 = 0 pois a probabilidade dele contribuir é zero e 𝑥2 =
1 pois ele não contribuiu, com isso a probabilidade é 1, de não contribuir no estado zero. 
Assim o o vetor estado no segundo estado é dado por 
𝑥(1) = 𝑃 ⋅ 𝑥(0) = [0 1] ⋅ [
0,8 0,2
0,3 0,7
] = [0,3 0,7] 
𝑥(2) = 𝑃 ⋅ 𝑥(1) = [0,3 0,7] ⋅ [
0,8 0,2
0,3 0,7
] = [0,45 0,55] 
Assim, daqui a dois anos, em 2020, podemos esperar com probabilidade 0,45 que o associado 
irá contribuir. Podemos continuar está conta, para estimar outros vetores estado deste 
associado a contribuir ao longo dos anos, por exemplo: 
2021 = 𝑥(3) = [0,525 0,475] 
2022 = 𝑥(4) = [0,563 0,438] 
2023 = 𝑥(5) = [0,581 0,419] 
Algumas contas depois, usando três casas decimais, a partir de 𝑥(11), para qualquer 𝑛, 
observamos que, 
𝑥𝑛 = [0,6 0,4] 
Neste caso, os vetores estados convergem para um vetor fixo à medidaque cresce o número 
de observações. 
Antes de partirmos para as questões, vamos ao último conceito básico: 
O Vetor estacionário de uma a matriz de transição 𝑃 da Cadeia de Markov é definido como 
sendo o vetor 
𝑞 = [𝑞1 ⋯ 𝑞𝑛] 
Tal que 𝑃 ⋅ 𝑞 = 𝑞. Note que o vetor 𝑞 deve ser um vetor estado, logo 
• 𝑞𝑖 ≥ 0 para todo 𝑖 
• 𝑞1 + ⋯ + 𝑞𝑘 = 1 
Voltando ao nosso exemplo, podemos ver que o vetor estacionário da matriz de transição 
𝑃 = [
0,8 0,2
0,3 0,7
] 
É 
𝑞 = [0,6 0,4] 
Note que poderíamos encontrar tal vetor, resolvendo o sistema homogêneo 
𝑞 ⋅ (𝐼 − 𝑃) = 0 
Agora é a sua vez! 
Questão 1 (3.0) 
Sejam 𝑝, 𝑡 ∈ (0,1), considere a matriz de Transição: 
[
1 − 𝑝 𝑝
𝑡 1 − 𝑡
] 
a) (1.0) Determine o seu outro autovalor. 
b) (2.0) A Matriz em questão sempre vai possuir um vetor estacionário? Se sim 
determine-o, em função de p e t 
Solução: 
Note que por tudo que estudamos é esperado que 1 seja autovalor da matriz em questão. De 
fato, fazendo 𝜆1 = 1, temos 
det |
1 − 𝑝 − 1 𝑝
𝑡 1 − 𝑡 − 1
| = 𝑝𝑡 − 𝑝𝑡 = 0 
Por outro lado, podemos calcular o polinômio característico, na unha: 
𝑃(𝜆) = (1 − 𝑝 − 𝑡) + 𝜆(−2 + 𝑝 + 𝑡) + 𝜆2 = (𝜆 − 1)[𝜆 − (1 − 𝑝 − 𝑡)] 
Agora vamos ao cálculo do vetor estacionário: 
[𝑥 𝑦] ⋅ [
−𝑝 𝑝
𝑡 −𝑡
] = 0 
Logo 𝑝𝑥 = 𝑡𝑦, portanto 
𝑣 = 𝑎 ⋅ [1 𝑡/𝑝] 
Para algum 𝑎 ∈ ℝ. Como para ser um vetor estacionário, a soma das coordenadas tem de ser 
1, temos que 
𝑎 =
𝑝
𝑝 + 𝑡
 
Logo 
𝑞 = [
𝑝
𝑝 + 𝑡
𝑡
𝑝 + 𝑡
] 
 
 
 
Questão 2 (3.0) 
O tempo em uma determinada região é classificado por: 𝐸1 = sol, 𝐸2 = nublado ou 
𝐸3 =chuva, e 𝑥
(𝑘) é o vetor estado do tempo no dia 𝑘. Baseado no diagrama 
 
a) 1.0 Monte a matriz de transição 𝑃 lembrando que 𝑝𝑖𝑗 é a probabilidade de um dia que 
está no estado 𝐸𝑗 passar ao estado 𝐸𝑖. 
b) 2.0 Ao olhar o clima tempo de seu telefone celular na quinta-feira, Marcelo se depara 
com as seguintes condições: 70% de cance de ficar nublado sem chuva, 20% chance 
de chuva. Baseado na matriz de transição do item (a) qual a probabilidade de não 
chover no sábado? 
Solução: 
𝑃 = [
0,4 0,4 0,2
0,5 0,3 0,2
0,1 0,5 0,4
] 
Como estamos na quinta feira e queremos determinar o sábado, desejamos 𝑥(2), logo 
𝑥(2) = 𝑥(0) ⋅ 𝑃 ⋅ 𝑃 
Pelos dados 
𝑥(0) = [0,1 0,7 0,2] 
Então 
𝑥(2) = [0,363 0,389 0,248] 
A probabilidade de não chover, é a soma das probabilidades de estar nublado somada a 
probabilidade de fazer sol: 
36,3% + 38,9% = 75,2% 
 
Questão 3 (4.0) 
Em uma experiência um psicólogo coloca um rato cada dia em uma gaiola com duas portas, A 
e B. O rato pode passar pela porta A, onde recebe um choque elétrico, ou pela porta B, onde 
recebe comida. Mantém-se o registro da porta usada pelo rato. 35 No início do experimento, 
em uma segunda-feira, o rato tem a mesma probabilidade de escolher a porta A ou a B. Depois 
de passar pela porta A e receber um choque, a probabilidade de usar a mesma porta no 
próximo dia é 0,3. Depois de passar pela porta B e receber comida, a probabilidade de usar a 
mesma porta no próximo dia é 0,6. 
a – 1.0 Qual a matriz de transição desta experiência? 
b – 1.0 Qual a probabilidade de o rato passar pela porta A, na quinta-feira (terceiro dia após o 
experimento)? 
c – 2.0 Determine o vetor estacionário desta experiência. 
Solução: 
a) Denotando por 𝑃 a matriz de transição, tem-se 
𝑃 = [
0,3 0,7
0,4 0,6
] 
b) 
𝑥(0) = [0,3 0,7] ⋅ 
𝑥(1) = 𝑃 ⋅ 𝑥(0) = [0,3 0,7] ⋅ [
0,3 0,7
0,4 0,6
] = [0,35 0,65] 
𝑥(2) = 𝑃 ⋅ 𝑥(1) = [0,35 0,65] ⋅ [
0,3 0,7
0,4 0,6
] = [0,365 0,635] 
𝑥(3) = 𝑃 ⋅ 𝑥(2) = [0,365 0,635] ⋅ [
0,3 0,7
0,4 0,6
] = [0,364 0,636] 
Na quinta-feira, terceiro dia após o início do experimento, 0, 364 ou 36, 4% de chance do rato 
passar pela porta A. 
c) Para tal devemos resolver o sistema homogêneo 
𝑞 ⋅ (𝐼 − 𝑃) = 0 
Mas vamos usar o exercício 1. 
𝑞 = [
𝑝
𝑝 + 𝑡
𝑡
𝑝 + 𝑡
] 
Onde neste caso, 𝑝 = 0,7 e 𝑡 = 0,6, logo 
𝑞 = [
7
13
6
13
]