Processos Estocsticos

RRuuii AAllvveess CCaattaarriinnaa DDeellggaaddoo

SSeetteemmbbrroo ddee 11999977

APRESENTAO

Este texto concretiza uma ideia que j tem alguns anos, mas que vinha sendo

adiada devido a afazeres de diversa natureza.

Dois factos ocorridos no ano lectivo de 1996/97 foram determinantes na concre-

tizao deste projecto: (i) a adopo, nas disciplinas de Investigao Operacional de

ambas as licenciaturas, de um livro (Investigao Operacional, de L. Valadares Tavares

et al., McGraw-Hill, 1996) que, embora cobrindo a matria de Programao Linear e de

Filas de Espera, omisso no que toca Programao Linear Inteira e s Cadeias de

Markov; (ii) a contratao da licenciada Catarina Delgado como assistente estagiria

das referidas disciplinas.

O facto de os alunos disporem de elementos de estudos (no livro adoptado) sobre

alguns pontos do programa tornou mais premente a concluso destes textos com o

objectivo de uma integral cobertura do programa. A disponibilidade da licenciada

Catarina Delgado foi na realidade crucial (sem o seu trabalho e o seu entusiasmo creio

que os textos no teriam ficado prontos), e o seu contributo justifica plenamente a co-

autoria que lhe devida, pois a ela se devem a primeira verso dos textos, todos os

exemplos profusamente ilustrados, e a incluso de uma maior variedade de problemas

tpicos de Programao Inteira.

Resta-nos desejar que os alunos, destinatrios ltimos destes trabalhos, deles

possam vir a tirar o desejado proveito. Todas as crticas e sugestes so benvindas,

salvaguardando que todos os erros e imprecises que os textos possam ter so da inteira

responsabilidade dos autores.

Faculdade de Economia do Porto, Setembro de 1997

Prof. Doutor Rui Alves

NDICE

1. INTRODUO ..................................................................................................... 1

1.1. Generalidades ......................................................................................................... 1

1.2. Classificao dos Processos Estocsticos .............................................................. 1

2. CADEIAS DE MARKOV EM TEMPO DISCRETO ........................................... 3

2.1. Definio ................................................................................................................ 3

2.2. Representao ........................................................................................................ 3

2.3. Probabilidades de Transio .................................................................................. 4

2.4. Classificao dos Estados ...................................................................................... 6

2.5. Probabilidades Estacionrias .................................................................................. 7

2.6. Tempos de Transio ............................................................................................. 9

2.7. Cadeias de Markov com Estados Absorventes ...................................................... 9

3. CADEIAS DE MARKOV EM TEMPO CONTNUO ........................................ 12

3.1. Definio .............................................................................................................. 12

3.2. Tempo de Permanncia no Estado ....................................................................... 12

3.3. Representao ...................................................................................................... 13

3.4. Probabilidades Estacionrias ................................................................................ 14

4. PROCESSOS DE NASCIMENTO-MORTE ...................................................... 15

4.1. Generalidades ....................................................................................................... 15

4.2. Equaes de Balano ........................................................................................... 16

5. BIBLIOGRAFIA ................................................................................................. 16

11. INTRODUO

1.1. GENERALIDADES

Qualquer sistema real opera sempre em ambientes onde a incerteza impera, prin-cipalmente quando o sistema envolve, pela sua natureza, aces humanas imprevisveisou avarias de mquinas. Os modelos determinsticos certamente contribuem para acompreenso, a um nvel bsico, do comportamento dinmico de um sistema. No en-tanto, por no poderem lidar com a incerteza, acabam por ser insuficientes nos processosde tomada de deciso. Assim, recorre-se a Processos Estocsticos como uma forma detratar quantitativamente estes fenmenos, aproveitando certas caractersticas deregularidade que eles apresentam para serem descritos por modelos probabilsticos.

Pode definir-se um Processo Estocstico (em ingls, Stochastic Process ouRandom Process) como um conjunto de variveis aleatrias indexadas a uma varivel(geralmente a varivel tempo), sendo representado por {X(t), tT}. Estabelecendo oparalelismo com o caso determinstico, onde uma funo f(t) toma valores bem definidosao longo do tempo, um processo estocstico toma valores aleatrios ao longo do tempo.Aos valores que X(t) pode assumir chamam-se estados e ao seu conjunto X espao deestados.

Como exemplos de processos estocsticos, poderemos considerar:

1) X(t) representa o estado de uma mquina (ligada/desligada) no momento t; 2) X(t) representa o nmero de clientes numa loja no instante t; 3) X(t) representa o nmero de mquinas avariadas no fim do dia t; 4) X(t) representa a cotao de uma aco no fim do dia t; 5) X(t) representa o nvel de stock de um determinado artigo no fim do dia t; 6) X(t) representa a condio de funcionamento dum componente no instante t.

