Capítulo 5: Processos de Markov e Cadeias de Markov de Primeira Ordem

Capítulo 5 Processos de Markov Neste capítulo trataremos de uma seqüência de estados que segue um processo de Markov tal que a probabilidade da próxima ocorrência dependerá apenas da ocorrência imediatamente anterior Isto é trataremos com cadeias de Markov de primeira ordem Processos de Markov constituem um tipo especial de processo estocástico que possui a propriedade de que as probabilidades associadas com o processo num dado instante do futuro dependem somente do estado presente sendo portanto independentes dos eventos no passado Desse modo os processos markovianos são caracterizados pelo que se designa como falta de memória Para caracterizar processos de Markov de maneira precisa é necessário estabelecer uma definição formal 51 Definição e caracterização de processos de Markov Antes de apresentar a definição de processos de Markov vamos expor um conceito mais abrangente que é o de processo estocástico Processo estocástico é definido como uma coleção indexada de variáveis aleatórias Xt onde o índice t pertence a um dado conjunto T O conjunto T é normalmente composto de números inteiros não negativos e t X representa uma característica mensurável de interesse num instante de tempo t Formalmente a notação indicada pela expressão 51 define processo estocástico sobre um dado espaço de probabilidade T t Xt 51 Os valores assumidos pela variável aleatória t X são chamados estados e o conjunto de todos os possíveis valores forma o espaço de estado do processo Como exemplo de um processo estocastico podemos citar o trafego de dados em uma rede local de computadores que se encontra interligada a rede Internet Neste sistema mensagens eletrénicas sao recebidas e enviadas enquanto sao feitos downloads de arquivos A taxa de transferéncia de bits por unidade de tempo num dado servidor desta rede é uma variavel incerta que depende da intensidade de uso do sistema pelos usuarios conectados naquele momento Podemos neste sistema caracterizar a varidvel aleatoria X como a velocidade de transferéncia de dados em bits onde ft é 0 instante de tempo pertencente ao intervalo T 00 O espago de probabilidade neste exemplo corresponde a funcao densidade de probabilidade que rege 0 comportamento da varidvel aleatéria X por exemplo uma distribuicgéo normal Definicgdo 51 Processo de Markov Um processo estocastico X te T chamado um processo de Markov quando para qualquer tempo tg t t t a distribuicado condicional de X para os valores dados de X X X dependem somente de X se Xassumir valores discretos esta definigao é expressa como PX x 1X X Xp Ape Xp 40 PX x 1X X 52 se X assumir valores continuos esta definicdo expressa como PX Sx 1X X Xp Mpa Xp O PX Sx 1X X 53 Nestas express6es fo ttrepresentam o passado e e ft sdo 0 futuro e o presente respectivamente E interessante estabelecer claramente como é lida por exemplo a expressdo 52 que é como segue a probabilidade da varidvel X ter valor igual a certo valor x no tempo f dado que a varidvel aleatéria tenha assumido os valores x X1 XQ respectivamente nos tempos f t1 tq igual a probabilidade da varidvel X ter valor igual a um certo valor x no tempo f dado apenas que a varidvel tenha assumido o valor x no tempo A Definigéo 51 pode ser traduzida para a linguagem natural como segue um processo estocdstico é um processo de Markov se o futuro do processo conhecido o estado presente é independente do passado 147 148 É fundamental no estudo de processos de Markov a noção de estado Propriedades em comum entre indivíduos ou objetos caracterizam o que designamos por estados São apresentados a seguir exemplos de objetos ou coisas que possuem propriedade em comum máquinas em uma linha de produção cujos estados podem ser máquina funcionando máquina parada e em reparo máquina parada aguardando por reparo uma população que migra de uma região para outra podendo encontrarse em um dos seguintes estados população ociosa população empregada safras de soja na região CentroOeste do Brasil sendo que os estados podem ser safra boa safra ruim ou safra razoável Os processos de Markov sempre envolvem a variável tempo seja considerada na forma discreta onde o tempo varia em saltos ou seja intervalos regulares ou na forma contínua podendo assumir valores reais Nos exemplos citados anteriormente podemos notar que o tempo está presente Uma máquina ao estragar requer tempo para ser consertada podendo portanto exibir alteração em seu estado se observada a intervalos regulares de tempo Povos que migram de um lugar a outro fazem isto com certa periodicidade Safras ocorrem em meses determinados que diferem em função da região e da cultura considerada 52 Relevância dos processos de Markov e possíveis aplicações Em todas as áreas da atividade humana buscase quantificar eventos que possuem certo grau de incerteza de ocorrência Isto implica de certa forma na necessidade de prever o futuro Modelos matemáticos probabilísticos são concebidos para auxiliar o homem na tomada de decisão No mundo real há diversos sistemas dinâmicos que podem ser modelados como processos de Markov Eis alguns exemplos de aplicações planejamento de sistemas de atendimento a filas de espera que são normalmente modelados como processos de nascimento e morte dimensionamento de recursos computacionais para servir a processos que compartilham tempo e espaço avaliação de equipamentos em operação numa linha de produção industrial ou em instalações complexas estudo de fendmenos econdmicos e movimentos sociais andlise de processos bioldgicos como a evolugao de certas espécies vivas seja para fins de exploragao comercial ou para a preservagao andlise da evolucao de certa epidemia numa comunidade Na bibliografia de Pesquisa Operacional sao encontradas aplicagdes de processos de Markov que compreendem desde 0 estudo de sistemas méveis de comunicagao passando pelo trafego de sinais digitais e o desenvolvimento de técnicas que objetivam disponibilizar 0 servigo aos usuarios bem como a analise da evolugao de corporagdes e sistemas sociais com 0 passar do tempo Em todas as aplicagdes notase um trago comum o tempo Conforme estabelecido na Definigao 51 ha duas categorias de processos de Markov 1 os processos de tempo discreto em que o indice f assume apenas valores inteiros nao negativos ou seja t 0 12 e 2 os processos nos quais a variavel tempo é continua ou seja te 0 Em ambas as categorias os estados sao caracterizados por nuimeros inteiros nao negativos definidos a partir dos valores que a varidvel aleatéria X pode assumir 53 Processos de Markov de tempo discreto Um processo de Markov esté completamente especificado se forem conhecidas as probabilidades de transicao e a distribuigao inicial de probabilidades dos estados Toda vez que um estado suceder a outro dizemos que o processo estocastico markoviano deu um passo O passo pode representar um periodo de tempo que resulte em outro estado possivel Se o nimero de passos é zero tal situagdo representa o presente igual a um estara representando um possivel estado no préximo passo e assim por diante Iniciaremos o estudo de processos de Markov de tempo discreto definindo probabilidades de transiao Definigao 52 Probabilidades de transigao As probabilidades condicionais PX p41 j X i para t012 149 sao chamadas de probabilidades de transiao Se para cada i e j PX p44 j X D PX j Xo 1 para todo t 0 12 entao as probabilidades de transigao para um passo sao ditas estacionarias e usualmente sao denotadas por pj A probabilidade de transigéo do estado i ao estado j em um passo simbolizada por pj a probabilidade de um objeto que se encontra no estado i apés um intervalo de tempo fixo predeterminado ser encontrado no estado j Para npassos a frente como extensdo da Definiao 52 é possivel escrever as probabilidades de transigao para cada i e j comn 0 12 conforme a expressao PXt4n J1X i PX j Xoq i para todo t 0 12 54 Para simplificar a notagao usaremos a seguinte simbologia PX j 1X0 py PX 1X9 O pM De acordo com a referéncia HILLIER e LIEBERMAN 1995 a notagao py introduzida anteriormente implica que para n0 Pi é PX9 jl Xo sendo igual a 1 se i j e igual a 0 em caso contrario As probabilidades de estados sao definidas como a seguir Definigao 53 Probabilidade de estado no instante n A probabilidade do estado i tomada no instante n é a probabilidade de um objeto ocupar o estado i apds um nimero n finito de passos Formalmente para M 1 estados pn PX i parai012M 150 Especificamente para o instante inicial temse a distribuiao inicial de probabilidades de estados a qual é representada por um vetor linha pO cujas componentes sao as probabilidades pn i012M PO po0 pO p20 py O 55 De posse das definigdes estabelecidas nesta sec4o estamos prontos para apresentar um exemplo numérico Exemplo 51 Numa certa regiao durante o perfodo de chuvas que dura cerca de seis meses a cada ano os estados observados sao dois dias ensolarados e dias chuvosos os quais serao designados pelos indices 0 e 1 respectivamente A partir de observag6es histéricas foram obtidas para um passo ou seja um dia as probabilidades de transigao supostas constantes A um dia chuvoso sucedera um dia chuvoso com probabilidade igual a e um dia ensolarado com probabilidade V Dias ensolarados sucedem dias ensolarados com probabilidades iguais a NM enquanto que ao ocorrer um dia ensolarado a probabilidade de chover no dia seguinte é My Desejamos estudar 0 regime de chuvas dessa regiéo modelando o processo estocastico descrito como um processo de Markov Como primeira informagao desse estudo precisamos inferir sobre 0 ntimero esperado de dias chuvosos anualmente se a tendéncia descrita pelas probabilidades permanecer inalterada Primeiramente vamos identificar os dados fornecidos no enunciado com as probabilidades definidas anteriormente Sendo 0 o ntmero associado ao estado sol e 1 o numero associado ao estado chuva temos as probabilidades condicionais seguintes para um passo dia chuvoso sucede dia chuvoso PX 11 X9 py dia ensolarado sucede dia chuvoso PX 01 Xq 1 pig A dia chuvoso sucede dia ensolarado PX 11 X9 0 po My dia ensolarado sucede dia ensolarado PX 01 X9 0 poo My 151 Para encontrar a probabilidade do estado 0 em um passo po1 podemos utilizar o conceito de probabilidade total o qual para dois estados possui a seguinte expressao Po PX 0 PX 01 X9 0PX9 0 PX 01 XQ DPXo 1 Po PooPo Pio Pi 0 Na Ultima expressdo observamos pg0 e p 0 que sdo as probabilidades iniciais dos estados vide a Definicdo 53 Procedendo de modo andlogo para encontrar a probabilidade do estado 1 em um passo p1 utilizamos novamente o conceito de probabilidade total py PX 1 PX 11 Xp DPX 1 PX 11 XQ 0PX 0 PQ Pr P1O PorPo Se for de interesse determinar as probabilidades dos estados 0 e 1 em dois passos respectivamente po2 e p2 tendo em vista que as probabilidades de transicao sao constantes basta escrever as expressdes conforme mostradas a seguir Po2 PooPaAD PioPiD P2 PriPi PorPo Se prosseguirmos com esta forma de calcular o calculo se revelara enfadonho com grande possibilidade de confusao com tantos indices Uma forma alternativa e muito mais funcional consiste no emprego da representacdo matricial Das expressdes de calculo de po1 e p 1 obtémse a representagao matricial mostrada a seguir Poo P01 po mMIp0 py Oo Pio PA 152 Analogamente das expressdes de cdlculo de po2 e p2 extraimos a representagao matricial mostrada a seguir Poo Pol po2 pi21po mid Pio Pil Ora se substituirmos 0 vetor po1 py 1 da segunda expressdo pela primeira expressao obteremos 0 seguinte Poo Po1 Poo Pol po2 pi2 p00 mor Pio PiujLPio Pll DP DP 00 01 po2 p12 P9 nO Pio PAL Finalmente ao empregarmos o Principio da Indugao Matematica é imediata a conclusao de que uma expressdo para n passos pode ser escrita conforme esta indicada a seguir Poo Pol 00 01 pom py po mi Pio PAL Esta expressdo resolveria o exemplo em pauta se conhecéssemos a distribuiao inicial isto é 0 vetor po0 p0 No entanto veremos a frente neste capitulo que sob certas condigdes as probabilidades dos estados a longo prazo sao independentes da distribuicgdo inicial sendo esta outra propriedade inerente 4 maioria dos processos de Markov Retornamos entéo ao Exemplo 51 Para resolver o exemplo langamos mao de um artificio conhecido por arvore de probabilidades A Figura 51 ilustra o diagrama em arvore partindo do estado 0 onde sao considerados apenas quatro passos Outro diagrama poderia ser construido porém partiria do estado 1 Mostraremos como se calcula a probabilidade do estado 1 apés quatro passos isto 6 p4 Notamos na darvore de probabilidades Figura 51 que dado que os eventos sdo independentes precisamos multiplicar todas as probabilidades dos caminhos 153 154 que levam ao estado 1 para calcular a probabilidade do estado 1 em quatro passos BILLINTON 1970 Figura 51 Diagrama em árvore de probabilidades iniciando no estado 0 A Tabela 51 mostra em detalhes os cálculos para obtenção de p14 chuva sol chuva sol chuva sol chuva sol chuva sol chuva sol chuva sol chuva sol chuva sol chuva sol chuva sol sol chuva sol chuva sol chuva sol chuva sol 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 4 3 4 3 4 3 4 3 4 3 4 3 4 3 4 1 4 1 4 1 4 1 4 1 4 1 4 1 Passo 1 Passo 2 Passo 3 Passo 4 Tabela 51 Planilha de calculo da probabilidade do estado 1 Se construirmos uma tabela para mostrar os calculos da probabilidade do estado 0 para quatro passos chegaremos sem dtivida no valor po4 4Y 58 0336 Se estendermos os calculos para mais passos nao é dificil concluir que a probabilidade do estado 1 encaminhara para x enquanto que a probabilidade do estado 0 sera de MK preservadas as condicées Com estes calculos podemos responder 4 questao formulada no enunciado do Exemplo 51 Portanto esperase que em seis meses 120 dias serao chuvosos 180x3 120 e 60 dias serao ensolarados 531 Matriz de transicgao de probabilidades Uma notaao conveniente para representar probabilidades de transigao para n passos é a forma de matriz Definigao 54 Matriz de probabilidades de transigfo para n passos Seja S 01 Mo conjunto finito de estados e seja o par de estados i j tal que i je SxS Associe a cada par ij um numero real pn de modo que sejam satisfeitas as propriedades 155 O Pi lparaVdjeSxSe Pij n 1 para VieS definese a matriz P leia jJeS se matriz P elevada ao expoente 7 Po Poi Pom pr Pol Pu Pi 56 Pmo pyi Pym Especificamente para um passo a matriz de probabilidades de transicao é como representada em 57 onde é omitido o indice 1 PoO Pol POM P P0 Pil Pim Dot Df 57 PMO PM1 PMM Em particular para n 0 temse como conseqiiéncia natural que P éa propria matriz identidade J de ordem M 1xM 1 0 que esta de acordo com o fato de que Py é igual a PX9 j X9 i e lseij 0 py on i j Com base no teorema da probabilidade total e na definigao de probabilidade de transiao para n passos pn PX j X1 temse a expressao 58 para o calculo da probabilidade do estado j em n passos pn PX A pi Opyn i 58 156 A partir da expresso 58 podemos concluir que a matriz P é relacionada a distribuigao inicial de probabilidades p0 definida pela expressdo 55 e ao vetor de probabilidades de estados para n passos através da expressdo 59 59 pn pOP eo Esta expresséo pode ser deduzida pela aplicacgao do Principio da Inducao Matematica a exemplo do que foi feito durante a solugéo do Exemplo 51 para o caso particular de um processo de 2 estados Em relagao a expressao 59 se o espaco de estados S do processo de Markov X for finito entdéo o cdlculo deP relativamente facil Para processos de Markov com espacos de estados contdveis porém infinitos 0 célculo deP nao é trivial Contudo existem métodos para determinar 0 comportamento assintdtico isto é quando noode pn e P 532 Cadeias de Markov Uma forma visual conveniente para representar um processo de Markov é através de um grafo que se comp6e de nds que sao os estados e arcos direcionados que simbolizam as transigOes entre estados Este grafo é denominado diagrama de transigao Definigado 55 Cadeia de Markov A seqiiéncia X n 0 1 2 chamada uma cadeia de Markov homogénea de tempo discreto com espaco de estados S 012M e matriz de probabilidades de transigao P se para todo n 0 1 2 a condiao PX JI Xp D PX f XQ O Di é satisfeita para todo i je SxS Considere 0 exemplo apresentado a seguir 157 Exemplo 52 Considere o problema enunciado no Exemplo 51 Desejamos utilizar a representagdo sob a forma de diagrama de transigéo de uma cadeia de Markov para expressar o problema daquele enunciado Identificamos dois estados portanto M1 e o espaco de estados éS01 O produto cartesiano SxS é 00 01 10 dD A matriz de probabilidades de transigao para um passo a seguinte Poo Pot lh P 7 P Vat Pio Pil MY y O grafo que corresponde a cadeia de Markov para este exemplo é ilustrado na Figura 52 pos Poo Ms PU A Soh Figura 52 Diagrama de transigao de uma cadeia de Markov com dois estados A analise de cadeias de Markov utilizando matriz de probabilidades de transigaéo pode ser efetuada tomandose certas precaugdes tendo em vista que nem todos os processos de Markov de tempo discreto comportamse de modo semelhante 4 medida que o numero de passos aumenta Surge entaéo a necessidade de uma classificagao das cadeias de Markov 533 Classificagao das cadeias de Markov Os estados de um processo de Markov sao divididos em transitorio e recorrente Esta classificagéo diz respeito 4 probabilidade do processo retornar a um dado estado i se 0 processo partiu deste estado 158 Seja f a probabilidade de que o processo retornara ao estado i dado que o processo tenha partido deste estado entaéo segue a definicdo de estado recorrente Definicgao 56 Estado recorrente Um estado i é recorrente se e somente se partindo do estado i 0 processo eventualmente retornara ao estado i com probabilidade f 1 O processo cuja cadeia de Markov foi apresentada no Exemplo 52 possui ambos os estados recorrentes Outro exemplo de estados recorrentes corresponde a matriz de probabilidades de transig4o mostrada a seguir 0 1 P 1 0 Uma cadeia de Markov com dois estados recorrentes esta ilustrada na Figura 53 Poo 1 go on Pi Figura 53 Diagrama de transigao de uma cadeia de Markov com dois estados recorrentes Estados transit6rios também conhecidos como nfo recorrentes so aqueles que partindo do estado i ha uma probabilidade positiva de que 0 processo nao retornara a esse estado isto é f 1 Estados recorrentes e transit6rios podem coexistir numa mesma cadeia de Markov A caracterizacao de estados transitérios nao é trivial e por esta razao os detalhes de processos de Markov desse tipo nao serao enfatizados neste texto Um tipo especial de estado recorrente 0 estado absorvente cuja definigao é estabelecida a seguir conforme a referéncia TRIVEDI 2002 Definicgao 57 Estado absorvente Um estado i é dito ser um estado absorvente se e somente se a probabilidade p é igual a 1 159 160 A cadeia cujo diagrama de transição está ilustrado na Figura 53 tem ambos os estados absorventes É importante ressaltar que só é possível escapar de um estado absorvente se o processo for reiniciado ou seja se o processo partir novamente de qualquer outro estado que não seja absorvente Vamos apresentar um exemplo para tornar mais claras as definições Exemplo 53 Considere um navio com dois sistemas propulsores que são duas turbinas idênticas Seja n X a variável aleatória tal que seu valor é o número de turbinas em operação normal no passo n Se uma das turbinas falhar ela poderá ser consertada enquanto se ambas falharem o navio pára mas ainda haverá possibilidade de que uma das turbinas seja consertada sendo esta a reignição do processo de Markov e não a transição para outro estado As probabilidades são as seguintes se uma turbina que nunca passou por reparo é boa no tempo nt 1 ela tem confiabilidade de 90 no tempo nt porém uma turbina que se estragou no tempo nt 1 após reparada é apenas 60 confiável no tempo nt Suponha as probabilidades independentes e modele o problema como um processo de Markov de tempo discreto Os valores possíveis para a variável X são 0 1 e 2 sendo respectivamente duas turbinas estragadas apenas uma operando e ambas operando O modelo de probabilidades sugerido é o Binomial já que os eventos são independentes ou seja a falha de uma turbina não implica na falha da outra e cada turbina só pode ser encontrada em uma dentre duas condições As probabilidades de transição são calculadas como a seguir ambas em operação 22 1 2 2 p X P X n n 0 81 90 90 22 p uma turbina boa e a outra estragada dado que ambas estavam em operação 21 1 2 1 p X P X n n 018 90 10 10 90 21 p ambas estragadas dado que as duas estavam boas 20 1 2 0 p X P X n n 0 01 1 21 22 20 p p p uma em operação e a outra entra em operação após o reparo 12 1 1 2 p X P X n n P12 99 x 06 054 nenhuma em operacao dado que apenas uma estava boa PX 0 X D pio P19 01 x 04 004 uma em operagao dado que uma delas estava estragada PX 11X py1 Pir 1 Piz Pio 042 O estado 0 é absorvente uma vez que entrando nele nao se pode abandonéa lo exceto se 0 processo partir novamente portanto Pog 1 A matriz de probabilidades de transicao para um passo fica conforme esta mostrada 2 1 0 2081 018 001 P1054 042 004 O O 0 1 As analises de sistemas cujos modelos sao representados por processos de Markov de tempo discreto para elevado nimero de passos trazem informac6es importantes No entanto nem todos os processos comportamse de maneira idéntica para n 9 e por isso nao permitem que certas conclusGes sejam extraidas Dai advém a necessidade de estabelecer objetivamente sob quais condigées as probabilidades limites existem e se possuem ou no algum significado fisico Definigao 58 Probabilidade limite ou probabilidade estacionaria Para o estado j de uma cadeia de Markov o elemento v j para j01 M é definido como a probabilidade limite v j lim Pj n ou seja v j é a probabilidade do estado j em regime estacionario neo Em conseqiiéncia 0 vetor vvg Wy vy éo0 vetor de regime estacionario Nos desenvolvimentos que seguem sera mostrado que para determinadas cadeias nem sempre é possivel obter o vetor de probabilidades limites Uma propriedade 161 requerida para a existéncia de v tal como definida anteriormente é que a cadeia seja aperiddica Definigao 59 Periodicidade de estados Se partindo do estado i retornamos a este estado em um numero par ou impar maior que 1 de passos dizemos que o estado é periéddico com periodo igual ao menor nimero inteiro de passos que for necessario para alcangar o estado A uma cadeia com estados periddicos designamos cadeia periddica Por outro lado sera aperiddica se todos os estados forem aperiddicos Uma forma de verificar a periodicidade de estados é visualizar 0 processo como uma 4rvore de probabilidades Por exemplo a cadeia cuja matriz é 0 1 OO 14 P 11 0 é periddica com periodo 2 A arvore de probabilidades ilustrada na Figura 54 mostra isto claramente 1 passo 2 passo 3 passo OO 0 n1 n2 n3 Figura 54 Arvore de probabilidades de uma cadeia de Markov com dois estados periddicos Por outro lado ambos os estados da cadeia de Markov da Figura 53 sao aperiddicos Outro exemplo de cadeia com estados aperiddicos é a cadeia cuja arvore esta ilustrada na Figura 51 Na arvore da Figura 51 é facil visualizar que partindo do estado 0 é possivel alcangar 0 estado 0 em um passo de modo andlogo se a partida for do estado 1 alcangase 0 mesmo estado em um passo Em contraposic4o aos estados absorventes se todos os estados de uma dada cadeia de Markov se comunicam a matriz de probabilidades de transigo dessa cadeia exibira propriedades especiais A definigao de estados comunicantes é dada em seguida 162 Definigao 510 Estados comunicantes O estado i se comunica com 0 estado j se partindo do estado 7 possivel alcangar 0 estado j direta ou indiretamente observandose o sentido do arco que os une Exemplo 54 Dadas as matrizes de transigao associadas as cadeias de Markov identificar se os estados se comunicam ou nao As posigdes marcadas com asterisco representam numeros positivos probabilidades de transigao para um passo 0 1 2 O O a P1 Q Os estados da cadeia de Markov da matriz P sao representados pelos numeros 0 le 2 Partindo do estado 1 isto é segunda linha da matriz é possivel chegar diretamente a qualquer um dos estados Na primeira linha de 0 nao conseguimos chegar diretamente ao estado 1 Todavia de 0 podemos chegar ao estado 2 e dai alcangamos 1 Portanto na cadeia que a matriz P representa todos os seus estados se comunicam A outra matriz é mostrada a seguir 0 1 2 0 Kk OK b P10 0 2 O A partir desta matriz é possivel construir o diagrama de transiao da cadeia na qual a existéncia de seta indica elemento positivo na matriz A Figura 55 ilustra o diagrama de transigdo que corresponde a ultima matriz Figura 55 Diagrama de transigao de uma cadeia de Markov onde 0 estado 1 é absorvente 163 Ao analisarmos a cadeia da Figura 55 é imediata a constatagao de que os estados 0 e 2 se comunicam e que 0 estado nao se comunica com os demais As cadeias de Markov em que todos os estados podem ser alcangados a partir de todos os outros estados em um ntmero finito de passos sao chamadas de cadeias irredutiveis Assim as cadeias dos Exemplos 52 e 54a sao irredutiveis e aperiddicas Os autores Hillier e Lieberman demonstram que todos os estados em uma cadeia de Markov irredutivel sao recorrentes Implicando que para identificar se uma cadeia de Markov é irredutivel é 0 bastante provar que todos os estados do processo se comunicam Esta assertiva pode ser colocada de outra forma mais pratica conforme esta exposta no Teorema 51 Teorema 51 Uma condigao suficiente para uma cadeia ser identificada como irredutivel é que exista algum numero n inteiro nao negativo tal que pn 0 para todo i ej Este teorema fornece uma regra pratica para a identificagaéo de cadeias irredutiveis Em outras palavras ao elevarmos a matriz P da cadeia que se quer identificar a poténcias n de pequenos valores por exemplo n2 n3 etc podemos verificar se existe algum n para o qual pjn0O para todo i ej Em caso afirmativo a cadeia irredutivel A referéncia BRONSON 1985 designa a cadeia que atende a condiao do Teorema 51 de cadeia regular Vamos aplicar o resultado do Teorema 51 para identificar as cadeias cujas matrizes sao dadas no Exemplo 55 Exemplo 55 Dadas as matrizes seguintes 0 0 OK O 0 0 a P O e b P 0 0 O Ok 0 0 verifique se elas correspondem a cadeias irredutiveis Tomamos a matriz P do caso a e a elevamos ao quadrado obtendose 164 pz 9 i QO al 0 OK 0 OOK Kk O Ao efetuarmos o produto simbdélicoP por P verificamos que todas as posigdes com elementos nulos foram preenchidas portanto é correto afirmar que a cadeia é irredutivel ou regular Tomamos a matriz P do caso b e a elevamos ao quadrado obtendose 0 O 0 O p 0 O 0 O De posse de P é imediata a constatagao que a matriz P exibe 0 mesmo padrao de preenchimentos com elementos positivos observado emP Conseqiientemente todas as poténcias Pt P P exibirio padrdes semelhantes ao de P E possivel concluir que nao existe n de tal modo que pjn 0 Isto implica que a cadeia em questao nao é irredutivel Conclusado idéntica pode ser extraida se aplicarmos o resultado do Teorema 51 a matriz do Exemplo 54b confirmando assim a identificagao feita pelo método dos estados comunicantes Para complementar a secéo que trata da classificagéo das cadeias de Markov considere a definiao de estado recorrente positivo ou nao nulo Definicgao 511 Estado recorrente positivo O estado i é recorrente positivo se partindo do estado i o tempo esperado para o processo visitar novamente este estado é finito Por outro lado ao partir do estado ise 0 tempo esperado para o processo visitar este estado for infinito o estado é dito recorrente nulo O tempo esperado para um processo revisitar o estado 7 também conhecido como tempo médio de recorréncia é definido pela esperanga matematica indicada pela expressao 510 Mi Unfyin para dX fim 1 510 nl nl 165 onde fn a probabilidade de revisitar 0 estado i em n passos O tempo esperado para um processo que tenha partido do estado i apdos npassos retornar ao estado j também conhecido como tempo de primeira passagem é definido conforme 511 Mj Lf 511 nl onde fjjn a probabilidade em n passos de visitar 0 estado j se 0 processo partiu do estado 7 Dado que fi 1 para i je SXS onde S 01 2 M as nl probabilidades n podem ser calculadas pelas relagoes recursivas 512 fg py py fig 2 pi fy DP ji 512 fin py 0 fj Dp gnD fy QP n2W fyOD j A aplicagao das expressdes 510 a 512 sera feita posteriormente Estados recorrentes positivos que sao aperiddicos sao chamados de estados ergddicos Conseqiientemente cadeias que tém todos os estados ergéddicos sao designadas como cadeias ergddicas 534 Analise de cadeias finitas irredutiveis com estados aperiddicos As cadeias finitas de Markov cujos estados sao recorrentes positivos e aperiddicos gozam de uma propriedade singular que esta expressa no Teorema 52 TRIVEDI 2002 Teorema 52 Para uma cadeia irredutivel e aperiddica com todos os estados recorrentes positivos o vetor de probabilidades limites vv9 vj vag tal que v j lim Pp j noo 166 é o nico vetor de probabilidades de regime estaciondrio e satisfaz as relagdes 513 e 514 a saber vvP 513 M dD vj lvj 20 514 j0 O calculo do vetor v pode ser efetuado usando 0 computador através da equacao iterativa yk v p para k 012 arbitrando um vetor de estimativa inicial yO até que a convergéncia seja alcangada Uma maneira alternativa para a obtengao de v é 0 método analitico constrdise 0 sistema 513 e trocase uma das M 1 equagdes lineares pela relagao 514 para em seguida solucionar o sistema de equagoes resultante Vamos aplicar o resultado do Teorema 52 para calcular as probabilidades estacionarias dos estados do sistema do Exemplo 51 Exemplo 56 Dado que a cadeia do Exemplo 51 atende as condigées do Teorema 52 isto é é irredutivel e aperiddica com estados recorrentes positivos calcule as probabilidades de regime estacionario Primeiramente vamos utilizar a equagdo de iteragéo tomando o vetor inicial yO 1 0 que para este exemplo fica conforme esta mostrada a seguir Vd vt Vi Ws a com y 1 0 My i A Tabela 52 resume os calculos iterativos Tabela 52 Iteragdes para obtencao do vetor de probabilidades de regime estacionario 0 1 0 0500 0500 0500 0500 0500 0500 0375 0625 0125 0125 0375 0625 0344 0656 0031 0031 0344 0656 0336 0664 8x103 8x1073 0336 0664 0334 0666 2x103 2x1073 167 168 Em função da precisão requerida nos cálculos mais iterações podem ser realizadas Sugerimos que o leitor repita o procedimento iterativo mostrado anteriormente tomando qualquer outro vetor v 0 como estimativa inicial A Figura 56 ilustra a evolução das probabilidades dos estados 0 e 1 à medida que o número de passos aumenta Ressaltamos nestes cálculos a coincidência entre o número de passos n e o contador de iterações k Os gráficos ilustrados na Figura 56 merecem alguns comentários No gráfico da esquerda o vetor de probabilidades iniciais é 0 1 0 p Enquanto que no gráfico da direita o vetor de probabilidades iniciais é 1 0 0 p Observase que o vetor de probabilidades de regime estacionário obtido ou seja 1 0 1 0 p p v v v independe do vetor de probabilidades iniciais Regra geral para qualquer cadeia irredutível aperiódica as probabilidades limites dos estados lim lim n p n p v ij n j n j existem e são independentes do vetor de probabilidades iniciais p0 Figura 56 Probabilidades dos estados em função do número de passos para dois vetores de probabilidades iniciais distintos O leitor é convidado a voltar ao Exemplo 51 e tragar um paralelo entre a solucdo obtida aqui através do processo iterativo e os calculos efetuados naquele exemplo Agora 0 calculo das probabilidades estaciondarias sera feito analiticamente Para tal com base na expresso 513 obtemos o sistema de equagoes Y 11y 0 0 VI vo wylv nlp 2 4 M 30 vag 0 Como as equacgdes sao linearmente dependentes substituise a segunda equacao arbitrouse a segunda mas poderia ser a primeira pela equacao 514 O sistema de equacoes assim obtido é 0 seguinte 1 1 20 veal 0 Vo tv 1 1 2 Zs A solugao deste sistema nos fornece v My Xl que é a mesma solucao para a qual converge 0 método iterativo Ao estudar processos de Markov é natural a expectativa do leitor por conhecer as aplicagGées dessa interessante teoria em problemas do mundo real A interpretagao fisica dos resultados obtidos com os calculos e a tradugao desses resultados para a linguagem natural s4o etapas essenciais para a compreensao do comportamento do sistema sob analise Neste contexto apresentamos em seguida algumas interpretag6es relevantes a probabilidade de regime estacionario v a porcentagem do tempo total considerado que 0 processo permanece no estado 1 para cadeias ergdédicas o reciproco da probabilidade de regime estacionario designado por 6 o tempo esperado de recorréncia do estado isto é 1 Hj para i012M i onde o tempo médio do processo revisitar 0 estado 7 169 seja fuma fungdo da varidvel aleatéria X por exemplo custos financeiros associados aos estados As probabilidades estacionarias v podem ser utilizadas para calcular a esperanga matematica de fX assim M EfX Lvf 515 i0 Em seguida apresentamos um exemplo que permite a interpretacdo dos resultados obtidos de maneira mais pratica Exemplo 57 Uma fabrica possui duas maquinas idénticas essenciais ao processo de manufatura e sao operadas continuamente exceto quando elas estao quebradas Devido ao fato que essas maquinas sio muito sensiveis e quebram freqiientemente é necessario remunerar em tempo integral um técnico para reparar a maquina quando ocorrer alguma falha Suponha que o intervalo de tempo de observacgéo seja de um dia e que a varidvel aleatéria X representa o nimero de maquinas quebradas no dia n Os valores possiveis para a varidvel aleatéria so X 0 1 e 2 Admita que durante cem dias de observacoes foram anotadas as situagdes das duas maquinas chegandose as probabilidades de transides dos estados para 1 dia que estéo mostradas na matriz P 2 1 O 2 1 O 240 20 40 204 02 04 P140 40 20 P104 04 02 0 20 20 60 002 02 06 Outro dado importante é que custos de estar nos estados 0 1 e 2 sao respectivamente 000 150000 e 1000000 e ha também o custo fixo de remuneragao do técnico que é 10000 ao dia O custo de duas maquinas paradas é alto porque implica na parada da linha de producao podendo causar sérios transtornos a fabrica A partir das probabilidades de regime estacionario calcule a se ambas as maquinas se estragam a probabilidade que o tempo para consertar uma dessas mAaquinas seja de dois dias 170 b na ocorréncia de ambas as maquinas fora de operacga4o em quantos dias esperase que esta situagao ocorra novamente c o nimero esperado de dias de ociosidade do técnico d 0 custo por dia a longo prazo para manter as maquinas A partir da matriz concluise que a cadeia é irredutivel e aperiddica com estados recorrentes positivos Por isso podemos aplicar o Teorema 52 para calcular 0 vetor v donde obtemos v03125 02500 04375 Para responder o item a precisamos calcular a probabilidade que o tempo de primeira passagem do estado 0 ao estado 1 seja igual a 2 dias ou seja fo 2 Utilizamos entao as relacOes recursivas para obter f92 foi Por for 92 for Poi for Pi Para concluir 0 item a precisamos calcular pg2 04 02 0404 02 04 032 024 044 P 04 04 02104 04 02036 028 036 Po 2 024 02 02 06102 02 06 028 024 048 Portanto a probabilidade que 0 tempo para consertar uma dessas maquinas seja de dois dias é igual a for poi for Pir foi 2 024 02 x 04 fo 2 016 O item b pede o tempo de recorréncia para o estado 2 Basta calcular fy7 I resultando no seguinte valor v2 171 My 3195 Haz 32 dias Para o item c 0 ntiimero esperado de dias de ociosidade do técnico corresponde aos dias em que ambas as maquinas ficam em operacéo ou seja é o tempo de recorréncia do estado 0 Moy 4375 Hoo 23 dias Finalmente para o item d o custo por dia a longo prazo para manter as maquinas é a esperanca matematica da fungdo custo em regime estacionario Ef X 04375 x 000 025 x 150000 03125 x 1000000 Ef X 350000 Devemos adicionar ao valor obtido anteriormente o custo fixo devido a remuneracgao do técnico Portanto 0 custo por dia a longo prazo para manter as maquinas é 360000 As cadeias de Markov analisadas nesta segéo exibem a propriedade especial de que a poténcia P para n tendendo ao infinito resulta numa matriz cujas linhas sao todas iguais A expressdo 516 exprime a mencionada propriedade de forma mais clara Yo ot YM Vy y eee Vv lim Pp 2 My 516 n oo Dot tee vo Vy eee VM Por exemplo a matriz do Exemplo 56 ao ser elevada a expoentes cada vez mais altos resulta na seguinte matriz Y Yl fy 2 lim P lim iy y oe noo nal Yo YH Esta é uma propriedade inerente as cadeias finitas irredutiveis e aperiddicas No entanto cadeias que possuem estados absorventes constituem uma classe especial de 172 processos que nao exibem tal propriedade Por exemplo a matriz do Exemplo 53 é um caso que nao atende a propriedade 535 Analise de cadeias finitas com estados absorventes O estudo das cadeias de Markov finitas com estados absorventes requer que a matriz de probabilidades de transigéo P seja expressa de modo especial Isto implica que as linhas de P que correspondem aos estados nao absorventes devem ser arranjadas em primeiro lugar e em seguida nas Ultimas linhas figuram os estados absorventes A expressao 517 mostra uma representagdo na forma candnica da matriz de probabilidades de transigéo quando ha estados absorventes M1 7 Ur rt 7 As Lee c Le QC p Gr Grr rrl pa QO O 1 O 0 7 517 QO O QO 1d estados nao absorventes Q Cc estados absorventes ee ee O cdlculo da poténcia P passa pelo seguinte desenvolvimento Primeiramente para k natural provase que PK é igual a identidade 518 k k Cc p 2 518 0 TI onde o elemento da posiao i 7 da matriz ok denota a probabilidade de chegar ao estado nao absorvente j apds k passos partindo do estado nao absorvente i enquanto que C denota a submatriz C apés k passos Uma das informag6es mais relevantes na andlise de cadeias absorventes é 0 numero esperado de passos em que o processo ficard no estado nao absorvente i antes da absorcao Considere o seguinte teorema 173 Teorema 52 Para uma cadeia de Markov com pelo menos um estado absorvente o nimero esperado de passos para a absorao partindo do estado nao absorvente i é 0 somatério dos elementos da i ésima linha da matriz J Qo Uma prova deste teorema fundamentase no fato de que para 0 processo alcangar a absorcdo este deve transitar antes por todos os estados nao absorventes nos passos 0 1 2 co Assim o nimero esperado de passos antes da absorcao se o processo partiu do estado nao absorvente i é a iésima linha da matriz que resulta do somatério ak 0 2 oo XO QQQ k0 lembrando que 0 I e que a norma da matriz Q seja menor que isto é llo 1 Finalmente recorremos as séries convergentes neste caso aplicadas a matrizes que nos permite concluir que 0 somatorio anterior é igual 4 matriz J Qo A matriz I Qo é designada como matriz fundamental e é uma rica fonte de informagao sobre cadeias de Markov Os elementos dessa matriz dao os nimeros de passos ou os numeros de vezes que 0 processo visita os estados nao absorventes antes de alcangar a absorao vide expressao 512 Antes de passarmos a um exemplo de aplicagaéo vamos estabelecer mais um conceito importante sobre cadeias absorventes Suponhamos que o processo tenha partido do estado nao absorvente i e desejamos calcular a probabilidade de absorgao no estado j Note se que aqui o indice j indica um estado absorvente Teorema 54 Para uma cadeia de Markov com pelo menos um estado absorvente a probabilidade do processo que partiu do estado nao absorvente i ser absorvido no estado j é o elemento da posigao i 7 da matriz que resulta do produto J oc A demonstragao deste teorema é deixada como exercicio para o leitor A referéncia SHAMBLIN 1989 traz um argumento que pode auxiliar o leitor nesta tarefa 174 Outra forma possivel para se concluir pela validade do Teorema 54 é mostrar que 0 limite jm P comportase como mostrado a seguir TRIVEDI 2002 noo cy g lim P lim Q 0 UQe 520 noo noo 0 I 0 IT Estamos de posse de métodos e informagdes que permite resolver um exemplo de aplicaao Exemplo 58 Considere 0 problema do enunciado do Exemplo 53 Ambas as turbinas em falha constituem um estado absorvente do qual s6 se pode escapar se uma das turbinas puder ser consertada enquanto o navio estiver completamente parado ou se de algum modo turbinas novas puderem ser transportadas ao navio Desejamos determinar o tempo médio ou seja o numero de passos para o navio paralisar totalmente suas maquinas supondo que ele se encontra com ambas as turbinas operando normalmente Calcule também as probabilidades de absorao Do Exemplo 53 temos que a matriz de probabilidades de transigéo para este problema é a seguinte 2 1 0 2081 018 001 P1054 042 004 O O 0 1 De acordo com a expressao 518 as matrizes QO C e I sao como dadas a seguir 081 018 001 Q C e J i 054 042 004 175 A primeira pergunta referese ao numero de passos para alcancgar o estado absorvente 0 tendo partido do estado 2 Portanto necessitamos calcular a matriz J go 10 1 0 081 O18 O19 018 0 1 054 042 054 058 got 219 018 446154 188462 054 058 415385 146154 A matriz fundamental J Qo é entao da seguinte forma 2 446154 188462 UQ 1 415385 146154 A resposta a primeira questéo é a soma dos elementos da primeira linha da matriz fundamental que resulta em 446154188462 634616 Isto significa que se duas turbinas estiverem em operacao 0 numero esperado de passos até que as duas se estraguem é de 635 unidades de tempo As probabilidades de absorgao sao calculadas com base no Teorema 54 l oye 019 018 001 446154 188462 001 1000 054 058 004 415385 146154 004 1000 Ul oc 2 1000 11000 Partindo do estado com duas turbinas a probabilidade de absorcao é igual a 1 Do mesmo modo partindo do estado com uma turbina a probabilidade de absorcdo é também igual a 1 As probabilidades para alcangar a absorgao partindo de qualquer um dos estados nao absorventes nem sempre sao iguais a unidade Isto ocorreu neste exemplo porque na cadeia de Markov analisada ha apenas um estado absorvente O exemplo que sera apresentado a seguir considera uma cadeia com dois estados absorventes e tem por objetivo 176 principal mostrar uma forma alternativa ao Teorema 53 de se calcular os tempos médios para absorao Exemplo 59 Um reservatério de uma usina hidrelétrica é utilizado com a finalidade de prover renda adicional 4 populacéo que habita suas vizinhancgas através da atividade pesqueira Periodicamente a companhia que detém a concessaéo supre o reservatério com alevinos que se tornarao adultos procriarao e também servirao ao propdsito da pesca Estudos mostraram que existem dois bons estados para pesca os quais serao designados por Ss 3 No entanto se a atividade pesqueira for intensificada a populacdo de peixes pode cair a niveis em que a pesca precisa ser interrompida por certo tempo Além disso por causas naturais 0 crescimento excessivo da populacgao de plantas aquaticas algas e outras pode alcangar um nivel a ponto de prejudicar a pesca levando também a suspensao da atividade que somente sera retomada apés a limpeza do lago Este sistema fisico foi modelado como um processo de Markov em que o periodo de tempo considerado razodvel para ser tomado como unidade de tempo é de um més isto significa que um passo equivale ao tempo de um més O estado que corresponde a insergdo de alevinos no reservatério é um estado transitério e é denotado por s Os estados de interrupgéo da pesca por redugdao do numero de peixes e suspensao da atividade por poluido aquatica sao simbolizados respectivamente por s4 5 sendo estes estados absorventes As probabilidades de transigao foram levantadas por métodos estatisticos e estaéo indicadas na matriz mostrada a seguir Desejamos conhecer o comportamento deste processo no regime estaciondério Determine os tempos de primeira passagem partindo de estados nao absorventes até os estados absorventes Calcule também a probabilidade de absorcao no estado s4 se 0 processo partiu do estado transitério Sy So 53 Sq S5 39 08 O OL O1 s90 O 07 01 01 Ps30 05 02 02 01 s40 O O 1 O s0 O O O 1 177 O grafo da cadeia de Markov deste exemplo esta ilustrado na Figura 57 a titulo de ilustragdo apenas Notese nesta figura o estado transitério s e os estados absorventes sy 55 01 S S 01 01 01 01 07 05 O21 Orn Figura 57 Diagrama de transicgao da cadeia de Markov do modelo de piscicultura do reservat6rio Os tempos médios para alcangar a absorgao que sao os nimeros esperados de meses para atingir os estados absorventes podem ser calculados pela aplicagao do Teorema 53 de maneira andloga ao que foi feito no exemplo anterior 1 0 0 0 O08 O 1 08 0O IQ0 1 Oj0 O1 070 09 07 0 0 1 0 05 02 0 05 08 108 oO 1 173 151 aQy0 09 07 0 216 189 0 05 08 O 135 243 A matriz fundamental J Qo é entao da seguinte forma 178 sf 1 173 151 Q50 216 189 s30 135 243 Os passos esperados antes da absorgao sao mostrados na Tabela 53 Tabela 53 Calculos dos passos esperados antes da absorcao a partir dos elementos da matriz fundamental Estado nao absorvente de partida Passos esperados antes da absorgao 216 189 405 meses Os passos calculados na Tabela 53 sao os tempos para absorcao partindo de estados nao absorventes As probabilidades de absorgao sao obtidas aproveitandose a matriz fundamental com base no procedimento proposto no Teorema 54 1 473 1517 01 01 dQc0 216 189 01 01 0 135 24302 O S4 S5 81 058 042 10 C 55 059 041 3062 038 A probabilidade de absorgaéo no estado sq se 0 processo partiu do estado transit6rio é 058 Os ntmeros que figuram na matriz obtida anteriormente podem ser obtidos aplicando o processo iterativo estabelecido na segao 534 que foi também utilizado no Exemplo 56 Arbitrando o vetor inicial yO fl 0 0 0 0 apos trinta iteragdes obtém 179 se o vetor v 0 000001 00001 05756 04243 Os dois tiltimos elementos de v0 referemse aos estados absorventes Um método alternativo de obtengéo dos tempos de primeira passagem usa as formulas recursivas 512 e 513 A aplicagao dessas formulas exige calculos sucessivos de poténcias da matriz de probabilidades de transigao o que implica necessariamente no emprego de computador HILLIER e LIEBERMAN 1995 Vamos exemplificar os calculos supondo s 0 estado de partida ou seja i1 Para j 4 temos fia pig 01 fia Pig fia Pag fi42 01801 x1 fi42 008 fi4Q pia fia pas fia2 pag fig3 03 01x 1008x1 fi43 012 fia4 pia4 fia pag 3 fia 2 p4g2 fia3 pag fia 0362401x1008x1012x1 f44 00624 fia pia fra pag 4 fra2 pag 3 fa 3 pga 2 fra4 Pag fi45 04207 01x1008 x1012x100624x1 f45 00583 Para j 5 temos fis pi5 01 fis Pis2 fisMPss fis2 018O01x1 fi52 008 fisG P1538 fis Ps52 fis2 P55 fis 0244 01x1008x1 fis3 0064 Fis4 P154 fis pss3 fis 2 p552 fis 3 P55 fis4 02896 01x1008 x10064x1 f54 00456 fis pis fis ps54 fis 2 P55 3 S153 p552 fis4 pss fi55 03244 01 x 1 008 x 1 0064 x 100456 x1 fi55 00348 Obviamente os calculos devem continuar até um valor de nconsiderado alto A Tabela 54 mostra os resultados parciais obtidos com o uso do computador Aplicamos entao a expressao 512 duas vezes resultando em 44 e em f45 Ma 25448 e 45 16981 180 Adicionando os dois tempos médios encontramos o nimero esperado de passos antes da absorcdo partindo do estado s 254481698142429 meses Este resultado se arredondado com duas casas decimais é 0 mesmo obtido anteriormente através da matriz fundamental vide Tabela 53 Tabela 54 Valores de fj4k e f5k para k 1240 fi4k Fi5k 01000 00091 00005 00000 01000 00058 00003 00000 00800 00068 00004 00000 00800 00043 00002 00000 01200 00050 00003 00000 00640 00032 00002 00000 00624 00037 00002 00000 00456 00024 00001 00000 00583 00028 00001 00000 00348 00018 00001 00000 00381 00021 00001 00000 00255 00013 00001 00000 00307 00015 00001 00000 00191 00010 00001 00000 00218 00011 00001 00000 00142 00007 00000 00000 00167 00009 00000 00000 00106 00005 00000 00000 00122 00006 00000 00000 00078 00004 00000 00000 O livro intitulado Matrix Analysis and Applied Linear Algebra uma publicagao da SIAM de autoria de Carl D Meyer traz interessante abordagem sobre a Teoria de PerronFrobenius que pode auxiliar o leitor na compreensio deste capitulo especificamente no que se refere ao tratamento de matrizes estocasticas Existem processos estocasticos com caracteristicas de processos de Markov em que o tempo nao é uma variavel discreta embora os estados sejam discretos Esta classe de processos markovianos sera estudada na seao seguinte 54 Processos de Markov de tempo continuo Processos de Markov de tempo continuo sao similares aos processos de Markov de tempo discreto exceto pelo fato de que as transigdes entre estados podem ocorrer em qualquer instante de tempo O conjunto que denota o espaco de estados do processo a exemplo dos processos de Markov estudados anteriormente é discreto podendo ser finito ou infinito Com o objetivo de caracterizar precisamente os processos markovianos de tempo continuo buscaremos a seguir estabelecer formalmente as relagdes que regem seu comportamento 181 Em primeiro lugar a Definigao 51 se aplica aos processos de Markov de tempo continuo em particular a expressao 53 Resta definir probabilidades de transiAo Definigao 512 Probabilidades de transigéo Sejam dois estados ie j 0 instante de tempo u tal queOute Xt e Xu as variaveis aleatérias discretas que contém os nimeros dos estados nos tempos f e uw respectivamente a probabilidade de transiao pj ut definida pela probabilidade condicional pyUt PXMjIXW sendo i j 012e 1 seij tt py seix As cadeias de Markov Xt tf 0 sao designadas como cadeias tempo homogéneas se as probabilidades de transigao put dependem somente da diferenga de tempos fu Para definirmos completamente um processo de Markov de tempo continuo precisamos definir as probabilidades dos estados p j t no instante t para j 012 Definigao 513 Probabilidade de estado A probabilidade do processo ser encontrado no estado j no instante de tempo é definida por PpjHDPXXM Com base no teorema da probabilidade total expressamos PX t j como 0 somatério PX J XW PXW1 l de modo que para u 0 resulta na expresso 182 Pj LpyO1pjO 521 l A expressao 521 mostra que um processo de Markov de tempo continuo esta completamente definido se as probabilidades de transigéo e o vetor inicial de probabilidades dos estados p0poO pO pry O sao especificados para M 1 estados Em seguida apresentaremos uma conseqiiéncia notavel das propriedades dos processos de Markov de tempo continuo Uma propriedade inerente as cadeias de Markov de tempo continuo do tipo tempohomogéneas é que o futuro do processo é completamente definido no estado presente Portanto a distribuigao da varidvel aleatéria tempo de permanéncia de um processo em um dado estado deve ser sem memoria Designando por Y tal varidvel aleatéria a seguinte probabilidade condicional PY strlY2nPY r descreve objetivamente essa propriedade Para auxiliar o leitor na compreensao desse conceito foi elaborada a Figura 58 na qual estao ilustradas no eixo dos tempos as localizagdes de te r sendo Ye ttr A variavel r é uma varidvel auxiliar que no decorrer da andlise tendera a zero presente futuro Vv 0 r t tr tempo Figura 58 Localizacao de variaveis no eixo dos tempos Com base na referéncia TRIVEDI 2002 segue entao o teorema Teorema 55 Para cadeias de Markov tempohomogéneas a variavel aleatéria tempo que o processo gasta ou permanece num dado estado possui distribuigao exponencial negativa com taxaiguala f 183 184 A demonstração deste teorema é como segue Seja fY t a função densidade de probabilidade exponencial tal que t Y e t f β β 0 t dt t dF t f Y Y de modo que genericamente t P Y FY t A derivada de FY t será denotada por t FY Do conceito de probabilidade condicional propriedade sem memória advém a expressão 1 t F t F r t F r F t P Y r t Y P t r P Y Y Y Y Y Se dividirmos ambos os membros da expressão anterior por r e tomarmos o limite para r 0 teremos a equação diferencial seguinte lembremos do quociente de Newton do Cálculo Diferencial e Integral 1 0 t F t F F Y Y Y cuja solução é a função exponencial t F Y Y e t F 0 1 t Y e t F 1 β Portanto a função densidade de probabilidade para a variável aleatória tempo gasto num dado estado das cadeias de Markov do tipo tempohomogêneas é a exponencial com taxa β Nas análises de cadeias de Markov de tempo contínuo necessitamos da definição de taxa de transição entre dois estados TRIVEDI 2002 Definição 514 Taxa de transição À função contínua não negativa qij t definida por u t ij ij t t u p t q damos o nome de taxa de transição do processo do estado i para o estado j Para uma cadeia de Markov de tempo continuo as taxas de transico e as probabilidades dos estados sao relacionadas por meio da equagao de Kolmogorov mostrada em 522 TRIVEDI 2002 dp t pj N Lay Opi 522 dt ij Na equacao 522 qjjt a taxa de transigao estabelecida na Definigao 514e q 0 somatorio das taxas de transigao do estado j aos estados adjacentes Vamos ilustrar a aplicagéo da equagaéo 522 para uma cadeia de dois estados que esta ilustrada na Figura 59 com suas taxas de transiao 101 Po Onn lt N10 Figura 59 Diagrama de transigao de uma cadeia de Markov de tempo continuo com dois estados Observando o diagrama da Figura 59 temse que 40 401 N10 Escreveremos em seguida para cada estado a equacao 522 apo Y dt 90P0 10P1 dp qp dt Pi 901P0 Para efeito de simplificagao admitiremos as taxas de transiao constantes e a seguinte notagéo gg 2 e gig H Em regime estacionario as equacdes diferenciais reduzemse a equacées algébricas linearmente dependentes 185 186 0 1 0 p p µ λ 0 0 1 p p λ µ Negligenciamos uma das equações e utilizamos o fato de que 1 1 0 p p para obter as probabilidades dos estados em regime estacionário µ λ µ p0 µ λ λ 1p É interessante neste ponto do texto estabelecer a notação correta para probabilidades dos estados em regime estacionário que é basicamente a mesma utilizada na seção que tratou de processos de Markov de tempo discreto de acordo com a Definição 58 A probabilidade limite ou probabilidade estacionária para o estado j é dada pelo limite lim p t v j t j Para tornar mais clara a análise da cadeia de dois estados feita anteriormente considere o exemplo apresentado a seguir Exemplo 510 Calcular as probabilidades instantâneas dos estados 0 e 1 que constam do diagrama de transição da Figura 59 Uma vez calculadas as funções p0 t e p1 t determine pela aplicação de limite para t as probabilidades estacionárias Dos cálculos efetuados anteriormente temse 1 0 0 p p dt dp µ λ 0 1 1 p p dt dp λ µ Para qualquer instante t a soma 1 1 0 p t p t deve se verificar Depois de realizadas substituições chegamos às equações diferenciais de primeira ordem seguintes µ µ λ 0 0 p dt dp λ µ λ 1 1 p dt dp Ao resolvermos estas equacgdes supondo que o processo tenha partido do estado 0 isto p01 e p00 obtemos as solucgdes que sdo as probabilidades instantaneas dos estados A Pot i e Amt AfL Atu 4 A atu Pt e A A Para concluir 0 exemplo supondo 4 Ocalculamos os limites das fungdes pt e pt para t para obter as probabilidades estacionarias vy e v A lim pt lime Gru Vo te too Atu AL A LL A Ll A A A lim pt lim 4rr 2 sy y 1900 se At um AM A fl A kl Ficam dessa forma estabelecidos os elementos fundamentais que permitirao a andlise de cadeias de Markov de tempo continuo em regime estacionario 541 Andalise de cadeias de Markov de tempo continuo para o regime estacionario O nosso interesse resumese aos processos de Markov que tenham alcangado o regime estacionario Isto quer dizer que pretendemos aplicar a teoria para andlises de problemas a longo prazo Do ponto de vista das equagdes os modelos serao independentes da varidvel tempo e conseqiientemente nao trataremos com equacg6ées diferenciais embora os modelos tenham origem na equacao de Kolmogorov dada em 522 Nas condig6es descritas a equagéo de Kolmogorov para o j ésimo estado é conforme mostrada por 523 O0gjv X qv para j 012M 523 ij 187 188 Para permitir a análise em regime estacionário o elemento chave é a matriz de transição a exemplo do que foi feito para cadeias de tempo discreto O primeiro passo naturalmente consistirá em estabelecer procedimentos sistemáticos para obter tal matriz 5411 Obtenção da matriz de transição Consideremos dois pontos de partida possíveis obtenção de P a partir do diagrama de transição e obtenção de P a partir da equação de Kolmogorov No primeiro caso o índice de cada estado é associado a uma única linha e a uma única coluna da matriz caracterizando genericamente um elemento de fora da diagonal da matriz P pelo par ordenado i j com i j O elemento da posição i j com i j associase univocamente com o arco orientado do diagrama de transição da cadeia de Markov que parte do estado i e vai até o estado j Assim temse a seguinte lei de formação da matriz de transição obtida a partir de um dado diagrama de transição elemento da posição i j i j taxa ij q arco orientado de i para j 524 elemento da posição j j 1 q j Para exemplificar este procedimento de obtenção da matriz P tomaremos como exemplo uma cadeia com quatro estados BILLINTON 1970 Exemplo 511 Dado o diagrama da cadeia de Markov ilustrado na Figura 510 obtenha a matriz de transição correspondente Observe que nem todos os nós estão interligados 1 0 4 µ 1 µ 2 µ 1 λ 3 λ 2 λ 4 λ 189 Figura 510 Diagrama de transição de uma cadeia de Markov de tempo contínuo com quatro estados Aplicamos então a regra estabelecida pela expressão 524 para os elementos de fora da diagonal donde obtemos a Tabela 55 Tabela 55 Elementos de fora da diagonal obtidos a partir do diagrama de transição Arco Posição e elemento Arco Posição e elemento De 0 a 1 01 1 λ De 2 a 0 20 2 µ De 0 a 2 02 2 λ De 2 a 1 21 0 De 0 a 3 03 0 De 2 a 3 23 3 λ De 1 a 0 10 1 µ De 3 a 0 30 0 De 1 a 2 12 0 De 3 a 1 31 4 µ De 1 a 3 13 4 λ De 3 a 2 32 3 µ O elemento da diagonal da matriz é obtido subtraindo da unidade a soma das taxas cujos arcos deixam o nó considerado Portanto os elementos da diagonal são Posição 00 1 2 1 λ λ Posição 11 1 4 1 µ λ Posição 22 1 3 2 µ λ Posição 33 1 4 3 µ µ Conseqüentemente a matriz de transição para este exemplo fica conforme indicada a seguir 0 1 2 3 01 4 4 A Ay 0 pu My 1uy A4 0 Ag 2 re 0 1 dy 43 3 3 0 M4 13 1 43 M4 Por outro lado se for conhecido o sistema de equagdes que decorre da aplicagao de 523 a todos os estados a obtencao da matriz de transigéo obedece ao seguinte procedimento genérico Para a equacdo do estado j adicionamos a varidvel v ao primeiro e ao segundo membros simultaneamente e em seguida agrupamos os termos semelhantes deixando a probabilidade estacionaria v explicita no primeiro membro Repetimos este procedimento para todos as M 1 equacées do sistema A idéia é reescrever 0 sistema sob a forma conhecida v vP onde P é a matriz que se deseja obter Exemplificaremos este procedimento através do Exemplo 512 Exemplo 512 Dado 0 sistema de equagées de uma cadeia de Markov de trés estados obtenha a matriz de transigao correspondente QO 3Vv9 YW oT 2v7 QO 4y vo V9 0 3y 3yy 2v9 Adicionamos vg vj v2 a ambos os membros das equacoes dos estados 0 1 e 2 respectivamente vo Ww 7 3V9 YW oT 2Vv YF Vy 4y Vo t VW Wy Ww 3V 3Vyy 2v9 Apos agrupar os termos semelhantes obtemos 190 vo 13vo YW OF 2v7 vo 7 2v09 Woot 2v7 y 4y vo WwW Da yy 3y vo VW Wa 13v 3yy 2Vv9 Wy 2Vv 3y 2v09 vy 7 2v09 OW 2v y vo 3y Vo WW 2Vv9 3y 2v Por fim resulta o sistema na forma matricial onde a matriz de transicdo esta explicita 2 1 2 bo wu velbo me mf tl 3 14 2 3 2 0 1 2 O2 1 2 P11 3 1 2 2 3 2 Quanto 4 classificagao das cadeias a mesma classificagao apresentada nas segdes que trataram de processos discretos no tempo é valida exceto o conceito de periodicidade que esta atrelado ao conceito de passos Assim teremos como antes cadeias com estados recorrentes e cadeias com estados transitorios A classe das cadeias recorrentes compreende também as cadeias absorventes Um estado i é dito ser absorvente se qj 0 para i j de modo que uma vez que se 0 processo entra neste estado o mesmo é destinado a permanecer nele Como definido anteriormente em uma cadeia irredutivel todo estado pode ser alcancado de qualquer outro estado Os processos de Markov de tempo continuo encontram aplicagdes em diversas areas dentro as quais destacamos sistemas de filas de espera processo conhecido como nascimento e morte e confiabilidade de sistemas fisicos em geral 191 192 Vamos ilustrar a análise de cadeias de Markov de tempo contínuo através da solução de dois exemplos O primeiro exemplo é transcrito do livro HILLIER e LIEBERMAN 1995 Exemplo 513 Um shopping tem duas máquinas idênticas que são operadas continuamente exceto quando estão quebradas Assim que uma máquina se quebra ela é reparada imediatamente por um técnico que fica de plantão para atender a emergência O tempo requerido para reparar uma máquina tem distribuição exponencial com média de 50 dia Uma vez que a operação de reparo é concluída o tempo até a próxima falha é também uma variável aleatória exponencial com média de 1 dia sendo estas distribuições independentes Defina a variável aleatória X t como X t número de máquinas quebradas no tempo t então os possíveis valores de X t são 0 1 e 2 Portanto sendo o tempo t uma variável contínua que se inicia em t 0 o processo estocástico de tempo contínuo 0 t X t dá a evolução do número de máquinas quebradas Dadas às características do problema este pode ser modelado como um processo de Markov de tempo contínuo com estados 0 1 e 2 Conseqüentemente podemos utilizar as equações de regime estacionário apresentadas anteriormente para calcular a distribuição de probabilidades do número de máquinas quebradas a longo prazo Para proceder à análise inicialmente precisamos determinar as taxas de transição que comporão a matriz de transição Determine a as taxas de transição do processo b o diagrama de transição c a matriz de transição P e d o percentual do tempo que ambas as máquinas estarão quebradas A solução é como segue O estado número de máquinas quebradas aumenta de 1 quando uma falha ocorre e decresce de 1 quando um reparo ocorre Considerando que as máquinas não se estragam ao mesmo tempo e que ambas não são consertadas simultaneamente as taxas q02 e q20 são iguais a zero Se o tempo médio de reparo é 50 dia a taxa de reparo de qualquer uma das máquinas é 2 Então q21 2 e 419 2reparos por dia O tempo esperado até que uma maquina que esta em operacdo se estrague de dia entéo gjy 1 Se ambas as mdquinas estiverem operacionais falhas ocorrem a uma taxa de 1 1 2 por dia Isto significa que go 2 O diagrama de transiao do processo descrito é ilustrado na Figura 511 qo1 2 q21 Figura 511 Diagrama de transigao do sistema de duas maquinas Para obter a matriz de transic4o utilizamos o primeiro procedimento descrito na seco 5411 0 1 2 Oj1 2 O P12 2 1 20 2 i Para calcular as probabilidades estacionarias v j para J 01 2 utilizamos M as relagdes v vP e v 1 que é resolvida tal com se fez no Exemplo 56 j0 vo 04 y 04 v 02 Assim a longo prazo ambas as maquinas estarao quebradas por 20 do tempo e uma maquina estara quebrada em 40 do tempo Estudaremos a seguir um exemplo de aplicacao a confiabilidade 193 194 Exemplo 514 É usual em subestações de energia elétrica utilizar dois transformadores idênticos em paralelo de modo que a potência de cada um dos equipamentos é suficiente para atender a instalação A motivação para isto é aumentar a confiabilidade da subestação relativamente à alternativa de usar um único transformador A Figura 512 ilustra o esquema elétrico simplificado para a análise de falha A seta da figura indica o sentido do fluxo da energia Figura 512 Dois transformadores idênticos em paralelo No esquema com dois transformadores em paralelo a indisponibilidade do sistema ocorrerá apenas se ambas as máquinas estiverem fora de operação porque implicará na interrupção do fluxo de energia Os estados possíveis para os transformadores são ambos em operação 0 em falha um em operação e o outro em falha 1 em falha e os dois fora de operação 2 em falha A taxa de falhas é λ e a taxa de reparo é µ ambas associadas à distribuições exponenciais independentes Suponhamos também que se os dois transformadores estiverem em operação não é possível que os dois falhem simultaneamente e nem é possível consertar dois transformadores ao mesmo tempo O diagrama de transição do processo está representado na Figura 513 Figura 513 Diagrama de transição da cadeia de Markov de dois transformadores em paralelo λ 2 1 0 µ 2 λ 2µ ambos em operação um em operação e o outro em falha ambos em falha Supondo que as condig6es de regime estacionario sejam verificadas isto é tf oo determine as seguintes informac6es a a probabilidade de falha do sistema b a disponibilidade do sistema e c o tempo médio para o sistema falhar dado que se encontra em plena operacao Para solucionar 0 exemplo montamos a matriz de transiao a partir do diagrama da Figura 513 0 1 2 0 12 2A 0 P1 uw 1Ap A 2 O 2u 12u Para obter as respostas as duas primeiras questdes precisamos calcular as M probabilidades estacionarias dos estados Para tal utilizamos as relagoes vvP e v 1 j0 que so solucionadas pelo método analitico 2 H 0 A 2A y A pM V2 aa 2 Fe A my Dado que cada unidade é capaz de suprir a instalagéo a probabilidade de falha do sistema corresponde a um ou dois equipamentos em falha que vj v7 2A ytVvg oa A pM A disponibilidade do sistema no caso do sistema em paralelo é a probabilidade de que ao menos uma unidade esteja em operacAo ou seja disponivel 195 2 2 Vo ty w 2M A pf A resposta ao item b esta intimamente relacionada a natureza do problema sob andlise neste caso depende essencialmente da forma como sao ligados os transformadores Por exemplo se os transformadores estivessem em série a disponibilidade implicaria necessariamente na operacao de ambos Para responder a Ultima questaéo formulada langamos mao de um artificio supomos que 0 estado 2 é absorvente e calculamos a partir da matriz de transiao modificada o tempo para alcangar a absorcao partindo do estado 0 ambos em operagao No contexto do estudo da confiabilidade 0 tempo para alcangar a falha total do sistema é designado por MTTF que é a sigla para Mean Time to Failure cuja tradugdo é tempo médio para a falha BILLINTON 1970 Supondo o estado 2 um estado absorvente a matriz de transicgéo P 6 como segue 0 1 2 0 1224 2A 0 P1 uw 1Amp Aa 2 O 0 1 A exemplo dos estudos feitos anteriormente na sedo 535 identificamos na matriz P a submatriz Q 0 1 O 0 12a 2A IL uw 1Am Calculamos a matriz fundamental J Qo 1 Atu 22a 1Q 24 Mh 2A 196 197 Partindo do estado 0 que é o sistema em plena operação o MTTF isto é o tempo antes do estado absorvente é MTTF 2 2 1 2 λ µ λ λ MTTF 2 2 3 λ λ µ Para concluir o estudo deste tema fascinante sugerimos a solução dos exercícios propostos 55 Exercícios propostos 1 BRONSON 1985 Um recenseamento econômico revelou que numa dada população as famílias são divididas em dois grupos 1 as economicamente estáveis e 2 aquelas em depressão Depois de um período de 10 anos a probabilidade de que uma família estável assim permaneça é de 092 enquanto a probabilidade dela entrar em depressão é de 008 A probabilidade de que uma família em depressão se torne estável é 003 enquanto a probabilidade de que ela assim permaneça é de 097 Calcule a probabilidade de uma família estável estar em depressão a longo prazo Obtenha também o tempo médio que uma família estável permanece nesta condição 2 Um representante comercial visita seus clientes cada mês A experiência passada mostra que se um cliente fez um pedido no último mês a probabilidade de um novo pedido no mês corrente é 03 e se não foi efetuado pedido algum no mês passado a probabilidade é 06 Assim em cada um dos meses subseqüentes ao primeiro cada cliente deve encontrarse em um dos dois estados estado 0 nenhum pedido no mês passado e estado 1 um pedido no mês passado Dessa forma com base nas probabilidades de transição podemos predizer o comportamento no futuro Para um cliente do universo dos que não fizeram pedidos no mês anterior determine a probabilidade que o tempo transcorrido para efetuar um novo pedido seja de 3 meses 3 SHAMBLIN 1989 Suponhamos que três fabricantes de automóvel colheram os seguintes dados sobre as compras de clientes A Tabela 56 representa a probabilidade de um cliente que agora possui Ford estado s 2 0 comprar um Ford Chevrolet estado sz ou Plymouth estado s3 na proxima vez isto é no préximo passo n1 Informacdo semelhante é fornecida para todos os proprietarios dos outros modelos Tabela 56 Probabilidade de compras em fungao do estado atual n0 n1 Modele o problema como uma cadeia de Markov de tempo discreto com passo igual a um ano Determine a a matriz de probabilidades de transiao para este processo b a classificagdo desta cadeia c as probabilidades estacionarias d o tempo médio que o comprador de um Ford permanece com esta marca e e o nimero esperado de anos que o cliente que atualmente possui um Ford compre um Plymouth Como sugestaéo para resolver a quest4o e faca artificialmente 0 estado s3um estado absorvente e calcule 0 tempo esperado para a absorcao 4 Dadas as matrizes de transigdo para um passo classifique cada uma das cadeias may SMS a ra 03 6 b P oo ot 03 04 03 oo Fe BS Kk bs 5 Em 1993 a utilizagéo do solo em uma cidade de 130 quilémetros quadrados de area ocupada apresentava os seguintes ndices 198 uso residencial 30 estado sj uso comercial 20 estado sy uso industrial 50 estado s3 a Calcule os percentuais de ocupacgaéo do solo nesta cidade em 2003 assumindo que as probabilidades de transigao para intervalos de 5 anos sao dados pela seguinte matriz Ss 82 83 s 908 OL O P sy 01 07 02 s3 O O1 09 b Encontre as probabilidades limites dos estados de utilizacdo do solo nesta cidade 6 Em relagao exercicio anterior sobre ocupacado do solo da cidade suponha que se uma area é destinada a industria esta fica imprestavel para uso residencial ou comercial Imaginando o estado s3 como estado absorvente determine 0 nimero esperado de passos em anos até que uma regiao que é residencial se torne industrial 7 As sociedades ocidentais sao estratificadas em fungao do poder aquisitivo de bens das familias Supondo que as classes sociais sejam a classe A ricos b classe B classe média c classe C pobres e d classes D E etc miseraveis No Brasil o Instituto Brasileiro de Geografia e Estatistica IBGE realiza periodicamente um censo econémico que com base em amostragem traga um perfil razoavelmente preciso da populagao com o foco na sua condigdo sdécioecondmica A cada censo sao observadas as mudangas das familias entre as classes Modele 0 processo como uma cadeia de Markov de tempo discreto onde os estados sao as classes indicadas anteriormente e o estado do item d é um estado absorvente Para analise considere os dados que constam da matriz de probabilidades de transicgao Se o passo o intervalo de tempo igual a 10 anos calcule o nimero de passos antes da absorao se 0 processo partiu do estado rico Ao usar a matriz considere as seguintes associagées pobre 0 miseravel 1 médio 2 rico 3 199 0 1 2 3 004 04 O01 O1 10 1 O OO P 203 0 05 01 301 0 06 03 8 Elabore um programa de computador para calcular fjk sendo i1e j 45 de modo que a partir dos dados do Exemplo 59 sejam reproduzidos os resultados que constam da Tabela 54 9 BILLINTON 1970 Dois equipamentos idénticos sao instalados e operam em série Suponha trés estados para modelar 0 processo como uma cadeia de Markov de tempo continuo com taxas A e mW respectivamente para falha e reparo Mostre que a we disponibilidade do sistema vale 7z que a MTTF é igual a NM yz MITTF 0 tempo A mM médio para a falha 10 Um sistema com um tnico servidor aberto ao ptblico tem seus tempos de atendimentos distribuidos exponencialmente com taxa igual a 2 Os tempos entre chegadas dos usuarios que demandam pelo servicgo desses guichés também exibem a distribuicao exponencial com taxas iguais a 2 Os usuarios que acessam o sistema surgem segundo o modelo de Poisson O estado é caracterizado pelo nimero de usuarios presentes 0 1 2 oo Nessas condic6es 0 sistema se enquadra como um processo de nascimento e morte podendo ser descrito como uma cadeia de Markov infinita de tempo continuo Desenhe o diagrama de transicgéo dessa cadeia e escreva as equagoes de Kolmogorov para 0 regime estaciondrio Supondo que i com base em séries convergentes prove que a expressdo para a probabilidade estaciondria vo em funcio do quociente p 7 é ungao do qu p vo 1 Pp onde vg a probabilidade de encontrar 0 sistema vazio ou seja livre de usuarios Neste exercicio vocé precisara usar o resultado da série S Vx axl tater get x se Oxl i0 Ix 200