4. Consider the Markov chain X = {X} with state space S and transition probabilities Pij = { 1 ifi-i-1 " 0 otherwise for i 1 = and {0, 1, 2,...} Poo = 0, Poj = 1 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 0100 00 p0q000 P 0 q 00 00 P 09 0 P = 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 Q -4 2 2 = 3 -4 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. Minimize z = 6x + 3x2 Subject to: 1. Write the dual for each of the following primal problems: Maximize u = -5x + 2x2 Subject to: -x1+x2-2 2x + 3x2 5 X1, X2 0 Maximize u = -x + 2x2 - 3x3 x1-x2-2 Subject to: 2x1 + x2 x3 15 x2 + x3 = 10 X1, X2 0 X3 unrestricted 6x13x2 + x3 2 3x1 + 4x2 + x3 5 X1, X2, X30 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 50 X1, X2, X3 0 3. Consider the following set of inequalities. Note that x = 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). 2x + 3x 12 -3x1 + 2x2 -4 3x1-5x2 2 x unrestricted; x 0 4. Consider the following LP. Use the dual problem to show that the basic solution with (x1,x2) = (0,0) is not optimal. Explain why. Maximize z = 2x + 4x2 + 4x3 - 3x4 Subject to: x1 + x2 + x3 = 4 x1 + 4x2 + x4 = 8 X1, X2, X3, X4 0