Processos Estocásticos Markovianos

1 Processos Estocasticos Markovianos Definição : Um processo estocástico diz-se Markoviano ou de Markov se for estacionário e ter a propriedade de Markov ou da “perda de memória”, isto é : seu comportamento futuro apenas é condicionado pelo estado presente, independentemente do seu historial ou dos estados visitados no passado. Para um processo de Markov é completamente irrelevante qualquer informação sobre estados passados ou sobre o tempo de permanência no estado presente. Num processo estocástico as transições entre estados são causadas pela ocorrência de acontecimentos ou eventos, pelo que a variável aleatória directamente implicada na propriedade de ausência de memória é o tempo entre acontecimentos sucessivos. Iremos ver mais à frente, que a única distribuição contínua que apresenta esta propriedade é a distribuição exponencial, assim num processo de Markov todos os tempos entre acontecimentos sucessivos têm de ser exponencialmente distribuídos. CADEIAS DE MARKOV EM TEMPO DISCRETO DEFINIÇÃO Uma Cadeia de Markov em Tempo Discreto é um processo estocástico em que a variável t representa intervalos de tempo, {X(t), t = 0, 1, 2, 3, …}, e que tem a propriedade de Markov, ou seja, a probabilidade de X(t) estar no estado j no próximo período depende apenas do estado presente e não dos estados visitados em períodos passados: Neste curso so serão consideradas Cadeias de Markov com as seguintes características: - O espaço de estados X é finito ou contável (estados discretos). - As probabilidades de transição entre estados são constantes no tempo (cadeia de Markov estacionária), ou seja : REPRESENTAÇÃO Uma Cadeia de Markov em tempo discreto fica completamente definida se conhecermos os estados X = {1, 2, …, N} e as probabilidades de transição entre os estados de um período para outro. 2 Existem duas formas de representação: graficamente, através do “diagrama de transições”, ou através da matriz P de dimensões N x N e que contem as probabilidades de transição de um período para outro. Num diagrama de transições cada estado é representado por um vértice, e cada arco orientado ligando dois vértices representa uma transição possível entre dois estados em um período, a qual tem uma certa probabilidade de ocorrência (o peso associado ao arco). Na matriz P, cada linha i representa um estado actual e cada coluna j representa um estado futuro (a ordem dos estados actuais deve ser igual à dos estados futuros, respectivamente, nas linhas e nas colunas de P). Deste modo, o elemento pij da matriz representa a probabilidade de ocorrência da transição do estado i para o estado j em um período. A matriz P é uma matriz estocástica, pois ela satisfaz as condições : pij  0, e para cada linha i : ∑ 𝑝𝑖𝑗 = 1 𝑁 𝑗=1 Exemplo: Na aldeia de Estialescq se produz dois tipos de queijos, o queijo de cabra cabretou e o queijo de vaca vachkyrie. Verificou-se que, para cada pessoa da aldeia que compra o cabretou, há 90% de probabilidade de que o próximo queijo que comprar seja o cabretou. Já para cada pessoa que compre o queijo vachkyrie, há 80% de probabilidade de que o próximo queijo comprado seja ainda ele. Com base nestes dados, pretende-se construir uma cadeia de Markov que represente a situação descrita das compras de queijo nessa aldeia. Se X(t) representar o tipo de queijo comprado por uma pessoa na sua t-ésima compra, então a cadeia de Markov limita-se a assumir um dos dois valores seguintes: C (o último queijo comprado foi o cabretou) ou V (último queijo comprado foi o vachkyrie). O espaço de estados será, deste modo, X = {C, V}e a cadeia de Markov pode então ser descrita pela seguinte matriz (estocástica) de transições: P = [0.90 0.10 0.20 0.80] 3 Uma outra forma de representar a cadeia é através do diagrama de transições: Exemplo : Gestão de estoque Uma loja de veiculos de luxo gera seus estoques de diferentes modelos semanalmente. Seja Di a demanda por um tipo de veiculo (o número de unidades que seriam vendidas, caso o estoque não estivesse esgotado) durante a semana i, i= 1, 2, …. Supõe-se que os Di sejam variáveis aleatórias independentes e identicamente distribuídas com uma distribuição de Poisson com média igual a 1. Façamos que N0 represente o número de veiculos disponíveis no inicio, N1 o número de veiculos disponíveis no final da semana 1, N2 o número de veículos disponiveis no final da semana 2, e assim por diante, de modo que o conjunto de variáveis aleatórias Nt (para t = 0, 1, 2, ... ) seja um processo estocástico. No final de cada semana t (sábado à noite), a loja faz um pedido que é entregue a tempo quando da próxima abertura da loja na segunda-feira. A loja usa a seguinte política de reposição : - Se Nt = 0, encomendar três carros. - Se Nt > 0, não encomendar nenhuma carro. Portanto, o nível de estoque varia entre um mínimo de nenhum carro até um máximo de três carros, de modo que os estados possíveis do sistema no instante t (o final de semana t) sejam 0, 1, 2 ou 3. Já que cada variável aleatória Nt (t = 0, 1, 2, ... ) representa o estado do sistema no final da semana t, seus únicos valores possíveis são 0, 1, 2 ou 3. As variáveis aleatórias Nt são dependentes e poderiam ser avaliadas iterativamente pela expressão (equação de estado) : 𝑁𝑡+1 = {max{3 − 𝐷𝑡+1, 0} 𝑠𝑒 𝑁𝑡 = 0 max{𝑁𝑡 − 𝐷𝑡+1, 0} 𝑠𝑒 𝑁𝑡 ≥ 1 V C 0.90 0.10 0.20 0.80 4 Já que Nt+1 é independente de qualquer histórico passado do sistema de estoques anterior ao instante t, o processo estocástico {Nt} (t =0, 1, ... ) possui a propriedade markoviana e, portanto, ele é uma cadeia de Markov. Considere, agora, como obter as probabilidades de transição em uma etapa, isto é, os elementos da matriz de transição de uma etapa : Dado que Dt+1 tem uma distribuição de Poisson com média igual a 1, temos : Assim : Para a primeira linha de P, estamos lidando com uma transição do estado Nt = 0 para algum estado Nt+1 igual a 0, 1, 2 ou 3 : Existem transições impossiveis : As outras transições tem as probabilidades : 5 Para a última linha de P, a semana t + 1 começa com três veiculos no estoque, de modo que os cálculos para as probabilidades de transição sejam exatamente os mesmos daqueles para a primeira linha. A matriz de transição P é dada por : O diagrama de transição de estados para este processo markoviano é dado por :