Processos_Estocasticos_2010-2_aula_2_

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Processos Estocásticos
Álgebra Linear II
Professor: Mário Jorge
Introdução e Definição
 → Um processo estocástico é uma família de variáveis que evoluem no tempo ou no espaço de acordo com leis probabilísticas.
 O processo é uma família Z = {Z(t), t є T} onde Z(t) é uma variável aleatória.
 → Os Processos Estocásticos constituem um ramo da Teoria da Probabilidade.
 Através destes processos, podemos definir modelos matemáticos para estudar o comportamento de diversos fenômenos. O leque das aplicações é muito vasto e vários modelos tem sido desenvolvidos nas áreas de economia, saúde, administração, engenharia, física, biologia, etc.
 → De uma forma geral, qualquer tipo de evolução temporal que seja analisável através da teoria das probabilidades pode ser chamada de processo estocástico.
	 → Os processos estocásticos podem classificados dentro das seguintes categorias: Contínuo,discreto, estacionário, não estacionário
	Processos de Tempo Contínuo: A variável aleatória pode assumir valores contínuos dentro de um determinado intervalo.
 Processos de Tempo Discreto: A variável aleatória pode assumir apenas alguns valores discretos. 
	Processos Estacionários: A média e variância da variável aleatória podem atingir uma estabilidade estatística
	Processos não-estacionários: O valor esperado e a variância não atingem um equilíbrio estatístico. 
Cadeias de Markov
Cadeias de Markov
 Definição: Uma cadeia de Markov é um caso particular de processo estocástico onde a evolução do processo é muito influenciada pelos estados mais recentes e influencia somente os estados posteriores mais próximos. A propriedade markoviana considera que os estados mais anteriores são irrelevantes para a predição dos estados seguintes. 
 Este processo pode assumir estados X[1],X[2],...X[n], de tal modo que a probabilidade de transição de um estado X[i] para um estado X[j] seja P[ij] (um número que só depende de X[i] e X[j]).
Tal processo pode assumir os estados X1, X2, X3, ..., Xn, de modo que a probabilidade de transição de um estado i para um estado j seja Pij
A matriz de transição (estocástica) será:
P11
P12
P13
.......
P1n
P21
P22
P23
.......
P2n
P31
P32
P33
.......
P3n
.......
.......
.......
.......
.......
Pn1
Pn2
Pn3
.......
Pnn
P =
Note que  Pj = 1.
 → Numa cidade industrial, os dados sobre a qualidade do ar são classificados como satisfatório (S) e insatisfatório (I). Assuma que, se num dia é registrado S, a probabilidade de se ter S no dia seguinte é de 2/5 e que, uma vez registrado I, tem-se 1/5 de probabilidade de ocorrer S no dia seguinte.
>
<
>
<
S
I
3/5
2/5
4/5
1/5
Método I
 → Multiplicação sucessiva das matrizes por elas mesmas dão as probabilidades em tempos futuros.
 → Soma de cada linha deve ser igual a 1.
 → Todos ou elementos devem ser maiores ou iguais a 0 (zero).
Exemplo:
	Existem três marcas de automóveis disponíveis no mercado: o Jacaré, o Piranha e o Urubu. O termo aij da matriz A a seguir é a probabilidade de que um dono de carro da linha i mude para o carro da coluna j, quando comprar um carro novo 
Como calcular as probabilidades de um consumidor mudar de uma marca para outra após duas compras?
A matriz que fornecerá a resposta será a matriz decorrente de A A, isto é, A².
Numa terceira compra o procedimento seria
A² A e assim sucessivamente.
PREVISÃO DO TEMPO
Em determinada região,
 observa-se que se chover muito em um ano, a probabilidade que chova muito no ano seguinte é de 1/4, e que a probabilidade de seca é de 3/4.
Ainda, se houver seca em um ano, no ano seguinte a probabilidade de haver seca ou muita chuva será a mesma, e igual a 1/2. Suponhamos que estas probabilidades não mudem ao passar dos anos. Os estados possíveis são Chuva (C) e Seca (S).
Se no primeiro ano houve seca, qual a probabilidade que chova muito no terceiro ano?
Árvore de Probabilidades 
Logo, se houve seca no primeiro ano, a probabilidade de chover muito no terceiro ano é de:
½  ¼ + ½  ½ = ⅜
O método da Árvore de Probabilidades é o mais simples, porém, à medida que o número de anos aumenta, as contas se tornam cada vez mais complexas. Por isso, precisamos usar outros métodos para realizarmos previsões a longo prazo.
Multiplicação da Matriz de Transição
A matriz T de transição deste problema tem a seguinte forma:
¼
¾
½
½
T = 
Para descobrirmos a probabilidade de chover no n-ésimo ano, basta multiplicarmos a matriz de transição n vezes:
chuva 
seca
seca
chuva
¼
¾
½
½
T2 =
¼
¾
½
½
=
(¼  ¼ + ¾  ½)
(½  ¼ + ½  ½)
(¼  ¾ + ¾  ½)
(½  ¾ + ½  ½)
7/16
9/16
3/8
5/8
T2 =
chuva 
seca
chuva
seca
Como podemos notar, por este método encontramos o mesmo resultado que através do método anterior: se houve seca no primeiro ano, a probabilidade de que haja muita chuva no terceiro ano é:
⅜
Método II
Matriz das probabilidades de transição (matriz estocástica)
→ A matriz T do sistema é uma matriz cuja soma dos elementos de cada coluna é 1. Uma matriz com essa duas propriedade é também uma matriz estocástica.
→A matriz das probabilidades é aquela cujo i-ésima linha dá a probabilidade de ocorrência do estado a[i] após n transações.
 → Então após n passos. 
