Modelagem e Avaliação de Cadeias de Markov na Engenharia Elétrica

Modelagem e Avaliação de Desempenho Pós Graduação em Engenharia Elétrica PPGEE Prof Carlos Marcelo Pedroso 2011 Cadeias de Markov Em 1907 Andrew Markov iniciou um estudo sobre um modelo onde o resultado de um experimento depende do resultado de um experimento anterior Este processo de modelagem é conhecido atualmente como Cadeias de Markov Markov Chain Cadeias de Markov Uma cadeia de Markov pode ser descrita da seguinte forma Considere um conjunto de estados Ss1 s2 sn O processo iniciase em um destes estados e se move sucessivamente de um estado para outro Cada troca é chamada de passo Se o estado corrente é si então ela se move para o estado sj com uma probabilidade denotada por pij e esta probabilidade não depende dos estados anteriores da cadeia de Markov As probabilidades pij são chamadas de probabilidades de transição Exemplo Suponha que a Terra de Oz foi abençoada com muitas coisa menos com bom tempo Eles nunca tem dois dias com com tempo em seguida Se há um dia bom é mais provável ter neve ou chuva no próximo dia Se há neve ou chuva existe uma chance de haver tempo bom no próximo dia Suponha a cadeia de Markov que representa a transição destes estados onde R representa chuva N representa tempo bom e S representa neve Podese escrever uma máquina de estados discreta para representar esta situação Matriz P P é chamada matriz de transição e possui algumas propriedades interessantes As linhas representam a probabilidade de transição de um estado para outro Para calcular a probabilidade da cadeia se encontrar no estado j mas a n passos adiante podese calcular Pn Exemplo Para o caso do exemplo anterior previsão do tempo na terra de Oz temos Matriz P Para se calcular a probabilidade de se encontrar no estado j dado um estado i n passos adiante podemos calcular Exemplo suponha que a probabilidade inicial para o clima na terra de Oz seja de 13 13 e 13 e desejase fazer a previsão do tempo para 3 dias Neste caso Exercício Considere três grandes universidades americanas Harvard Darmouth e Yale Suponha que os filhos de exalunos Harvard tem 80 de chance de estudar na mesma escola e os demais estudam em Yale Suponha que 40 dos filhos de exalunos de Yale estudam também em Yale e os demais dividemse igualmente entre Darmouth e e Harvard Suponha que os filhos de exalunos de Darmouth tem 70 de chance de estudar em Darmouth enquanto 20 entram em Harvard e 10 em Yale 1 Encontre a matriz P 2 Encontre a probabilidade de que um neto de um exaluno de Harvard estude em Darmouth 3 Encontre a probabilidade de que um bisneto de um exaluno de Darmouth estude em Yale Cadeias de Markov Absorventes Considere uma cadeia de Markov onde existem estados onde não é possível realizar a transição para nenhum outro estado Este estado é denominado estado absorvente Um estado absorvente apresenta pij 1 Esta é uma variação especial das cadeias de Markov Em uma cadeia de Markov absorvente o número de passos até atingir o estado absorvente é chamado transiente Cadeias de Markov Absorventes Exemplo Um bêbado caminha na rua Cada número de 1 a 3 representa um quarteirão enquanto o número 0 representa a casa dele e o número 4 representa o bar Escreva a matriz P correspondente Cadeias de Markov Absorventes As questões que surgem são Qual a probabilidade de que o processo seja eventualmente absorvido Na média quantos passos serão dados até que o processo seja absorvido Na média quantas vezes um dado estado transiente será visitado até que o processo seja absorvido As respostas a estas questões dependem do estado inicial e da matriz de transição Cadeias de Markov Absorventes Considere a matriz P com r estados absorventes ABS e t estados transientes TR A matriz P canônica é formada conforme abaixo I é uma matriz identidade r por r O é uma matriz 0 r por t R é uma matriz t por r Q é uma matriz t por t Exemplo No exemplo do bêbado Cadeias de Markov Absorventes Para uma cadeia de Markov absorvente a matriz NIQ1 é chamada matriz fundamental para P Um elemento nij de N fornece o número esperado de vezes que o processo estará no estado transiente sj caso o estado inicial seja o estado si Cadeias de Markov Absorventes Exemplo Iniciandose no estado 2 o número médio de vezes em que o sistema permanece nos estados 1 2 e 3 será respectivamente 1 2 e 1 Cadeias de Markov Absorventes Outro fator importante a se considerar é o número médio de passos para a absorção Seja t número de passos até a absorção dado que o estado inicial seja si e t ser o vetor coluna que armazena o número médio de passos para absorção a partir dos estados transientes e c é um vetor coluna com todos os elemtos iguais a 1 Então Calcular para o exemplo anterior Cadeias de Markov Absorventes Um analista pode estar interessado também em calcular a probabilidade do sistema encerrar em um dos estados absorventes Neste caso se bij representar a probabilidade da cadeia ser absorvida por um estado sj caso o estado inicial seja um estado transiente si então a matriz B t por r será dada por Cadeias de Markov Absorventes Um analista pode estar interessado também em calcular a probabilidade do sistema encerrar em um dos estados absorventes Neste caso se bij representar a probabilidade da cadeia ser absorvida por um estado sj caso o estado inicial seja um estado transiente si então a matriz B t por r será dada por Exemplo No exemplo do bêbado Cadeias de Markov Ergódicas Uma cadeia de Markov é chamada de ergódica se é possível ir de um estado para qualquer outro da cadeia não necessariamente em um único passo Alguns autores chamam este tipo de cadeia de Markov de irredutível Seja P a matriz de transição de uma cadeia de Markov Dizse que P é regular se alguma potência de P contêm somente entradas positivas Dizse que a cadeia de Markov é regular se sua matriz de transição é regular Uma cadeia de Markov absorvente não pode ser regular Cadeias de Markov Ergódicas Suponha a matriz de transição de probabilidade dada por A cadeia é ergódica No entanto não é regular se o número de passo é ímpar não é possível atingir um dado estado Outro exemplo A cadeia é ergódica e regular E a cadeia do exemplo do clima na terra de Oz Cadeias de Markov Regulares Seja P uma matriz de transição para uma cadeia de markov regular Então conforme n tende a infinito as potências Pn se aproximam da matriz limite W em que todas as linhas são iguais vetor w O vetor w é um vetor de probabilidade onde todos os componentes são positivos e sua soma é igual a 1 Ver exemplo da terra de Oz Cadeias de Markov Regulares No exemplo De modo geral Cadeias de Markov Regulares Utilizando o resultado é possível determinar o valor limite fazendo Cadeias de Markov Regulares De onde se obtem Resolvendo o sistema obtemos Cadeias de Markov Regulares Utilizando o resultado é possível determinar o valor limite fazendo Cadeias de Markov Para uma cadeia de Markov Ergodica existe um único vetor w tal que wPw com w positivo Qualquer linha do vetor é tal que vPv é múltiplo de w Qualquer coluna do vetor x tal que Pxx é um vetor constante Cadeias de Markov Ergodica Para uma cadeia de Markov Ergodica O que significa que a longo prazo a permanência em cada estado é dada pelo vetor W independentemente do estado inicial Exercício Suponha que um experimento possui a matriz P como segue O valor de p é desconhecido No entanto repetindose muitas vezes o experimento 20 das vezes o sistema encontranse no estado 1 e 80 no estado 2 Encontre o valor p Número médio de passos médio para primeira passagem e recorrência Duas medidas quantitativas de interesse para cadeias de Markov ergódicas são Número médio de passos para retornar a um determinado estado Número médio de passos para ir de um estado para outro Número médio de passos para primeira passagem Uma maneira de analisar o problema é o seguinte Suponha que a cadeia de Markov em estudo é ergódica qualquer estado pode ser atingido a partir que qualquer estado inicial Para determinar o número médio de passos para atingir um determinado estado i basta fazer este estado um estado absorvente Depois apenas é necessário fazer o estudo com a teoria de cadeias de Markov absorventes Número médio de passos para primeira passagem Uma maneira de analisar o problema é o seguinte Suponha que a cadeia de Markov em estudo é ergódica qualquer estado pode ser atingido a partir que qualquer estado inicial Para determinar o número médio de passos para atingir um determinado estado i basta fazer este estado um estado absorvente Depois apenas é necessário fazer o estudo com a teoria de cadeias de Markov absorventes Tempo médio para primeira passagem Exemplo Labirinto Número médio de passos para primeira passagem Exemplo Labirinto Como podemos determinar se o rato é mais esperto Número médio de passos para primeira passagem Exemplo Para calcular o tempo médio para atingir o estado 5 fazemos este estado absorvente Número médio de passos para primeira passagem Exemplo Calculamos a matriz fundamental N Iniciandose no estado 1 o número médio de vezes em que o sistema permanece nos estados 1 2 3 etc será respectivamente 14 9 4 Número médio de passos para primeira passagem Exemplo Labirinto Iniciandose no estado 1 o sistema leva em média 6 passos para atingir o estado 5 absorvente Iniciandose no estado 2 o sistema leva 5 passos para atingir o estado absorvente e assim por diante Número médio de passos para recorrência Qual será o número médio de passos em que um estado será visitado novamente Dado um estado si qual será o número médio de passos que o sistema irá levar para se encontrar novamente no estado si no futuro Dado o vetor w com a probabilidade limite basta calcular 1wi e teremos o número médio de passos para visitar o estado Número médio de passos para recorrência No exemplo do labirinto pode ser calculado wPw acrescentado somatório de wi1 obtendose De onde pode ser deduzido o vetor r número médio de passsos para recorrência Cadeias de Markov Ergódicas em tempo contínuo Ergodic Continous Time Markov Chain A novidade é considerar a variável tempo Neste caso o tempo de permanência em cada transição é considerado como exponencialmente distribuído esta é uma exigência hipótese básica para validade deste raciocínio Considere que o parâmetro que determina a taxa de transição do estado i para o próximo estado j seja dado por qij Cadeias de Markov Ergódicas em tempo contínuo Desta forma podemos definir Onde Q é a matriz de transição de taxas O vetor Π é o vetor de estado estacionário Para o vetor Q o elemento qii diagonal principal é obtido fazendose o complemento do somantório dos demais elementos da linha ver exemplo em sala Cadeias de Markov Ergódicas em tempo contínuo Exemplo Suponha dois servidores operando em cluster Um servidor falha com uma taxa μ exponencialmente distribuída ou seja o tempo médio entre falhas é dado por 1μ A taxa de reparo é dada por λ ou seja o tempo médio de reparo é dado por 1λ Suponha que as instalações de reparo podem trabalhar em dois servidores simultaneamente Desejase descobrir expressões para o estado estacionário Qual a probabilidade de falha total do sistema Ver solução apresentada em sala Cadeias de Markov Ergódicas em tempo contínuo Exercício Suponha um sistema com diagrama de transição de estados a seguir Suponha que as transições possuem distribuição exponencial e λi representa as taxas correspondentes Calcule as probabilidades de estado estacionário Cadeias de Markov Ergódicas em tempo contínuo Exemplo Suponha dois servidores operando em cluster Um servidor falha com uma taxa μ exponencialmente distribuída ou seja o tempo médio entre falhas é dado por 1μ A taxa de reparo é dada por λ ou seja o tempo médio de reparo é dado por 1λ Suponha que as instalações de reparo podem trabalhar em dois servidores simultaneamente Desejase descobrir expressões para o estado estacionário Qual a probabilidade de falha total do sistema Ver solução apresentada em sala