M/G/Infinity Service Distribution

Part of “ESTIMATION OF A HIDDEN SERVICE DISTRIBUTION OF AN M/G/∞ SYSTEM”

This article was my first thesis topic. My advisor Richard Barlow said it would not do as a thesis, because it was not publishable. Neither of us recognized its potential for estimation of reliability, actuarial rates, and survivor functions. In 1989 at Apple Computer Service, Mike Johanns suggested I do a literature search on “M/G/∞ service systems” and “statistics.” We had data on part return counts per month and wanted to estimate computer part reliabilities to estimate reliability, forecast demands, and recommend stock levels for spare parts. Mike visualized computer part lives as service times in M/G/∞ self-service systems. We also knew part gozintos (which parts go into which computers and how many); I had to use industry publications for computer sales counts. The only hit was this article…

The publisher kindly grants authors permission to reprint part of their articles. This part is from George, L. L. and Agrawal, A. C. (1973), Estimation of a hidden service distribution of an M/G/∞ system, Naval Research Logistics, 20: 549–555. doi: 10.1002/nav.3800200314, http://onlinelibrary.wiley.com/doi/10.1002/nav.3800200314/abstract.

ABSTRACT

The maximum likelihood estimator of the service distribution function of an M/G/∞ service system is obtained based on output observations. This estimator is useful when observation of each customer may be impossible. The estimator is compared with the empirical distribution function based on a sample of service times and found to have drawbacks though each estimator may have applications in special circumstances.

1. INTRODUCTION

Suppose customers arrive at a service system at instants T1,T2,...,Tn, where {Tk } is a stationary Poisson process with rate parameter λ customers per unit time. Each customer is served upon arrival and there are sufficient servers. Service times are independently and identically distributed with some unknown distribution function . These conditions describe the M/G/∞ service system. They are often found in self-service systems. It may be necessary to estimate the unknown service distribution. Direct observations on the service time for each customer may be impossible. An example may be cars entering a freeway where the distribution function of the time spent by cars on the freeway is to be estimated. A similar situation may also exist in a store where it may not be possible to follow each customer through the store. The service time distribution is hidden, and estimation must be based on information other than a sample of service times.

2. MAXIMUM LIKELIHOOD ESTIMATOR OF THE HIDDEN SERVICE DISTRIBUTION WHEN λ IS KNOWN AND OBSERVATIONS ON OUTPUT TIMES ARE AVAILABLE

Mirasol [3] shows that the output of an M/G/∞ service system is a nonstationary Poisson Process with

(2.1) P[Number of departures in (0,t) = n|system initially empty] = 

exp[–λ∫G(s)ds](λ∫G(s)ds)n/n!

for n = 1,2,.., where G(s) is the common service time distribution function, λ is the Poisson arrival rate, and the integrals are from 0 to t. The intensity function of this time dependent process, λG(t), is both nonnegative and nondecreasing and is bounded above by λ the Poisson arrival rate. The likelihood function for a nonstationary Poisson Process with  as the times of occurrence of events is given by the joint density function s

(2.2) f(t1, t2,...,tn; λ(t)) = P[Observing events at t1, t2,...,tn; λ(t)] = 

L[t1, t2,...,tn; λ(t)] = ∏[λ(tk)]exp[–∫λ(s)ds)

where λ(.) is the intensity function of the Poisson events, the product is over k = 1,2,...,n, and the integrals are from 0 to tk. The first step in the problem under study involves finding a function λ(t), for nonnegative t, which maximizes the likelihood function given by equation (2.1) for fixed t1, t2,...,tn under the condition that λ(t), for nonnegative t, is nonnegative and nondecreasing. The maximum likelihood estimator of λ(t), satisfying these conditions has been obtained by Boswell [1] as,

(2.3) λhat = 0 if 0 ≤ t < t1; min{M, λhat(tk)} if tk ≤ t < tk+1, k = 1,2,...,n–1;M < if t ≥ tn}

where

{2.4) λhat(tk) = max1 ≤ α ≤ k mink ≤ β ≤ n {(β–α+1)/(aα+aα+1+...+aβ)}

