xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-X1-Assignment 1

时间：2021-04-14

Solution-Assignment 1 (for Stat3021)

1. Assume Xn are independent and identically distributed with P (X1 = 1) = p,

P (X1 = 0) = r and P (X1 = −1) = q. where p, r, q > 0 and p + r + q = 1.

Let Sn =

∑n

i=1Xi, n = 1, 2, . . ..

(a) Prove that {S1, S2, . . .} is an irreducible Markov chain with state space S =

{0,±1,±2, ...} and write down its transition matrix.

(b) Is the chain aperiodic?

(c) Find expressions for:

i. P (S3 = 2).

ii. P (S4 = 1|S1 = 1).

iii. P (S10 = 1|S7 = 0).

iv. ESn and var(Sn).

Solution:

(a) It’s a MC since Sn+1 = Sn + Xn+1 so that conditional on S1, S2, . . . , Sn, or

equivalently X1, X2, . . . , Xn, it is only Sn that is relevant for predicting the

value of Sn+1. It’s clear that all states communicate, since any state j can be

reached from any other state i, in |j − i| steps, with positive probability. The

transition matrix is (with r’s on diagonal)

P =

...

...

...

...

...

...

...

. . . q r p . . . . . . . . .

. . . . . . q r p . . . . . .

. . . . . . . . . q r p . . .

...

...

...

...

...

...

...

(b) Yes, it’s aperiodic, since e.g. pn00 ≥ rn > 0 for n = 1, 2, . . ..

(c) i. {S3 = 2} involves two +1’s and one 0 so the answer is 3p2r.

ii. P (S4 = 1|S1 = 1) = P (S3 = 0). This involves three 0’s or one each of 0,

−1 and +1, so the answer is r3 + 6pqr.

iii. This is the same as P (S3 = 1) which entails two 0’s and a +1 or two +1’s

and a −1. So the answer is 3r2p+ 3p2q.

iv. ESn = n(p− q) and var(Sn) = n(4pq + r(p+ q)).

2. Suppose a transition diagram is given as follows:

1 2

5

3

4 6 7

1/2

1/2

1/2

1/4

1/4

For this chain, there are two recurrent classes R1 = {6, 7} and R2 = {1, 2, 5}, and

one transient class R3 = {3, 4}.

(a) Find the period of state 3 and the probability that, starting at state 3, the

state 3 is eventually re-entered (i.e., f33).

(b) Assuming X0 = 3, find the probability that the chain gets absorbed in R1.

(c) Assuming X0 = 3, find the expected time (number of steps) until the chain

gets absorbed in R1 or R2. More specifically, let T be the absorption time,

i.e., the first time the chain visits a state in R1 or R2. We would like to find

E[T |X0 = 3].

Note: there are missing transition probabilities for this chain, but no impact for

your solution.

Solution:

(a) Note that

p

(2k)

33 = (0.5× 0.4)k > 0, p(2k+1)33 = 0, k = 1, 2, ...

The period of state 3 is 2. Similarly, we have

f

(1)

33 = 0, f

(2)

33 = 1/2× 1/4 = 1/8, f (k)33 = 0, k ≥ 3

It follows that f33 =

∑∞

n=1 f

(n)

33 = 1/8.

(b) We can apply the standard methodology to find probability of absorption in

state R1. Define

ai = P (absorption in R1|X0 = i), for all i ∈ S.

We have aR1 = 1, and aR2 = 0. To find the unknown values of ai’s, we can use

the following equations

ai =

∑

k

akpik, for i ∈ S.

2

We obtain

a3 =

1

2

aR1 +

1

2

a4

=

1

2

+

1

2

a4,

a4 =

1

4

aR1 +

1

4

a3 +

1

2

aR2

=

1

4

+

1

4

a3.

Solving the above equations, we obtain

a3 =

5

7

, a4 =

3

7

.

Therefore, if X0 = 3, the chain will end up in class R1 with probability a3 =

5

7

.

(c) For all i ∈ S, define

ti = E[T |X0 = i].

