PYTHON HOMEWORK 3 - DUE 10/21 AT 11:59 PM PSTAT 160A - Fall 2016 Professor Hohn Instructions: Please note that you must work by yourself ! You will submit two files on GauchoSpace: (1) clear and concise explanations, graphics (if any), and results in PDF format (worth 20 points in total) and (2) your Python code in .py format (5 points). Note that if the grader finds identical copies or very similar files, the grader cannot and will not grade them. 1. In this Python assignment, you will be estimate the number of time steps it will take to get to a specific state. Note that this problem is similar to the cereal box collection problem in your first homework assignment. Using Markov chains is an alternate way to solve that problem. Suppose that there are 5 songs on your professor's half marathon running playlist. She sets it in shuffle mode which plays songs uniformly at random, sampling with replacement (i.e. repeats are possible). Let Xn be the number of unique songs that have been heard after the nth song played with X0 = 0. (a) (Without Python) Briefly explain why (Xn ) n=0 forms a stationary discrete time Markov chain. Find the transition probability matrix. Hint: it may be easier to see what's happening by drawing a jump diagram. (b) In Python, simulate one sample path of (Xn ) n=0 . Print the number of time steps it took for all 5 songs to be heard. (c) Simulate 10000 sample path of the Markov chain (Xn ) n=0 . (d) Using the simulation in part (c), estimate the probability that all songs are heard after n plays for each n = 5, 6, . . . from your simulation. That is, estimate P(Xn = 5) for n = 5, 6, 7, . . .. (e) Make a bar graph of your results (number of time steps to 5 songs vs probability). Python Code Hints numpy.random.choice( alist ) will randomly pick one element from the set alist. You may need to use a for loop or while statement in you code. See http://www.openbookproject.net/books/bpp4awd/ch04.html for examples. When Python indexes list, the index of the list starts at 0. That is, to access the first entry of a list like a=[7, 8, 9], we need to write a[0]. alist = [1, 4, 7] alist.append( 3 ) will add 3 to the end of your list. So, alist = [1, 4, 7, 3]. matplotlib.pyplot.bar(left = x, height = y ,align='center', alpha=0.5, color='g') produces a bar graph with x-axis described by x and y axis described by y. Both x and y are lists here. If you are using Python 2, you'll need to import division from Python 3 so that it acts like Python 3 when using the / symbol in your calculations. If you are using Python 2, write at the top of your py file, from __future__ import division Page 2