Onde é uma matriz estocástica com n linhas e n colunas.
 
PESQUISA DE MERCADO
Uma equipe de pesquisa de mercado está fazendo um levantamento sobre a preferência dos atletas em relação aos uniformes. A mostra consiste de 200 atletas, cada um experimentando diversas marcas durante os meses. A seguinte estatística sobre a preferência é observada.
Existem duas opções: Adidas ou Nike. 
A probabilidade de um consumidor da Adidas mudar para Nike é 0,2 e a probabilidade de um consumidor da Nike mudar para Adidas é 0,3 a cada mês.
Suponha que 120 estejam usando Adidas e 80 Nike.
Quantos estarão usando cada uma das marcas dois meses depois? 
0,7
0,2
0,3
0,8
120
80
C = 
Nike
Adidas
P = 
Nike
Adidas
Nike
Adidas
0,7
0,2
0,3
0,8
120
80
=
100
100
2x1
2x1
2x2
100
100
0,7
0,2
0,3
0,8
=
90
110
2x1
Logo, dois meses depois, 90 atletas usarão Adidas e 110 usarão Nike.
Primeiro mês: 
Segundo mês: 
Exemplo:
	Duas substâncias distintas estão em contato e trocam íons de sódio entre si. Sabe-se (por dedução teórica ou experimentação) que um íon de sódio do meio (1) tem probabilidade de 0,7 de passar ao meio (2), enquanto um íon de sódio que esteja no meio (2) tem 0,1 de chance de passar ao meio (1). Colocando-se 2 mols de sódio no meio (1) quais serão as concentrações de sódio em cada um dos meios após um longo período de tempo?
p1 = 1/8
p2 = 7/8
Logo, como foram colocados a príncipio 2 mols, as concentrações finais em cada meio serão:
C(p1) = 2 x 1/8 = 0,25 mol
C(p2) = 2 x 7/8 = 1,75 mol
 Um espaço de estados é representável por uma de matriz de transição, com o (i, j)-ésimo elemento igual a:
Previsões a Longo Prazo
 Para um espaço de estados discretos, as integrações na probabilidade de transição de k passos são somatórios, e podem ser calculados como a k-ésima potência da matriz de transição. Isto é, se P é a matriz de transição para um passo, então Pk é a matriz de transição para a transição de k passos.
 
A distribuição estacionária é o vetor que satisfaz à equação
Previsões a Longo Prazo
onde πT é a matriz transposta de π. Em outras palavras, a distribuição estacionária π é o autovetor esquerdo da matriz de transição, associado com o autovalor 1.
 
 Como conseqüência, nem a existência nem a unicidade de distribuição estacionária é garantida para uma matriz de transição qualquer P. Contudo, se P é irredutível e aperiódica, então existe uma distribuição estacionária π. Além disso, Pk converge para uma matriz na qual cada linha é a (transposta da) distribuição estacionária πT, que é dada por:
onde é o vetor coluna com todas
as entradas iguais a 1. Isto é estabelecido pelo Teorema de Perron-Frobenius.Isto significa que se nós simularmos ou observamos uma caminhada aleatória com matriz de transição P, então a probabilidade de longo prazo de que o indivíduo que faz a caminhada esteja em um certo estado é independente do estado em que a caminhada começou, e é definida pela distribuição estacionária. 
Previsões a Longo Prazo
 A caminhada aleatória "ignora" o passado. Em suma, cadeia de Markov é o passo seguinte depois dos processos sem memória (isto é, uma seqüência de variáveis aleatórias independentes distribuídas uniformemente).
 Uma matriz de transição que é positiva (isto é, todo o elemento da matriz é positivo) é irredutível e aperiódica. 
 Uma matriz é uma matriz estocástica se e somente se é uma matriz de probabilidades de transição de uma cadeia de Markov.
