Suponha que um sistema físico ou matemático está sofrendo mudanças tais que a cada momento ele pode ocupar um dentre um número infinito de estados. Por exemplo, o tempo de uma certa cidade poderia estar em um dentre três estados possíveis: ensolarado, nublado ou chuvoso; ou então, um indivíduo poderia estar em um dentre quatro estados emocionais possíveis: feliz, triste, irritado ou apreensivo. Suponha que um tal sistema muda com o tempo de um estado para o outro e que em instantes pré-determinados observamos o estado do sistema. Se o estado do sistema em qualquer observação não puder ser predito com certeza, mas se a probabilidade de um certo estado ocorrer puder ser predita unicamente a partir do conhecimento do estado do sistema na observação imediatamente anterior, então o processo de mudança de um estado para o outro é chamado uma cadeia ou um processo de Markov.
Denotamos por 1, 2, ..., k os k estados possíveis de uma cadeia de Markov. A probabilidade de o sistema estar no estado i em qualquer observação, se na observação imediatamente precedente estava no estado j, é denotada por $p_{ij}$ e é chamada a probabilidade de transição do estado j ao estado i. A matriz P = [$p_{ij}$] é chamada a matriz de transição da cadeia de Markov.
Por exemplo, em uma cadeia de Markov de três estados, a matriz de transição tem o formato
$ EstadoPrecedente(j) \\ \begin{bmatrix} p_{11} & p_{12} & p_{13} \\ p_{21} & p_{22} & p_{23} \\ p_{31} & p_{32} & p_{33} \\ \end{bmatrix} NovoEstado(i)$
Nesta matriz $p_{32}$ é a probabilidade que o sistema vai mudar do estado 2 para o estado 3, $p_{11}$ é a probabilidade que o sistema vai continuar no estado 1 imediatamente depois de ter sido observado no estado 1, e assim por diante.
Uma locadora de automóveis tem três lojas de atendimento, denotadas por 1, 2 e 3. Um cliente pode alugar um carro de qualquer uma das três lojas e devolver o carro para qualquer uma das três lojas. O gerente nota que os clientes costuma devolver os carros de acordo com as seguintes probabilidades:
# importando a biblioteca de funções numpy do Python
import numpy as np
# definindo a matriz de transição A
A = np.array([[80/100, 30/100, 20/100],
[10/100, 20/100, 60/100],
[10/100, 50/100, 20/100]])
# imprimindo a matriz aluguelCarro
print("A matriz de transição A é:\n\n{}".format(A))
A matriz de transição A é: [[0.8 0.3 0.2] [0.1 0.2 0.6] [0.1 0.5 0.2]]
Esta é a matriz de transição do sistema se ele for considerado uma cadeia de Markov. A partir desta matriz, a probabilidade que um carro alugado na loja 3 vá ser devolvido na loja 2 é de 60%, a probabilidade que um carro alugado na loja 1 vá ser devolvido na loja 1 é 80%, e assim por diante.
Adiante vamos trabalhar mais com esse exemplo.
Conferindo os registros de doações recebidas, a secretaria da associação de ex-alunos de uma universidade norte-americana observa que 80% de seus ex-alunos que contribuem ao fundo da associação 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. Isto pode ser visto como uma cadeia de Markov de dois estados: o estado 1 corresponde a um ex-aluno que contribui em um ano qualquer e o estado 2 corresponde a um ex-aluno que não contribuiu naquele ano. A matrriz de transição é:
# definindo a matriz de transição P
P = np.array([[80/100, 30/100],
[20/100, 70/100]])
# imprimindo a matriz P
print("A matriz de transição P é: \n\n{}".format(P))
A matriz de transição P é: [[0.8 0.3] [0.2 0.7]]
Nos exemplos acima, as matrizes de transição das cadeias de Markov têm a propiedade que as entradas em qualquer coluna somam 1. Isto não é acidental. Se P = [$P_{ij}$] é a matriz de transição de uma cadeia de Markov qualquer de k estados, então para cada j nós devemos ter $$p_{1j} + p_{2j} + ... p_{kj} = 1$$ por que se o sistema está no estado j em uma observação, é certo que estará em um dos k estados possíveis na próxima observação.
Uma matriz com essa propiedade é chamada matriz estocástica, matriz de probabilidade ou matriz de Markov. Pelo que observamos acima, a matriz de transição de uma cadeia de Markov é sempre uma matriz estocástica.
Em geral, não pode ser determinado com certeza o estado de um sistema em uma cadeia de Markov numa observação arbitrária. O melhor que podemos fazr é especificar probabilidades para cada um dos estados possíveis. Por exemplo, nós podemos descrever o estado possível do sistema em uma certa observação em uma cadeia de Markov com três estados, por um vetor-coluna:
Na qual $x_{1}$ é a probabilidade que o sistema está no estado 1, $x_{2}$ é a probabilidade que ele está no estado 2 e $x_{3}$ é a probabilidade que ele está no estado 3. Em geral, temos a seguinte definição:
O vetor-estado de uma observação de uma cadeia de Markov com k estados é um vetor-coluna x cujo i-ésimo componente $x_{i}$ é a probabilidade do sistema estar, naquela observação, no i-ésimo estado.
Observe que as entradas em qualquer vetor-estado de uma cadeia de Markov são não-negativas e têm soma 1. (Por que?) Um vetor-coluna com está propiedade é chamado vetor de probabilidade.
Suponha agora, que nós sabemos o vetor-estado $x^{(0)}$ de uma cadeia de Markov em alguma observação inicial. O teorema seguinte nos permitirá determinar os vetores-estado $$x^{(1)}, x^{(2)}, ..., x^{(n), ...}$$ nas observações subsequentes.
Teorema: Se P é a matriz de transição de uma cadeia de Markov e $x^{(n)}$ é o vetor-estado da n-ésima observação, então $x^{(n + 1)} = Px^{n}$.
A prova deste teorema envolver ideias de teorias da probabilidades e não será dada aqui. Deste teorema, segue que
| $$x^{(1)} = PX^{(0)}$$ |
| $$x^{(2)} = PX^{(1)} = P^{2}x^{(0)}$$ |
| $$x^{(3)} = PX^{(2)} = P^{3}x^{(0)}$$ |
| $$x^{(n)} = PX^{(n - 1)} = P^{n}x^{(0)}$$ |
Desta maneira, o vetor-estado inicial $x^{(0)}$ e a matriz de transição P determinam $x^{(n)}$ para n = 1, 2, ...
A matriz de transição no exemplo 2 era:
# imprimindo a matriz P
print("A matriz de transição P: \n\n{}".format(P))
A matriz de transição P: [[0.8 0.3] [0.2 0.7]]
Nós agora iremos construir um registro futuro provável de doações de um novo graduando que não doou no primeiro ano após a formatura. Para um tal graduando, o sistema está, inicialmente, com certeza no estado 2, de modo que o vetor-estado inicial é:
# definindo o vetor-estado x
x = np.array([[0],
[1]])
# imprimindo o vetor-estado x
print("O vetor-estado é: \n\n{}".format(x))
O vetor-estado é: [[0] [1]]
Pelo Teorema acima, nós temos, então,
# função que realizará a mudança de estado até o ano a ser definido
def estado(matrizTransicao, vetorEstado, transicao):
# estrutura de repetição for de 0 até (anos - 1)
for indice in range(0, transicao):
# realiza o calculo definido no teorema acima
vetorEstado = np.dot(matrizTransicao, vetorEstado)
# retorna o vetor estado após sofrer todas as mudanças de estado até o ano informado
return vetorEstado
# vetor-estado após 1 ano
print("O vetor-estado após 1 ano é: \n\n{}".format(estado(P, x, transicao = 1)))
O vetor-estado após 1 ano é: [[0.3] [0.7]]
assim, após 1 ano é esperado que o aluno tenha 30% de chance de doar nesse ano (estado 1) e 70% de chance de não doar nesse ano (estado 2).
# vetor-estado após 8 ano
print("O vetor-estado após 8 anos é: \n\n{}".format(estado(P, x, transicao = 8)))
O vetor-estado após 8 anos é: [[0.59765625] [0.40234375]]
# vetor-estado após 11 ano
print("O vetor-estado após 11 ano é: \n\n{}".format(estado(P, x, transicao = 11)))
O vetor-estado após 11 ano é: [[0.59970703] [0.40029297]]
Observe que entre os vetores-estado após 8 anos e 11 anos, a mudança de probabilidade não mudou de forma brusca. Em outras palavras, os vetores-estado convergem a um vetor fixo à medida que cresce o número de observações.
Vamos voltar ao exemplo 1 para aplicar os nossos novos conhecimentos.
# imprimindo a matriz de transição do exemplo 1
print("A matriz de transição A do exemplo 1 é: \n\n{}".format(A))
A matriz de transição A do exemplo 1 é: [[0.8 0.3 0.2] [0.1 0.2 0.6] [0.1 0.5 0.2]]
Se um carro é inicialmente alugado na loja 2, então o vetor estado inicial é
# definindo o vetor-estado inicial
w = np.array([[0],
[1],
[0]])
# imprimindo o vetor w
print("O vetor-estado w é: \n\n{}".format(w))
O vetor-estado w é: [[0] [1] [0]]
Esse é o vetor-estado no estado 2, o qual indica que o carro foi alugado na loja 2 no aluguel inicial.
# vetor-estado após a 1º observação
print("O vetor-estado na 1º observação é: \n\n{}".format(estado(A, w, transicao = 1)))
O vetor-estado na 1º observação é: [[0.3] [0.2] [0.5]]
Após a 1º observação temos 30% de chance do carro ser devolvido na loja 1, 20% de chance na loja 2 e 50% de chance na loja 3. Para a próxima observação, sempre consideramos a observação atual e a relacionamos com a matriz de transição. Então, tendo agora o vetor-estado com as caracteristicas acima do carro ser devolvido nessas lojas, teremos na 2º observação:
# vetor-estado após a 2º observação
print("O vetor-estado na 2º observação é: \n\n{}".format(estado(A, w, transicao = 2)))
O vetor-estado na 2º observação é: [[0.4 ] [0.37] [0.23]]
e na 4º observação:
# vetor-estado após a 4º observação
print("O vetor-estado na 4º observação é: \n\n{}".format(estado(A, w, transicao = 4)))
O vetor-estado na 4º observação é: [[0.5114] [0.2607] [0.2279]]
Assim, no 4º aluguel de carros, temos a probabilidade de 51% do carro ser devolvido na loja 1, 26% do carro ser devolvido na loja 2 e 22% do carro ser devolvido na loja 3.
# vetor-estado após a 10º observação
print("O vetor-estado na 10º observação é: \n\n{}".format(estado(A, w, transicao = 10)))
O vetor-estado na 10º observação é: [[0.556162 ] [0.23016171] [0.21367629]]
# vetor-estado após a 11º observação
print("O vetor-estado na 11º observação é: \n\n{}".format(estado(A, w, transicao = 11)))
O vetor-estado na 11º observação é: [[0.55671337] [0.22985432] [0.21343231]]
Duas coisas deveriam ser observadas neste exemplo. Em primeiro lugar, não foi necessário saber por quanto tempo o cliente permaneceu com o carro. Ou seja, num processo de Markov o tempo entre as observações não precisa ser regular. Em segundo lugar, os vetores-estado comvergem a um vetor fixo à medida que n cresce, exatamente como no exemplo anterior.
Uma guarda de trânsito é designada para controlar o trâfego nos oito cruzametos da rua central. Ela é instruida a permanecer em cada cruzamento por uma hora e, em seguida, ou permanecer no mesmo cruzamento ou seguir para um cruzamento adjacente. Para evitar que ela estabeleça um padrão, ela deve escolher o novo cruzamento de maneira aleatória, com qualquer escolha igualmente provável. Por exemplo, se ela está no cruzamento 5, seu próximo cruzamento pode ser 2, 4, 5 ou 8, cada um com probabilidade de $\frac{1}{4}$. Cada dia ela começa no cruzamento em que parou no dia anterior. A matriz de transição desta cadeia de Markov é
# definindo a matriz de transição C
C = np.array([[1/3, 1/3, 0 , 1/5, 0 , 0 , 0 , 0 ],
[1/3, 1/3, 0 , 0 , 1/4, 0 , 0 , 0 ],
[0 , 0 , 1/3, 1/5, 0 , 1/3, 0 , 0 ],
[1/3, 0 , 1/3, 1/5, 1/4, 0 , 1/4, 0 ],
[0 , 1/3, 0 , 1/5, 1/4, 0 , 0 , 1/3],
[0 , 0 , 1/3, 0 , 0 , 1/3, 1/4, 0 ],
[0 , 0 , 0 , 1/5, 0 , 1/3, 1/4, 1/3],
[0 , 0 , 0 , 0 , 1/4, 0 , 1/4, 1/3]])
# imprimindo a matric C
print("A matriz de transição C é: \n\n{}".format(C))
A matriz de transição C é: [[0.33333333 0.33333333 0. 0.2 0. 0. 0. 0. ] [0.33333333 0.33333333 0. 0. 0.25 0. 0. 0. ] [0. 0. 0.33333333 0.2 0. 0.33333333 0. 0. ] [0.33333333 0. 0.33333333 0.2 0.25 0. 0.25 0. ] [0. 0.33333333 0. 0.2 0.25 0. 0. 0.33333333] [0. 0. 0.33333333 0. 0. 0.33333333 0.25 0. ] [0. 0. 0. 0.2 0. 0.33333333 0.25 0.33333333] [0. 0. 0. 0. 0.25 0. 0.25 0.33333333]]
Temos que a probabilidade da guarda, que está localizada no cruzamento velho j, querer ir para o cruzamento i, está dada na matriz acima.
Se a guarda inicialmente começa no cruzamento 5, suas prováveis localizações, hora a hora, são dadas pelos vetores abaixo:
# determinando o vetor-estado inicial y se ela começar no cruzamento 5
y = np.array([[0],
[0],
[0],
[0],
[1],
[0],
[0],
[0]])
# imprimindo o vetor-estado y
print("O vetor-estado y é: \n\n{}".format(y))
O vetor-estado y é: [[0] [0] [0] [0] [1] [0] [0] [0]]
# vetor-estado após a 1º observação
print("O vetor-estado na 1º observação é: \n\n{}".format(estado(C, y, transicao = 1)))
O vetor-estado na 1º observação é: [[0. ] [0.25] [0. ] [0.25] [0.25] [0. ] [0. ] [0.25]]
Assim, no 1º, 3º, 6º e 7º estados há 0% de chance da guarda ir para o cruzamento novo 1, 3, 6 e 7, respectivamente,e 25% nos 2º, 4º, 5º e 8º estados de chance da guarda mudar para o cruzamento 2, 4, 5 e 8, respectivamente.
# vetor-estado após a 10º observação
print("O vetor-estado na 10º observação é: \n\n{}".format(estado(C, y, transicao = 10)))
O vetor-estado na 10º observação é: [[0.11289968] [0.11487928] [0.10035458] [0.17818898] [0.1486313 ] [0.09887482] [0.13813863] [0.10803273]]
# vetor-estado após a 22º observação
print("O vetor-estado na 22º observação é: \n\n{}".format(estado(C, y, transicao = 22)))
O vetor-estado na 22º observação é: [[0.10736939] [0.1074327 ] [0.10691423] [0.17857082] [0.14304836] [0.1068521 ] [0.14266778] [0.10714462]]
Para todos valores de n maiores do que 22, todos os vetores-estado são iguais a $x^{(22)}$ até três casas decimais. Assim, como nos dois exemplos anteriores, os vetores-estado convergem a um vetor fixo à medida que n cresce.