Student Solutions Manual for Markov Processes for Stochastic Modeling (eBook)

Markov Processes for Stochastic Modeling 1
Oliver C. Ibe 1
University of Massachusetts 1
Lowell, Massachusetts 1
Preface 4
Chapter 1 Basic Concepts 6
1.1 A sequence of Bernoulli trials consists of choosing seven components at random from a batch of components. A selected compon... 6
1.3 A sequence of Bernoulli trials consists of choosing components at random from a batch of components. A selected component is... 6
a. The first success occurs on the fifth trial. 6
b. The third success occurs on the eighth trial. 6
c. There are 2 successes by the 4th trial, there are 4 successes by the 10th trial, and there are 10 successes by the 18th trial. 6
a. The probability that the first success occurs on the fifth trial is given by 7
b. The probability that the third success occurs on the eighth trial is given by 7
c. The probability that there are two successes by the fourth trial, there are four successes by the tenth trial and there are ten successes by the eighteenth trial can be obtained by partitioning the timeline as follows: 7
1. There are 2 successes in the first 4 trials 7
2. There are 2 successes in the next 6 trials 7
3. There are 6 successes in the next 8 trials 7
1.5 A Girl Scout troop sells cookies from house to house. One of the parents of the girls figured out that the probability that ... 8
a. What is the probability that the first house where they make their first sale is the fifth house they visit? 8
b. Given that they visited 10 houses on a particular day, what is the probability that they sold exactly six sets of cookie packs? 8
c. What is the probability that on a particular day the third set of cookie packs is sold at the seventh house that the girls visit? 8
a. The probability that the house where they make their first sale is the fifth house they visit is given by 8
b. Let the random variable denote the number of sets of cookie packs they sell given that they visited 10 houses on a particular day. Then is a binomially distributed random variable with the PMF 8
c. The probability that on a particular day the third set of cookie packs is sold at the seventh house that the girls visit is given by 9
1.7 Cars arrive at a gas station according to a Poisson process at an average rate of 12 cars per hour. The station has only one... 9
1.9 Suppose X(t) is a Gaussian random process with a mean and autocorrelation function . Assume that the random variable A is defined as follows: 9
a. 10
b. 10
a. The mean of A is given by 10
b. Since the mean of A is zero, the variance of A, that is,
1.11 Customers arrive at the neighborhood bookstore according to a Poisson process with an average rate of 10 customers per hour. Independent of other customers, each arriving customer buys a book with probability 1/8. 11
a. What is the probability that the bookstore sells no book during a particular hour? 11
b. What is the PDF of the time until the first book is sold? 11
a. The probability that the bookstore sells no book during a particular hour is given by 11
b. Let X denote the time between book sales, which is also the time until the first book is sold. Then X is an exponentially distributed random variable with the PDF 11
1.13 Three customers A, B, and C simultaneously arrive at a bank with two tellers on duty. The two tellers were idle when the th... 12
1.15 Customers arrive at a bank according to a Poisson process with an average rate of six customers per hour. Each arriving cus... 14
1.17 Bob has a pet that requires the light in his apartment to always be on. To achieve this, Bob keeps three lightbulbs on with... 15
a. Probabilistically speaking, given that Bob is about to leave the apartment and all three bulbs are working fine, what does he gain by replacing all three bulbs with new ones before he leaves? 15
b. Suppose X is the random variable that denotes the time until the first bulb fails. What is the PDF of X? 15
c. Given that Bob is going away for an indefinite period of time and all three bulbs are working fine before he leaves, what is the PDF of Y, the time until the third bulb failure after he leaves? 15
d. What is the expected value of Y? 15
a. Probabilistically speaking, given that Bob is about to leave the apartment and all three bulbs are working fine, Bob gains no... 15
b. The 3 bulbs behave as a single system with a failure rate . Thus, the time X until the first bulb fails is exponentially distributed with the PDF 15
c. Given that Bob is going away for an indefinite period of time and all three bulbs are working fine before he leaves, the rand... 15
d. The expected value of Y is 16
1.19 A 5-motor machine can operate properly if at least 3 of the 5 motors are functioning. If the lifetime X of each motor has t... 16
1.21 Cars arrive from the northbound section of an intersection in a Poisson manner at the rate of cars per minute and from the eastbound section in a Poisson manner at the rate of cars per minute. 17
a. Given that there is currently no car at the intersection, what is the probability that a northbound car arrives before an eastbound car? 17
b. Given that there is currently no car at the intersection, what is the probability that the fourth northbound car arrives before the second eastbound car? 17
a. Given that there is currently no car at the intersection, the probability that a northbound car arrives before an eastbound car is given by the probability that X is smaller than Y, which is 17
b. Given that there is currently no car at the intersection, the event that the fourth northbound car arrives before the second eastbound car can occur as follows: 18
1. The first 4 arrivals are northbound cars. The probability of this event is the probability that there are 4 successes in 4 Be... 18
2. There are 3 successes in the first 4 Bernoulli trials and the 5th trial results in a success. Thus, this event is defined by the 4th-order Pascal random variable in which the 4th success occurs in the 5th trial. 18
1.23 Let the random variable be defined as follows: 18
a. For what values of p (relative to q) is a martingale? 18
b. For what values of p is a submartingale? 19
c. For what values of p is a supermartingale? 19
a. If , which is the case when , we have that and is a martingale. 19
b. If , which is the case when , we have that and is a submartingale. 19
c. If , which is the case when , we have that and is a supermartingale. 19
1.25 Let be independent and identically distributed Bernoulli random variables with values that have equal probability of . Let and be positive integers, and define as follows: 19
a. Show that . 20
b. Show that . 20
Chapter 2 Introduction to Markov Processes 22
Chapter 3 Discrete-Time Markov Chains 24
3.1 Consider the following transition probability matrix: 24
a. Give the state-transition diagram. 24
b. Given that the process is currently in state 1, what is the probability that it will be in state 2 at the end of the third transition? 24
c. Given that the process is currently in state 1, what is the probability that the first time it enters state 3 is the fourth transition? 24
b. Given that the process is currently in state 1, the probability that it will be in state 2 at the end of the third transition, , can be obtained as follows: 24
c. Given that the process is currently in state 1, the probability that the first time it enters state 3 is the fourth transition is given by 25
3.3 A taxi driver conducts his business in three different towns 1, 2, and 3. On any given day, when he is in town 1, the probab... 25
a. Determine the state-transition diagram for the process. 26
b. Give the transition probability matrix for the process. 26
c. What are the limiting-state probabilities? 26
d. Given that the taxi driver is currently in town 2 and is waiting to pick up his first customer for the day, what is the probability that the first time he picks up a passenger to town 2 is when he picks up his third passenger for the day? 26
e. Given that he is currently in town 2, what is the probability that his third passenger from now will be going to town 1? 26
b. The transition probability matrix for the process is the following: 26
c. The limiting-state probabilities can be obtained as follows. Let denote the limiting- state probability that the process is in state k, . 26
d. Given that the taxi driver is currently in town 2 and is waiting to pick up his first customer for the day, the probability t... 27
e. Given that he is currently in town 2, the probability that his third passenger from now will be going to town 1 is , which is given by 27
3.5 Consider the following transition probability matrix: 28
a. What is ? 28
b. Obtain , the mean occupancy time of state 3 up to five transitions given that the process started from state 1. 28
3.7 Consider the following transition probability matrix: 29
a. Put the matrix in the canonical form 30
b. Calculate the expected absorption times and . 30
3.9 Let be a Markov chain with the state space and transition probability matrix 31
a. 31
b. 31
c. 31
Chapter 4 Continuous-Time Markov Chains 34
4.1 A small company has two identical PCs that are running at the same time. The time until either PC fails is exponentially dis... 34
a. Give the state-transition-rate diagram of the process. 34
b. What is the fraction of time that both machines are down? 34
a. Since each PC fails independently of the other, the failure rate when both PCs are operational is . Thus, the state-transition-rate diagram of the process is given by 34
b. Let denote the limiting state probability that the process is in state k, . Then the fraction of time that both machines are down, , can be found by using local balance equations as follows: 34
4.3 A small company has two PCs A and B. The time to failure for PC A is exponentially distributed with a mean of hours, and the... 35
a. Give the state-transition-rate diagram of the process. 35
b. What is the probability that both PCs are down? 35
c. What is the probability that PC A is the first to fail given that both PCs have failed? 35
d. What is the probability that both PCs are up? 35
a. The state-transition-rate diagram of the process is given by 35
b. Let denote the limiting-state probability that the process is in state k. If we define and , then from local balance we have that 36
c. The probability that PC A is the first to fail given that both PCs have failed is the probability that the process is in state given that both machines have failed and is given by 37
d. The probability that both PCs are up is the probability that the process is in state and is given by 37
4.5 A switchboard has two outgoing lines serving four customers who never call each other. When a customer is not talking on the... 37
a. Give the state-transition-rate diagram of the process. 37
b. What is the fraction of time that the switchboard is blocked? 37
a. The state-transition-rate diagram of the process is given by 37
b. The fraction of time that the switchboard is blocked is the limiting-state probability that the process is in state 2, which ... 38
4.7 A taxicab company has a small fleet of three taxis that operate from the company’s station. The time it takes a taxi to take... 38
a. Give the state-transition-rate diagram of the process. 38
b. What is the probability that an arriving customer sees exactly one taxi at the station? 38
c. What is the probability that an arriving customer goes to another taxicab company? 38
a. The state-transition-rate diagram of the process is given as follows: 39
b. Let denote the limiting-state probability that the process is in state k. If we define , then from local balance we obtain 39
c. The probability that an arriving customer goes to another taxicab company is the probability that the process is in state 0, which is given by 39
4.9 An assembly line consists of two stations in tandem. Each station can hold only one item at a time. When an item is complete... 40
a. Give the state-transition-rate diagram of the process. 40
b. Calculate the limiting state probabilities . 40
4.11 Consider a system consisting of two birth and death processes labeled system 1 and system 2. Customers arrive at system 1 a... 41
Chapter 5 Markovian Queueing Systems 44
5.1 People arrive to buy tickets at a movie theater according to a Poisson process with an average rate of 12 customers per hour... 44
a. What is the probability that an arriving customer does not have to wait? 44
b. What is the mean number of waiting customers at the window? 44
c. What is the mean waiting time of an arbitrary customer? 44
a. The probability that an arriving customer does not have to wait is the probability that the customer arrives when the server is idle, which is . 44
b. The mean number of waiting customers is 44
c. The mean waiting time is minutes. 44
5.3 A shop has five identical machines that break down independently of each other. The time until a machine breaks down is expo... 44
5.5 People arrive at a library to borrow books according to a Poisson process with a mean rate of 15 people per hour. There are ... 46
a. What is the probability that an arriving person will have to wait? 46
b. What is the probability that one or both attendants are idle? 46
a. The probability that an arriving person will have to wait is 46
b. The probability that one or both attendants are idle is the complement of the probability that an arriving customer has to wait, which is 46
5.7 A company is considering how much capacity K to provide in its new service facility. When the facility is completed, custome... 47
a. How much capacity should the facility have to achieve this goal? 47
b. With the capacity obtained in part (a), what is the probability that an arriving customer is lost? 47
5.9 A machine has four identical components that fail independently. When a component is operational, the time until it fails is... 48
a. What is the probability that only one component is working? 48
b. What is the probability that the machine is down? 48
a. The probability that only one component is working is , which is the probability that three components have failed and is given by 48
b. The probability that the machine is down is the probability that more than two components have failed, which is 48
5.11 Consider a birth-and-death process representing a multi-server finite population system with the following birth and death rates: 48
a. Find the , in terms of and . 49
b. Find the average number of customers in the system. 49
a. The can be obtained as follows: 49
b. The expected number of customers in the system is given by 50
5.13 Customers arrive at a checkout counter in a grocery store according to a Poisson process with an average rate of 10 custome... 50
5.15 Consider an M/M/1 queueing system with mean arrival rate and mean service time that operates in the following manner. When ... 51
a. Give the state-transition-rate diagram of the process. 51
b. What is the probability that the server is idle? 51
c. Find the actual arrival rate of customers in the system. 51
5.17 Consider an M/M/2 queueing system with hysteresis. Specifically, the system operates as follows. Customers arrive according... 52
a. Give the state-transition-rate diagram of the process. 52
b. What is the probability that both servers are idle? 52
c. What is the probability that exactly one server is busy? 53
d. What is the expected waiting time in the system? 53
5.19 Consider a finite capacity G/M/1 queueing that allows at most three customers in the system including the customer receivin... 58
5.21 Consider a queueing system in which customers arrive according to a Poisson process with rate . The time to serve a customer is a third-order Erlang random variable with parameter . What is the expected waiting time of a customer? 60
Chapter 6 Markov Renewal Processes 62
6.1 Consider a machine that is subject to failure and repair. The time to repair the machine when it breaks down is exponentiall... 62
6.3 Victor is a student who is conducting experiments with a series of lightbulbs. He started with 10 identical lightbulbs, each... 63
a. After Victor came back, what is the expected time until the next bulb failure? 63
b. What is the expected length of time between the fourth bulb failure and the fifth bulb failure? 63
a. Since the lifetimes are exponentially distributed, when Victor comes back the lifetimes of the bulbs start from scratch becau... 63
b. By the time Victor went for the break, 4 bulbs had failed. Thus, given that all 6 bulbs were still working by the time he cam... 63
6.5 A high school student has two favorite brands of bag pack labeled X and Y. She continuously chooses between these brands in ... 64
a. What is the long-run probability that she has a brand Y bag pack? 64
b. Given that she has just purchased brand X, what is the probability that t months later her last purchase was brand Y? 64
a. The long run probability that she has a brand Y bag pack is , which is given by 65
b. Given that she has just purchased brand X, the probability that t months later her last purchase was brand Y is , which is given by the matrix method as follows: 65
6.7 Consider a Markov renewal process with the semi-Markov kernel Q given by 66
a. Determine the state-transition probability matrix P for the Markov chain . 66
b. Determine the conditional distributions of the waiting time in state i given that the next state is j for all i, j. 66
6.9 Customers arrive at a taxi depot according to a Poisson process with rate . The dispatcher sends for a taxi where there are ... 66
6.11 In her retirement days, a mother of three grown-up children splits her time living with her three children who live in thre... 67
a. Obtain the transition probability functions of the process that is, obtain the set of probabilities , where is the probability that the process is in state j at time n given that it entered state i at time zero.
b. What is the occupancy distribution of the process? 68
a. To find the we proceed as follows. Recall that for a geometrically distributed random variable K with PMF , , is , where is the mean. Thus, 68
b. The occupancy distribution of the process is given by any row of the first matrix above. That is, . Alternatively it can be obtained as follows. The limiting state probabilities of the embedded Markov chain are given by 70
Chapter 7 Markovian Arrival Processes 72
7.1 Give the state transition-rate diagram for the BMAP(2)/M/1 queue with internal rates and , external arrival rates and , and service rate . Specify the infinitesimal generator, Q, if the batch size is equally likely to be 1, 2, or 3. 72
7.3 Consider an MMBP(2)/Geo/1 queueing system, which is a single-server queueing system with a second-order Markov modulated Ber... 72
7.5 Consider an m-server queueing system that operates in the following manner. There are two types of customers: type 1 and typ... 73
Chapter 8 Random Walk 76
8.1 A bag contains four red balls, three blue balls and three green balls. Jim plays a game in which he bets $1 to draw a ball f... 76
8.3 Chris has $20 and Dana has $30. They decide to play a game in which each pledges $1 and flips a fair coin. If both coins com... 76
8.5 Consider the random walk , where the are independent and identically distributed Bernoulli random variables that take on the value 1 with probability and the value with probability . 76
a. Find the probability . 76
b. What value of p maximizes ? 77
8.7 Consider an asymmetric random walk that takes a step to the right with probability p and a step to the left with probability . Assume that there are two absorbing barriers, a and b, and that the walk starts at the point k, where . 77
a. What is the probability that the walk stops at b? 77
b. What is the mean number of steps until the walk stops? 77
8.9 Consider a coordinated random walk with stay. That is, a walker can move to the right, to the left, or not move at all. Give... 81
a. Find the values of , and . 82
b. Obtain the transition probability matrix of the process and show that the process is a quasi-birth-and-death process. 82
a. The transition matrix for the three different indices is as follows: 82
b. We assume that there is a reflecting boundary at so that the state transition digram is as shown below. 83
Chapter 9 Brownian Motion and Diffusion Processes 88
9.1 Assume that X and Y are independent random variables such that and . Consider the random variables and . Show that U and V are independent with and . 88
9.3 Let be a Brownian motion with drift rate and variance parameter . What is the conditional distribution of given that ? 90
9.5 Let , where is a standard Brownian motion. Find 90
a. 90
b. 90
c. The conditional distribution of , given that 90
9.7 What is the mean value of the first passage time of the reflected Brownian motion with respect to a positive level x, where is the standard Brownian motion? Determine the CDF of . 92
9.9 Let be a standard Brownian motion, and define the process that is, is the Ornstein-Uhlenbeck process.
a. Show that is a Gaussian process. 94
b. Find the covariance function of the process. 94
1. 94
2. is a Gaussian process 94
3. 94
4. , where is a constant. In particular, . 94
Chapter 10 Controlled Markov Processes 96
10.1 A recent college graduate is presented with N job offers, one after another. After looking at an offer, she must either acc... 96
10.3 A farmer is considering the optimal course of action for his farm each year. The two options are to fertilize the farm and ... 97
10.5 Consider a salesman who has offices in two towns called town 1 and town 2. He can be in one of these towns on any particula... 100
a. Stay in each town until he makes a sale and then go to the next town. 100
b. Work in one town one day and then go to the next town the next day whether or not a sale is made. 100
Chapter 11 Hidden Markov Models 102
11.1 Consider an HMM with two states 1 and 2 and emits two symbols: A and B. The state transition diagram is shown in Figure 11.18. 102
Figure 11.18 Figure for Problem 11.1 102
a. Use the Viterbi algorithm to obtain the most likely state sequence that produced the observation sequence {ABBAB}. 102
b. Estimate the probability that the sequence {BAABA} was emitted by the preceding system. 102
11.3 Construct the profile HMM for the following variable length sequences DOR, DM, DAP, VGBLM. (Hint: Use the following alignment to identify the match, insert, and delete states.) 106
a. We define a match state to be a column that does not contain a gap. In this case, there are two match states, , which correspond to the first and last columns, one insert state, , and no delete state. 106
b. We define a match state to be a column that has less than half of its entries as gaps. In this case, there are three match states, , which correspond to the first, second, and the last columns, and one insert state and one delete state. 106
11.5 Consider a system that can be modeled by an array of 6 states labeled . Apart from state 4, which makes a transition to its... 108
Figure 11.19 Figure for Problem 11.5 109
a. What is the PMF of L? 109
b. What is the expected value of L? 109
Chapter 12 Markov Random Fields 110
12.1 Show that the Markov chain is a Markov random field. 110
12.3 For the three binary image data shown in Figure 12.9 that correspond to the Gibbs random field realizations denoted by , respectively, assume that the clique potential is defined as follows: 110
a. 111
b. 111
Chapter 13 Markov Point Processes 114
13.1 Two classes of customers arrive at Paul’s barber shop: class 1 and class 2. Class 1 customers arrive according to a Poisson... 114
a. What is the probability that no customer arrives over a two-hour period? 114
b. What is the mean time between customer arrivals at Paul’s shop? 114
c. Given that a customer has just arrived at the shop, what is the probability that the next customer to arrive at the shop is a class 2 customer? 114
a. The probability that no customer arrives over a period of 2 hours is . 114
b. The time between customer arrivals at the shop is exponentially distributed with a mean of . 114
c. There are two competing Poisson processes. Over the next time , the probability that an arrival occurs is , and the probability that the arrival is a class 2 customer is . 114
13.3 Let be a sequence of independent and identically distributed random variables with PDF , and let N be an integer-valued random variable with PMF , where N and the are independent. Consider a process in which events occur at times . 114
a. Calculate the mean, variance and s-transform of the PDF of the time of the last event. 114
b. What is the expected number of events in the interval (0, t)? 114
13.5 Passengers arrive at a train station according to a Poisson process with a rate of 25 customers per hour. It has been found... 116
Chapter 14 Markov Chain Monte Carlo 118
14.1 Consider the Weibull random variable X with the CDF where and are parameters. Obtain , where . 118
14.3 Consider the PDF given by 118