Question:
Buses arrive at a bus station with i.i.d. interarrival times following an exponential distribution with intensity ?. Alice arrives at the bus station at a deterministic time t. a. (4pts) What is the expected waiting time for Alice until next bus comes? b. (6pts) Let ? be the time when the last bus arrived before time t. Show that t ? ? follows an exponential distribution with parameter ?. c. (6pts) Show that the expected interarrival time between the last bus which arrived before time t and the first bus which arrives after time t is 2 ? . Explain why it is different from the general expected interarrival time 1 ? .
4. Consider the Markov chain X" = {X,} with state space S = {0, 1, 2, ...} and transition probabilities 1 ifj=i-1 Puj = 10 otherwise , for i 2 1 and Poo = 0, Poj = for j > 1. (a) Is this Markov chain irreducible? Determine the period for every state. (b) Is the Markov chain recurrent or transient? Explain. (c) Is the Markov chain positive recurrent? If so, compute the sta- tionary probability distribution. (d) For each state i, what is the expected number of steps to return to state i if the Markov chain X starts at state i? 5. Consider a Markov chain X = {X} with state space S = {0, 1, 2, ...} and transition probability matrix 0 1 0 0 P 0 0 P = O p 0 q 0 0 . . . 0 0 P 0 4 0 Here p > 0, q > 0 and p+q =1. Determine when the chain is positive recurrent and compute its stationary distribution.2. (10 points) Consider a continuous-time Markov chain with the transition rate matrix 4 2 2 Q = 3 1 5 0 -5 (a) What is the expected amount of time spent in each state? (b) What is the transition probability matrix of the embedded discrete-time Markov chain? (c) Is this continuous-time Markov chain irreducible? (d) Compute the stationary distribution for the continuous-time Markov chain and the em- bedded discrete-time Markov chain and compare the two.1. Write the dual for each of the following primal problems: Maximize u = -5x1 + 2x2 Minimize z = 6x1 + 3x2 Subject to: Subject to: -xitx2 s -2 6x1 - 3x2 + X3 2 2 2x1 + 3x2 $5 3x1 + 4x2 + X3 25 X1, X2 2 0 X1,X2,X3 20 Maximize u = -x1 + 2x2 - 3x3 Subject to: X1 - X2 5 -2 2x1 + X2 - X3 2 15 Xz + X3 = 10 X1, X2 2 0 X3 unrestricted 2. Find the optimal value of the objective function for the following problem by inspecting only its dual. Do not solve the dual by the simplex method. Explain how you found the answer. Minimize z = 10x1 + 4x2 + 5X3 Subject to: 5x1 - 7x2 + 3x3 2 50 X1,X2, X3 20 3. Consider the following set of inequalities. Note that X1 = X2 = 0 is not a feasible solution. A feasible solution can be found by using the trivial objective function (maximize z = x1 + X2) with the constraints and then solving the dual, from which a solution for the set of inequalities can be found. Find a feasible point with this method (show your work). 2x1 + 3x2 $ 12 -3x1 + 2x2 5-4 3x1 - 5x2 $ 2 x1 unrestricted; x2 2 0 . Consider the following LP. Use the dual problem to show that the basic solution with (x1, *2) = (0,0) is not optimal. Explain why. Maximize z = 2x1 + 4x2 + 4x3 - 3x4 Subject to: X1 + X2 + X3 = 4 X1 + 4x2 + X4 = 8 X1, X2, X3, X4 2 0