By the above definition, we have tR1 = tR2 = 0. To find t3 and t4, we can use

the following equations

ti = 1 +

∑

k

tkpik, for i = 3, 4.

Specifically, we obtain

t3 = 1 +

1

2

tR1 +

1

2

t4

= 1 +

1

2

t4,

t4 = 1 +

1

4

tR1 +

1

4

t3 +

1

2

tR2

= 1 +

1

4

t3.

Solving the above equations, we obtain

t3 =

12

7

, t4 =

10

7

.

Therefore, if X0 = 3, it will take on average

12

7

steps until the chain gets

absorbed in R1 or R2.

3

3. An apparatus consists of two containers C1 and C2, and four balls, in one or the

other of the two containers. At regular times the following procedure is carried out:

with probability θ a ball is chosen uniformly at random (from all four balls) and

is removed from its container and placed in the other one; with probability 1 − θ

things are left as they were. Let Xn denote the number of balls in container C1 at

time n.

(a) Explain why Xn forms a Markov chain with stationary transition probabilities.

(b) Complete the following transition matrix P

P =

1− θ θ ∗ ∗ ∗

θ/4 1− θ 3θ/4 ∗ ∗

0 θ/2 ∗ ∗ ∗

∗ ∗ ∗ 1− θ θ/4

∗ ∗ ∗ ∗ 1− θ

(c) Classify the states, taking care to distinguish the cases θ = 0, 0 < θ < 1 and

θ = 1.

Draw a transition diagram to aid your explanation.

(d) Suppose 0 < θ < 1. Calculate the stationary distribution pi = (pi0, · · · , pi4).

Explain briefly why the distribution is the same for all θ ∈ (0, 1).

(e) Suppose 0 < θ < 1. What is the limit of P n, where P is the transition matrix

given in part (b)? Explain.

(f) Let mj be the expected time to reach state 4, given X0 = j, for j = 0, 1, 2, 3.

Calculate mj when θ = 0

Solution:

(a) Given the values of {X0 = i0, X1 = i1, ..., Xn = in}, Xn+1 can only take the

three possible values in and in ± 1. Thus

P (Xn+1 = j | X0 = i0, X1 = i1, ..., Xn = in) = P (Xn+1 = j | Xn = in),

i.e., it’s a Markov Chain. Furthermore the transition probabilities donot de-

pend on n, so it has stationary transition probabilities.

(b)

P =

1− θ θ 0

θ/4 1− θ 3θ/4 0

0 θ/2 1− θ θ/2 0

0 3θ/4 1− θ θ/4

0 θ 1− θ

(c) θ = 0: Each state is absorbing (and therefore aperiodic and positive recurrent).

θ ∈ (0, 1): State form a single class, aperiodic and positive recurrent.

θ = 1: states form a single class, period 2.

4

(d) The stationary dist. satisfies that pi = pi P , i.e.,

pi0 = (1− θ)pi0 + θpi1/4

pi1 = θpi0 + (1− θ)pi1 + θpi2/2

pi2 = 3θpi1/4 + (1− θ)pi2 + 3θpi3/4

pi3 = θpi2/2 + (1− θ)pi3 + θpi4/2

pi4 = θpi3/4 + (1− θ)pi4

This yields that

pi1 = 4pi0

pi2 = 2(pi1 − pi0) = 6pi0

pi3 =

4

3

(pi2 − 3

4

pi1) = 4pi0

pi4 =

1

4

pi3 = pi0

and it follows from

∑4

j=0 pii = 1 that pi0 = 1/16, i.e., the stationary dist.

pi0 = 1/16, pi1 = 1/4, pi2 = 3/8, pi3 = 1/4, pi4 = 1/16.

Note that the stationary dist. is Binomial B(4, 1/2).

θ affects the rate of change from state to state but not the limit distribution.

(e) The limit of P n =

pipi

pi

where each row is the stationary dist since it is an

irreducible, aperiodic and positive recurrent MC.

(f) θ = 0: Each state is absorbing (and therefore aperiodic and positive recurrent).

Therefore, mj =∞, given X0 = j, for j = 0, 1, 2, 3.