Como se pode constatar pelos exemplos apresentados, h casos em que o tempo considerado de forma discreta ( no fim do dia t) e outros em que tomado de modocontnuo ( no momento t). A varivel tempo , por definio, uma varivel contnua,a qual pode ser discretizada se os fenmenos forem observados a intervalos regulares.Outra constatao que se pode fazer que os estados tanto so valores que a varivelX(t) pode assumir (nmero de clientes, nmero de mquinas, etc) como so estados(mquina avariada, a funcionar, etc).

1.2. CLASSIFICAO DOS PROCESSOS ESTOCSTICOS

Para classificar os processos estocsticos analisam-se (i) o espao de estados, (ii) anatureza do conjunto T e (iii) as caractersticas estatsticas das variveis aleatrias quedefinem o processo.

(i) Espao de estados

Se X for um conjunto de estados finito ou contvel (X = {0, 1, 2, }, ou seja, oconjunto de inteiros no-negativos), X(t) um processo de estados discretos ou, como

2 usualmente referido, uma cadeia. Para qualquer outro caso, o processo designadopor processo de estados contnuos.

Dos exemplos atrs referidos os trs primeiros so cadeias, enquanto que osrestantes podem ser processos de estados contnuos.

(ii) A varivel temporal

Se o conjunto T, que especifica os valores da varivel t, for finito ou contvel, X(t) um processo em tempo discreto e a notao usada {X(t) , t = 0, 1, 2, 3, }. Nestecaso, T normalmente o conjunto dos inteiros no-negativos. Em caso contrrio X(t) designado por processo em tempo contnuo, sendo usada a notao {X(t) , t 0}.

Dos exemplos apresentados, os exemplos 3, 4 e 5 so processos em tempo discretouma vez que representam quantidades observadas dia a dia, enquanto que os restantesso processos estocsticos em tempo contnuo por representarem fenmenos observadosem qualquer momento do tempo.

(iii) Caractersticas estatsticas das variveis aleatrias

Um processo estocstico diz-se estacionrio se o seu comportamento estocsticofor independente do tempo, ou seja, se a funo distribuio da(s) v.a. que o define(m)no variar no tempo.

Um processo estocstico diz-se Markoviano ou de Markov se for estacionrio egozar da propriedade de Markov ou da perda de memria, isto , se o seu comporta-mento futuro apenas for condicionado pelo estado presente, independentemente do seuhistorial ou dos estados visitados no passado. De facto, para um processo de Markov completamente irrelevante qualquer informao sobre estados passados ou sobre otempo de permanncia no estado presente. Num processo estocstico as transies entreestados so causadas pela ocorrncia de acontecimentos ou eventos, pelo que a varivelaleatria directamente restringida pela propriedade de ausncia de memria o tempoentre acontecimentos sucessivos (em ingls interevent time). Dado que, como iremosver mais frente, a nica distribuio contnua que apresenta esta propriedade adistribuio exponencial, num processo de Markov todos os tempos entre aconteci-mentos sucessivos tm de ser exponencialmente distribudos.

Um processo estocstico de Semi-Markov uma generalizao de um processo deMarkov, j que, para aquele, a informao sobre o tempo de permanncia no estadoactual deixa de ser irrelevante; continua, contudo, a ser irrelevante para o comporta-mento futuro qualquer informao sobre os estados visitados no passado. A conse-quncia que os tempos entre acontecimentos sucessivos deixam de estar restringidos distribuio exponencial, podendo seguir qualquer distribuio de probabilidade.

No nossa inteno abordar aqui todos os tipos de processos estocsticos exis-tentes, mas sim analisar, com algum detalhe, uma pequena parcela, bastante relevantepara o estudo de alguns problemas interessantes, desde problemas de jogos a sistemas defilas de espera: as Cadeias de Markov (tanto em tempo discreto como em tempocontnuo) e os Processos de Nascimento-Morte. Apesar da propriedade de Markov nem

3sempre ter aderncia realidade, os processos de Markov so, de longe, os processosestocsticos mais utilizados graas sua facilidade de tratamento.

Este texto encontra-se organizado da seguinte forma: no ponto 2 so estudadasCadeias de Markov em Tempo Discreto e no ponto 3 as Cadeias de Markov em TempoContnuo. No ponto 4 analisado um caso especial de Processos Estocsticos, os Pro-cessos de Nascimento-Morte. Finalmente, no ponto 5 listada a bibliografia consultadapara a elaborao do texto e considerada mais relevante nesta matria.

2. CADEIAS DE MARKOV EM TEMPO DISCRETO

2.1. DEFINIO

Uma Cadeia de Markov em Tempo Discreto um processo estocstico em que avarivel t representa intervalos de tempo, {X(t), t = 0, 1, 2, 3, }, e que goza da pro-priedade de Markov, ou seja, a probabilidade de X(t) estar no estado j no prximoperodo depende apenas do estado presente e no dos estados visitados em perodospassados:

