EE 351K Probability, Statistics and Stochastic Processes - Spring 2016 Homework 12 Topics: Random Processes, Markov Chain Homework and Exam Grading \"Philosophy\" Answering a question is not just about getting the right answer, but also about communicating how you got there. This means that you should carefully define your model and notation, and provide a step-by-step explanation on how you got to your answer. Communicating clearly also means your homework should be neat. Take pride in your work it will be appreciated, and you will get practice thinking clearly and communicating your approach and/or ideas. To encourage you to be neat, if you homework or exam solutions are sloppy you may NOT get full credit even if your answer is correct. Occasionally we will give additional problems on a homework which will not be graded. These are intended as extra practice which in my experience many of you will ask for anyway. Q. 1 Consider a telephone call center staffed by 3 operators. Any incoming call is routed immediately to a free operator; if no operator is free, the call is kept on hold until one of the operators become free and is then routed to that person. Calls are served in a first-come-first-serve manner. A call is said to be active if it is either being served by an operator or on hold waiting to be served. The calls arrive in batches: At the beginning of each minute, either {0, 1, 2} new calls are made to the call center, and all these three possibilities are equally likely and independent of any other event. An operator serves a caller for a random number of minutes (minimum service time is 1 minute), with the service time distributed as a Geometric random variable with mean of 2 minutes. Once the operator completes service, the caller hangs up and disappears from the system. Describe the system evolution by a Discrete Time Markov Chain (DTMC) that models the number of active calls at the call center. Determine the stace-space, draw the state transition diagram and determine the transition probabilities. Is this DTMC aperiodic and irreducible? Q. 2 A random walker walks among 3 points labelled {a, b, c}. Each minute, she takes a step, and her movement dynamics are as follows: (i) If (current position) equals (previous-minute position), then go to any one of the other two positions with equal probability; (ii) If (current position) does not equal (previous-minute position), then continue to stay in current position during the next minute. Please answer the following questions: (a). Determine the state-space, such that the system evolution can be described by a Discrete Time Markov Chain. Justify your answer. Draw the state transition diagram, with the states labeled and the edges labeled with the transition probabilities. (b). Is the Markov chain irreducible and aperiodic? Q. 3 A particle is initially present at location '0' and can move on the integer lattice (i.e., {. . . , 2, 1, 0, 1, 2, . . .}). At each timestep, it moves one step to it's left or right. The probabilities are as follows: (i) If it is located on a positive integer, it moves to its left with probability 0.8, and to its right with probability 0.2; (ii) If it is located on a negative integer, it moves to its left with probability 0.1, and to its right with probability 0.9; (iii) If it is located at '0', it moves to either of its neighbors or stays in its current location (i.e., +1, 0 or 1) with equal probability. Further, denote the location of the particle at time n by Xn , n = 0, 1, 2, . . . , and recall that X0 = 0. 1 (a). Determine if {Xn , n = 0, 1, 2, . . .} is a discrete-time Markov chain? Determine the state-space and the transition probabilities (you do not need to list all the probabilities, a few representative values will suffice). Is it aperiodic? (b). Next let Yn = |Xn |. In other words, Yn denotes the magnitude of the location at time n. Is Yn a discrete time Markov Chain? Justify your answer. Q. 4 A DTMC with 4 states is known to be aperiodic and irreducible. Recall that for any DTMC, for each row, the sum of probabilities in the P matrix equals '1' (i.e., the sum of outgoing probabilities for each state always equals '1'). For this specific 4 state DTMC, it is further known that that the sum of incoming probabilities for each state also equals '1' for every state. More formally, the transpose PT also has row sums equaling '1' for each row. Show that in steady-state, all states are equally likely, i.e., the unique steady-state distribution for the DTMC is given by 1 = 2 = 3 = 4 = 0.25. Q. 5 (Note: We will discuss this problem in greater detail in class on Tuesday, May 3). Suppose that we have a connected graph consisting of nodes and edges, with nodes being labeled {1, 2, . . . , L} (see figure for an example). A particle is initially placed on one of the nodes at time zero. At each discrete time, the particle moves to a neighboring node randomly (i.e. it chooses one of the edges incident on the current node equally likely, and traverses that edge). Suppose that the graph has no self loops and is connected (i.e. there is a path between any pair of nodes). Further, assume that the graph is aperiodic (in the example graph below, we can return to node '1' after either 2 steps or 3 time steps, thus ensuring aperiodicity). Consider the DTMC {X0 , X1 , . . .}, where Xn is the particle's location (node) at time n. Argue that that this Markov chain has a unique stationary distribution. Show that this steady-state probability of being at node i is proportional to number of edges incident on it. For example, in the figure below, the number of edges incident on vertices {1, 2, 3, 4, 5} are: {3, 3, 2, 1, 1}, and the corresponding stationary distribution is: = [0.3, 0.3, 0.2, 0.1, 0.1]. Verify the example, and also show this property for any general 1 4 2 3 5 Figure 1: An example of a connected graph with 5 nodes. connected finite graph which is aperiodic, irreducible and has no self-loops. Finally, suppose that you receive a reward of i dollars each time the particle lands on state i. Determine the expected reward in steady-state. Q. 6 A mouse travels in a maze (shown in figure). At each discrete time-step, the mouse chooses one of the doors from the room it is curently in (uniformly at random), and moves to the chosen neighboring room. Room three has a block of cheese in it (reward for the mouse). (a). Model the location of mouse as a DTMC and check if it is irreducible and aperiodic. (b). Find the steady state distribution for this DTMC. 2 (c). Let m be the expected number of time-steps between two successive visits of the mouse to the room with cheese. Find m by writing down the reccurence equations. (d). Find 1 (3) . (e). Check if answers in parts (c) and (d) are same, and comment on what you observe. 1 3 2 4 cheese 5 Figure 2: The maze. Q. 7 A gambler starts with 1 dollar and decides to play until she loses all her money or she accumulates 3 dollars. She repeatedly gambles; on each play she either gains a dollar or loses a dollar. Specifically, she wins each gamble with probability q, and gains one dollar. On the other hand, if she loses a gamble (with probability 1 q), then she loses one dollar. (a). Draw the state transition diagram for this system with transition probability clearly marked. (b). Determine the probability of losing all her money (as a function of q). Further calculate this probability when q = 0.6. 3