Cadeias de Markov

Você vai perceber que nesta aula específica não há "certo" ou "errado" -- o que há é um processo de aprendizado. Sendo o processo tão particular de cada um, é preciso que cada um seja responsável por si. O que gostaríamos nessa atividade é praticar o seguinte fluxo de pensamento:

flowchart TD A[Entender a situação proposta: qual é o problema, e como sabemos que ele foi resolvido, isto é, quais são os critérios de aceitação] --> B[Ligar a situação a um modelo matemático e suas variáveis] --> C[Resolver o modelo matemático, possivelmente implementando um programa para isso] --> D[Identificar, dentro do modelo resolvido e/ou dos resultados mostrados pelo programa, como a situação inicial foi resolvida]

Por esse motivo, essa atividade não tem uma "rubrica" ou um "gabarito". Existem muitas soluções para cada um dos exercícios propostos. Porém, é importante que, para cada um deles, você explicitamente passe por todas as etapas do fluxo.

A quarta etapa é especialmente importante: como este é um trabalho aberto, isto é, que envolve o pensamento divergente, é esperado do aluno (e dos grupos de alunos) que o entendimento de cada etapa, e do que significa ter "resolvido" cada etapa, seja discutido pelo grupo de trabalho. Isso significa que fazer essa atividade pensando em "cumprir rapidamente etapas para entregar um resultado que será avaliado" não é produtivo. Ao invés disso, trata-se um trabalho importante pelo vivenciar o processo, e não pela entrega em si.

Dito isso, é claro que GPTs e IAs atuais resolvem todas as atividades. Não use GPTs e IAs para fazer o trabalho criativo para você neste contexto - até porque isso não faz nenhum sentido porque a atividade não recebe nota. Use essa oportunidade para identificar onde estão as suas dificuldades, e, ao superá-las, para exercitar o senso estético/poético de apreciar os resultados do programa que for fazendo.

Exercício 1

Objetivo: Entender a Cadeia de Markov como um sistema dinâmico

Já por perto de 2010 a 2011, Montreal tinha um sistema de bicicletas públicas bastante parecido com as bicicletas Itaú que temos hoje em São Paulo. Só que Montreal é uma cidade que fica em uma montanha (cujo ponto mais alto é o Mount Royal), o que levou a um problema interessante: as pessoas tendem a tomar uma bicicleta emprestada na estação que fica na região mais alta e devolver em uma das estações das regiões mais baixas, mas raramente alguém faz o caminho inverso. O fim dessa história é que a prefeitura contratou caminhões para ficarem levando bicicletas morro acima, e uma consequência inesperada é que essa história seria um exemplo numa aula de álgebra linear dez anos depois num outro hemisfério.

Em nosso modelo, vamos fazer várias suposições que cabem para o nosso exemplo, mas que não necessariamente correspondem a dados reais.

  • Vamos supor que temos três estações. As duas primeiras (E1 e E2) ficam na parte baixa da cidade. A outra estação (E3) fica na parte alta.
  • Quando uma bicicleta é tomada emprestada em E1, ela tem 90% de chance de ser devolvida em E2 e 10% de chance de ser devolvida em E3.
  • Quando uma bicicleta é tomada emprestada em E2, ela tem 95% de chance de ser devolvida em E1 e 5% de chance de ser devolvida em E3.
  • Quando uma bicicleta é tomada emprestada em E3, ela tem 70% de chance de ser devolvida em E1 e 30% de chance de ser devolvida em E2.

Podemos entender essa situação como uma máquina de estados probabilística. Nessa máquina, uma bicicleta sempre está em algum estado (que, nesse problema, representa uma estação). A cada iteração do sistema, todas as bicicletas movem de uma estação para a outra, seguindo as regras que definimos acima. A máquina pode ser desenhada da seguinte maneira:

graph LR; E1 --> E2; E2 --> E1; E3 --> E1; E1 --> E3; E2 --> E3; E3 --> E2

(a) Atribua pesos às arestas da figura de forma a evidenciar as probabilidades de uma bicicleta ser retirada de cada estação e devolvida na outra.

(b) Supondo que uma bicicleta está em E1, qual é a probabilidade de, após uma retirada, ela ser devolvida em E2?

(c) Supondo que uma bicicleta foi retirada em E1 e devolvida em alguma estação, e, após, foi retirada e devolvida novamente (ou seja: há duas retiradas seguidas), qual é a probabilidade dela ter sido devolvida em cada uma das estações E1, E2 e E3?

Exercício 2

Objetivo: manipular probabilidades relacionadas a Cadeias de Markov

