A computer device can be either in a busy mode (state 1) processing a task, or in an idle mode (state 2), when there are no tasks to process. Being in a busy mode, it can finish a task and enter an idle mode any minute with the probability 0.2. Thus, with the probability 0.8 it stays another minute in a busy mode. Being in an idle mode, it receives a new task any minute with the probability 0.1 and enters a busy mode. Thus, it stays another minute in an idle mode with the probability 0.9. The initial state is idle. Let Xnbe the state of the device after n minutes. a) Find the distribution of X2. b) Find the steady-state distribution of Xn.
1 University of Rwanda CST STOCHASTIC PROCESSES TRIMESTER 3 Model Question-STOCHASTICS PROCESSES 1. Which of the following matrices are stochastic matrices? I) 13 13 13 1 2 0 1 2 II) 1516 116 2 3 0 2 3 III) 1 0 1 2 1 2 V I) 32 −12 1 4 3 4 (1) Solution 2. Determine which of the following matrices are transition matrices. If a matrix is not a transition matrix explain why not. (a) 0 1 3 4 1 4 (b) 12 1 1 2 0 (c) 12 13 16 1 4 1 2 2 3 Solution 3. Given the transition matrix p = 1 0 1 2 1 2 (2) with initial probability distribution p(0) = ( 1 3 , 2 3 ) . Define and find : i) p(3)21 ii) p(3) iii) p(3)2 2 Solution 4. we suppose that customers arrive at a bank counter according to a Poisson Process with rate λ = 10 per hour. Let N(t) be the number of customers in the interval [0, t]. (a) What is the probability that no customers arrive over a 15−minute time period? (b) Knowing that eight customers arrive during a given hour, what is the probability that at most two customers will arrive over the following hour? (c) Given that a customer arrived during a certain 15−minute time period, what is the probability that he arrived during the first 5 minutes of the period considered? 5. A salesman’s territory consists of three cities, A,Band C. He never sells in the same city on successive days. If he sells in city A, then the next day he sells in city B. However, if he sells in either B or C, then the next day he is twice as likely to sell in city A as in the other city. In the long run, how often does he sell in each of the cities ? Solution a) The transition matrix of the problem is as follows P = 0 1 0 2 3 0 1 3 2 3 1 3 0 (3) b) We seek the unique fixed probability vector t of the matrix P [ π1 π2 π3 ] 0 1 0 2 3 0 1 3 2 3 1 3 0 = π1 π2 π3 (4) or 2 3 π2 + 2 3 π3 = π1 π1 + 1 3 π2 = π2 1 3 π2 = π3 3 Set, say, π3 = l. Then by the third equation π2 = 3, and by the first equation π1 = 83 . Thus u = (8 3 , 3, 1). Also 3u = (8, 9, 3) is a fixed vector of P. Multiply 3u by 1/(8+9+3) = 1 20 to obtain the required fixed probability vector t = (2 5 , 9 20 , 3 20 ) = (.40, .45, .15). Thus in the long run he sells 40% of the time in city A, 45% of the time in B and 15% of the time in C 6. Let {X(t), t ≥ 0} be a birth and death process whose state space is the set {o, 1, 2} and for which λ0 = λ, λ1 = µ1 = λ 2 and µ2 = λ We consider two independent copies {X1(t), t ≥ 0} and {X2(t), t ≥ 0} of this process, and we define Y (t) = |X1(t)−X2(t)| for t ≥ 0 We can show that {Y (t), t ≥ 0} is also a birth and death process. a) Give the birth and death rates of the process {Y (t), t ≥ 0}. b) Calculate the expected value of the random variable Y (t) after two transitions if X1(0) = X2(0) = 0 c) Calculate the limiting probabilities of the processes {Y (t), t ≥ 0}. Solution 7. We consider the queuing system M/M/2/3 a) Write the balance equations of the system, and calculate the limiting probabilities πj . If λ = 2µ b) Let T be the total time that an entering customer will spend in the system. Calculate the expected value of T if µ = 1. c) Suppose that the customers form two waiting lines, by standing at random in front of either server. Calculate, with µ = 1 the average time that an arbitrary customer who enters the system, and finds two customers already present, will spend in this system if we assume that the number of customers in each queue is then a random variable having a binomial distribution with parameters n = 2 and p = 1/2. 4 Solution We consider the queuing system M/M/2/3 a) State j departure rate from j = arrival rate to j 0 λπ0 = µπ1 1 (λ+ 2µ)π1 = λπ0 + 2µπ2 2 (λ+ 2µ)π2 = λπ1 + 2µπ3 3 2µπ3 = λπ2 Then π0 = 1/7, π1 = π2 = π3 = 2/7 b) 1.2 c) 2 8. The lifetime of a certain machine is a random variable having an exponential distribution with parameter A. When the machine breaks down, there is a probability equal to p (re- spectively, 1− p) that the failure is of type I (resp., II). In the case of a type I failure, the machine is out of use for an exponential time, with mean equal to 1 µ time unit(s). To repair a type II failure, two independent operations must be performed. Each operation takes an exponential time with mean equal to 1 µ . • (a) Define a state space such that the process {X(t), t ≥ 0}, where X(t) denotes the state of the system at time t, is a continuous-time Markov chain. (b) Calculate, assuming the existence of the limiting probabilities, the probability that the machine will be functioning at a (large enough) given time instant. Solution 9. Two boys b1 and b2 and two girls g1 and g2 are t throwing a ball from one to the other. Each boy throws the ball to the other boy with probability 1/2 and to each girl with probability 1/4. On the other hand, each girl throws the ball to each boy with probability 1/4 and never to the other girl. In the long run, how often does each receive the ball? 5 Solution This is a Markov chain with state space {b1, b2, g1, g2} and the transition matrix P = 0 1 2 1 4 1 4 1 2 0 1 4 1 4 1 2 1 2 0 0 1 2 1 2 0 0 (5) We seek a fixed vector u = (x, y, z, w) of P ; (x, y, z, w)P = (x, y, z, w). Set the corresponding components of uP equal to u to obtain the system 1 2 y + 1 2 z + 1 2 w = x 1 2 x+ 1 2 z + 1 2 w = y 1 4 x+ 1 4 y = z 1 4 x+ 1 4 y = w such that x+ y + z + w = 1 Thus u = (2, 2, 1, 1)and so the unique fixed probability of P is π = (1 3 , 1 3 , 1 6 , 1 6 ) The long run, each boy receives the ball 1 3 of the time and each girl 1 6 of the time. 10. we suppose that customers arrive at a bank counter according to a Poisson Process with rate λ = 10 per hour. Let N(t) be the number of customers in the interval [0, t]. (a) What is the probability that no customers arrive over a 15−minute time period? (b) Knowing that eight customers arrive during a given hour, what is the probability that at most two customers will arrive over the following hour? (c) Given that a customer arrived during a certain 15−minute time period, what is the probability that he arrived during the first 5 minutes of the period considered? Solution 11. Customers in a certain city are continually switching the brand of soap they buy. If a customer is now using brand A, the probability he will use brand A next week is .5, that he switches to brand B is .2 and that he switches to brand C is .3. If he now uses brand B, the 6 probability he uses B next week is .6, that he switches to C is .4, and he doesn?t switch to A. If he now uses brand C, the probability he stays with C is .4, that he switches to A is .2 and to B is .4. Assuming the process is a Markov Chain, a) Find the percentage of customers using each brand of soap in the long run. b) Find the probability a customer now using brand A will be using brand B in two weeks. c) If the percentage of customers now using brand A is 30%, the percentage using brand B is 20% and the percentage using brand C is 50%, find the percentage of customers using brand C in three weeks. d) Find the probability a customer now using brand A will be using brand B in 6 weeks. Solution Let the states be ”using brand A”, ”using brand B”, and ”using brand C”. Then the transition matrix T is T = A B C A 0.5 0.2 0.3 B 0 0.6 0.4 C 0.2 0.4 0.4 (6) where the order of the states is as listed above. a) b) The answer to this question is p(2)12 , so let’s find T 2. T = 0.5 0.2 0.3 0 0.6 0.4 0.2 0.4 0.4 2 = 0.31 0.34 0.35 0.8 0.52 0.4 0.18 0.44 0.38 (7) Thus,p(2)12 = 0.34 c) Now, p0 = (.3.2.5) and, omitting the computations involved in finding p0T 3, it turns out that:p0T 3 = (0.1745 0.4454 0.3801). So in three weeks the percentage of customers using brand C is about 38%. 7 d) Here p612 is needed, so computing T 6 gives T = 0.160599 0.456266 0.383135 0.150632 0.46048 0.38532 0.155002 0.460636 0.384362 Thus the probability a customer now using brand A will be using brand B in 6 weeks is p(6)12 = 0.456266 12. Suppose that customers arrive at n counter in accordance with Poisson process with mean rate 2 per minute. The interval between any 2 successive arrival follows exponential distri- bution with mean 1/λ = 1/2 minute compute the probability that the interval between 2 successive arrival is I) More than 1 minute II) 4 minutes or less III) Between 1 and 2 minutes. Solution 13. A computer device can be