ESTUDO DIRIGIDO 2017 01

Prévia do material em texto

UNIVERSIDADE ESTÁCIO DE SÁ
MARCELO DE MIRANDA LEITE
Processos Markovianos - Estudo Dirigido
MARCELO DE MIRANDA LEITE
Processos Markovianos - Estudo Dirigido
Trabalho de Estudo Dirigido da Disciplina: Simulação da Produção e Teoria das Filas - Curso de Engenharia de Produção da Universidade Estácio de Sá, como parte dos requisitos à obtenção do título de Bacharel em Engenharia de Produção. 
Prof. Jonas Ricardo
	 Leite, Marcelo de Miranda 
Trabalho de Estudo Dirigido da Disciplina: Simulação da Produção e Teoria das Filas - Curso de Engenharia de Produção da Universidade Estácio de Sá, como parte dos requisitos à obtenção do título de Bacharel em Engenharia de Produção. 
Prof. Jonas Ricardo
RESUMO
O presente estudo foi feito para contemplar processos estocásticos a tempo discreto concentrado-se principalmente em Cadeias de Markov e simulação. Outro tópico apresentado que também é de grande relevância no estudo probabilístico é o passeio aleatório. Foram utilizados métodos que visam calcular transições do processo markoviano por meio de potências da matriz estocástica. Em virtude da complexidade nas manipulações algébricas, fez-se uso do Máxima, manipulador algébrico precursor do Maple. 
	
INTRODUÇÃO 
PROCESSO DE DECISÃO DE MARKOV
A cadeia de markov é um processo estocástico caracterizado por seu estado futuro depender apenas do seu estado atual, sendo que os estados passados não influenciam no estado futuro. O nome cadeia de markov foi dado em homenagem ao matemático russo Andrey Markov.
A própria natureza dos cálculos em probabilidade nos conduz ao questionamento se existe ou não dependência na ocorrência de fenômenos simultâneos ou sucessivos. Será que ao retirarmos sucessivamente duas bolas de uma urna que contem inicialmente 7 bolas azuis e 3 brancas, essas retiradas serão dependentes? Caso sejam, de que tipo seria essa dependência? E se as retiradas fossem simultâneas? Por mais simples que pareçam, essas questões fazem parte do alicerce da teoria de probabilidades e foi a busca por respostas a perguntas similares a estas que levaram grandes matemáticos como Thomas Bayes, Kolmogorov, Fisher, Pearson e muitos outros, a contribuírem no desvendar desse fascinante universo das incertezas. Em particular, pode-se citar Andrei Markov, precursor no estudo da propriedade da perda de memória, propriedade que levou ao desenvolvimento da teoria sobre Cadeias de Markov, ferramenta de grande aplicabilidade nos mais diversos ramos da ciência. Um dos exemplos mais clássicos de aplicabilidade das Cadeias de Markov talvez seja em teoria dos jogos, onde pode-se provar com indiscutível simplicidade o problema da ruína do jogador. Outro ramo bastante fecundo em cadeias de Markov é a teoria de filas, a qual busca modelar matematicamente o comportamento de uma fila a fim de satisfazer da melhor forma possível o cliente, usuário da fila, e de modo que seja economicamente viável ao prestador de serviços. Na mesma linha de importância, podemos citar também a aplicabilidade dessa teoria em processos migratórios, epidemiológicos, difusão de informação e muitos outros.
 
Figura 1: Grandes Matemáticos
Definição:
Um processo de Markov  é um processo estocástico com a propriedade de que, dado o valor de  os valores de , para  não são influenciados pelos valores de  para . Ou seja, a probabilidade de qualquer comportamento futuro do processo, quando o seu estado atual é conhecida exatamente, não é alterada pela conhecimento adicional sobre seu comportamento passado.
Se o conjunto de índice for discreto então a propriedade da cadeia de markov é dada da seguinte forma
.
Vamos trabalhar apenas com o conjunto de índice discreto, assim notamos que a cadeia e markov é um processo de estados
Definimos a probabilidade de transição de n-passos como:
	
Exemplo:
Seja  um processo estocástico com , no qual  é o conjuntos dos naturais com o zero. Definamos o seguinte que:
	
	
	
	
	
	
 
Esse processo é chamado de processo de nascimento e morte, pois no fundo estamos dizendo que existem apenas 3 possibilidades em cada instantes
- Nascer - acrescentar um novo elemento com probabilidade de que isso ocorra sendo p.
- Morrer - diminuir um novo elemento com probabilidade de que isso ocorra sendo q.
- Nada - não acrescentar, nem diminuir com probabilidade .
Notemos que no processo de nascimento e morte, a probabilidade de acrescentar, diminuir ou nada acontecer não depende do tamanho atual da população, ou seja, não depende de i.
Teorema CHAPMAN - KOLMOGOROV
Dado uma cadeia de Markov  com o espaço de estados E, ou seja, E é o conjunto dos possíveis valores de  e a probabilidade de transição . Para  temos que
	