5

学霸联盟

1. Assume Xn are independent and identically distributed with P (X1 = 1) = p,

P (X1 = 0) = r and P (X1 = −1) = q. where p, r, q > 0 and p + r + q = 1.

Let Sn =

∑n

i=1Xi, n = 1, 2, . . ..

(a) Prove that {S1, S2, . . .} is an irreducible Markov chain with state space S =

{0,±1,±2, ...} and write down its transition matrix.

(b) Is the chain aperiodic?

(c) Find expressions for:

i. P (S3 = 2).

ii. P (S4 = 1|S1 = 1).

iii. P (S10 = 1|S7 = 0).

iv. ESn and var(Sn).

Solution:

(a) It’s a MC since Sn+1 = Sn + Xn+1 so that conditional on S1, S2, . . . , Sn, or

equivalently X1, X2, . . . , Xn, it is only Sn that is relevant for predicting the

value of Sn+1. It’s clear that all states communicate, since any state j can be

reached from any other state i, in |j − i| steps, with positive probability. The

transition matrix is (with r’s on diagonal)

P =

...

...

...

...

...

...

...

. . . q r p . . . . . . . . .

. . . . . . q r p . . . . . .

. . . . . . . . . q r p . . .

...

...

...

...

...

...

...

(b) Yes, it’s aperiodic, since e.g. pn00 ≥ rn > 0 for n = 1, 2, . . ..

(c) i. {S3 = 2} involves two +1’s and one 0 so the answer is 3p2r.

ii. P (S4 = 1|S1 = 1) = P (S3 = 0). This involves three 0’s or one each of 0,

−1 and +1, so the answer is r3 + 6pqr.

iii. This is the same as P (S3 = 1) which entails two 0’s and a +1 or two +1’s

and a −1. So the answer is 3r2p+ 3p2q.

iv. ESn = n(p− q) and var(Sn) = n(4pq + r(p+ q)).

2. Suppose a transition diagram is given as follows:

1 2

5

3

4 6 7

1/2

1/2

1/2

1/4

1/4

For this chain, there are two recurrent classes R1 = {6, 7} and R2 = {1, 2, 5}, and

one transient class R3 = {3, 4}.

(a) Find the period of state 3 and the probability that, starting at state 3, the

state 3 is eventually re-entered (i.e., f33).

(b) Assuming X0 = 3, find the probability that the chain gets absorbed in R1.

(c) Assuming X0 = 3, find the expected time (number of steps) until the chain

gets absorbed in R1 or R2. More specifically, let T be the absorption time,

i.e., the first time the chain visits a state in R1 or R2. We would like to find

E[T |X0 = 3].

Note: there are missing transition probabilities for this chain, but no impact for

your solution.

Solution:

(a) Note that

p

(2k)

33 = (0.5× 0.4)k > 0, p(2k+1)33 = 0, k = 1, 2, ...

The period of state 3 is 2. Similarly, we have

f

(1)

33 = 0, f

(2)

33 = 1/2× 1/4 = 1/8, f (k)33 = 0, k ≥ 3

It follows that f33 =

∑∞

n=1 f

(n)

33 = 1/8.

(b) We can apply the standard methodology to find probability of absorption in

state R1. Define

ai = P (absorption in R1|X0 = i), for all i ∈ S.

We have aR1 = 1, and aR2 = 0. To find the unknown values of ai’s, we can use

the following equations

ai =

∑

k

akpik, for i ∈ S.

2

We obtain

a3 =

1

2

aR1 +

1

2

a4

=

1

2

+

1

2

a4,

a4 =

1

4

aR1 +

1

4

a3 +

1

2

aR2

=

1

4

+

1

4

a3.

Solving the above equations, we obtain

a3 =

5

7

, a4 =

3

7

.

Therefore, if X0 = 3, the chain will end up in class R1 with probability a3 =

5

7

.

(c) For all i ∈ S, define

ti = E[T |X0 = i].

By the above definition, we have tR1 = tR2 = 0. To find t3 and t4, we can use

