Aproxima˘c~ao de Distribui˘c~oes de Probabilidade N~ao-Exp ... fileos quais a hip otese de distribui˘c~ao exponencial dos tempos e essencial [Carvalho (1991)]

12 a 15/09/06 Goiânia, GOPesquisa Operacional na Sociedade: Educação, Meio Ambiente e DesenvolvimentoXXXVIII SIMPÓSIO BRASILEIRO PESQUISA OPERACIONALDE

Aproximacao de Distribuicoes de Probabilidade

Nao-Exponenciais por Distribuicoes do Tipo Fase

Marcio Nunes de MirandaUniversidade Federal de Goias

Campus Samambaia, Goiania - [email protected]

Alvaro Junio Pereira FrancoUniversidade Federal de Goias

Campus Samambaia, Goiania - [email protected]

Solon Venancio de CarvalhoInstituto Nacional de Pesquisas Espaciais

Av. dos Astronautas, 1.758, Jd. Granja, Sao Jose dos Campos - [email protected]

RESUMO

A distribuicao do tipo fase pode ser vista como uma representacao do tempo ate a ab-sorcao numa cadeia de Markov. Atraves do metodo dos estagios, ela permite a insercao detempos aleatorios nao exponencialmente distribuıdos em modelos nao Markovianos. O prob-lema consiste em obter uma distribuicao do tipo fase FPH que aproxime uma distribuicaode probabilidades contınua e positiva F (t) dada. Em trabalhos anteriores, e gerada umaamostra a partir da distribuicao a ser aproximada e, usando a amostra ge-rada, e realizadaa estimacao dos parametros da distribuicao do tipo fase pelo metodo da maxima verossim-ilhanca. Este trabalho utiliza uma nova abordagem onde o problema de estimacao dosparametros e formulado como um problema de minimizacao de uma funcao de distanciaestocastica diretamente proporcional a [f(t)− fPH(P0,Λ, t)]

2, onde f(t) e fPH(P0,Λ, t) saoas funcoes densidade de probabilidade de F (t) e FPH(P0,Λ, t), respectivamente, e P0 e Λsao os parametros da distribuicao do tipo fase a serem determinados.Palavras-chave. Aproximacao. Distribuicoes do tipo fase. Distancia estocastica.Otimizacao combinatoria.

ABSTRACT

The Phase distribution can be considered as a generalisation of the exponential dis-tribution with negative parameter that incorporates the Erlang and the hyperexponentialdistributions. This distribution, through the method of stages, allows the insertion of non-exponentially distributed random times in non Markovian Models. The problem to be treatedis to find a Phase distribution (FPH) that best fits a given positive and continuous proba-bility distribution function (F (t)). Previous works [Bobbio (1992)][Bobbio (1992a)] treatedthis problem using samples generated from the analytical expression of the distribution to befitted. The parameters estimation of the Phase distribution is performed using the maximumlikelihood method. This work suggest to estimate the parameters minimizing a probabilitydistance function, proportional to [f(t) − fPH(P0,Λ, t)]

2, where f(t) and fPH(t) are theprobability density functions of F (t) and FPH(t), respectively, and P0 and Λ are the param-eters to be found.Keywords. Approximation, Phase-type distribution. Stochastic distance. Com-binatorial optimization.

XXXVIII SBPO [ 1604 ]


1 Introducao

Muitos dos metodos utilizados para modelar sistemas sao baseados em diagrama deestados e, em muitos deles, impoe-se a hipotese de que o tempo de permanencia em cadaestado ate uma transicao e exponencialmente distribuıdo. Porem esta hipotese nem sempree verdadeira para muitos sistemas reais. Por outro lado, seria interessante que, de algumamaneira, o comportamento do sistema pudesse ser aproximado de forma que os tempos en-volvidos fossem exponenciais, pois desta maneira poderiam ser aproveitadas as propriedadesanalıticas dos processos de Markov e diversas ferramentas para solucao desses modelos, paraos quais a hipotese de distribuicao exponencial dos tempos e essencial [Carvalho (1991)].