DEMONSTRAÇÃO 
Primeiramente lembremos que , podemos encontrar mais detalhes sobre a probabilidade condicional na apostila de probabilidade.
	Assim, temos que 
	
 
Observe que , se , ou seja eles são dois a dois disjuntos assim:
	
	
	
	
	
	
 E portanto o resultado segue.
Uma notação muito usada e útil é a notação matricial que nos fornece toda informação sobre os estados de transição.
	 
	
	
	
Suponha que uma concessionária tem a seguinte estratégia para um determinado veículo modelo de veículo de seu estoque. Todo sexta-feira a noite quando a concessionária fecha ela contabiliza o número de veículos deste modelo e faz um pedido para o fornecedor que lhe entrega na segunda-feira pela manhã antes da concessionária abrir novamente.
Se há veículos no estoque, a concessionária não faz nenhum pedido
Se não há veículos no estoque, a concessionária pede 3 veículos ao fornecedor
Caso durante a semana este modelo de veículo termine no estoque, ele não será vendido até a semana seguinte.
Assim definamos nosso processo  como sendo o número de veículos na sexta feira da semana n, e  como sendo o número inicial de veículos.
Definimos  a demanda da semana i. Suponha que  e sejam independentes, ou seja,  tem distribuição poisson com parâmetro . Para mais detalhes sobre a distribuição poisson consulte apostila de probabilidade.
Desta forma nossa variável
	
	
 
A primeira coisa que devemos fazer é verificar se esse processo é uma cadeia de markov se a resposta for afirmativa então devemos encontrar sua matriz de transição.
Notemos que nosso processo tem apenas 4 fases possíveis, ou seja, nosso espaço de fase é dado por:
	
	
	
	
 
Se , então
	
	
	
	
	
	
 Se 
	
	
	
	
	
	
.
 
Agora estamos em posição de calcular a matriz de transição.
	
	
 
Agora vamos supor que no instante inicial a concessionária tinha 3 automóveis do modelo estudado. Então
	
	
 
O interessante da cadeia de markov é que dado um estado inicial, podemos calcular a distribuição assintótica do sistema.
DEFINIÇÃO
Uma cadeia de markov é dita ser homogênea se a probabilidade de transição for estacionária, ou seja, se a probabilidade de transição não depender da etapa n.
Seja  um processo markoviano, então dado um estado inicial  temos que
	
	
 
Se o a cadeia de markov for homogênea então .
Como  é o estado inicial então temos que . Assim
	
	
 
Agora usando a equação de Chapman-Kolmogorov, temos que
	
	
.
 
Assim por indução temos que
	
	
 
E portanto o resultado segue.
3.1.1 Exemplo
Seja uma cadeia de markov  homogênea com o espaço de transição  e a seguinte matriz de transição:
	
	
 
Calcule  e .
Basta observarmos que:
	
	
	
	
	
	
	
	
 
Da mesma forma temos que
	
3.1.2 Exemplo 
Seja uma cadeia de markov  homogênea com o espaço de transiçãoe a seguinte matriz de transição:
	
	
 
E com a seguinte condição inicial 
Calcule 
Observemos que
 
REFERÊNCIAS 
Anton, Howard, Álgebra Linear Aplicada, trad Claus Ivo Doering. 8. ed. - Porto Alegre: Bookman, 2001. 
Ferrari, P.A. e Galves, J.A., Acoplamento em Processos Estocásticos, Notas para um minicurso apresentado na XIII Escuela Venezolana de Matematicas, 2000. 
Hoel, P. G., Port, S. C. e Stone, C. J. Introduction to stochastic processes, Waveland Press,1986. 
Júnior, V.V., Concentração de Massa da Medida Invariante de uma Classe de Caderas de Markov. Dissertação de Mestrado, 2006. 
Mello, M. P. ; dos Santos, J. P. O. e Murari, I. T.C. Introdução à análise combinatória , Editora Ciência Moderna, 1a Edição - 2008. 
Norris, J.R., Markov Chains, Cambridge University Press,1998. 
RIPLEY, B.D., Stochastic Simulation, Wiley-Interscience,1a edição, 2006. 
Ross, S. M., A first course in probability, Prentice Hall; 8a edição , 2009. 
Ross, S. M., Simulation, Academic Press, 4a edição, 2006. 
S.H. Ross, Stochastic Processes, Wiley Series in Probability and Mathematical Statistics, 1996.