Previsões a Longo Prazo
Exemplos e Exercícios 
 → Exemplo 1: Seja X a variável aleatória que indica se chove ou não num determinado dia num dado local. A seqüência que indica o estado do tempo em dias consecutivos forma um processo estocástico. É um processo estocástico não estacionário, pois as probabilidades variam ao longo do tempo. X1, X2,... , Xn
 
 → Exemplo 2: Uma seqüência de lançamentos de um dado forma um processo estocástico estacionário. As probabilidades são constantes ao longo do tempo.
 
 → Exemplo 3: No jogo da Glória, a seqüência de valores aleatórios (X1, X2,... Xn ) representa a posição no jogo ao longo do tempo. Esta seqüência é um processo de Markov uma vez que a probabilidade do jogador se encontrar numa dada casa depende apenas da casa onde estava na jogada anterior.
 → Exemplo 4: Imagine um bêbado, que após muito caminhar consegue enxergar sua casa. Supondo que o caminho esteja desimpedido, o instinto o levará a tentar caminhar em linha reta; A questão é que a bebida não permite. Se traçarmos um sistema cartesiano de modo que o bêbado esteja na origem e a casa em algum ponto do eixo das ordenadas, o bêbado é uma partícula caminhando para cima, pois a linha reta é o caminho mais curto; porém, o vetor deslocamento não coincide com o vetor (0,1), pois o bêbado cambaleia para a direita ou esquerda aleatoriamente, fazendo com que a posição no bêbado no instante t seja (xt,t), supondo velocidade constante no eixo das ordenadas, onde xt é um valor aleatório. 
		 A seqüência de valores xt e suas variáveis aleatórias associadas Xt recebem o nome de cadeia, um caso especial de processo estocástico. 
 
 
 
 onde P(A | B) é a probabilidade do evento A ocorrer dado que o evento B ocorreu e são as posições anteriores do bêbado. Esta relação de probabilidades quer dizer que a única informação que pode nos ajudar a prever onde o bêbado estará no próximo instante de tempo é a posição do bêbado no momento atual, sendo que a trajetória anterior, velocidade resultante, etc. não nos fornecem nenhuma informação extra.
 → Exemplo 5: O passeio aleatório consiste em uma trajetória formada por passos aleatórios de mesmo tamanho a cada qual em uma direção aleatória.
Classificação de Estados
Acessibilidade e Comunicabilidade:
 O estado j é dito acessível a partir do estado i, ou j pode ser alcançado a partir de um estado i (ou, i atinge j), denota-se i → j, se existe um inteiro a → 1 tal que Pª (i, j) > 0.
 Isto significa que é possível para o processo eventualmente entrar no estado j quando ele começa no estado i.
 Dois estados i e j se comunicam se i acessa j e se j acessa i, ou seja, i → j e j → i.
 Propriedade reflexiva: Qualquer estado se comunica com ele mesmo, ou seja, P °(i, i ) = 1.
 Propriedade transitiva: se i → j e j → k então i → k.
Classe de Estados 
 Denomina-se classe do estado i ao conjunto de todos os estados que se comunicam com i, também denominado conjunto fechado. Desta forma, os estados de uma cadeia de Markov podem ser subdivididos em uma ou mais classes disjuntas (que não têm elementos em comum), tais que aqueles estados que se comunicam entre si se encontram na mesma classe, e um conjunto de estados transitórios.
 Se em uma cadeia de Markov existir apenas uma classe, ou seja, se todos os estados se comunicam, esta cadeia é dita irredutível. Se, ao contrário, a cadeia possuir mais de uma classe ou possuir estados transitórios, ela é denominada redutível.
Transitoriedade e 
Recorrência 
 Um estado é denominado recorrente se, partindo deste estado, sua probabilidade de retorno é 1, ou seja, se i é recorrente i → j e j → i.
Propriedades:
 1. Se i é recorrente e i → j então j é recorrente.
 
 2. Um estado i ϵ E é dito transitório se existir um estado j ϵ E (j ≠ i) que seja acessível do estado i, mas o estado i não é acessível de j, ou seja, i → j mas j /→ i para algum j.
Absorvência 
 
Propriedade: 
 
 1. Todo estado absorvente é recorrente.
Probabilidade Limite 
 Para classificar os estados de uma Cadeia de Markov com um número finito de estados:
 1. Identificam-se os conjuntos fechados irredutíveis – todos os estados pertencentes a um conjunto fechado irredutível finito são recorrentes;
 2.Os estados restantes, se houver, são transitórios;
 3. determina-se a periodicidade.
Tempo de Primeira Passagem 
 Em muitas situações deseja-se saber o número de transições realizadas pelo processo para ir do estado i ao estado j pela primeira vez, período denominado tempo de primeira passagem.
 Se j = i, o tempo de primeira passagem é o número esperado de transições até que o processo retorne ao estado inicial i, denominado tempo esperado de retorno. 
37
Aplicações
 → Os processos estocásticos possuem aplicações na Física, Economia, Ciências da Computação e em outros inúmeros campos. Como exemplos têm o movimento Browniano das moléculas em líquidos e gases, estimação do tamanho da Web, oscilação dos preços das ações, sistemas de filas com senhas como em bancos e serviços automatizados por computador, otimizando o sistema computacional para a chegada aleatória dos clientes variando com o tempo e o atendimento dos caixas; operação e planejamento da expansão do sistema elétrico nacional, relacionando vazões afluentes e usina hidrelétricas com reservatórios; Sistemas de Saúde, marcando consultas individuais com hora marcada, distribuindo os tempos de espera e os tempos ociosos, chegadas aleatórias com taxas variáveis e alocação de menos médicos em horários de descanso. Em inteligência artificial, programas estocásticos trabalham através do uso de métodos probabilísticos para resolver problemas, como em redes neurais estocásticas e nos algoritmos genéticos.