Pij = P{X(t+1) = j | X(t) = i, X(t-1) = kt-1, , X(1) = k1, X(0) = k0} = P{X(t+1) = j | X(t) = i} , " t = 0, 1, 2, "i, j, k0, k1, ,kt-1 X

No nosso estudo apenas vamos considerar Cadeias de Markov com as seguintes carac-tersticas:

1) O espao de estados X finito ou contvel (estados discretos).2) As probabilidades de transio entre estados so constantes no tempo

(cadeia de Markov estacionria), ou seja,

Pij = P{X(t+1) = j | X(t) = i} = P{X(1) = j | X(0) = i} , "t =0, 1, 2, "i, jX

2.2. REPRESENTAO

Uma Cadeia de Markov em tempo discreto fica completamente definida se co-nhecermos os estados X = {0, 1, 2, , s} e as probabilidades de transio entre os esta-dos em um perodo. Existem duas formas de representao: graficamente, atravs dodiagrama de transies, ou atravs da matriz quadrada P que contem as probabilidadesde transio em um perodo.

Num diagrama de transies cada estado representado por um vrtice, e cadaarco orientado ligando dois vrtices representa uma transio possvel entre dois estadosem um perodo, a qual tem uma certa probabilidade de ocorrncia (o coeficienteassociado ao arco).

Na matriz P, cada linha i representa o estado actual e cada coluna j representa oestado futuro (a ordem dos estados actuais deve ser igual dos estados futuros, respec-

4tivamente, nas linhas e nas colunas de P). Deste modo, o elemento pij da matriz repre-senta a probabilidade de ocorrncia da transio do estado i para o estado j em umperodo. A matriz P uma matriz estocstica, pois sendo os seus elementos probabili-dades, pij 0, e contendo cada linha i uma distribuio de probabilidade, j pij = 1.

Para melhor ilustrar o que foi dito, considere-se o exemplo seguinte.

No pequeno pas Verdscamp'sfloridos, a bebida tradicional, um estranho licorde flores silvestres, produzida apenas por duas famlias concorrentes, a famlia Flo-rescente e a famlia Petalado. Cada famlia introduziu, ao longo das geraes, dife-rentes alteraes na frmula original, de forma a conferir ao seu licor um sabor es-pecial. Embora as frmulas sejam guardadas no segredo dos deuses, descobriu-seque uma poro de ptalas de malmequeres pode realmente fazer a diferena, ga-rantindo famlia Florescente a primazia nas preferncias dos verdscamp'sflorideses.De facto, verificou-se que, para cada pessoa que compre o licor Florescente h 90%de probabilidade de o prximo licor que comprar seja licor Florescente; j para cadapessoa que compre o licor Petalado h s 80% de probabilidade de a essncia demiostis o tornar to inesquecvel que o prximo licor comprado seja ainda o licorPetalado.

Com base nestes dados, pretende-se construir uma cadeia de Markov que re-presente a situao descrita.

Se X(t) representar o tipo de licor comprado por uma pessoa na sua t-sima com-pra, ento a cadeia de Markov limita-se a assumir um dos dois valores seguintes: F(ltimo licor comprado foi o Florescente) ou P (ltimo licor comprado foi o Petalado).O espao de estados ser, deste modo, X = {F, P}.

A cadeia de Markov pode ento ser descrita pela seguinte matriz (estocstica) detransies:

(F) (P)P = (F) 0.90 0.10

(P) 0.20 0.80

Uma outra forma de representar a cadeia atravs do diagrama de transies:

2.3. PROBABILIDADES DE TRANSIO

O conhecimento das probabilidades de transio entre os estados de grande im-portncia nas cadeias de Markov. Conforme foi referido anteriormente, as probabilida-des de transio em um perodo fazem parte da definio da cadeia de Markov. igualmente importante conhecer as probabilidades de transio em n perodos ou passos.

F P

0.20

0.10 0.800.90

5Define-se a probabilidade de transio em n passos como

pij(n) = P{X(t+n) = j | X(t) = i} = P{X(n) = j | X(0) = i} , "t =0, 1, 2, "i, jX

Uma das formas de obter o valor de pij(n) calcular as probabilidades de cada um

dos caminhos que, partindo do estado i, conduzem ao estado j em n passos, e som-las.Apesar da aparente simplicidade deste mtodo, medida que n aumenta tambm au-menta a possibilidade de esquecimento de caminhos alternativos e o clculo da proba-bilidade torna-se mais complexo. Alternativamente pode-se calcular o elemento (i,j) damatriz Pn, mtodo bastante mais eficiente.

Para demonstrar a equivalncia dos dois mtodos, retomar-se- o exemplo definidono ponto anterior. Suponhamos que se pretende conhecer a probabilidade de a terceiracompra futura de um habitante de Verdscamp'sfloridos ser licor Petalado, sabendo que,no momento presente, comprou licor Florescente, ou seja, pFP(3).