Vamos agora extrapolar a situação anterior para o caso de termos \(n\) estações.

Vamos chamar de \(P(e_t = j)\) a probabilidade de uma bicicleta estar na estação \(j\) após \(t\) iterações do nosso sistema.

Seguindo essa mesma notação, temos que \(P(e_t = j | e_{t-1} = i)\) é a probabilidade de uma bicicleta estar na estação \(j\) na iteração \(t\) dado que sabemos que ela estava na estação \(i\) na iteração \(t-1\).

Como estar em um determinado estado (ou: uma bicicleta estar em uma estação) leva necessariamente a não estar em outro estado (isto é: uma bicicleta só pode estar em uma estação de cada vez), então temos que:

\[ P(e_t = j) = \sum_{i} P(e_t = j | e_{t-1} = i) P(e_{t-1} = i) \]

(a notação \(\sum_i\) representa "somatória para todo \(i\) válido").

(a) Demonstre que \(P(e_t = j) = \sum_{i} P(e_t = j | e_{t-1} = i) P(e_{t-1} = i)\) (dica: lembre-se da definição de probabilidade condicional e desenhe um diagrama de Venn desse caso).

(b) Demonstre que é possível calcular \(P(e_t = 1)\) usando a forma matricial:

\[ \begin{bmatrix} P(e_t = 1) \end{bmatrix} = \left[ P(e_t = 1 | e_{t-1} = 1) \quad P(e_t = 1 | e_{t-1} = 2) \quad \cdots \quad P(e_t = 1 | e_{t-1} = n) \right] \begin{bmatrix} P(e_{t-1} = 1) \\ P(e_{t-1} = 2) \\ \vdots \\ P(e_{t-1} = n) \end{bmatrix} \]

(c) Demonstre que podemos calcular \(P(e_t = j)\) para todo \(j\) usando a equação:

$$ x_{t} = A x_{t-1}, $$
onde:

\[ x_{t} = \begin{bmatrix} P(e_{t} = 1) \\ P(e_{t} = 2) \\ \vdots \\ P(e_{t} = n) \end{bmatrix}, \]
\[ x_{t-1} = \begin{bmatrix} P(e_{t-1} = 1) \\ P(e_{t-1} = 2) \\ \vdots \\ P(e_{t-1} = n) \end{bmatrix}, \]

e

\[ A = \begin{bmatrix} a_{i,j} \end{bmatrix}, a_{i,j} = P(e_t = j | e_{t-1} = i) \]

(d) Se \(A\) é uma matriz que leva as probabilidades de estar em cada estação numa iteração para essas mesmas probabilidades na iteração seguintes, que matriz é capaz de calcular as probabilidades de estar em estações duas iterações adiante?

Exercício 3

Simular computacionalmente o processo de bicicletas

Voltando a nosso caso de três estações. Vamos supor que cada estação começa com um número igual de bicicletas, e que não há um limite máximo de bicicletas que podem ficar em cada estação. Use apoio computacional para encontrar as seguintes respostas:

(a) Após uma iteração, qual é a proporção esperada de bicicletas em cada estação?

(b) Após várias iterações, qual estação fica com mais bicicletas?

(c) Se, ao invés de começarmos nossas iterações com um número igual de bicicletas em cada estação, começarmos com todas as bicicletas na estação E3, no topo do morro, devemos encontrar uma quantidade final de bicicletas diferente, ao fim de várias iterações?

(d) Repita o experimento (c) para todas as bicicletas começando em E1 e, após, para todas as bicicletas começando em E2.

Exercício 4

Objetivo: calcular auto-valores e auto-vetores usando pacotes Python

O problema das bicicletas de Montreal está ligado a uma característica de matrizes que é a existência de vetores e valores chamados de auto-valores e de auto-vetores. Quando um auto-vetor de uma matriz é multiplicado pela própria matriz, o resultado é um múltiplo do próprio vetor, isto é:

$$ Ax = x \lambda, $$
onde: \(A\) é a matriz, \(x\) é o auto-vetor e \(\lambda\) é o auto-valor correspondente.

Por exemplo:

$$ \begin{bmatrix} 2 \quad 0 \\ 0 \quad 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \end{bmatrix} = 2 \begin{bmatrix} 1 \\ 0 \end{bmatrix}, $$
portanto \(\begin{bmatrix}1\\0\end{bmatrix}\) é um auto-vetor de \(\begin{bmatrix} 2 \quad 0 \\ 0 \quad 1 \end{bmatrix}\), e \(2\) é o auto-valor associado.

Se tivermos algum vetor na mesma direção de \(x\) mas multiplicado por algum número real \(\alpha\), isto é, \(y=\alpha x\), podemos manter a mesma equação:

