xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

Python代写-MATH 303

时间：2021-02-10

MATH 303 Practice Problems Solutions - Week 2 Jamuary 22, 2021

Problem 1

1.

P =

1

2

1

2 0 0 0 0

1

2

1

2 0 0 0 0

0 0 12 0

1

2 0

1

4

1

4 0 0

1

4

1

4

0 0 12 0

1

2 0

0 13 0

1

3

1

3 0

2. The transition diagram may be represented as:

1

2

3

4

5

6

1/2

1/2 1/2

1/2

1/2 1/2

1/4

1/4

1/4

1/4

1/2

1/2

1/3

1/3

1/3

There are three communicating classes:

• C1 = {1, 2} (P12 > 0 and P21 > 0 so 1↔ 2, and 1 and 2 do not give access to other states).

• C2 = {3, 5} (by the same argument as above).

• C3 = {4, 6} (4↔ 6 and they do not communicate with any other classes).

3. Since periodicity, transience and recurrence are class properties, we can consider each class to

study the properties of all the states they contain.

States in:

• C1 are aperiodic (since p

(1)

11 > 0 for example).

• C2 are aperiodic (same as above).

• C3 are of period 2 (starting from any state it takes an even number of steps to revisit the

state)

States in:

• C1 and C2 are recurrent (since the class is closed and finite)

• C3 are transient (for example 4→ 2 and 2 6→ 4).

Problem 2

1.

r p 0 0 0 q

q r p 0 0 0

0 q r p 0 0

0 0 q r p 0

0 0 0 q r p

p 0 0 0 q r

2. For all states i, j, i↔ j since one can move from any vertex to any other by successively moving

in one direction. So the chain has only one communicating class and it is irreducible.

3. If r > 0, then p11 = r > 0, so the period divides 1, so it is equal to 1 and the chain is aperiodic.

4. If N is even, then there exists a proper 2-coloring of the N -gon: the states can be colored

red or blue such that Pij > 0 if and only if i and j have different colors. Suppose state

1 is colored blue, and consider any path 1 → 1 of length n, say (X0 = 1, X1 = x1, X2 =

x2, . . . , Xn−1 = xn−1, Xn = 1), that has positive probability to occur. Since xj and xj−1 have

different colors for j = 1, 2, . . . , n, and Xn = 1 is blue, there are exactly

n

2 blue states in the

sequence (x0, x1, . . . , xn−1), namely x0, x2, . . . , xn−2. Thus n2 is an integer, so n must be even,

and Pn11 = 0 if n is odd. Finally, p

2

11 > p

1

12p

1

21, so d(1) = 2.

If N is odd then,

p

(N)

11 ≥ p12p23p34 . . . pN1 = qN > 0

so d(1)|N . As we observed previously, d(1)|2 (this did not depend on the parity of N). So

d(1) = 1 and the chain is aperiodic.

5. Let (Xn)n≥0 describe the position of the random walk at time n, and suppose that we start

at X0 = 1. If X1 = 2, the the probability to visit all states before returning to 1 is the same

as the probability of hitting N − 1 before getting ruined in the gambler’s ruin problem, with

a probability of winning a single game p and starting from 1. From class we know that this

probability is

P1 =