O metodo dos estagios e uma forma de representar distribuicoes nao-exponenciais poruma combinacao de estagios (estados fictıcios) onde o tempo de permanencia em cada estadoe exponencialmente distribuıdo [Singh (1977)]. A combinacao de estagios e representadanos modelos de Markov pela introducao de estados fictıcios, tornando possıvel a utilizacaodo ferramental analıtico disponıvel para os processos de Markov [Carvalho (1991)]. Por estemotivo o estudo da distribuicao do tipo fase e de sua aplicacao no metodo dos estagios eum dos principais objetivos deste trabalho.

O problema da estimacao dos parametros da distribuicao do tipo fase tem sido tratadoutilizando-se o metodo da maxima verossimilhanca [Bobbio (1992)][Bobbio (1992a)] ou ometodo dos momentos [Carvalho (1991)]. No metodo onde se utiliza a funcao de verossimi-lhanca pode-se trabalhar com amostras da funcao a ser aproximada [Carvalho (1991)][Lima(1994)] ou com valores obtidos diretamente da expressao analıtica da distribuicao que sedeseja aproximar, dividindo-se o seu domınio em pequenos intervalos e tomando o valor dafuncao no ponto medio de cada intervalo [Cumani (1982)].

O objetivo deste trabalho e utilizar uma metodologia onde a estimacao dos parametrose realizada atraves da minimizacao de uma funcao de distancia estocastica, que forneceuma medida da separabilidade entre a densidade da distribuicao a ser aproximada (f(t)) euma densidade da distribuicao do tipo fase (fPH(P0,Λ, t)), que a aproxima. Foi utilizadaa seguinte funcao, devido ao seu facil tratamento analalico:

∆(P0,Λ) =

∫ ∞

0[f(t)− fPH(P0,Λ, t)]

2dt (1)

onde P0 e Λ sao os parametros da distribuicao do tipo fase a serem obtidos. Pode-semostrar que a integral acima converge para funcoes densidade de probabilidade (pdf) f(t)que possuam transformada de Laplace diferenciavel ou, equivalentemente, pdf com funcaogeratriz de momentos.

O presente trabalho se restringe a classe de distribuicoes do tipo fase acıclicas, ondecada estado da cadeia de Markov correspondente e atingido no maximo uma vez antes daabsorcao. Esta restricao e necessaria, pois os resultados conhecidos para as distribuicoes dotipo fase acıclicas permitem reduzir o problema tratado a um problema de minimizacao deuma funcao nao linear sujeito a um conjunto de restricoes lineares. Para a resolucao desteproblema sera utilizado um algoritmo de programacao nao linear denominado metodo dePowell.

Este artigo esta estruturado da seguinte forma. A secao 2 contem algumas definicoesbasicas importantes, assim como as principais propriedades das distribuicoes do tipo faseacıclicas e alguns casos especiais desta distribuicao. A metodologia para estimacao dosparametros da distribuicao do tipo fase e descrita na secao 3. Na secao 4 sao apresentadosos resultados obtidos e a analise dos mesmos. As consideracoes finais se encontram na secao5.



2 Distribuicoes do Tipo Fase

As distribuicoes de probabilidades do tipo fase sao definidas a partir das cadeias deMarkov. O presente trabalho trata das distribuicoes baseadas em cadeias de Markov atempo contınuo.

Uma variavel aleatoria positiva e contınua X possui distribuicao de probabilidade dotipo fase, definida em [0,∞), se e somente se X pode representar o tempo ate a absorcaonuma cadeia de Markov a tempo contınuo com espaco de estados E = 1, 2, ...,m + 1, ondeos estados 1, 2, ...,m sao transitorios e o estado m+ 1 e absorvente. Os elementos de E saochamados de estagios ou, alguma vezes, estados fictıcios.

