MATH10007 Stochastic Modelling (BSc) 1 (1) Poppy is playing a game with infinitely many levels. When she is at level i ∈ {0, 1, 2, 3, . . . }, she either moves to level i + 1 with non-zero probability pi, or she fails and goes back to level 0. (a) Write down the one step transition probabilities. [2 marks] (b) Determine the communicating classes. [2 marks] (c) Give a condition on pi for level 77 being recurrent. [2 marks] (d) Give a condition on pi for level 0 being positive recurrent. [2 marks] (e) Calculate the stationary probabilities when they exist. [2 marks] Hint: you may use that the mean of non-negative discrete random variables can be written as ET = ∑ n P (T > n). [Please turn over] MATH10007 Stochastic Modelling (BSc) 2 Solution: (a) pi,i+1 = pi, pi,0 = 1− pi for i ≥ 0 and all other transition rates are zero. (b) Each state is accessible from each state, since from each state you can reach zero and from there any other state in finite steps with finite probability. Hence there is a single communicating class. (A pathological case is pi = 1 for i > i0 for some i0, but that’s not required to notice.) (c) State 77 is recurrent if and only if state 0 is recurrent since recurrency is a class property. State 0 is recurrent if the probability of escape is zero, that is if 1− ρ00 = ∏ i≥0 pi = 0 (d) The probability of not returning by time n is P (T0 > n|X0 = 0) = p0…pn−1, where the empty product is considered to be one. By using the hint, the main return time to level zero is ET0 = 1 + p0 + p0p1 + . . . , and state 0 is positive recurrent if this expression is finite. (e) From the global balance equations we get pij = pij−1pj−1 for j ≥ 1 and hence pij = p0p1 . . . pj−1pi0, and from the normalization ∑ pii = 1 we get pi0 = (1 + p0 + p0p1 + . . . ) −1 when the sum exists, that is when the chain is positive recurrent. [Please turn over] MATH10007 Stochastic Modelling (BSc) 3 (2) Consider a random walk on a clock, that is on the integers 1, 2, . . . , 12, where 1 and 12 are also considered adjacent. A random walk can jump to one of the two adjacent numbers with the same probability 1/2. Justify all your answers. (a) What are the communicating classes? [1 mark] (b) Classify each state (transient, null or positive recurrent). [1 mark] (c) What is the stationary distribution? [1 mark] (d) Is this also the limiting distribution? [1 mark] (e) Starting from 12, what is the mean return time to 12? [2 marks] (f) Starting from 12, what is the probability that you visit all numbers before returning to 12? [4 marks] [Please turn over] MATH10007 Stochastic Modelling (BSc) 4 Solution: (a) Each state is accessible from any state by at most 11 steps, hence the there is only a single communicating class. (b) Each state is positive recurrent in a finite closed class. (c) Solve the global or the detailed balance conditions, or recall that for random walks on graphs the stationary probabilities are proportional to the degrees. Hence pii = 1/12 for all i. (d) No, since the system is periodic, since it always moves from even to odd state and vice versa. (e) This is just m12,12 = 1/pi12 = 12. (f) From symmetry, it doesn’t matter where you step first, so let’s assume you step to 1. Alternatively, condition on the first step. Now the question is the probability to get to 11 before back to 12. Let hi = P (Tˆ11 < Tˆ12|X0 = i), then h11 = 1 and h12 = 0, otherwise hi = (hi−1 +hi+1)/2, which is solved by hi = i/11 for i ≥ 1, hence the answer is h1 = 1/11. [Please turn over] MATH10007 Stochastic Modelling (BSc) 5 (3) Team A and B are playing football. Time is measured in hours from the beginning of the game, and the game is two hours long. Team A scores a goal at rate 1 but team B continuously gets better with time, and scores a goal at rate t. Justify all your answers to the following questions. (a) What is the mean number of goals by each team during the game? [2 marks] (b) What is the probability that none of the teams scored a goal during the game? [2 marks] (c) What is the probability that the first goal of the game was scored during the second hour? [2 marks] (d) If there was precisely one goal during the game, what is the density function of the time it happened? [2 marks] (e) Each team has 11 players and one of them is the captain. A goal scored by a team is equally likely scored by any of the team’s 11 players. What is the probability that none of the captains scored a goal during the game? [2 marks] [Please turn over] MATH10007 Stochastic Modelling (BSc) 6 Solution: We’ll use the notation At and Bt for the scores by each team, λi(s) for the rate of scoring and Λi(t) = ∫ t 0 λi(s)ds for the total rate by each team i = A or B. (a) Let At and Bt be the scores by the teams until time t. The number of scores are Poisson random variables with mean ΛA(2) = 2 and ΛB(2) = 2. (b) Since teams score independently, P (A2 = B2 = 0) = P (A2 = 0)P (B2 = 0) = e−2e−2 = e−4. (c) From superpositioning the scores from the teams, write Nt = At +Bt, so scores from any team arrive at rate λ(t) = 1 + t, with integral Λ(t). We need the probability of no score during the first hour and at least one score during the second hour, that is P (N1 = 0, N (1) 1 ≥ 1) = P (N1 = 0)P (N (1)1 ≥ 1) = e−Λ(1)(1− e−(Λ(2)−Λ(1))) = e−Λ(1) − e−Λ(2) = e−3/2 − e−4 = 0.204815 . . . where we used superpositioning and the independent increments property. (d) Conditioning on one score, from Cambell’s theorem, the density is proportional to λ(t), that is f(t) = (1 + t)/4 on [0, 2] and zero otherwise. (e) Due to the splitting property, the captain from each team scores goals at rate λA(t)/11 and λB(t)/11 respectively, and due to superpositioning both captains together score at rate (λA(t) + λB(t))/11. Hence none of them scored with probability e− ∫ 2 0 (λA(t)+λB(t))/11dt = e−4/11 = 0.695144 . . . [Please turn over] MATH10007 Stochastic Modelling (BSc) 7 (4) There are N water lily buds in a lake, and each blossoms independently into a flower at rate 1. Initially none of the buds have blossomed. (a) Let Xt be the number of flowers at time t. Model the system as a CTMC, by specifying the state space and the generator. [2 marks] (b) For N = 1 write down and solve the forward Kolmogorov equation with the given initial condition. [2 marks] (c) For general N , what is the mean number of flowers at time t? [2 marks] (d) What is the probability of having j flowers at time t? [2 marks] (e) How long do we have to wait on average until the first flower? [2 marks] [Please turn over] MATH10007 Stochastic Modelling (BSc) 8 Solution: (a) The state space is S = {0, 1, . . . , N} and the qi,i+1 = N − i, qii = −(N − i) for i < N and all other rates are zero. (b) For N = 1 the p′00(t) = −p00(t) with p00(0) = 1, hence p00(t) = e−t, and p01(t) = 1− e−t. (c) Let us define X (i) t as one if the i-th bud flowered by time t, which define independent processes. Their sum is the number of flowers Xt = ∑ iX (i) t . Since E(X (i) t |X(i)0 = 0) = P (X(i)t = 1|X(i)0 = 0) = p01(t) = 1− e−t for any i from the previous subquestion, we have E(Xt|X0 = 0) = NE(X(1)t |X(1)0 = 0) = N(1− e−t) (d) Buds turn to flowers independently, and at time t each of them has flowered with probability 1 − e−λt. Hence the probability of having j flowers at time t follows a binomial distribution P (Xt = j|X0 = 0) = ( N j ) (1− e−t)j(e−t)N−j (e) Initially blooming happens at rate N , and hence q0 = N , so we wait a mean 1/N time for the first flower. [Please turn over] MATH10007 Stochastic Modelling (BSc) 9 (5) Consider a husband and wife. Each of them independently starts using their phone after an exponential time with parameter λi, and then use it for an exponential time with parameter µi, with i = 1 for the wife, and i = 2 for the husband. (a) Model the system on a state space with four states, describing who is on the phone at a given time. Give the generator. [2 marks] (b) Draw the state diagram. [1 mark] (c) Calculate the stationary probability that both of them are on the phone simultan eously. [2 marks] (d) If they are not on the phone, they talk to each other. How long is such a conversation on average? [1 mark] (e) Currently no one is on the phone. What is the probability that the woman gets on the phone first? [1 mark] (f) Currently no one is on the phone. What is the probability that at the next time when the woman gets on the phone, the man is on the phone? [3 marks] [Please turn over] MATH10007 Stochastic Modelling (BSc) 10 Solution: (a) Denote the states as S = {0, 1, 2, 3}, where 3 refers to both of them being on the phone simultaneously. q01 = q2,3 = λ1, q02 = q1,3 = λ2, q10 = q3,2 = µ1 and q20 = q3,1 = µ2, and all other rates are zero. (b) The state diagram is 0 1 2 3 λ1 λ2 λ2 µ1 λ1 µ2 µ1 µ2 (c) We can solve the global balance equations or try to solve the detailed balance equations. The latter are pi2µ2 = pi0λ2, pi0λ1 = pi1µ1, pi2λ1 = pi3µ1, pi1λ2 = pi3µ2 and ∑ pii = 1. The solution is pi1 = λ1 µ1 pi0, pi2 = λ2 µ2 pi0, pi3 = λ1 µ1 λ2 µ2 pi0 and from the last equation we get pi0, and all other probabilities explicitly pi0 = µ1µ2 (µ1 + λ1)(µ2 + λ2) , . . . , pi3 = λ1λ2 (µ1 + λ1)(µ2 + λ2) , A simpler way for full marks is to consider two independent processes to describe husband and wife, X (1) t , X (2) t , and obtain the joint stationary probability as a product of the corresponding stationary probabilities of the independent processes. (d) They talk to each other when in state 0, which state is left at rate λ1 +λ2, hence after an average chat time 1/(λ1 + λ2). (e) Each of them start talking after an exponential waiting time Ti ∼ expo(λi). The woman starts talking first if her waiting time is shorter, that is P (T1 < T2) = λ1/(λ1 + λ2). (f) The question can be reformulated as from state 0 what is the probability to enter state 3 before state 1. If Tˆi is the first passage time to state i, then we need hi = E(Tˆ3 < Tˆ1|X0 = i), for which h1 = 0, h3 = 1 and (λ1 + λ2)h0 = λ1h1 + λ2h2, (λ1 + µ2)h2 = λ1h3 + µ2h0 which leads to h0 = λ1λ2 λ1λ2 + λ21 + λ1µ2 [End of Paper]
