Applied Stochastic Processes (PSTAT 160B) Homework 1. Instructor: Alex ShkolnikDue: 10/09/2018 (in class) In this exercise set we consider the following modification of the Ehrenfest…

Applied Stochastic Processes (PSTAT 160B) Homework 1. Instructor: Alex ShkolnikDue: 10/09/2018 (in class)

In this exercise set we consider the following modification of the Ehrenfest urn problem. Suppose there are 2d particles placed into two urnsfor an integer d 1. At each step we pick a particle uniformly at random and place it into the same urn (the one from which it came) withprobability p 2 Œ0; 1 and into the other urn with probability q D 1p.We let Xk denote the number of particles in the left urn at time step k.Exercise 1. What is the state space S for X D fXkgk0, the Markov chain counting the particles in the left urn? Compute its transition probabilities fPxygx;y2S.Exercise 2. Suppose X0 D ·. Show that E.Xk/ D d C .1 q=d/k .· d / fork 0. What is the average number of particles in the left urn after a long time?Exercise 3. Let denote the stationary distribution of X. We recover the classical Ehrenfest urn for which .x/ D 2d x =22d when q D 1 (Sec. 4.8 Ross). Provethis is also the stationary distribution when q 2 .0; 1/. What is when q is zero?Exercise 4. Let fPxygx;y2S be as in Exercise 1 and be as in Exercise 3 for q > 0.Compute Qxy D Pyx .y/ .x/ and verify that fQxygx;y2S forms a well-defined setof transition probabilities for a Markov chain. Describe this Markov chain.Programming problem. Implement our modified Ehrenfest urn in either R orPython. Fix 100 particles, initialize X0 some number randomly chosen fromf0; : : : ; 10g and simulate the entropy process S of the Markov chain X. Here,S D kB log WXwhere kB is the Bolzmann constant (set it to one) and W· D 2d · is the numberof configurations of the state · 2 S. Generate a path of S over 103 time stepsand plot it (S on the y-axis and times k D 0; 1; : : : 103 on the x-axis) for q D 1.Produce plots for three more values of q: 0:5; 0:1; 0:01. What do you observe?The reason for the formula W· D 2d · is as follows. Entropy is a measure ofdisorder or randomness of a closed system. One way to define this is through thenumber of microstates (the more microstates the more disordered a system gets).To model this we let each Xk W  ! S where  D f0; 1g2d , the set of all sequencesof length 2d with elements in f0; 1g. Each ! 2  is a configuration that recordswhich urn each of the 2d particles is in. We write ! D .!1; : : : !2d / where wi D 1if particle i is in the left urn and wi D 0 if its in the right one. It is easy to see thatXk .!/ D P2d iD1 wi. Then, W· D jf! 2 j P2d iD1 wi D ·gj D 2d · , the numberof ways to arrange the 2d particles with · in the left urn and 2d · in the right.1