Week10 practice 1

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
This is part of probstat.

Generating Poisson and exponential random variables

Most programming languages provide library functions for generating uniform continuous random variable in the range (0,1). However, they often do not provide any functions for generating more complicated types of random variables.

Poisson random variables

Given a uniform random variable in (0,1), we can generate Poisson and exponential random variables based on their cumulative distribution function. Here is a simple idea. Let's consider, as an example, generating a Poisson random variable with parameter . Using the definition of Poisson random variables, we have its pmf as in the following list (for the first few values):

  • f(0) = 0.006738
  • f(1) = 0.033690
  • f(2) = 0.084224
  • f(3) = 0.140374
  • f(4) = 0.175467
  • f(5) = 0.175467
  • f(6) = 0.146223
  • f(7) = 0.104445
  • f(8) = 0.065278
  • f(9) = 0.036266

With this we can compute cdf :

  • F(0) = 0.006738
  • F(1) = 0.040428
  • F(2) = 0.124652
  • F(3) = 0.265026
  • F(4) = 0.440493
  • F(5) = 0.615961
  • F(6) = 0.762183
  • F(7) = 0.866628
  • F(8) = 0.931906
  • F(9) = 0.968172
  • ...
  • F(17) = 0.999995
  • F(18) = 0.999999
  • F(19) = 1.000000
  • F(20) = 1.000000

Note: note that F(9) on the list above is not even close to 1, so in order the generate the Poisson r.v., we need to generate up to, say, F(19) or F(20).

It is not hard to use this list together with a uniform random variable in range (0,1) to generate a Poisson random variable. Suppose that we generate a uniform r.v. and get 0.3. Note that that value falls in the range F(3) and F(4) in the above list. We then say that our Poisson r.v. is 4.

Exponential random variables

For exponential random variables, it is much easier because we have a simple closed form for its cdf. We know that for an exponential random variable X with parameter , its cdf is given by

Given a uniform random variable in the range (0,1), U, we can find x such that F(x) = U by taking the inverse, i.e.,

Exercises

Write functions that generate Poisson and exponential random variables for given parameters. For each of these items, generate 200 instances of the specified random variable, and plot its histogram.

  • Poisson random variable with parameter
  • Poisson random variable with parameter
  • Poisson random variable with parameter
  • Poisson random variable with parameter
  • Poisson random variable with parameter
  • Exponential random variable with parameter
  • Exponential random variable with parameter
  • Exponential random variable with parameter
  • Exponential random variable with parameter
  • Exponential random variable with parameter

Simulations

We consider a simple queue system. We are a restaurant manager (say, in โรงอาหารวิศวะ). We has one server who can deliver 5 dishes per minute. We want to find statistics on

  • average queue size, and
  • maximum queue size over time,

when customers come in at the specified rates.

We will perform simulations using Poisson random variables and exponential random variables. Both methods are described below. For each approach, you should perform simulations for various customer arriving rates of 2, 3, 4.5, 4.8, 4.9, 5, 5.1, 5.5, 6, and 7 customers per minute.

Simulation with Poisson random variables

This will be a discrete simulation. For each customer rate , you can generate a random sequence of number of customers arriving at the restaurant in each minute.

For example, when , you might get the following sequence

  • 3, 4, 7, 4, 5, 6, 2, 5, 4, 7, ...

You can generate 10,000 of these random numbers. Then you can feed it in a simulator that acts like a server. For each minute, it serves 5 customers in the queue. The number of customer in a queue is a given minute is the number remaining from the last minute plus the number arriving at this minute. If the number of customers is at most 5, all of them is gone in the next minute; otherwise, there will be some unserved customer and they will be in the queue for the next minute.

The sequence above results in the following table:

minute 1 2 3 4 5 6 7 8 ...
new customers 3 4 7 4 5 6 2 5 ...
queue size (beginning) 3 4 7 6 6 7 4 5 ...
queue size (end) 0 0 2 1 1 2 0 0 ...

In this case, the average queue size (up to the values shown in the table) is (3+4+7+6+6+7+4+5)/8 = 5.25, and the max queue size is 7.

Simulation with exponential random variables

Exponential random variables model the "wait" period between events. Suppose that we consider having customers arriving at rate customers per minute. Generating an exponential r.v. with parameter , you get:

  • 0.047, 0.418, 0.153, 0.171, 0.287, 0.082, ...

These are periods between two customers. From that, we have that customers arrive at time

  • 0.047, 0.465, 0.618, 0.789, 1.076, 1.158, ...

Since our server can deliver 5 dishes per minute, the server takes 0.2 minutes to complete any request. Using the above arriving times, we can run our simulation like this:

  • Customer 1, arriving at 0.047: server is free, get served at 0.047, done at 0.047 + 0.2 = 0.247
  • Customer 2, arriving at 0.465: server is free, get served at 0.465, done at 0.465 + 0.2 = 0.665
  • Customer 3, arriving at 0.618: server is not free (free at 0.665), get served at 0.665, done at 0.665 + 0.2 = 0.865
  • Customer 4, arriving at 0.789: server is not free (free at 0.865), get served at 0.865, done at 0.865 + 0.2 = 1.065
  • Customer 5, arriving at 1.076: server is free (because 1.065 < 1.076), get served at 1.076, done at 1.076 + 0.2 = 1.276
  • Customer 6, arriving at 1.158: server is not free (free at 1.276), get served at 1.276, done at 1.276 + 0.2 = 1.476
  • and so on ...

You can measure the average wait time (average of 0, 0, (0.665 - 0.618), (0.865 - 0.789), 0, (1.276 - 1.158)), and the maximum wait time for all customers (0.118 = 1.276 - 1.158).

Optional: For average queue size and max queue size, you will have to use more accurate simulation mechanism, i.e., you may have to actually maintain a queue.

Relationships