Practice Quiz IAnswers to Practice Quiz IMATH 56A: STOCHASTIC PROCESSESQUIZ FROM 2006From the [new, 2008] syllabus: Quizzes will be given [every] 2 or 3 weeks. Studentsregistered in the class should form groups of 2, 3 or 4 to work on these problems in class,solve them and help other students in the group to understand them. Students auditingthe class can also participate in a way that I will discuss in class. Each group should handin their answers signed by all members of the group. There is a special rule for Quiz 2.You cannot form the same groups as in Quiz 1. You must form a new group for Quiz 2.Afterwards there are no rules, except that the group is limited to at most 4.These are old quizzes from 2006 with answers.This first quiz is for practice and does not count. The purpose is for me to see what youcan do and for you to see what kinds of questions I think of.Practice Quiz I1. Give an example of a Markov chain that has two recurrent classes and two transientclasses.2. (Random walk with reflecting walls) Suppose there are four states 1, 2, 3, 4 in a line.If you are at one of the endpoints you always move inward in the next step. If you are atone of the inside points you move left with probability 1/3 and right with probability 2/3.(1) What is the transition matrix? (Put a dot in place of each 0 in the matrix.)(2) In the long run how much time is spent in each state? What formula did you use?(3) What is the expected length of time between visits to state 3? What is the formula?(4) What is the period of this Markov chain? How is this reflected in your answer to (2)?3. A mouse is put through a maze over and over. At the end there are two trap doors.One gives a big reward, the other doesn’t. The reward is placed 3/4 of the time on the leftand 1/4 of the time on the right according to a random number generator.The mouse somehow know that the reward is more often on one side than the other. Hepicks one of the two sides at random and keeps picking that side until he is wrong twice ina row. Then he switches to the other side and continues.(1) Is this a Markov chain? Explain why or why not. If it isn’t then change the assump-tions or set up so that it becomes a Markov chain.(2) What are the states of your chain? (Fewer is better.)(3) What is the transition matrix? (Put a dot in place of each 0 in the matrix.)1Answers to Practice Quiz I1. Give an example of a Markov chain that has two recurrent classes and two transientclasses.Here is one answer:1p←− 1 → 2q−→ 3where p, q are both positive.2. (Random walk with reflecting walls) Suppose there are four states 1, 2, 3, 4 in a line.If you are at one of the endpoints you always move inward in the next step. If you are atone of the inside points you move left with probability 1/3 and right with probability 2/3.(1) What is the transition matrix? (Put a dot in place of each 0 in the matrix.)P =· 1 · ·1/3 · 2/3 ·· 1/3 · 2/3· · 1 ·(2) In the long run how much time is spent in each state? What formula did you use?The proportion of time spent at the states is given by the invariant distributionπ =114,314,614,414This is the left eigenvector corresponding to eigenvalue 1, i.e., πP = π(3) What is the expected length of time between visits to state 3? What is the formula?The expected time between visits to 3 is 1/π(3) = 14/6 = 7/3.(4) What is the period of this Markov chain? How is this reflected in your answer to(2)? The period is 2. So, half the time is spent in states 1,3:114+614=123. A mouse is put through a maze over and over. At the end there are two trap doors.One gives a big reward, the other doesn’t. The reward is placed 3/4 of the time on the leftand 1/4 of the time on the right according to a random number generator.The mouse somehow know that the reward is more often on one side than the other. Hepicks one of the two sides at random and keeps picking that side until he is wrong twice ina row. Then he switches to the other side and continues.(1) Is this a Markov chain? Explain why or why not. If it isn’t then change the as-sumptions or set up so that it becomes a Markov chain. This is not a Markov chainbecause the future depends on the past instead of just on the present. To makeit into a Markov chain, past events must be made into present states of mind ofthe mouse. So, we assume that the mouse has four possible present states of mind:(L, y), (L, n), (R, y), (R, n). Here L or R tells whether the mouse thinks the reward ison the left or right. The second coordinate y =yes or n =no tells whether his presenthypothesis was correct last time. So, e.g., (L, n) means he thinks it is on the lefteven though it was on the right last time.(2) What are the states of your chain? (Fewer is better.) There are at least threedifferent ways to write the four possible states. (L, n) is the same as (L, R) meaninghe is guessing left and it was right last time. It is also (L, 1) where the 1 is thenumber of consecutive mistakes he has made with the present hypothesis.(3) What is the transition matrix? (Put a dot in place of each 0 in the matrix.)P =3/4 1/4 · ·3/4 · 1/4 ·· · 1/4 3/43/4 · 1/4 ·Experimental data (using people instead of mice and skip the maze) shows that peoplewill eventually guess left 3/4 of the time and guess right 1/4 of the time. The optimalstrategy is to guess left all the