Cadeia de Markov: Conceitos e Exemplo Prático

Universidade Candido Mendes Cadeia de Markov Internet ATENÇÃO O CONTEÚDO AUDIOVISUAL DESTA AULA É EXCLUSIVO PARA FINS ACADÊMICOS ESTANDO PROTEGIDO PELAS LEIS DE PROPRIEDADE INTELECTUAL PROIBIDA A SUA CESSÃO OU OUTRA FORMA DE UTILIZAÇÃO NÃO AUTORIZADA Cadeia de Markov SEJA Xt uma variável aleatória que caracteriza o estado do sistema em pontos discretos do tempo t 12 A família de variáveis aleatórias Xt forma um processo estocástico O número de estados em um processo estocástico pode ser finito ou infinito Cadeia de Markov Um processo estocástico é um processo de Markov se a ocorrência de um estado futuro depender somente do estado imediatamente precedente Isso significa que dados os tempos cronológicos t0 t1 tn dizse que a família de varáveis aleatórias Xtn x1 x2 xn é um processo de Markov se possuir a seguinte propriedade Cadeia de Markov Em um processo markoviano com n estados resultados exaustivos e mutuamente exclusivos as probabilidades em um ponto específico do tempo t 0 1 2 são habitualmente expressas por Isso é conhecido como probabilidade de transição em uma etapa de passar do estado i em t1 ao estado j em t Cadeia de Markov Um modo conveniente de resumi as probabilidades de transição em uma etapa é usar a seguinte notação matricial A matriz P define a denominada cadeia de Markov Uma propriedade dessa matriz é que todas as suas probabilidades de transição Pij são fixas estacionárias e independentes ao longo do tempo Embora uma cadeia de Markov possa incluir um número infinito de estados só iremos ver cadeias finitas Cadeia de Markov Exemplo Todo ano no início da estação de plantio de mudas março a setembro um jardineiro usa um teste químico para verificar a condição do solo Dependendo do resultado do teste a produtividade para a nova estação cai em um dos três estados 1 Bom 2 Razoável 3 Ruim Ao longo dos anos o jardineiro observou que as condições do solo no ano anterior causava um impacto sobre a produtividade do ano corrente e que a situação podia ser descrita pela seguinte cadeia de Markov Cadeia de Markov O jardineiro pode alterar as probabilidades de transição P usando fertilizante para melhorar a condição do solo Neste caso a matriz de transição se torna Exercícios 1 Um carro de polícia esta patrulhando uma região conhecida pelas atividades de gangues Durante uma patrulha há 60 de chance de a localidade que precisar de ajuda ser atendida a tempo se não o carro continuará sua patrulha normal Ao receber uma chamada há 10 de chance de cancelamento e 30 de chance de o carro já estar atendendo a uma chamada anterior Quando o carro de polícia chega à cena há 10 de chance de os arruaceiros terem fugido e 40 de chance de uma prisão imediata Caso contrário os policiais farão uma busca na área Se ocorrer uma prisão há 60 de chance de transportar os suspeitos até o distrito policial caso contrário serão liberados e o carro volta à patrulha Expresse as atividades probabilísticas da patrulha policial sob a forma de uma matriz de transição Exercícios 2 Um professor de engenharia compra um novo computador a cada dois anos e tem preferência por três modelos M1 M2 M3 Se o modelo atual for M1 o próximo computador pode ser M2 com probabilidade 02 ou M3 com probabilidade de 015 Se o modelo atual for M2 as Probabilidades de troca para M1 e M3 são 06 e 025 respectivamente e se o modelo for o M3 então as probabilidades de troca para M1 e M2 são 05 e 01 respectivamente Represente a situação como uma cadeia de Markov Probabilidade de Transição em Netapas e absolutas Dadas as probabilidades iniciais a0 aj 0 de iniciar no estado j e a matriz de transição P de uma cadeia de Markov as probabilidades absolutas a0 aj 0 de estar no estado j após n transição n0 são calculadas da seguinte maneira Probabilidade de Transição em Netapas e absolutas Continuando da mesma maneira obtemos an a0Pn n 1 2 A matriz Pn é conhecida como matriz de transição de n etapas Por esses cálculos podemos ver que Pn Pn1 P ou Pn Pnm Pn 0mn Essas equações são conhecidas como equações de Chanpman Kolomogorov Probabilidade de Transição em Netapas e absolutas Exemplo A seguinte matriz de transição se aplica ao problema do jardineiro com fertilizante A condição inicial do solo é boa isto é a0 1 0 0 Determine as probabilidades absolutas dos três estados do sistema após 1 8 e 16 estações de plantio de mudas Probabilidade de Transição em Netapas e absolutas As linhas de P8 e o vetor de probabilidade absolutas a8 são quase idênticos O resultado é mais pronunciado para P16 Ele demonstra que à medida que aumenta o numero de transições as probabilidades absolutas são independentes da inicial a0 Nesse caso as probabilidades resultantes são conhecidas como Probabilidades de estado de Equilíbrio Probabilidade de Transição em Netapas e absolutas Exercício 3 Utilizando o Exercício 1 se no momento em questão o carro de polícia estiver em uma cena para onde foi chamado determine a probabilidade de ocorrer uma prisão em duas patrulhas 4 Utilizando o exercício 2 determine a probabilidade de o professor comprar o modelo corrente dentro de 4 anos Classificação dos estados em uma cadeia de Markov Os estados de uma cadeia de Markov podem ser classificados como base na probabilidade de transição pij de p Um estado j é absorvente se retornar para ele mesmo com certeza em uma transição isto é pij 1 Um estado j é transiente se puder alcançar outro estado mais não puder voltar ao mesmo estado em que estava com base em outro estado Um estado j é recorrente se a probabilidade de voltar as estado em que estava com base em outro estado for 1 isso pode acontecer se e somente se o estado não for transiente Um estado j é periódico com período t1 se um retorno so for passível em t 2t 3t Etapas Dizse que uma cadeia de Markov é ergódica se todos os seus estados forem recorrentes e aperiódicosNão periódicos Estado periódicos Podemos testar a periodicidade de um estado calculando Pn e observando os valores de pij n para n 234 Esses valores serão positivos no período correspondente do estado Por exemplo na cadeia Continuando com n 67Pn mostra que p11 e p33 são positivas com valores pares de n e valores zero caso contrario Isso significa que o período para o estado 1 e 3 é 2 Classificação dos estados em uma cadeia de Markov Exercícios Classifique os estados das seguintes cadeias de Markov Se um estado for periódico determine o seu período Probabilidades de estado no Equilíbrio e tempos médios de retorno de cadeias ergódicas Em uma cadeia de Markov ergódica as probabilidades de estado de equilíbrio são definidas por Essas probabilidades que são independentes de aio podem ser determinadas com base nas equações uma das equações em é redundante O que diz que as probabilidades de ermanecem inalteradas após uma transição e por essa razão representam a distribuição do estado no equilíbrio Probabilidades de estado no Equilíbrio e tempos médios de retorno de cadeias ergódicas Um subproduto direto das probabilidades de estado no equilíbrio é a determinação do número esperado de transições antes de os sistemas retornarem a um estado j pela primeira vez Isso é conhecido como tempo do primeiro retorno ou tempo médio de recorrência e é calculado em uma cadeia de Markov de n estados por Exemplo Para determinar a distribuição de probabilidade de estado no equilíbrio do problema do jardineiro com fertilizante temos Que dá como resultado o seguinte conjunto de equações Lembrando que uma qualquer uma das três primeiras equações é redundante a solução é O que essa probabilidade dizem é que no lomgo prazo a condição do solo será boa aproximadamente 10 das vezes razoável 52 das vezes e ruim 37 das vezes Os tempos médios do primeiro retorno são calculados por Isso significa que dependendo do estado atual do solo levará aproximadamente 10 estações de plantio de mudas para o solo voltar a um estado bom 2 estações para voltar a um estado razoável e 3 estações para voltar a um estado Ruim Esses resultados indicam uma perspectiva mais sombria do que promissora para a condição do solo Aplicando outro tipo de fertilizante se obtém a seguinte matriz de transição Exemplo de Modelo de Custo Considere o problema do jardineiro com fertilizante Suponha que o custo do fertilizante seja R50 por saco e que o jardim precise de dois sacos se o solo estiver bom A quantidade de fertilizante é 25 maior se o solo tiver razoável e 60 maior se o solo estiver ruim O jardineiro estima que o rendimento anual será de R250 se não for utilizado fertilizante e R420 se ele for aplicado Vale a pena utilizar fertilizante Exercício Em um domingo ensolarado de primavera o MiniGolf pode obter R2000 de receita bruta Se o dia estiver nublado a receita cai 20 Um dia chuvoso reduz a receita em 80 Se o dia de hoje estiver ensolarado há 80 de chance que amanhã o tempo também vai estar ensolarado sem nenhuma chance de chuva Se o dia estiver nublado há 20 de chance de chover amanha e 30 de chance de fazer sol A chuva continuará no dia seguinte com uma probabilidade de 08 mas há 10 de chance de fazer sol a Determine a receita diária esperada para o miniGolf b Determine o número médio de dias em que o tempo não está ensolarado Tempo de primeira passagem Um modelo de determinar o tempo médio da primeira passagem para todos os estados em uma matriz de m transições P é usar a seguinte formula baseada em matriz Considerando mais uma vez a cadeia de Markov do jardineiro com fertilizante Para demonstrar o cálculo do tempo da primeira passagem para um estado específico partindo de todos os outros considerando a passagem dos estados 2 e 3 para o estado 1 Assim j 1 e Universidade Candido Mendes