Para desenvolver as expressoes associadas as distribuicoes do tipo fase, considera-se umacadeia de Markov onde o gerador infinitesimal Q e dado por:

Q =

[Λ Λ0

0m 0

](2)

onde Λ e uma matriz de dimensao m×m (matriz de taxas de transicao entre os estadostransitorios), tal que λij ≥ 0, para i 6= j, λii = −λi ≤ −

∑j 6=i λij, para 1 ≤ i ≤ m e

Λ0 e um vetor coluna de dimensao m e elementos positivos ou nulos (vetor de taxas detransicao em direcao ao estado absorvente), 0m e um vetor linha de zeros de dimensao me ainda: Λ1m + Λ0 = 0, onde 1m e um vetor coluna de “uns” de dimensao m. Denotando[P0 p0a], onde P0 ·1m+p0a = 1, o vetor linha de probabilidades iniciais dos estados, onde P0

corresponde as probabilidades iniciais dos estados transitorios e p0a a probabilidade inicialdo estado absorvente. O par (P0,Λ) e chamado representacao de uma distribuicao do tipofase (FPH(P0,Λ, t)). A ordem de uma representacao de FPH(t) e definida como a ordemda matriz Λ associada [Carvalho (1991)].

Em [Neuts (1981)] e mostrado que a hipotese de m estados transitorios e um absorventee verificada se e somente se a matriz Λ e nao singular e que, sob esta hipotese, dado o vetorde probabilidades iniciais [P0 p0a] a distribuicao de probabilidades FPH(t) do tempo ate aabsorcao no estado m+ 1 e dada por:

FPH(t) = 1− P0 exp (Λt)1m (3)

para t ≥ 0.A funcao densidade de probabilidade correspondente e dada por fPH(t) = dFPH(t)

dt (ex-ceto em t = 0, onde existe uma descontinuidade). Sendo δ(t) a funcao de Dirac:

fPH(t) = p0aδ(t) − P0 exp (Λt)Λ1m (4)

onde t ≥ 0. Supondo que a probabilidade de absorcao imediata (em t = 0) e zero, isto e,p0a = 0, tem-se que:

fPH(t) = −P0 exp (Λt)Λ1m (5)

2.1 Distribuicao de Cox

A distribuicao de Cox e um caso particular de uma distribuicao do tipo fase que possuia representacao P0 = (1, 0, ..., 0) e

Λ =

−λ1 p1λ1

−λ2 p2λ2 0...

...0 −λm−1 pm−1λm−1

−λm

(6)



Esta configuracao e proposta em [Cox (1955)], artigo no qual ele mostra que toda dis-tribuicao do tipo fase pode ser colocada na forma da figura 1.

p p p1 2 3λ λ λ λ1 2 3 n2 1 3 n+1n

(1-p ) λ1 1 (1-p 2 )λ 2(1-p 3 ) λ3

Figura 1: Diagrama de estados para a distribuicao de Cox

2.2 Forma transformada

Para manipular os parametros da distribuicao do tipo fase e, consequentemente, tratar asua representacao (P0,Λ), e essencial que se consiga desenvolver analiticamente a expressao−P0 exp (Λt)Λ1m (que inclui um termo do tipo exponencial de matriz), de maneira a coloca-la numa forma computacionalmente tratavel. [Carvalho (1991)] propoe a aplicacao de umatransformacao matricial sobre a matriz Λ de forma a diagonaliza-la (ou reduzi-la a umaforma de Jordan, quando a matriz nao for diagonalizavel). Pode-se mostrar [Cox (1955)]que:

fPH(t) =

d∑

i=1

ki∑

j=1

wij ·λki−j+1i

(ki − j)!· tki−j exp (−λit) (7)

sera uma das expressoes utilizadas no processo de estimacao dos parametros.