Uma hiptese seria calcular as probabilidades de todas as sequncias de compras,de forma que a transio FP ocorra em trs aquisies ou passos. Assim, verifica-se ques h quatro sequncias diferentes de transies em trs passos tais que, partindo doestado F, se acaba no estado P:

(1) F P P P(2) F F P P(3) F F F P(4) F P F P

Relembrando que, se A e B forem independentes, P{A e B} = P{A} P{B}, po-demos ento calcular a probabilidade de cada sequncia:

(1) P{FP e PP e PP} = 0.1 0.8 0.8 = 0.064(2) P{FF e FP e PP} = 0.9 0.1 0.8 = 0.072(3) P{FF e FF e FP} = 0.9 0.9 0.1 = 0.081(4) P{FP e PF e FP} = 0.1 0.2 0.1 = 0.002

Do mesmo modo, P{A ou B} = P{A} + P{B}, pelo que

pFP(3) = 0.064 + 0.072 + 0.081 + 0.002 = 0.219

Houve aqui a aplicao directa das equaes de Chapman-Kolmogorov:

pij(q+m) = k pik(q) pkj(m)

De facto, assumindo q = 1 e m = 2 aquisies,

6pFP(3) = P{FP} P(2){PP} + P{FF} P(2){FP},

sendoP(2){PP} = P{PP} P{PP} + P{PF} P{FP} e

P(2){FP} = P{FP} P{PP} + P{FF} P{FP}.

Este resultado pode ser obtido por outra via, pois o elemento da linha que corres-ponde ao estado F (estado actual) e da coluna que corresponde ao estado P (estado fu-turo) da matriz P3 exactamente 0.219, como se poder ver seguidamente.

(F) (P) P3 = (F) 0.781 0.219

(P) 0.438 0.562

Na verdade, a forma usada para calcular o valor anterior (somar as probabilidadesde caminhos alternativos) corresponde exactamente operao de multiplicao dematrizes que nos conduz a P3, tendo correspondncia directa com as equaes deChapman-Kolmogorov.

importante referir que se P for uma matriz estocstica, ento qualquer potnciade P tambm o , pois Pn = [pij

(n)], sendo pij(n) 0 e j pij(n) = 1.

2.4. CLASSIFICAO DOS ESTADOS

Um caminho do estado i para o estado j uma sequncia de transies com pro-babilidades de ocorrncia positivas que ligam os dois estados (do exemplo anterior:FPFP). No existe qualquer limite ao nmero de transies nem h a obrigaode a sequncia ser a mais curta entre os dois estados.

Diz-se que o estado j atingvel a partir do estado i se e s se houver pelo menosum caminho de i para j. Dois estados i e j so comunicantes se e s se j for atingvel apartir de i e i for atingvel a partir de j.

Diz-se que uma Cadeia de Markov irredutvel se e s se qualquer estado j foratingvel a partir de qualquer estado i, ou seja, se todos os estados forem comunicantes.

Um estado j diz-se transiente se existir um estado k que seja atingvel a partir de j,mas no sendo j atingvel a partir de k. Por outras palavras, se j for transiente no h agarantia de, saindo de j, voltar l.

Um estado j diz-se recorrente se no for transiente, ou seja, se for sempre possvelregressar a j.

No exemplo seguinte os estados 0 e 1 so transientes enquanto os estados 2 e 3so recorrentes.

7Um estado j diz-se absorvente se aps o processo l entrar no mais voltar a sair,ou seja, se pjj = 1. No exemplo seguinte o estado 0 absorvente enquanto os estados 1 e2 so transientes.

Um estado recorrente j diz-se peridico com perodo k > 1 se k for o menor inteirotal que todos os caminhos de j para j tiverem um comprimento mltiplo de k (ou seja, k o mximo divisor comum dos comprimentos de todos os caminhos do estado j para oestado j). No exemplo seguinte os estados 0 e 1 tm perodo k = 2.

Um estado recorrente diz-se aperidico se k = 1. Uma cadeia de Markov diz-seergdica se todos os estados forem recorrentes, aperidicos e comunicantes. A cadeiaseguinte ergdica.

2.5. PROBABILIDADES ESTACIONRIAS

Numa Cadeia de Markov irredutvel e ergdica, decorrido um nmero muito ele-vado de perodos de tempo (n), a probabilidade de o processo estar no estado j constante e independente do estado inicial i, como se pode observar atravs da matrizP16, que contem as probabilidades de transio em dezasseis perodos:

(F) (P)P16 = (F) 0.6677 0.3323

(P) 0.6644 0.3356

0 1

0.40

1

2 3

1

1

0.60

0

0.60

0.30 2

1

0.40 0.70

1

0 10.30

1

21

0.70

0 10.25

1 0.75