the following equations

ti = 1 +

∑

k

tkpik, for i = 3, 4.

Specifically, we obtain

t3 = 1 +

1

2

tR1 +

1

2

t4

= 1 +

1

2

t4,

t4 = 1 +

1

4

tR1 +

1

4

t3 +

1

2

tR2

= 1 +

1

4

t3.

Solving the above equations, we obtain

t3 =

12

7

, t4 =

10

7

.

Therefore, if X0 = 3, it will take on average

12

7

steps until the chain gets

absorbed in R1 or R2.

3

3. An apparatus consists of two containers C1 and C2, and four balls, in one or the

other of the two containers. At regular times the following procedure is carried out:

with probability θ a ball is chosen uniformly at random (from all four balls) and

is removed from its container and placed in the other one; with probability 1 − θ

things are left as they were. Let Xn denote the number of balls in container C1 at

time n.

(a) Explain why Xn forms a Markov chain with stationary transition probabilities.

(b) Complete the following transition matrix P

P =

1− θ θ ∗ ∗ ∗

θ/4 1− θ 3θ/4 ∗ ∗

0 θ/2 ∗ ∗ ∗

∗ ∗ ∗ 1− θ θ/4

∗ ∗ ∗ ∗ 1− θ

(c) Classify the states, taking care to distinguish the cases θ = 0, 0 < θ < 1 and

θ = 1.

Draw a transition diagram to aid your explanation.

(d) Suppose 0 < θ < 1. Calculate the stationary distribution pi = (pi0, · · · , pi4).

Explain briefly why the distribution is the same for all θ ∈ (0, 1).

(e) Suppose 0 < θ < 1. What is the limit of P n, where P is the transition matrix

given in part (b)? Explain.

(f) Let mj be the expected time to reach state 4, given X0 = j, for j = 0, 1, 2, 3.

Calculate mj when θ = 0

Solution:

(a) Given the values of {X0 = i0, X1 = i1, ..., Xn = in}, Xn+1 can only take the

three possible values in and in ± 1. Thus

P (Xn+1 = j | X0 = i0, X1 = i1, ..., Xn = in) = P (Xn+1 = j | Xn = in),

i.e., it’s a Markov Chain. Furthermore the transition probabilities donot de-

pend on n, so it has stationary transition probabilities.

(b)

P =

1− θ θ 0

θ/4 1− θ 3θ/4 0

0 θ/2 1− θ θ/2 0

0 3θ/4 1− θ θ/4

0 θ 1− θ

(c) θ = 0: Each state is absorbing (and therefore aperiodic and positive recurrent).

θ ∈ (0, 1): State form a single class, aperiodic and positive recurrent.

θ = 1: states form a single class, period 2.

4

(d) The stationary dist. satisfies that pi = pi P , i.e.,

pi0 = (1− θ)pi0 + θpi1/4

pi1 = θpi0 + (1− θ)pi1 + θpi2/2

pi2 = 3θpi1/4 + (1− θ)pi2 + 3θpi3/4

pi3 = θpi2/2 + (1− θ)pi3 + θpi4/2

pi4 = θpi3/4 + (1− θ)pi4

This yields that

pi1 = 4pi0

pi2 = 2(pi1 − pi0) = 6pi0

pi3 =

4

3

(pi2 − 3

4

pi1) = 4pi0

pi4 =

1

4

pi3 = pi0

and it follows from

∑4

j=0 pii = 1 that pi0 = 1/16, i.e., the stationary dist.

pi0 = 1/16, pi1 = 1/4, pi2 = 3/8, pi3 = 1/4, pi4 = 1/16.

Note that the stationary dist. is Binomial B(4, 1/2).

θ affects the rate of change from state to state but not the limit distribution.

(e) The limit of P n =

pipi

pi

where each row is the stationary dist since it is an

irreducible, aperiodic and positive recurrent MC.

(f) θ = 0: Each state is absorbing (and therefore aperiodic and positive recurrent).

Therefore, mj =∞, given X0 = j, for j = 0, 1, 2, 3.

5

学霸联盟