and aα = tk+1–tk, k = αk, αk+1,...,β.

It may be noted that, in the absence of an upper bound M on the value of λ(t), the solution obtained will carry no meaning as (2.2)can be made arbitrarily large by setting λ(t)= ϵ > 0 for t < tn and setting λ(tn) arbitrarily large. Therefore, let λ(t) ≤ M for some fixed positive number. 

The maximum likelihood estimator  for the function λ(t), t > 0 may be used to estimate,λG(t) ≥ 0 from output observations of an M/G/∞ system during some interval [0, T], T > t. This will give an estimate of λG(t) for t∊[0,TJ. To obtain estimates of λG(t) for small t, the output process should be observed for small t. For large values of t, the output becomes a stationary Poisson process at rate of λ. For large values of t, G(t) is estimated as 1.0. lf the input rate λ is assumed to be known (Estimate it from input data.), and it is also assumed that the system starts empty, then the maximum likelihood estimate of the service distribution function G(t) is:

(2.5) Ĝ(t) = min[λhat(t)/λ, 1]

3. PROPERTIES OF MAXIMUM LIKELIHOOD ESTIMATOR FOR

The maximum likelihood estimator of  is a step function λG(t)  with jumps at output times T1≤T2≤,...,≤Tn . The first nonzero value or the estimate of G(t) occurs at or after  giving no information about G(t) for t < T1. This limitation may be removed by taking observations on N repeated runs of the service system starting empty. The ordered output times for all runs are used in calculating the estimator of G(t). Its maximum likelihood estimator is, 

(3.3) ĜN(t) = min[λhat(t)/Nλ, 1].

Marshall and Proschan [3] prove strong consistency of the maximum likelihood estimate of a distribution function with an increasing failure rate may be applied to show that the maximum likelihood estimator of an increasing distribution function G(t) is strongly consistent at the points of continuity; i.e., Ĝ(t;N) = G(t) with probability 1 for a sufficiently large number of repeated observations N on the service system output starting empty. This may be done because the failure rate function r(t) = 

f(t)/(1–F(t))  for an increasing failure rate distribution function F(t) corresponds to a nondecreasing intensity function λ(t) of a nonstationary Poisson process. In fact λ(t) is the failure rate function of the distribution function of the event times conditional on previous event times. The maximum likelihood estimate of λ(t) based on event times of a nonstationary, nondecreasing intensity Poisson process is the same as the maximum likelihood estimator of the failure rate function r(t) from a nondecreasing failure rate distribution.

4. NUMERICAL RESULTS AND COMPARISONS

The maximum likelihood estimate of the hidden service distribution function G(x) was obtained for simulated operation of an M/M/∞ system for various arrival rates l and service rate μ. The results shown in Figure 1 correspond to an arrival rate of λ=1 customers per minute and exponential service at rate μ= 0.1 customers/min. Simulation was carried out for five runs, each consisting of 50 observations. The estimated values  are plotted against output times . The empirical distribution function and an exponential distribution function for the service times are also plotted for the purpose of comparing the simulated results. It can be seen that the estimated distribution function is close to the empirical and the actual distribution function.

[Under "Files, Workbooks, Etc." you will find files named npmle.* that implement the estimator in this article. Open npmle.nb in Mathematica or execute NPmle.cdf using http://www.wolfram/com/cdf-player. If there is a problem, contact pstlarry@yahoo.com. Nov. 10, 2016]  

Figure 1. Maximum Likelihood Estimate (MLE)

REFERENCES

[1] Boswell, M. T., Estimation and Testing Trend in a Stochastic Process of Poisson Type," The Annals of Mathematical Statistics, 37,  1564-1573 (1966).

[2] Gumbel, E. J., Statistics of Extremes, (Columbia University Press, New York, 1968).

[3] Marshall, A. W. and F. Proschan, "Maximum Likelihood Estimation for Distributions with Monotone Failure Rate," The Annals of Mathematical Statistics, 36, 69-77 (1965)

[4J Mirasol, N. M., The Output of an M/G/∞ Queuing System is Poisson," Operations Research, 11, 282-284, (1963)