{

1− a−1

aN−1−1 , where a =

1

p − 1, if p 6= 12

1− 1N−1 if p = 12 .

Similarly, if X1 = N , we have that the probability of visiting all states before returning to 1 is

P2 =

{

1− b−1

bN−1−1 , where b =

1

q − 1, if q 6= 12

1− 1N−1 if q = 12 .

The reasoning is the same for any initial position X0 and p+ q = 1, so we may conclude that

P (visiting all states before returning to initial position) = pP1 + qP2

=

{

p

(

1− a−1

aN−1−1

)

+ q

(

1− b−1

bN−1−1

)

, where a = 1p − 1, b = 1q − 1, if p 6= 12

1− 2N−1 if p = 12 .

Problem 3

1. The 2-step transition matrix is M2 =

1

4

2 1 1

1 2 1

1 1 2

2. (1, 0, 0)M2 = 14 (2, 1, 1), so E(X2) =

1

4

(0× 2 + 1× 1 + 2× 1) = 3

4

.

3. Let N(i) be the mean number of transitions before visiting 2, given that X0 = i, i = 0, 1.

Then, by conditioning on the outcome of X1, N(0) = (1 +N(0))p00 + (1 +N(1))p01 + p02, and

N(1) = (1 + N(0))p10 + (1 + N(1))p11 + p12. Solving for N(0) and N(1), we obtain that the

answer is N(0) = 4.

Problem 4

1.

E0(T ) = 0, EN (T ) = 0.

2.

Ek(T ) = Ek(T | win first game)P (win first game) + Ek(T | lose first game)P (lose first game)

= (Ek+1(T ) + 1)p+ (Ek−1(T ) + 1)(1− p)

⇐⇒ xk = (xk+1 + 1)p+ (xk−1 + 1)(1− p)

⇐⇒ pxk+1 − xk + (1− p)xk−1 = −1

3. (a) We solve the characteristic equation

pX2 −X + (1− p) = 0

with discriminant

∆ = 1− 4p(1− p) = (2p− 1)2

• If p 6= 12 then ∆ > 0 and

yn = A

(

1 + 2p− 1

2p

)n

+B

(

1− 2p+ 1

2p

)n

so

yn = A+B

(

1− p

p

)n

if p 6= 1

2

.

• If p = 12 then ∆ = 0 and

yn = A

(

1

2p

)n

+Bn

(

1

2p

)n

so

yn = A+Bn if p =

1

2

.

(b) Replacing xi with Ci in (∗) gives C = − 12p−1 if p 6= 12 . Replacing xi with Ci2 in (∗) gives

C = −1 when p = 12 .

(c) If p 6= 12 , initial conditions impose{

A+B = 0,

A+B(α− 1)N = N2p−1 , where α = 1p

⇐⇒

{

A = −B,

−B(1− (α− 1)N ) = N2p−1 ,

(1)

⇐⇒

{

A = − N1−2p 11−(α−1)N ,

B = N1−2p

1

1−(α−1)N ,

(2)

So

Ek(T ) = xk = yk + Ck =

1

1− 2p

( −N

1− (α− 1)N +

N(α− 1)k

1− (α− 1)N + k

)

for p 6= 12 ,

Ek(T ) =

1

1− 2p

(

k +N

1− (α− 1)k

1− (α− 1)N

)

where α = 1p .

If p = 12 , similarly, we find {

A = 0

B = N

and Ek(T ) = Nk − k2 so for p = 12 we have Ek(T ) = k(N − k).

学霸联盟

Problem 1

1.

P =

1

2

1

2 0 0 0 0

1

2

1

2 0 0 0 0

0 0 12 0

1

2 0

1

4

1

4 0 0

1

4

1

4

0 0 12 0

1

2 0

0 13 0

1

3

1

3 0

2. The transition diagram may be represented as:

1

2

3

4

5

6

1/2

1/2 1/2

1/2

1/2 1/2

1/4

1/4

1/4

1/4

1/2

1/2

1/3

1/3

1/3

There are three communicating classes:

• C1 = {1, 2} (P12 > 0 and P21 > 0 so 1↔ 2, and 1 and 2 do not give access to other states).

• C2 = {3, 5} (by the same argument as above).

• C3 = {4, 6} (4↔ 6 and they do not communicate with any other classes).

3. Since periodicity, transience and recurrence are class properties, we can consider each class to

study the properties of all the states they contain.

States in:

• C1 are aperiodic (since p

(1)

11 > 0 for example).

• C2 are aperiodic (same as above).

• C3 are of period 2 (starting from any state it takes an even number of steps to revisit the

state)

States in:

• C1 and C2 are recurrent (since the class is closed and finite)

• C3 are transient (for example 4→ 2 and 2 6→ 4).

Problem 2

1.

r p 0 0 0 q

q r p 0 0 0

0 q r p 0 0

0 0 q r p 0

0 0 0 q r p

p 0 0 0 q r

2. For all states i, j, i↔ j since one can move from any vertex to any other by successively moving

in one direction. So the chain has only one communicating class and it is irreducible.

3. If r > 0, then p11 = r > 0, so the period divides 1, so it is equal to 1 and the chain is aperiodic.

4. If N is even, then there exists a proper 2-coloring of the N -gon: the states can be colored

red or blue such that Pij > 0 if and only if i and j have different colors. Suppose state

1 is colored blue, and consider any path 1 → 1 of length n, say (X0 = 1, X1 = x1, X2 =

x2, . . . , Xn−1 = xn−1, Xn = 1), that has positive probability to occur. Since xj and xj−1 have

different colors for j = 1, 2, . . . , n, and Xn = 1 is blue, there are exactly

n

2 blue states in the

sequence (x0, x1, . . . , xn−1), namely x0, x2, . . . , xn−2. Thus n2 is an integer, so n must be even,

and Pn11 = 0 if n is odd. Finally, p

2

11 > p

1

12p

1

21, so d(1) = 2.

If N is odd then,

p

(N)

11 ≥ p12p23p34 . . . pN1 = qN > 0

so d(1)|N . As we observed previously, d(1)|2 (this did not depend on the parity of N). So

d(1) = 1 and the chain is aperiodic.

5. Let (Xn)n≥0 describe the position of the random walk at time n, and suppose that we start

at X0 = 1. If X1 = 2, the the probability to visit all states before returning to 1 is the same

as the probability of hitting N − 1 before getting ruined in the gambler’s ruin problem, with

a probability of winning a single game p and starting from 1. From class we know that this

probability is

P1 =

{

1− a−1

aN−1−1 , where a =

1

p − 1, if p 6= 12

1− 1N−1 if p = 12 .

Similarly, if X1 = N , we have that the probability of visiting all states before returning to 1 is

P2 =

{

1− b−1

bN−1−1 , where b =

1

q − 1, if q 6= 12

1− 1N−1 if q = 12 .

The reasoning is the same for any initial position X0 and p+ q = 1, so we may conclude that

P (visiting all states before returning to initial position) = pP1 + qP2

=

{

p

(

1− a−1

aN−1−1

)

+ q

(

1− b−1

bN−1−1

)

, where a = 1p − 1, b = 1q − 1, if p 6= 12

1− 2N−1 if p = 12 .

Problem 3

1. The 2-step transition matrix is M2 =

1

4

2 1 1

1 2 1

1 1 2

2. (1, 0, 0)M2 = 14 (2, 1, 1), so E(X2) =

1

4

(0× 2 + 1× 1 + 2× 1) = 3

4

.

3. Let N(i) be the mean number of transitions before visiting 2, given that X0 = i, i = 0, 1.

Then, by conditioning on the outcome of X1, N(0) = (1 +N(0))p00 + (1 +N(1))p01 + p02, and

N(1) = (1 + N(0))p10 + (1 + N(1))p11 + p12. Solving for N(0) and N(1), we obtain that the

answer is N(0) = 4.

Problem 4

1.

E0(T ) = 0, EN (T ) = 0.

2.

Ek(T ) = Ek(T | win first game)P (win first game) + Ek(T | lose first game)P (lose first game)

= (Ek+1(T ) + 1)p+ (Ek−1(T ) + 1)(1− p)

⇐⇒ xk = (xk+1 + 1)p+ (xk−1 + 1)(1− p)

⇐⇒ pxk+1 − xk + (1− p)xk−1 = −1

3. (a) We solve the characteristic equation

pX2 −X + (1− p) = 0

with discriminant

∆ = 1− 4p(1− p) = (2p− 1)2

• If p 6= 12 then ∆ > 0 and

yn = A

(

1 + 2p− 1

2p

)n

+B

(

1− 2p+ 1

2p

)n

so

yn = A+B

(

1− p

p

)n

if p 6= 1

2

.

• If p = 12 then ∆ = 0 and

yn = A

(

1

2p

)n

+Bn

(

1

2p

)n

so

yn = A+Bn if p =

1

2

.

(b) Replacing xi with Ci in (∗) gives C = − 12p−1 if p 6= 12 . Replacing xi with Ci2 in (∗) gives

C = −1 when p = 12 .

(c) If p 6= 12 , initial conditions impose{

A+B = 0,

A+B(α− 1)N = N2p−1 , where α = 1p

⇐⇒

{

A = −B,

−B(1− (α− 1)N ) = N2p−1 ,

(1)

⇐⇒

{

A = − N1−2p 11−(α−1)N ,

B = N1−2p

1

1−(α−1)N ,

(2)

So

Ek(T ) = xk = yk + Ck =

1

1− 2p

( −N

1− (α− 1)N +

N(α− 1)k

1− (α− 1)N + k

)

for p 6= 12 ,

Ek(T ) =

1

1− 2p

(

k +N

1− (α− 1)k

1− (α− 1)N

)

where α = 1p .

If p = 12 , similarly, we find {

A = 0

B = N

and Ek(T ) = Nk − k2 so for p = 12 we have Ek(T ) = k(N − k).

学霸联盟