8A esta probabilidade chama-se probabilidade estacionria do estado j e repre-senta-se por pj. Por outras palavras,

pij(n+1) pij(n) pj quando n .

Tendo esta caracterstica presente, e como (pelas equaes de Chapman-Kol-mogorov) pij

(n+1) pode ser escrito como o produto [linha i de Pn] [coluna j de P], en-to, para n muito elevado, podemos escrever

pj = p [coluna j de P], sendo p o vector linha [p1, p2, p3, ,ps].

Isto corresponde a um sistema de equaes (p = p P) em que o nmero de equa-es igual ao nmero de variveis, sendo ambos iguais ao nmero de estados. Noentanto este sistema indeterminado, pois uma das equaes redundante; a indeter-minao resolvida acrescentando a equao que garante que a soluo seja uma dis-tribuio de probabilidades. Assim, para conhecer as probabilidades estacionrias pjresolve-se o sistema

pj = i pi pij (1)j pj = 1 (2).

Subtraindo pj pij a ambos os membros das equaes (1) do sistema, elas podem serre-escritas da seguinte forma

pj (1 - pjj) = ij pi pij ,

tendo a seguinte interpretao:

[Probabilidade de uma transio para fora do estado j] =

= [Probabilidade de uma transio para o estado j].

Relembrando o exemplo que nos acompanha desde o incio, quais as probabilida-des estacionrias?

pF = 0.90 pF + 0.20 pP pF = 0.6666pP = 0.10 pF + 0.80 pP pF + pP = 1 pP = 0.3333

O que estes valores significam que, aps bastante tempo, cerca de dois teros daspessoas, em mdia, compraro o licor Florescente, enquanto que s um tero delas ircomprar o licor Petalado. Deste modo as probabilidades estacionrias podem ser usadascomo indicadores das quotas de mercado de cada marca e ser muito teis em processosde tomada de deciso. De facto, a famlia Petalado sabe que se conseguir aumentar ograu de fidelizao dos clientes que compram o seu licor aumentar a sua quota demercado, servindo o modelo para quantificar estes aumentos.

92.6. TEMPOS DE TRANSIO

O tempo (medido em nmero de perodos) que decorre at que o processo,partindo do estado i, atinja o estado j pela primeira vez, chamado tempo de transio(em ingls, first passage time). Se o estado final coincidir com o estado inicial (j = i),este tempo chamado de tempo de recorrncia para o estado i. O tempo de transiodo estado i para o estado j representado por tij.

Trata-se de uma varivel aleatria, uma vez que assumir diferentes valores comdiferentes probabilidades, consoante o caminho percorrido entre os dois estados. Co-nhecer a distribuio de probabilidade das variveis tij pode no ser fcil. , no entanto,relativamente simples conhecer o seu valor esperado (E[tij] = mij), chamado tempoesperado de transio (ou de recorrncia, consoante o caso).

Para calcular o tempo esperado da transio de i para j no preciso encontrar to-dos os caminhos entre i e j e as respectivas probabilidades de ocorrncia. Alm de fas-tidioso, seria praticamente impossvel obter o valor desejado desta forma. Qualquer queseja a cadeia de Markov, a transio do estado i para o estado j feita em um perodocom probabilidade pij, e em todos os outros casos (k j) o nmero esperado de perodosser igual a (1+mkj) com probabilidade pik. Ento podemos escrever a seguinteexpresso

mij = pij (1) + kj pik (1 + mkj),

a qual, depois de simplificada, d origem ao seguinte sistema de equaes lineares:

mij = 1 + kj pik mkj .

Voltando novamente ao exemplo anterior:

mFF = 1 + 0.10 mPF mFF = 1.5mFP = 1 + 0.90 mFP mFP = 10mPF = 1 + 0.80 mPF mPF = 5mPP = 1 + 0.20 mFP mPP = 3

No caso dos tempos mdios de recorrncia verifica-se que mii = 1/pi. No exem-plo considerado, mFP significa que uma pessoa que compre o licor Florescente demora,em mdia, 10 perodos at passar a comprar licor Petalado.

2.7. CADEIAS DE MARKOV COM ESTADOS ABSORVENTES

Consideremos agora o caso das cadeia de Markov com estado(s) absorvente(s).Uma vez que um estado absorvente j tem pjj = 1, uma vez visitado a Cadeia de Markovno mais sai deste estado. Assim, numa cadeia de Markov com estados absorventesqualquer estado que comunique com um estado absorvente um estado transiente.

10

Se pensarmos no que acontece medida que o nmero de perodos vai aumen-tando (n), concluimos que a probabilidade de o processo estar num estado transiente(obviamente) tende para zero. Ou seja, no longo prazo o processo estar num estadoabsorvente. Neste caso interessa conhecer a probabilidade de, estando num dado estadotransiente, o processo vir a entrar (mais tarde ou mais cedo) num estado absorvente.Estas probabilidades so chamadas probabilidades estacionrias de absoro, ou seja,as probabilidades de o processo passar de um qualquer estado transiente para umqualquer estado absorvente num qualquer nmero de perodos.