\[ A \alpha x = \alpha x \lambda \Rightarrow Ay = y \lambda. \]

Se você quiser calcular auto-valores e auto-vetores manualmente, pode usar. Porém, essa conta é muito longa e por isso usaremos um pacote computacional para isso.

a) A instrução w, v = np.linalg.eig(A) retorna os auto-vetores da matriz A na variável v e os auto-valores correspondentes na variável w. Use essa função para calcular os auto-valores e auto-vetores da matriz \(A\) do problema das bicicletas de Montreal.

b) (use apoio computacional!) Calcule o ângulo entre cada um dos auto-vetores encontrados e o vetor de probabilidades \(x_{t}\) encontrado ao fim de muitas iterações. Qual é o auto-vetor que está mais alinhado com \(x_t\), e qual é seu auto-valor associado?

Exercício 5

Objetivo: auto-vetores e auto-valores como pontos de estabilidade, expansão, ou colapso

Vamos retomar o problema da população de carcarás e de sapos. Nesse problema, tínhamos a situação em que carcarás estão no mesmo habitat que sapos, obedecendo às seguintes regras:

  • A população de carcarás naturalmente cai em 20% a cada mês
  • Para cada cinco mil sapos existentes naquele mês, um novo carcará nasce
  • A população de sapos naturalmente sobe em 10% porque eles se reproduzem
  • A cada mês, cada carcará consegue comer 100 sapos

Isso significa que podemos escrever equações para calcular o número de carcarás e de sapos a cada mês, tomando por base a quantidade deles no mês anterior:

\[ \begin{cases} \begin{aligned} c_t = 0.8 c_{t-1} + 0.2 s_{t-1} \\ s_t = - 0.1 c_{t-1} + 1.1 s_{t-1} \\ \end{aligned} \end{cases} \]

Podemos fazer esse cálculo usando a operação matricial:

$$ \begin{bmatrix} c_t \\ s_t \end{bmatrix} = \begin{bmatrix} 0.8 \quad 0.2\\ -0.1 \quad 1.1 \end{bmatrix} \begin{bmatrix} c_{t-1} \\ s_{t-1} \end{bmatrix} $$

a) Calcule os auto-vetores e auto-vetores da matriz \(A = \begin{bmatrix} 0.8 \quad 0.2\\ -0.1 \quad 1.1 \end{bmatrix}\).

b) Iniciando com uma população aleatória de carcarás e sapos, calcule o vetor \(x_{t}\) com a população de carcarás e sapos após muitos meses da iteração nessa comunidade.

c) Encontre o ângulo entre \(x_t\) e cada um dos auto-vetores de \(A\). Qual é o auto-vetor de \(A\) mais alinhado a \(x_t\)? Qual é o auto-valor associado a ele?

import matplotlib.pyplot as plt
import numpy as np

A = np.array([[0.8, 0.2], [-0.1,  1.1]])
x = np.array([[600], [500]])
populacao_carcaras = []
populacao_sapos = []
for _ in range(1000):
    populacao_carcaras.append(x[0,0])
    populacao_sapos.append(x[1,0])
    x = A @ x

plt.figure(figsize=(7,2))
plt.plot(populacao_carcaras, label='Carcarás')
plt.plot(populacao_sapos, label='Sapos (* 1000)')
plt.ylim([0,800])
plt.ylabel('População')
plt.xlabel('Semanas')
plt.show()

(d) Usando auto-valores e auto-vetores no caso da população de carcarás, justifique matematicamente o fato de que muito provavelmente a população deve tender a um equilíbrio ao longo de muitos meses. 

A = np.array([[0.8, 0.2], [-0.1,  1.1]])
w, v = np.linalg.eig(A)
print(w)
print(v)

(e) Partindo do caso da população de carcarás, suponha a seguinte situação. A população local decidiu que existem muitos carcarás nas redondezas, e por isso autorizou a caça. Com isso, ao fim do mês, ao invés de morrerem 20% dos carcarás existentes, morrem 80% dos carcarás existentes. Use auto-valores e auto-vetores para prever se esse processo de caça será eficaz para conter a população de carcarás. Após, confirme seu resultado usando uma simulação.

(f) Após a publicação de imagens chocantes sobre a caça dos carcarás, foram aprovadas leis de proteção e cuidado ambiental que fazem com que a mortalidade dos carcarás de um mês para o outro seja de apenas 19%. Usando auto-valores e auto-vetores, determine qual é o efeito dessa lei, a longo prazo, para as populações de carcarás e sapos na região.