2.3 Distribuicoes do Tipo Fase Acıclicas

As distribuicoes do tipo fase acıclicas sao uma subclasse das distribuicoes do tipo fase quesao geradas a partir de uma cadeia de Markov a tempo contınuo acıclica. Foi demonstrado[Cumani (1982)] que as distribuicoes do tipo fase acıclicas fornecem representacoes mınimas(denominadas formas canonicas), unicas, com taxas de transicao reais e nao-crescentes.

Para uma distribuicao PH acıclica existem tres formas canonicas basicas, denominadasCF1, CF2 e CF3 [Bobbio (1992)]. Neste trabalho estamos particularmente interessados naforma canonica CF3 (configuracao de Cox). [Carvalho (1991)] apresenta um algoritmo paraobtencao dos coeficientes wij da expressao (7) a partir dos parametros λi, i = 1, 2, ..., n epi, i = 1, 2, ..., n − 1, considerando este tipo de configuracao.

λn2 1 3 n+1n

(1-q 1 ) λ 1(1− q2 )λ

q1

q2 q3λ λ λ1 2 3

2 (1-q 3 ) λ3

Figura 2: Forma canonica CF3



Na figura 2 1− pi e a probabilidade de o sistema atingir o estado absorvente a partir doestado ei e pi e a probabilidade do sistema atingir o estado ei+1 a partir do estado ei.

Representacao (P0,Λ):P0 = (1, 0, ...0) e

Λ =

−λ1 p1λ1

−λ2 p2λ2 0... ...

... ...0 −λn−1 pn−1λn−1

−λn

(8)

com 0 ≤ pi ≤ 1 e λ1 ≥ λ2 ≥ ... ≥ λn.

2.3.1 Relacao entre a Configuracao de Cox e a forma transformada (W,ΛT )

Suponha que seja extraıdo um subconjunto da configuracao de Cox (figura 2), formadopelos estados er, er+1, ..., en (r = 1, 2, ..., n). Para cada valor de r, a forma transformadacorrespondente pode ser escrita como:

f∗r (s) =d∑

i=1

ki∑

j=1

wij(r)

[λi

(s+ λi)

]ki−j+1

(9)

onde wij(r) e o j-esimo elemento do vetor wi(r) (de dimensao ki), para r = 1, 2, ..., n.A partir do desenvolvimento desta expressao, realizado em [Miranda (1996)], obtem-se

a relacao entre os vetores wi(r) e wi(r + 1):

wi(r + 1) = wi(r)1

pr∆i(r) (10)

para r = 1, 2, ..., n − 1, onde ∆i(r) e uma matriz quadrada de ordem ki dada por:

∆i(r) =

λr−λiλr

λiλr

0λr−λiλr

.

. .. .

. λiλr

0 λr−λiλr

(11)

A equacao (10) permite obter, sucessivamente, as probabilidades pi = 1 − qi (i =1, 2, ..., n − 1). Essas probabilidades correspondem a passagem do estado ei ao estado ei+1

numa configuracao de Cox. Cada funcao f ∗r (s) e a transformada de Laplace de uma funcaodensidade de probabilidade e portanto:

d∑

i=1

ki∑

j=1

wij(r) =

d∑

i=1

wi(r)1ki = 1 (12)

para r = 1, 2, ..., n, onde 1ki e um vetor coluna de uns de dimensao ki.Combinando as equacoes (10) e (12) tem-se:

pr =

d∑

i=1

wi(r)∆i(r)1ki (13)



para r = 1, 2, ..., n − 1.Substituindo este valor na equacao (10):

wi(r + 1) =wi(r)∆i(r)

d∑i=1

wi(r)∆i(r)1ki

(14)

para r = 1, 2, ..., n − 1.A partir do vetor wi(1), conhecido, pode-se calcular p1 por (13) e wi(2) por (14). A