Para ilustrar este tipo de cadeia de Markov, consideremos o seguinte exemplo:

Na loja de artigos informticos do Sr. Pague-Depressa, os clientes so divididosem categorias, consoante o nvel dos pagamentos j efectuados: pagou (categ. 0),atrasado no mais de 30 dias (categ. 1), atrasado no mais de 60 dias (categ. 2) oucaloteiro (categ. 3). As contas so verificadas mensalmente e o estado de cada cliente determinado. Segundo as regras do Sr. Pague-Depressa, os clientes devero pagaruma conta dentro de 30 dias mas, pagando prestaes, podem-se atrasar no mximo60 dias; a partir dessa data o Sr. Pague-Depressa entrega os dados do cliente a umaempresa especializada em cobrana de dvidas.

Aps a anlise dos dados histricos da loja, construiu-se a seguinte matriz detransies:

(0) (3) (1) (2)(0) 1 0 0 0

P = (3) 0 1 0 0(1) 0.7 0 0.2 0.1(2) 0.5 0.2 0.1 0.2

Com base nestes dados, pretende-se conhecer a probabilidade de um clienteacabar, eventualmente, na categoria 3 (caloteiro), dado estar actualmente quer nacategoria 1 quer na categoria 2.

O diagrama de transies o seguinte:

Consideremos as seguintes parties na matriz das probabilidades de transio:

=

QR

0IP ,

em que: I a matriz (identidade) que contem as probabilidades de transio entre esta-dos absorventes; 0 a matriz nula, indicando que no existem transies dos estados

1 20.10

0.10 0.200.20

0.70

3

1

0

10.20

0.50

11

absorventes para os estados transientes; R a matriz que contem as probabilidades detransio dos estados transientes para os estados absorventes; Q a matriz que contemas probabilidades de transio entre estados transientes.

As probabilidades de passar de um qualquer estado transiente para um qualquerestado absorvente

- em 1 perodo so dadas por R ;- em 2 perodos so dadas por QR ;- em 3 perodos so dadas por Q2R ;

- em n+1 perodos so dadas por QnR .

Para obter as probabilidades de passar de um qualquer estado transiente para umqualquer estado absorvente num qualquer nmero de perodos temos que considerar asoma

R + QR + Q2R + Q3R + = (I Q)-1R ,

Ou seja, os elementos da matriz (I Q)-1R so as probabilidades estacionrias deabsoro. Alternativamente, chegava-se mesma concluso se se considerasse a matrizPn quando n.

A matriz (I Q)-1 chamada a matriz fundamental da cadeia de Markov, tendo osseus elementos um significado especial: o elemento (i,j) representa o nmero esperado devezes que o estado transiente j visitado antes de o processo entrar num estadoabsorvente qualquer, partindo do estado transiente i. No exemplo anterior

(I Q)-1R = 0.968 0.0320.747 0.254

Assim, a probabilidade de um cliente ser, eventualmente, caloteiro igual a 0.032se o seu dbito no tiver mais de 30 dias e igual a 0.254 se o seu dbito tiver entre 30 e60 dias. Por outro lado,

(I Q)-1 = 1.27 0.160.16 1.27

o que significa que uma conta com um dbito at 30 dias demora 1.27 + 0.16 = 1.43meses at estar totalmente liquidada. Note-se que possvel uma conta rejuvenescer,ou seja, ter um dbito entre 30 e 60 dias num ms e no ms seguinte ter um dbito at 30dias (por pagamento do dbito antigo e novas compras).

12

3. CADEIAS DE MARKOV EM TEMPO CONTNUO

3.1. DEFINIO

Uma cadeia de Markov em tempo contnuo , como a designao indica, umacadeia de Markov em que a varivel tempo contnua, representando instantes ou mo-mentos do tempo (e no perodos no tempo como no ponto anterior). Assim, umacadeia de Markov em tempo contnuo um processo estocstico {X(t), t 0} com apropriedade de Markov, ou seja, a probabilidade de o processo estar no estado j nummomento futuro depende apenas do estado presente e no dos estados visitados emqualquer momento passado:

Pij(t) = P{X(t+s) = j | X(s) = i , X(u) = k para 0 u s} =

P{X(t+s) = j | X(s) = i}, "i, j, k X

Apenas vamos considerar cadeias de Markov com as seguintes caractersticas:

1) O espao de estados X finito ou contvel.

2) As probabilidades de transio de um estado para outro no dependem dotempo de permanncia nesse estado (cadeia estacionria), ou seja,

Pij(t) = P{X(t+s) = j | X(s) = i} = P{X(t) = j | X(0) = i}, "s 0 "i, jX

