Math 303 Assignment 4, out of 25
Midterm test 1 will be held in class on Friday February 14, and will be based on the material covered in
Assignments 1–4. No assignment will be given on February 7; Assignment 5 will be available on February
14.
I. Problems to be handed in:
1. This question introduces the topic of generating functions, which are another common method of calculation. Consider symmetric simple random walk (S0 , S1 , . . . ) on Z with S0 = 0. The position Sn at time
n is the result of making steps X1 , X2 , . . . , Xn . Each step Xi is a r.v. whose value is either +1 or −1,
each with probability 12 . These steps are independent and Sn = X1 + X2 + · · · + Xn .
(a) (1 point) For k a real number, compute E0 ekX1 as a function of k.
Solution: E0 ekX1 = 12 ek + 21 e−k = cosh k.
(b) (2 points) Compute E0 ekSn as a function of k using independence and the answer to part a
Solution:
n
E0 ekSn = E0 ekX1 +kX2 +···+kXn = E0 ekX1 . . . E0 ekXn = cosh k
(1)
(c) (1 point) What is E0 eikSn , where i2 = −1. You should read the notes on complex numbers posted
on our web page.
Solution:
cos k
n
(d) (1 point) Show that
because cos k =
1
2π
Rπ
−π
1
2
eik + e−ik .
eikn dk = 1 if n = 0 and is 0 if n is not 0 but is an integer.
Solution: From the notes on complex numbers,
Z
1
eiax dx = eiax + C.
ia
Therefore
1
2π
Z
π
−π
eink dk =
iπ
1 h ink iπ
1 h
e
=
cos(nk) + i sin(nk)
2πin
2πin
−π
−π
When n is an integer and is not zero the right hand side is zero because cos(nπ) = cos(−nπ)
and similarly for sin. When n = 0 we can use eink = ei0 = cos 0 + i sin 0 = 1 and
Z π
Z π
1
1
eink dk =
1 dk = 1.
2π −π
2π −π
This will be continued in later homeworks.
2. (5 points) Ross Chapter 4 #52 (recommended problem #41(b) may be useful).
A taxi driver provides service in two zones of a city. Fares picked up in zone A will have destinations
in zone A with probability 0.6 or in zone B with probability 0.4. Fares picked up in zone B will have
destinations in zone A with probability 0.3 or in zone B with probability 0.7. The driver’s expected
profit for a trip entirely in zone A is 6; for a trip entirely in zone B is 8; and for a trip that involves both
zones is 12. Find the taxi driver’s average profit per trip.
Solution:
Thesequence of zones is an irreducible aperiodic Markov chain with S = {A, B} and
.6 .4
P=
giving stationary distribution π = (3/7, 4/7). The long-run proportion of steps
.3 .7
which are from state i to state j is πi Pij (the proportion of time in state i × the proportion of those
times when we jump to j). Hence the long-run average profit per trip is
6πA PAA + 8πB PBB + 12(πA PAB + πB PBA ) = 62/7.
3. Ross Chapter 4 #67.
At all times an urn contains N balls– some white balls and some black balls. At each step in time a
coin is flipped, having probability p, 0 < p < 1, of landing with heads. If heads appears, then a ball is
chosen at random from the urn and is replaced by a white ball; if a tail appears then a ball is chosen at
random from the urn and is replaced by a black ball. Let Xn denote the number of white balls after the
nth step. This is a Markov chain.
(a) (1 point) What are the communicating classes? What are their periods? Are they transient or
recurrent?
Solution: irreducible, aperiodic, recurrent
(b) (1 point) Compute the transition probabilities Pij .
Solution: Pi,i+1 = p(N − i)/N for i = 0, 1, . . . , N − 1,
Pi,i−1 = (1 − p)i/N for i = 1, . . . , N ,
Pi,i = pi/N + (1 − p)(N − i)/N for i = 0, . . . , N .
(c) (2 points) Find limn→∞ Pi (Xn = j) as a function of p and N .
Solution: Bin(N, p), so πi =
N
i
pi (1 − p)N −i for i = 0, 1, . . . , N .
(d) (1 point) If p = 1 what is the expected time until there are only white balls in the urn, if initially
there are i white and N − i black? This is not related to Thm 4.1. and the answer involves a sum
from i to N − 1.
Solution: Let Tj be the number of balls chosen until the first black ball is chosen, starting
from j white balls. This is geometric with p = (N − j)/N = 1 − j/N , so ETj = N/(N − j).
PN −1
PN −1
Therefore, E(time) = E( j=i Tj ) = N j=i (N − j)−1 .
4. §4 #54.
Consider the Ehrenfest urn model in which M molecules are distributed between two urns, and at each
time one of the molecules is picked at random and is then removed from its urn and placed in the other
urn. Let Xn denote the number of molecules in urn 1 after the nth switch and let µn = EXn .
(a) (3 points) Show that µn+1 = 1+(1−2/M )µn . Recall that expectations have the property EXn+1 =
E[E(Xn+1 |Xn )].
Solution: µn+1 = EXn+1 = E[E(Xn+1 |Xn )]. Given Xn , Xn+1 = Xn + 1 with probability
(M − Xn )/M , and Xn+1 = Xn − 1 with probability Xn /M . Therefore,
µn+1 = E[(Xn + 1)(M − Xn )/M + (Xn − 1)Xn /M ]
1
M −2
=
E[(M − 2)Xn + M ] =
µn + 1.
M
M
(b) (2 points) Use the last part to prove that for M 6= 2 µn =
for M = 2?
M
2
+
M −2 n
M
E[X0 ] −
M
2
. Is it true
Solution: By iteration, the solution of µn+1 = aµn + b is µn = an µ0 + b(1 − an )/(1 − a) and
the result follows by substitution of a = (M − 2)/M and b = 1. If M = 2 then these formulas
have division by zero. To sort this out go back to µn+1 = 1 + (1 − 2/M )µn , which holds for all
n ≥ 0, set M = 2 to get µn+1 = 1; in other words µn = 1 for all n ≥ 1.
5. (5 points) §4 #76.
On a chessboard compute the expected number of moves it takes a knight, starting in one of the four
corners to return to its initial position, if we assume it is the only piece on the board and at each move
it is equally likely to choose any of its legal moves. (Use the idea in Example 4.36).
P
Solution: The following chessboard has entry j wi,j in square i (note that i represents a board
location, or node, and not just a row or column):
2
3
4
4
4
4
3
2
3
4
6
6
6
6
4
3
P
4
6
8
8
8
8
6
4
P
4
6
8
8
8
8
6
4
4
6
8
8
8
8
6
4
4
6
8
8
8
8
6
4
3
4
6
6
6
6
4
3
2
3
4
4
4
4
3
2
P
For i a corner node, j wi,j = 2. Also, i j wi,j = 336.
By Example 4.36 (4.32 in 9th edition), for i a corner node, πi =
return time is π1i = 168.
2
336
=
1
168 .
Therefore, the mean
II. Recommended problems: These provide additional practice but are not to be handed in.
1
2
Pi,i−1 =
§4 #62* [ n+1
,(p − q)/(1 − (q/p)n ) + (q − p)/(1 − (p/q)n )], 68*, #70 [Pi,i+1 = ( m−i
m ) ,
m 2
(
)
i
( mi )2 , Pi,i = 2 mi m−i
πi = 2m
.], §4 #71, #73.
m ,
(m)
Quote of the week:
Men wanted for hazardous journey. Low wages, bitter cold, long hours of complete darkness. Safe return
doubtful. Honour and recognition in event of success.
unattributed quote from Ernest Shackleton
© Copyright 2024 ExpyDoc