partir de wi(2) calcula-se p2 e wi(3) e assim sucessivamente ate se obter pn−1, ou seja,obtem-se a configuracao de Cox correspondente a forma transformada dada.

Se todas as taxas sao diferentes (λ1 > λ2 > ... > λn), a relacao entre os vetores wi e asprobabilidades pi podem ser facilmente obtidas a partir da equacao (10) e do conhecimentode wi(1).

3 Metodologia de Estimacao dos Parametros

Nesta secao e introduzida uma nova abordagem para a estimacao dos parametros da dis-tribuicao PH, onde e utilizada a expressao analıtica da funcao densidade de probabilidadesda distribuicao que se deseja aproximar, ao contrario de amostras da mesma, como foirealizado em trabalhos anteriores. A ideia baseia-se em minimizar o erro quadratico entreas curvas da densidade da distribuicao do tipo fase (fPH(t)) e da densidade da distribuicaoque se deseja aproximar (f(t)).

As medidas de distancias probabilısticas, usualmente chamadas de distancias estocasticas,sao funcoes definidas de maneira a se quantificar a separabilidade entre distribuicoes deprobabilidade. Este tipo de funcao tera um papel fundamental neste trabalho pois o metodose baseia em encontrar os parametros da distribuicao FPH que minimizam a funcao abaixo,a qual e diretamente proporcional a area hachurada da figura 3:

∆(P0,Λ) =

∫ ∞

0[f(t)− fPH(P0,Λ, t)]

2dt (15)

onde ∆(P0,Λ) e a distancia estocastica que se pretende minimizar e (P0,Λ) correspondea uma forma de Cox. A escolha da funcao acima se deve a sua facilidade de tratamentoanalıtico e computacional.

t

f(t)

fPH(t)

Figura 3: f(t) e fPH(t)

A minimizacao da funcao acima esta sujeita as restricoes: λ1 ≥ λ2 ≥ ... ≥ λn > 0,0 < pi ≤ 1 , para i = 1, 2, ..., n−1 e f(t) deve ser positiva e integravel. O metodo de Powell



sera utilizado para se obter os parametros P0 e Λ de uma forma mais rapida e eficiente doque aquelas encontradas na bibliografia, que utilizam o metodo da maxima verossimilhanca[Carvalho (1991)].

4 Resultados

Nesta secao sao apresentados e analisados os resultados obtidos atraves da implementacaocomputacional da metodologia proposta, fundamentais para a comparacao com outrasmetodologias.

4.1 Distribuicoes tratadas

As seguintes distribuicoes foram incluıdas no banco de testes para a avaliacao do metodoproposto:

Distribuicao de Erlang de ordem m:

f(t) =λm

(m− 1)!· tm−1exp(−λt) m > 0, inteiro (16)

Parametros: m = 2 e λ = 2.0 – E1(2, 2.0); m = 4 e λ = 2.0 – E2(4, 2.0)

Distribuicao hiperexponencial com dois estados (HE2):

f(t) =

2∑

i=1

piλiexp(−λit) (17)

Parametros: λ1 = 2.0, λ2 = 5.0 e p1 = 0.3 – H1(2.0, 5.0, 0.3)

Distribuicao Uniforme: Parametros: a = 0 e b = 1 – U1(0, 1)

Distribuicao Gama: Parametros: r = 2.5 e λ = 2.0 – G1(2.5, 2.0)

Histograma: Com o objetivo de facilitar a implementacao do algoritmo, define-se umhistograma de uma forma diferente daquela encontrada na bibliografia, na qual, usualmente,um histograma e uma funcao discreta, o que contraria a suposicao da metodologia proposta(funcoes integraveis e positivas).

HT1 =

0 se x < 01 se 0 ≤ x ≤ 0.50.6 se 0.5 ≤ x ≤ 1.00.4 se 1.0 ≤ x ≤ 1.50 se x > 1.5

(18)

Distribuicao de Weibull:

f(t) = abtb−1exp(−atb) a > 0, b > 0 (19)

Parametros: a = 1.0 e b = 1.5 – W1(1.0, 1.5)



4.2 Visualizacao grafica dos resultados

Foram gerados graficos que permitem uma melhor visualizacao dos resultados. Paraeste fim utilizou-se o pacote de SW matematico Mathematica para tracar os graficos dasfiguras (4) a (12), onde as curvas contınuas (na grande maioria dos casos) sao de fPH(t) eas curvas pretas tracejadas sao de f(t).

Figura 4: (Aproximacao de E1(2,2.0))

Figura 5: (Aproximacao de E2(4,2.0))

Distribuicao de Erlang: Sendo a distribuicao de Erlang um caso particular da dis-tribuicao do tipo fase espera-se que o erro seja praticamente zero. Analisando os resultadospara 2 e 4 estados (figuras (4) e (5), respectivamente) confirma-se a previsao.

Figura 6: (Aproximacao de H1(2.0,5.0,0.3))

Distribuicao hiperexponencial: A distribuicao hiperexponencial e um caso particularda distribuicao do tipo fase, portanto espera-se que o grafico de f(t) e de fPH(t) coincidamquase perfeitamente. Isto pode ser comprovado pela observacao da figura (6). Somenteanalisando os valores encontrados para a funcao objetivo e para os erros relativos nosmomentos pode-se perceber diferencas, devido a problemas de aproximacao.

Distribuicao Uniforme: Na figura (7) percebe-se a dificuldade em se realizar a apro-ximacao para densidades que nao possuem curvas suaves. Para uma aproximacao com



Figura 7: (Aproximacao de U1(0,1) utilizando 2, 4 e 8 estados)

pequeno erro seriam necessarios centenas ou milhares de estados. Em [Ou (1996)] mostra-se que quando o numero de estados tende a infinito qualquer distribuicao positiva e contınuapode ser aproximada por uma combinacao de distribuicoes hiperexponenciais (que sao dis-tribuicoes do tipo fase). Percebe-se uma tendencia da curva da densidade da distribuicaoPH de oscilar em torno do patamar superior da distribuicao U1(0,1), a medida em que seaumenta o numero de estados.

Figura 8: (Aproximacao de G1(2.0,2.5) com 2 estados)

Figura 9: (Aproximacao de G1(2.0,2.5) com 4 estados)

Distribuicao Gama: Como a distribuicao Gama possui uma densidade suave e derivavel,percebe-se que somente a figura (8), onde apenas 2 estados sao utilizados na aproximacao,apresenta um desvio consideravel. Na figura (9) o erro e quase imperceptıvel visualmente.

Histograma: Neste caso observa-se um rendimento melhor do algoritmo somente com16 estados (vide figuras 10 e 11). Isto se deve ao fato de o histograma possuir as mesmasdificuldades da distribuicao uniforme. No entanto, foi utilizado um histograma atıpico,para facilitar a implementacao e ilustrar a utilidade do metodo proposto. Isto certamentecontribuiu para a dificuldade da aproximacao. Talvez um histograma mais proximo da



Figura 10: (Aproximacao de HT1 com 4 estados)

Figura 11: (Aproximacao de HT1 com 16 estados)

realidade, possuindo maior quantidade de nıveis, torne a curva mais suave e forneca umresultado mais satisfatorio.

Figura 12: (Aproximacao de W1(1.0,1.5) com 2 estados)

Distribuicao de Weibull: A figura 12 mostra que o algoritmo apresentou bons resul-tados utilizando-se apenas 2 estados. Apesar de se notar, graficamente, uma melhoria daaproximacao quando se aumenta o numero de estados, nao e possıvel se detectar a mesmarelacao no que diz respeito aos erros nos momentos, pois o algoritmo foi desenvolvido com oobjetivo de minimizar a funcao objetivo e nao os erros relativos nos momentos. Em relacaoa funcao objetivo pode-se observar claramente uma diminuicao de seu valor para o caso dadistribuicao G1, enquanto que para U1 e HT1 a variacao e muito pequena. A distribuicaoW1 apresentou resultados compatıveis com a distribuicao G1.

