Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Statistics – STATS 4024

Stochastic Processes

2019

1.  Suppose that deuce (equal score) has been reached in a tennis game between Adrian and Marian.   The player winning the next point has advantage.   On the following point, the player having advantage either wins the game or the game returns to deuce. Marian has probability p = 1/3 of winning the next point and Adrian has probability q = 2/3. Assume that the game can be modelled with a homogeneous Markov chain, with the following five states:  k = 0: match point Adrian, k = 1: advantage Adrian, k = 2:  deuce, k = 3 advantage Marian, k = 4:  match point Marian.  What is the probability that Adrian will win the game (or equivalently, that Marian will lose the game)? Break the problem up into the following subproblems:

(a) Let Ck  denote the event that Adrian will win (or, equivalently, that Marian will lose) the game when the game is in state k. Apply the law of total probability to prove the following homogeneous difference equation for uk  = P (Ck ):

uk   =  uk+1p + uk _1 q

[2 MARKS]


(b) What are the boundary conditions for the difference equation in Part (a)?

[2 MARKS]

(c) Find the general solution of the homogeneous difference equation in Part (a).

[4 MARKS]

(d) Find the specific solution of the homogeneous difference equation subject to the

boundary conditions from Part (b).

(e) What is the probability that Adrian will win the game?

[3 MARKS]

[1 MARK]


2. A simple model for molecular diffusion is an unrestricted symmetric random walk on a straight line starting at the origin: X0  = 0, where Xn  denotes the position at step n.  In each step, n, the molecule either moves one unit to the right, with probability P (Xn+1   =  m + 1lXn   =  m)  = p  =  0.5,  or one unit to the left,  with probablity P (Xn+1  = m - 1lXn  = m) = q = 1 - p = 0.5.  Let An  denote the event that the molecule is at the origin at step n:  Xn  = 0; let Bn  denote the event that the first return to the origin occurs in the n-th step.  Use the following abbreviations for the probabilities of An  and Bn : vn  = P (An ) and fn  = P (Bn ).

(a) Define V (s), the probability generating function for vn , and F (s), the probability generating function for fn .  (Note:  Do not copy the specific expressions given in the next part of the question. What is needed here is a general definition.)

[2 MARKS]

(b) It can be shown that V (s) = o, and F (s) = 1 - f1 - s2 . Find s(l)im*1 V (s) and

lim F (s).                                                                                                     [1 MARK]

s*1

(c) What does this imply for vn  and fn ?  Are vn  and fn  proper probability distribu- tions?  Choose the correct option from the following table and write it down in your script book (only 1 option is correct):


[2 MARKS]

(d)  Select the option that best explains the reason for the difference between

lim V (s) and lim F (s).

s*1                         s*1


(e) Use the expression of F (s) to obtain the probability of a first return to the origin after 2 steps and after 3 steps. Justify your answer!                          [4 MARKS]
[3 MARKS]


3. In a certain town, there are four entertainment venues. Both Marian and Adrian visit one of these venues every weekend, independently of each other.  Each of them visits the venue of the week before with probability 0.4 and chooses otherwise at random one of the other three venues. Treat this problem as a two-state Markov chain, where state 0 means that Marian and Adrian are at different venues and state 1 means that they are at the same venue.

(a) Apply the law of total probability to obtain the one-step transition probability P01 , by deriving the probabilities of three mutually exclusive and jointly exhaustive events:  that Adrian does not change venue and Marian goes to Adrian’s venue, that Marian does not change venue and Adrian goes to Marian’s venue, and that both Marian and Adrian change venue and go to the same venue. Apply a similar method to obtain the probability P11 , by deriving the probabilities of two mutually exclusive and jointly exhaustive events:  that neither Marian nor Adrian change venue, and that both Marian and Adrian change venue and go to the same venue.

[5 MARKS]

(b) Find the transition matrix of the Markov chain.                                  [1 MARK]

(c) Is the Markov chain ergodic? What does that imply for the limiting distribution?

[2 MARKS]

(d) What is the long-run (i.e. limiting) fraction of weekends that Marian and Adrian visit the same venue?                                                                          [2 MARKS]

(e) What is the limiting probability that Marian and Adrian visit the same venue two weekends in a row?                                                                             [2 MARKS]


4.  (a)  Consider a time-homogeneous reversible Markov chain defined over discrete states i, and let T denote its stochastic transition matrix.   Show that the stationary distribution P- (i) satisfies the following equation:

P- (i)Tik   =  P- (k)Tki

[3 MARKS]

(b) Assume you want to sample from a discrete probability distribution P (i) = defined over the discrete state space,  where  φ(i) is easy to compute,  but the normalisation constant Z =     k φ(k) is intractable.  Assume that the stochastic matrix T is ergodic.   Use the result from the previous part of the question to describe a method for approximately sampling from P (i) = .      [3 MARKS]

(c)  Consider a mouse that is trapped in a closed maze. The maze has 15 rooms. The rooms are positioned according to the following three-by-five array:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Doors connect any two neighbouring rooms.  For example, room 1 is connected with rooms 2 and 6, room 2 with rooms 1, 3 and 7, room 7 with rooms 2, 6, 8 and 12, and so on. The mouse moves randomly from room to room, where at each time one of the available doors is chosen with equal probability.

i. It can be shown that there exists a positive integer n > 0 such that Tn  is a strictly positive matrix, meaning that all its elements are strictly positive. What does that imply for the limiting distribution?                     [1 MARK]

ii. Use the equation from Part (a) to find the stationary (= limiting) distribution. Hint:  Make use of the symmetry of the maze.  There are four corner rooms (1, 5,  11, and 15), each of which has two neighbouring rooms; eight outer rooms (2, 3, 4, 6, 10, 12, 13, 14), each of which has three neighbouring rooms; and three inner rooms (7, 8, 9), each of which has four neighbouring rooms.

[5 MARKS]


5.  Consider a queue with a single server.   Let the random variable  N(t) denote the number of individuals in the queue at time t  (including the person being served). New customers arrive independently, and these arrivals form a Poisson process with intensity λ > 0. Service times have an exponential distribution with parameter µ > 0, that is the distribution with probability density function f(t) = µ exp(-µt), t > 0. It can be shown that the evolution of the probability pn (t) = P [N(t) = n] is described by the following differential equations:

dpn (t)

dt

dp0 (t)

dt

=   λpn_1 (t) + µpn+1(t) - [λ + µ]pn (t);    n > 1

=   µp1 (t) - λp0 (t)

(a) How do you get the limiting distribution limt* pn (t)  = pn , where pn   is time invariant, from the differential equations?                                          [2 MARKS]

(b) In the lectures we showed that the limiting distribution is given by

pn   = n p0

Find the value of p0  for the cases (i) λ < µ and (ii) λ > µ .  Interpret the result.

[5 MARKS]

(c) In the lectures we derived the following expression for the expected length of the queue including the person being served:

λ

µ - λ

Use this expression to find the expected length of the queue excluding the person being served:

←(M)  =       (n - 1)pn   = ?

n=2

[5 MARKS]