Approximating general distributions

Figure 1.2: An example of Markov chain modeling: an M/M/1/FCFS queue. The system is modeled as a Markov chain, and the analysis of the Markov chain gives (mean, variance, etc. of) the response time of the system. Here, jobs arrive according to a Poisson process with rate $\lambda$ (i.e., the interarrival time between two consecutive job arrivals has an exponential distribution with rate $\lambda$). The jobs are served in the order of their arrivals (first-come-first-served, FCFS). The service demand of a job has an exponential distribution with rate $\mu$.

$\Longrightarrow$ modeling

$\Longrightarrow$ analysis

response time

Typically, a first step in the analysis via computational probability is to model the behavior of the system as a Markov chain. (For an introduction to Markov chains, we refer readers to [169,167,210].) By analyzing the Markov chain, we can understand the performance of the system, for example with respect to the mean response time^1.1 (see Figure 1.2). Modeling as a Markov chain is possible when system parameters such as service demand (time needed to complete a job) and interarrival time (time between two consecutive arrivals of jobs) are exponential random variables or some combinations of exponential random variables (for example, a sum of exponential random variables)^1.2. However, these system parameters are not usually given as combinations of exponential random variables, but they are rather given as some general probability distributions. Thus, an important step in modeling system behavior as a Markov chain is to map these general probability distributions into some combinations of exponential distributions. Here, we face a fundamental problem in Markov chain modeling.

How can we map a general distribution into a combination of exponential distributions?