4.3 Resultados numericos

Os resultados numericos da funcao objetivo (fobj), para os erros relativos dos momentos(e∗1, e∗2, e∗3) e para o tempo de processamento(t) sao apresentados na tabela 1. O sımbolo(*) indica o numero de estados usados para cada aproximacao.

Pode-se reparar um crescimento acentuado do tempo de processamento em funcao doaumento do numero de estados. Os resultados obtidos sao considerados bastantes satis-fatorios, o que pode ser comprovado pelos graficos. Em [Bobbio (1992)] os tempos de



fobj e1∗ e2

∗ e3∗ t(seg.)

E1 0 1.6E − 4 3.3E − 4 4.9E − 4 1.4

E2 5.2E − 5 6.6E − 5 2.9E − 4 7.9E − 4 11.0

H1 0 0 0 0 1.5

H2 0 0 0 1.0E − 6 6.3

H3 0 5.4E − 5 2.6E − 4 7.1E − 4 70.0

U1− 2∗ 5.9E − 1 2.2E − 1 1.2E − 0 3.9E − 0 1.0

U1− 4∗ 4.0E − 1 9.0E − 2 4.3E − 1 1.2E − 0 5.9

U1− 8∗ 4.0E − 1 8.0E − 2 4.1E − 1 1.1E − 0 40.0

U2− 2∗ 1.2E − 1 2.0E − 1 7.4E − 1 2.0E − 0 1.0

U2− 4∗ 8.0E − 2 1.1E − 1 3.5E − 1 8.0E − 1 9.0

U2− 8∗ 7.0E − 2 1.0E − 1 2.9E − 1 6.5E − 1 45.0

G1− 2∗ 5.7E − 3 4.1E − 2 4.6E − 1 3.4E − 1 1.5

G1− 4∗ 1.8E − 4 4.3E − 3 1.5E − 2 3.3E − 2 15.0

G1− 8∗ 8.2E − 3 7.1E − 3 1.5E − 2 6.1E − 1 100.0

HT1− 2∗ 2.8E − 2 1.2E − 1 4.3E − 1 1.1E − 0 2.5

HT1− 4∗ 2.5E − 2 7.4E − 2 2.5E − 1 6.1E − 1 7.5

HT1− 8∗ 2.2E − 2 6.9E − 2 2.2E − 1 5.1E − 1 67.0

HT1− 16∗ 1.8E − 2 5.6E − 2 2.1E − 1 4.1E − 1 703.0

W1− 2∗ 1.4E − 3 6.0E − 2 1.9E − 1 4.2E − 1 3.0

Tabela 1: Resultados Numericos

execucao ficaram em torno de 20 seg. para 2 estados, um minuto para 4 estados e 4 minu-tos para 8 estados. No presente trabalho, os tempos de execucao (a menos de alguns casosque indicam problemas na convergencia) oscilaram em torno de um segundo para 2 estados,entre 6 e 15 segundos para 4 estados e em torno de 1 minuto para 8 estados. O computa-dor utilizado em [Bobbio (1992)][Bobbio (1992a)][Bobbio (1992b)] foi um IBM-RISC 6000enquanto que neste trabalho foi utilizado um IBM-PC Pentium 133 Mhz. Percebe-se quenos dois casos o tempo de convergencia aumenta com o numero de estados.

5 Comentarios Finais

