SOLUTIONS TO SMS
Department of Computer Science and Engineering
1a. Explain Poisson distribution.
• Solution:
• In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate and independently of the time since the last event.
• It is a mathematically simple distribution
• Both the mean and variance of a Poisson distribution are equal to µ. The formula for the Poisson probability mass function is
• is the shape parameter which indicates the average number of events in the given time interval.
beeps is known to be in accordance with a Poisson distribution with a mean 2 per hour. Find the probability of 3 beeps in the next hour. Solution:
The probability of three beeps in the next hour is given by the equation:
Substituting x=3 and lamda=2 in above equation, we get p(3,2) =0.18
2a. Explain normal distribution.
• Solution:
• The normal distribution is considered the most prominent probability distribution in statistics.
• The normal distribution is pattern for the distribution of a set of data which follows a bell shaped curve. This distribution is sometimes called the Gaussian distribution
• Normal distributions are symmetric with scores more concentrated in the middle than in the tails.
• The general formula for the probability density function of the normal distribution is
• The normal cdf is
• The result, p, is the probability that a single observation from a normal distribution with parameters µ and σ will fall in the interval (-∞ x].
• The standard normal distribution has µ = 0 and σ = 1.
2b. The time to pass through a queue to begin self service at a cafeteria has been found to be N(15,9). Find the probability that an arriving customer waits b/w 14 to 17 minutes. Solution:
The probability that an arriving customer waits b/w 14 to 17 minutes is computed as follows
:-
P(14<=X<=17)=F(17) –F(14) = φ((17-5)/3) - φ((14-15)/3)
= φ(0.667)- φ(-0.333)
=0.3780
The probability that an arriving customer waits between 14 and 17 minutes is 0.3780
3.What are the primary Long-run measures of queuing systems? Explain L and Lq with an example. Solution:
The primary long-run measures of performance of queuing systems are the long-run time-average number of customers in the system (L) and in the queue (LQ), the long-run average time spent in system (w) and in the queue (wQ) per customer, and the server utilization, or proportion of time that a server is busy (ρ). The term "system” usually refers to the waiting line plus the service mechanism, but, in general, it can refer to any subsystem of the queuing system; whereas the term "queue" refers to the waiting line alone. Other measures of performance of interest include the long-run proportion of customers who are delayed in queue longer than to time units, the long-run proportion of customers turned away because of capacity constraints, and the long-run proportion of time the waiting line contains more than ko customers.
4a. Explain with steady state behavior of single server queues with Poisson arrivals and Unlimited capacity. Solution:
For the infinite population models, the arrivals are assumed to follow a Poisson process with rate(lamda) arrivals per time unit-that is, he inter arrival time are assumed to be exponentially distributed with mean (1/lamda).Service times may be exponentially distributed(M) or arbitrarily(G).The queue discipline will be FIFO. Because of the exponential-distributional of the arrival process, these models are called Markovian models.
A queuing system is said to be statistical equilibrium, or steady state, if the probability that the
P(L(t)=n)=Pn(t)=Pn
Is independent of time t. Two properties-approaching statistical equilibrium from any starting state, and remaining in statistical equilibrium once it is reached- are characteristic of many stochastic models. On the other hand, if the analyst were interested in the transient behavior of a queue over a relatively short period of time ad were given some specific initial condition, the result to be presented here would be inappropriate, A transient mathematical analysis or, more likely, a simulation model would be the chosen tool of analysis.
4b. Widget making machines malfunction apparently at random and then require a mechanic’s attention. It is assumed that malfunction occur according to a Poisson process at the rate of (lambda)=1.5 per hour. Repair times of single machine is an avg of 30 minutes with a standard deviation of 20 minutes. Find the steady state time average number of broken machines. Solution:
The mean service time= 1/µ =1/2 hour The service rate is µ= 2 per hour.
Also , ơ2=202 minutes2 =1/9 hours2
The customers are the widget makers, and the appropriate model is the M/G/1queue, because only the mean and variance of service times are known, not their distribution.
The proportion of time the mechanic is busy is =(lamda)/ µ=1.5/2=0.75
Also, the steady state time average number of broken machine therefore is given by,
= 0.75+1.625=2.375 machines.
5a. Define random numbers. Explain the statistical properties of random numbers.
Solution:
A random number is a number chosen as if by chance from some specified distribution such that selection of a large set of these numbers reproduces the underlying distribution.
The statistical properties of random numbers are:-
1. The routine should be fast, individual computations are inexpensive, but simulation may require many hundreds of thousands of random numbers. The total cost can be managed by selecting a computationally efficient method-number generation.
2. The routine should be portable to different computers, and ideally to different programming languages. This is desirable so that the simulation program produces the same results wherever it is executed.
3. The routine should have a sufficiently long cycle. The cycle length or period, represents the length of the random-number sequence before previous numbers begin to repeat themselves in an earlier order. Thus, if 10,000 events are to be generated, the period should be many times that long. A special case of cycling is degenerating. A routine degenerates when the same random numbers appear repeatedly. Such an occurrence is certainly unacceptable. This can happen rapidly with some methods.
4. The random numbers should be replicable. Given the starting point (or conditions), it should be possible to generate the same set of random numbers, completely independence of the system that is being simulated. This is helpful for debugging purposes and is a mean of facilitating comparisons between systems. For the same reasons, it should be possible to easily specify different starting points, widely separated, within the sequence.
5. Most important, and as indicated previously, the generated random numbers should closely approximate the ideal statistical properties of uniformity and independence.
5b. Explain the combined linear congruential generator. Solution:
One fruitful approach is to combine two or more multiplicative congruential generators in such a way that the combined generator has good statistical properties and a longer period.
If Wi, 1 , Wi , 2. . . , W i,k are any independent, discrete-valued random variables (not necessarily identically distributed), but one of them, say Wi, 1, is uniformly distributed on the integers 0 to mi — 2, then
Wi= mod m1 – 1 is uniformly distributed on the integers 0 to mi — 2.
To see how this result can be used to form combined generators, let Xi,1, X i,2,..., X i,k be the i th output from k different multiplicative congruential generators, where the j th generator has prime modulus mj, and the multiplier aj is chosen so that the period is mj — 1. Then the j'th generator is producing integers Xi,j that are approximately uniformly distributed on 1 to mj - 1, and Wi,j = X i,j
— 1 is approximately uniformly distributed on 0 to mj - 2. L'Ecuyer [1988] therefore suggests combined generators of the form
k=Σ(-1) j-1 X i,j mod m1 – 1 j=1 with R i = { Xi/m1 , Xi > 0 m1 -1 ⁄m1 Xi = 0
Notice that the " (-1)j-1 "coefficient implicitly performs the subtraction X i,1-1; for example, if k = 2, then (-1)°(X i 1 - 1) - ( - l ) l ( X i 2 - 1)=Σ2 j=1( -1)
j-1 X i,j
The maximum possible period for such a generator is
P= (m1 -1)(m2 - l ) - - - (mk - 1)
------
2 k-1
6a. Lead times are found to be exponentially distribute with mean 3.7 days. Generate 4 lead times from this distribution, given random numbers (0.1306,0.0422,0.6597,0.7965,0.7696) Solution:
Procedure for generating random variates for the exp dist. Using inverse transform technique.
1. Compute cdf of the desired random variable X.
2. Set F(X) = R on the range of X i.e., [ 1 – e-λx] on the range x >= 0
[Note :- X is a random variable with exp distribution, hence, R is also a random variable with exp distribution over the interval [0,1] ] 3. Solve the eqn F(X) = R in terms of R. 1 – e-λx = R e-λx = 1 – R -λX = ln(1 – R)
X = -1/λ ln (1 – R)
4. Generate random numbers R1, R2, R3….. and compute random variates X1, X2, X3,….. using the above eqn.
i / 1 / 2 / 3 / 4 / 5Ri / 0.1306 / 0.0422 / 0.6597 / 0.7965 / 0.7696
Xi / 0.1400 / 0.0431 / 1.078 / 1.592 / 1.468
6b. The sequence of numbers 0.54,0.73,0.98,0.11 and 0.68 has been generated. Use Kolmogorov-Smirnov test with α=0.05 to learn whether the hypothesis that the numbers are
uniformly distributed on the interval [0,1] can be rejected. Dα=0.565 Solution:
R (i) / 0.11 / 0.54 / 0.68 / 0.73 / 0.98i/N / 0.20 / 0.4 / 0.6 / 0.8 / 1.0
i/N –R(i) / 0.09 / - / - / 0.07 / 0.02
R(i)-(i-1)/N / 0.11 / 0.34 / 0.28 / 0.13 / 0.18
D+ = max(0.09,0.07,0.02)=0.09
D-=max(0.11,0.34,0.28,0.13,0.18)=0.34
D=max(D+,D-)=max(0.09,0.34)=0.34 Dα=0.565 given
We observe that D<Dα from the above computations. Therefore conclude that no difference has been detected between the true distribution of (R1,R2…..RN) and the uniform distribution.
7. For the following sequence can the hypothesis that the numbers are independent can be rejected on the basis of length of runs up and down when α=0.05.
Solution:
Same as in Page 234, Eg.7.8 Its done for 30 samples..Problem requires it for 50 samples. Procedure remains the same.