3.2. TEMPO DE PERMANNCIA NO ESTADO

O tempo que o processo permanece em cada estado passa a ser uma consideraoimportante, pois o processo em tempo contnuo e no em tempo discreto. Este tempo, naturalmente, incerto ou aleatrio. Seja ti a varivel aleatria tempo de permannciano estado i, isto , o tempo necessrio para que o sistema saia do estado i, efectuandouma transio para outro estado.

Ento, facilmente se conclui que o processo permanece no estado i entre os ins-tantes 0 e t se e s se o tempo de permanncia no estado i for superior a t, ou seja,

P{X(t) = i | X(0) = i} = P{ti > t | ti > 0} = P{ti > t}, " t 0 "i X .

Por outro lado, o sistema permanece no estado i entre os instantes s e (t + s) se es se o tempo necessrio para que o sistema saia do estado i for superior a (t + s), dadoque o tempo de permanncia no estado i era superior a s, ou seja,

P{X(t + s)=i | X(s)=i} = P{ti > t + s | ti > s} , " t , s 0 "i X .

13

Como P{X(t+s) = i | X(s) = i} = P{X(t) = i | X(0) = i} ento P{ti > t+s | ti > s} =P{ti > t}. Por outras palavras, a distribuio da varivel aleatria tempo de permann-cia num dado estado independente do tempo que o processo tenha j passado nesseestado (propriedade da ausncia de memria). Como a nica distribuio contnua quegoza desta propriedade a distribuio exponencial, concluimos que ti tem distribuioexponencial.

Suponhamos que a varivel aleatria ti 0 tem distribuio exponencial comparmetro (taxa) mi. Ento a funo distribuio dada por Fti (t) = P{ti t} = 1 - e

-t

mi " t 0. O valor esperado E[ti] = 1/ mi e a varincia V[ti] = 1/ mi2, verificando-sesempre que a mdia igual ao desvio padro, sendo ambos iguais ao inverso doparmetro.

A distribuio exponencial goza de duas propriedades muito importantes no estudodas cadeias de Markov em tempo contnuo, as quais sero apresentadas sem qualquerdemonstrao. Uma, que foi j referida a propriedade da ausncia de memria,segundo a qual P{ti > t + s | ti > s} = P{ti > t} , " s,t 0. A outra diz-nos que se avarivel aleatria tmin for o mnimo de diferentes variveis aleatrias independentes (t1,t2, , tN), cada qual com distribuio exponencial de parmetro mi (i =1, , N), entotmin tem tambm distribuio exponencial, sendo o parmetro dado por m = i mi.

3.3. REPRESENTAO

Uma Cadeia de Markov em tempo contnuo fica completamente definida se co-nhecermos os estados X = {0, 1, 2, , s}, o parmetro mi da distribuio (exponencial)de cada varivel ti (tempo de permanncia em cada estado i) e as probabilidades de oprocesso transitar para o estado j, dado que saiu do estado i (pij). Em alternativa a co-nhecer os parmetros mi e as probabilidades pij, basta conhecer as taxas de transio en-tre os estados, mij.

A interpretao intuitiva de mi e de mij de que se trata de taxas de transio.Concretamente, mi a taxa de transio para fora do estado i, significando que mi onmero esperado de vezes que o processo sai do estado i por unidade de tempo passadono estado i. Assim, mi o inverso do tempo mdio de permanncia no estado i, ou seja,E[ti] = 1/mi. De modo semelhante, mij a taxa de transio do estado i para o estado j,significando isto que mij o nmero esperado de vezes que o processo efectua uma tran-sio de i para j por unidade de tempo passado no estado i.

Existem duas formas de representao: graficamente, atravs do diagrama detransies, ou atravs de uma matriz quadrada U que contem as taxas de transio.

Num diagrama de transies cada estado representado por um vrtice, e cadaarco orientado ligando dois vrtices representa uma transio possvel entre dois estados,sendo o coeficiente associado ao arco a respectiva taxa.

14

Na matriz U, cada linha i representa o estado actual e cada coluna j representa oestado futuro (a ordem dos estados actuais deve ser igual dos estados futuros, respec-tivamente, nas linhas e nas colunas de U). Deste modo, o elemento mij da matriz repre-senta a taxa de transio do estado i para o estado j.

As taxas de transio mij so dadas por mij = mi pij (ij), e portanto verifica-se que

ji mij = mi ji pij = mi .

3.4. PROBABILIDADES ESTACIONRIAS

No estudo das cadeias de Markov em tempo contnuo interessa conhecer as pro-babilidades estacionrias (t) de o processo estar nos diferentes estados (pj).

Para se obterem as probabilidades estacionrias, escrevem-se as chamadas equa-es de balano que traduzem a ideia de que, em equilbrio, a taxa mdia de sadas deum qualquer estado deve ser igual taxa mdia de entradas nesse mesmo estado. Essasequaes constituem o seguinte sistema:

mj pj = ij pi mij . (1)

semelhana do que acontecia nas cadeias em tempo discreto, tambm o sistema(1) indeterminado. Encontram-se, ento, as probabilidades estacionrias acrescentandoa equao seguinte:

j pj = 1 . (2)

Consideremos o exemplo seguinte:

Uma mquina, integrada numa linha de produo, solda duas peas idnticas.Sabe-se que o tempo entre duas chegadas consecutivas de peas mquina tem umadistribuio exponencial com mdia igual a um quarto de hora. Da mesma forma, otempo de soldagem segue uma distribuio exponencial com mdia igual a meia hora.Pretende-se construir uma cadeia de Markov que represente a situao descrita,determinando as probabilidades estacionrias.

Se X(t) representar o nmero de peas na mquina no momento t, ento X(t)limita-se a assumir um dos trs valores seguintes: 0, 1 ou 2 peas. O espao de estadosser, deste modo, X ={0, 1, 2}. Existem apenas dois tipos de acontecimentos: chegadade uma pea mquina (mch=4 peas/h) e sada das duas peas soldadas (mp=2 peassoldadas/h).

As transies so descritas seguidamente no respectivo diagrama. As transies01 e 12 correspondem chegada de uma pea mquina, enquanto a transio20 corresponde sada das peas soldadas. No se considera a possibilidade de haver

15

a transio 02 pelo facto de se considerar que s ocorre um evento de cada vez (possvel efectuar a separao temporal de acontecimentos quase simultneos).

A matriz que contem as taxas de transio a seguinte:

(0) (1) (2)(0) 0 4 0

U = (1) 0 0 4(2) 2 0 0

Para calcular as probabilidades estacionrias, escrevemos as equaes de balano ea equao de normalizao:

Equaes de balano: estado 0: 4 p0 = 2 p2 estado 1: 4 p1 = 4 p0 estado 2: 2 p2 = 4 p1

Equao de normalizao: p0 + p1 + p2 = 1

A soluo do sistema p0 = 0.25, p1 = 0.25 e p2 = 0.50. Significa isto que amquina passa 25% do tempo com 0 ou 1 pea, e 50% com 2 peas.

4. PROCESSOS DE NASCIMENTO-MORTE

4.1. GENERALIDADES

Os Processos de Nascimento-Morte so processos estocsticos muito utilizados nadescrio de Sistemas de Filas de Espera, dada a sua particular estrutura: as transiesde um qualquer estado s so possveis para estados vizinhos (i.e., de um estado i paraos estados i+1 ou i-1). De facto, adoptando um espao de estados X ={0, 1, } erepresentando cada estado um certo nvel de populao (nmero de clientes numa loja,nmero de mensagens num atendedor de chamadas, nmero de produtos a processar,etc) tais transies podem ser facilmente interpretadas: a transio do estado i para oestado i+1 ser um nascimento (por exemplo, chegada de um cliente), por significarum aumento do nvel da populao, enquanto que a transio do estado i para o estadoi-1 ser uma morte (partida de um cliente), por significar um decrscimo do nvel dapopulao.

0 1 2

4 4

2

16

4.2. EQUAES DE BALANO

As equaes de balano so facilmente escritas a partir do diagrama de transies,pois o facto de as transies de um qualquer estado s serem possveis para, no mximo,dois estados torna as equaes bastante compactas.

Consideremos o seguinte diagrama de transies:

As equaes de balano sero, ento:

estado 0: p0 m01 = p1 m10estado 1: p1 (m10 + m12) = p0 m01 + p2 m21estado 2: p2 (m21 + m23) = p1 m12 + p3 m32 estado n: pn (mn,n-1 + mn,n+1) = pn-1 mn-1,n + pn+1 mn+1,n

Da primeira equao concluimos que p1 = (m01/m10) p0. Da segunda equao, e substi-tuindo p1 pela sua expresso em termos de p0, tiramos que p2 = (m12 m01 / m21 m10) p0.Prosseguindo da mesma forma possvel exprimir as restantes probabilidades em termosde p0, e atravs da equao de normalizao encontrar o valor de p0. As restantesprobabilidades estacionrias so ento muito simples de calcular.

5. BIBLIOGRAFIA

inlar, Erhan (1975), Introduction to Stochastic Processes, Prentice-Hall, Inc.

Hillier, G. and J. Lieberman (1995), Introduction to Operations Research, Sixth Edition,McGraw-Hill.

Kleinrock, Leonard (1975), Queueing Systems (Vol. I: Theory), John Wiley & Sons.

Ross, Sheldon M. (1983), Stochastic Processes, John Wiley & Sons.

Winston, Wayne L. (1994), Operations Research Applications and Algorithms, ThirdEdition, Duxbury Press.

0 1 2 3

m01 m12 m23 m34

m10 m21 m32 m43