Uma boa quantidade de distribuicoes pode ser aproximada por distribuicoes do tipo fase.Este resultado possibilita a utilizacao de ferramentas de modelagem desenvolvidas para oestudo de confiabilidade de sistemas reais. Os metodos de estimacao dos parametros dadistribuicao do tipo fase apresentados em [Bobbio (1992)] e [Carvalho (1991)] necessitam daobtencao de amostras da funcao a ser aproximada. Esta exigencia, somada a complexidadedas formas analıticas para a determinacao dos parametros da distribuicao PH, torna osreferidos metodos computacionalmente lentos. O metodo proposto neste trabalho obtem osparametros de uma forma mais direta. Por este motivo nota-se uma reducao em relacaoaos tempos de execucao apresentados em [Bobbio (1992a)]. Os resultados obtidos para afuncao objetivo, assim como a avaliacao grafica realizada mostram claramente a validade ea utilidade do trabalho apresentado, pois na maioria dos casos a funcao objetivo posui umvalor bem pequeno e os graficos coincidem perfeitamente. Este trabalho mostra que, pelomenos para os casos tratados, a funcao de distancia estocastica e mais facilmente tratavelque a funcao de verossimilhanca utilizada em [Bobbio (1992)] e [Carvalho (1991)]. Alemdisso, mostra que as distribuicoes PH acıclicas sao eficientes na aproximacao de algumas



distribuicoes que possuem a curva de densidade suave e derivavel. Sua utilizacao para apro-ximar distribuicoes como a uniforme ou histogramas ainda deve ser melhor estudada porque,principalmente no caso da distribuicao uniforme, muitos estados devem ser utilizados parauma boa aproximacao, o que exige uma otimizacao do programa.

Referencias

Bobbio, A. e Cumani, A (1992), ML estimation of parameters of a PH distribution intriangular canonical form. Computer Performance Evaluation, (2):33–45, Sept. 1992.

Bobbio, A. e Telek, M (1992a), Parameter estimation of phase type distributions. In:European Meeting of Statisticians, 20., Bath, UK, Sept. 14-18, 1992a, RT 423.

Bobbio, A. e Telek, M (1992b), A benchmark for PH estimation algorithms: results foracyclic-PH, Nov. 1992b.

Carvalho, S.V. (1991), Modeles stochastiques appliques a l’optimisation de laperformance et de la surete de fonctionnement des systems de production. (DoctoralThesis) – Universite Paul Sabatier, Toulouse, France, Nov. 1991.

Cox, D. R. (1955), A use of complex probabilities in the theory of stochastic processes.In: Cambridge Phil. Society, 51:p. 313–319, 1955 Proceedings.

Cumani, A. (1982), On the canonical representation of homogeneous Markov processesmodelling failure-time distributions. Microeletronics and Reliability , (22):583–602, 1982.

Lima, L.G.F. e Carvalho, S.V. (1994), Statistical modeling and validation in the use of

the method of stages. In: 9eme Colloque International de Fiabilite e Maintenabilite, LaBaule, France, mai 30 – juin 3, 1994. Anais. p. 557–562.

Miranda, M.N. (1996), Aproximacao de Distribuicoes de ProbabilidadeNao-Exponenciais por Distribuicoes do Tipo Fase. (dissertacao de mestradoComputacao Aplicada) – Instituto Nacional de Pesquisas Espaciais, Sao Jose dosCampos, SP, Set. 1996.

Neuts, M.F. (1981), Matrix-geometric solutions in stochastic models - an algorithmicapproach. London, UK, John Hopkins Press University, 1981.

Ou, J., Li, J. e Ozekici, S. (1996), Approximating a CDF by generalizedhyperexponential distributions. To appear in Probability in the Engineering andInternational Science, 1996.

Singh, C., Billinton, R. e Lee, S.Y. (1977), The method of stages for non-Markovmodels. IEEE Transactions on Reliability ,R-26,(2): 1977.


Documents

Aproxima˘c~ao de Distribui˘c~oes de Probabilidade N~ao-Exp ... fileos quais a hip otese de distribui˘c~ao exponencial dos tempos e essencial [Carvalho (1991)]