<< . .

. 65
( : 70)

. . >>

for all a, b ∈ A. By considering

g(x) = (1 ’ )f (x) + a0

for some a0 ∈ A and > 0 show that

inf{ f (a) ’ a : a ∈ A} = 0

and deduce that f has a ¬xed point in A.
Give an example to show that the conclusion may be false if any one of
the three conditions:- convex, closed and bounded is omitted.
The following result is useful in the theory of Markov chains (see Exer-
cise K.258). Suppose pij ≥ 0 for 1 ¤ i, j ¤ n and n pij = 1 for 1 ¤ i ¤ n.
Give R the norm
j=1 |xj |. By choosing an appropriate
1 where x 1 =
A and f show that we can ¬nd πi ≥ 0 for 1 ¤ i ¤ n with n πi = 1 such
πi pij = πj .

Exercise K.257. [12.1, P] Throughout this question (X, d) is a non-empty
metric space with the Bolzano-Weierstrass property and T : X ’ X is
a map such that d(T x, T y) ¤ d(x, y) and such that, given any x, y ∈ X
such that x = y we can ¬nd a strictly positive integer N (x, y) such that
d(T N (x,y) x, T N (x,y) y) < d(x, y).
(i) Show that the map S : X ’ R given by Sx = d(x, T x) is continuous.
Explain why this means that there is a y ∈ X such that d(y, T y) ¤ d(T x, x)
for all x ∈ X. Show that, in fact y = T y. Show that y is the unique ¬xed
point of T .
(ii) Let > 0 and write

Un = {x ∈ X : d(T n x, y) < }.

Show that Un ⊆ Un+1 and that Un is open for all n ≥ 1. Write U = ∞ Un
and F = X \ U . Why does F have the Bolzano-Weierstrass property? Show
that T x ∈ F whenever x ∈ F . Use part (i) to show that, if F were non-
empty, there would exist a w ∈ F with T w = w. Deduce that F is indeed
(iii) Show that, if x ∈ X, then d(T n x, y) ’ 0 as n ’ ∞.
Exercise K.258. (Finite Markov chains.) [12.1, T!, ‘ ] In a ¬nite
Markov chain with states 1, 2, . . . , m, if the system is in state i at time
n it will be in state j at time n + 1 with probability pij irrespective of any
earlier history. Thus, if it is in state i with probability qi at time n and in
state j with probability qj at time n + 1, we have
qj = qi pij .

The reader may ignore the previous paragraph but it explains why we are
interested in the space
X = {q ∈ Rm : qi = 1, qs ≥ 0 [1 ¤ s ¤ m]}

and the map T : X ’ Rm given by T q = q where qj = m qi pij for all
1 ¤ j ¤ m. Verify that if, as we shall do from now on, we take pij ≥ 0 for all
1 ¤ i, j ¤ m and m pij = 1 for all 1 ¤ i ¤ m then T q ∈ X for all q ∈ X
and so we may consider T as a map from X to X.
Finally we have to choose a metric d. In most of this book the particular
choice of metric has not been important but here it is. We take
d(u, v) = u ’ v |ui ’ vi |

for all u, v ∈ X.
(i) Explain why (X, d) has the Bolzano-Weierstrass property.
(ii) Show that d(T u, T v) ¤ d(u, v) for all u, v ∈ X.
(iii) Show that, if n ≥ 1,
(T q)j = qi pij

(n) (n)
for all 1 ¤ j ¤ m where pij ≥ 0 for all 1 ¤ i, j ¤ m and m pij = 1 for
all 1 ¤ i ¤ m. If you know some probability prove this both by an algebraic
and a probabilistic argument.
Please send corrections however trivial to twk@dpmms.cam.ac.uk

(iv) Show that, if
(N )
pij > 0 for all 1 ¤ i, j ¤ m

for some N ≥ 1, then d(T N u, T N v) < d(u, v) for all u, v ∈ X with u = v.
(v) Conclude, using Exercise K.257, that, provided only that holds for
some N ≥ 1, there is a unique π ∈ X such that T π = π and that, if q ∈ X,
then d(T n q, π) ’ 0 as n ’ ∞. If the associated Markov chain has been
running for a long time, what can you say about the probability that it is in
state i?
(vi) Suppose that m = 2, p12 = p21 = 1 and p11 = p22 = 0. Show that
is a unique π ∈ X such that T π = π. For which q ∈ X is it true that
d(T n q, π) ’ 0 as n ’ ∞? Why does your result not contradict (v)?
(vii) Suppose that m = 2, p12 = p21 = 0 and p11 = p22 = 1. Find all the
π ∈ X such that T π = π. What can you say about the behaviour of T n q
as n ’ ∞ for each q ∈ X? Why does your result not contradict (v)?
(viii) Suppose that m = 4 and that pij = 1/2 if 1 ¤ i, j ¤ 2 or 3 ¤ i, j ¤
4 and that pij = 0 otherwise. Find all the π ∈ X such that T π = π. What
can you say about the behaviour of T n q as n ’ ∞ for each q ∈ X?
(ix) Note that, by Exercise K.256, the equation T π = π always has a
solution in X even if does not hold.
Exercise K.259. (Countable Markov chains.) [12.1, T!] In this exer-
cise and the next we consider Markov chains with an in¬nite number of states
1, 2, . . . . In algebraic terms we consider a collection of positive numbers pij
[1 ¤ i, j] such that ∞ pij = 1 for each i ≥ 1.
(i) Consider l the space of real sequences whose sum is absolutely con-

n=1 |xn |. Show that, if we write
vergent, with norm 1 given by x ∞ =

(T x)j = j=1 xi pij , then T is well de¬ned continuous linear map from l 1 to
l1 with operator norm T = 1. Show further that, if we write

X = {q ∈ l1 : q = 1 and qi ≥ 0 for all i ≥ 1},

then T q ∈ X whenever q ∈ X. (Note that you are manipulating in¬nite
sums and you must justify each step carefully. Results like Lemma 5.3.9 may
be useful.)
(ii) We shall only be interested in systems satisfying the following exten-
sion of . If k ≥ 1 there exists an N (k) such that
(N (k))
> 0 for all 1 ¤ i, j ¤ k.

Show that, under this condition, given any u, v ∈ X with u = v, we can
¬nd an N ≥ 1 such that d(T N u, T N v) < d(u, v).

(iii) Show, under assumption , that, if the equation T π = π has a
solution π ∈ X, then it is unique. Let

Y = {h ∈ l1 : hi ≥ 0 for all i ≥ 1.}

Find all the solutions of the equation T h = h with h ∈ Y ¬rstly under the
assumption that the equation T π = π has a solution π ∈ X and secondly
under the assumption that it does not.
(iv) Show, under assumption , that, if the equation T π = π has a
solution π ∈ X, then πi > 0 for all i.
(v) Consider the following systems. In each case show we have a Markov
chain satisfying . By solving the appropriate di¬erence equations, or
otherwise, show that in case (a) the equation T π = π has a solution π ∈ X
but in cases (b) and (c) it does not.
(a) p12 = 1; pi i’1 = 1/2, pi i = pi i+1 = 1/4 for i ≥ 2; pij = 0 otherwise.
(b) p12 = 1; pi i+1 = 1/2, pi i = pi i’1 = 1/4 for i ≥ 2; pij = 0 otherwise.
(c) p12 = 1; pi i’1 = pi i = pi i+1 = 1/3 for i ≥ 2; pij = 0 otherwise.

Exercise K.260. [12.1, T!, ‘ ] This question continues the previous one.
We assume that condition holds and that the equation T π = π has a
solution π ∈ X. We will need part (ii) of Exercise K.195.
(i) Let J ≥ 1 be ¬xed. Show, using part (iv) of question K.259, that we
can ¬nd an h ∈ Y such that T h = h and hJ = 1.
(ii) We continue with the notation of (i). Explain why X does not have
the Bolzano-Weierstrass property but

XJ = {q ∈ X : hi ≥ qi for all i ≥ 1}

does. Explain why XJ is non-empty and show, carefully, that T q ∈ XJ
whenever q ∈ XJ . Deduce that, if q ∈ XJ , then T n q ’ π 1 ’ 0 as n ’ ∞.
(iii) Let e(p) ∈ l 1 be given by e(p)p = 1, e(p)i = 0 otherwise. Explain why
T n e(p)’π 1 ’ 0 as n ’ ∞. Deduce that, if q ∈ X, then T n q’π 1 ’ 0.
Interpret this result probabilistically.

Exercise K.261. [12.2, P] Let (X, d) be a complete metric space and T :
X ’ X a mapping such that T n is a contraction mapping. Show that T has
a unique ¬xed point. [Hint. Show that if w is a ¬xed point for T n then so is
T w.]
If you have done Question K.253, explain why the example asked for in
the last paragraph of that question does not contradict the result of the ¬rst
paragraph of this question.
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Consider the space C([a, b]) with the uniform norm. Let φ be a continuous
real-valued function on R — [a, b] which satis¬es the Lipschitz condition

|φ(x, t) ’ φ(y, t)| ¤ M for x, y ∈ R and t ∈ [a, b],

and let g ∈ C([a, b]). De¬ne T : C([a, b]) ’ C([a, b]) by
(T h)(t) = g(t) + φ(h(s), s) ds.

Show, by induction, or otherwise that
(T n h)(t) ’ (T n k)(t) M (t ’ a)n h ’ k
∞ ∞
for all h, k ∈ [a, b].
Show that T has a ¬xed point and comment brie¬‚y on the associated
theorem on the existence of solutions of a certain di¬erential equation.

Exercise K.262. [12.2, P] Suppose that f : R ’ R is di¬erentiable with
|f (x)| < M for all x ∈ R. Show that the system of equations
aij f (xj ) + bi [1 ¤ i ¤ n]
xi =

with aij and bi real has a unique solution provided that
n n
a2 < .
i=1 j=1

Exercise K.263. [12.2, P, S] Consider the di¬erential equation for a func-
tion y : R ’ R

y (t) = y(t)± , y(0) = 0

where ± is real and strictly positive. For which values of ± does have only
one solution and for which values of ± does it have more than one? If has
only one solution, prove this. If has more than one solution, give at least
two solutions explicitly.

Exercise K.264. [12.2, P] Dieudonn´ is associated in most mathemati-
cians™ minds with the abstract approach of Bourbaki and his own text Foun-
dations of Modern Analysis [13]. He may have had this in mind when he

wrote the determinedly concrete In¬nitesimal Calculus [14] from which this
exercise is taken.
(i) Suppose f : R2 ’ R is a continuous function with f (t, u) < 0 when
tu > 0 and f (t, u) > 0 when tu < 0. Explain why f (0, t) = f (u, 0) = 0 for
all t and u. If y : R ’ R is a di¬erentiable function with

y (t) = f (t, y(t)) for all t ∈ R, y(0) = 0,

show, by considering the behaviour of y at a maximum and a minimum in
each interval [0, c] with c > 0, or otherwise, that y(t) = 0 for all t ≥ 0. Show
that y(t) = 0 for all t ∈ R and so has a unique solution.
(ii) Now de¬ne
if x ≥ t2 ,

f (t, u) = ’2x/t if t2 > x > ’t2 ,

if ’t2 > x.

Verify that f is well de¬ned and continuous everywhere and satis¬es the
hypotheses of (i). Now set y0 (t) = t2 and de¬ne
yn+1 (t) = f (s, yn (s)) ds.

Show that yn (t) fails to converge as n ’ ∞ for any t = 0 although, as we
know from (i), has a unique solution.
Exercise K.265. [12.3, P] (This exercise makes repeated use of the mean
value inequality.)
(i) Consider the di¬erential equation

y (t) = |y(t)|±

with ± > 1. Suppose y is a solution with y(0) ≥ 1. Show that y(t) is strictly
increasing for t ≥ 0 and y(t) ≥ t + 1 for t ≥ 0. Let tj be de¬ned by taking
y(tj ) = 2j . Show that tj+1 ’ tj ¤ 2(1’β)j and deduce that there exists a
t— ∈ R such that tj ’ t— as j ’ ∞. Conclude that y(t) ’ ∞ as t ’ t—
through values of t < t— .
(ii) Prove the result of Example 12.3.6 by an argument along the lines of
part (i).
(iii) Show that there exists a di¬erentiable function y : [0, ∞) ’ R such
that y(0) = e and

y (t) = y(t) log y(t).
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.266. (Euler™s method.) [12.3, T] The next few questions
deal with Euler™s method for ¬nding approximate solutions of a di¬erential
equation. They were suggested by the typically neat treatment in [44]. You
will ¬nd the discussion more interesting if you have used Euler™s method
before or if you try one of the excellent demonstrations which now exist on
the Internet.
Suppose we wish to solve the di¬erential equation y (t) = f (t, y(t)),
y(0) = y0 numerically on a computer. (We shall look at y(t) for t ≥ 0
but the same ideas apply when t ¤ 0.) A natural approach is to seek (ap-
proximate) solutions at the points xr = rh where the strictly positive number
h is called the ˜step length™ and r is a positive integer. Explain brie¬‚y why
we expect
y (r + 1)h ≈ y(rh) + f (rh, y(rh))h.
This suggests that our approximation yr to y(rh) could be obtained by solving
the system of equations
yr+1 = yr + f (xr , yr )h. (A)
This is called Euler™s method.
Euler™s method seems reasonable and works on suitable test examples.
In this question we investigate its behaviour in general. We shall assume
stronger conditions on f than we did in Theorem 12.2.3 and elsewhere in
Sections 12.2 and 12.3. Speci¬cally, we demand that f : R2 ’ R is once
di¬erentiable and there exist constants K and L such that |f,2 (t, u)| ¤ K
|f,1 (t, u)| + |f,2 (t, u)f (t, u)| ¤ L
for all (t, u) ∈ R2 . Explain brie¬‚y why these conditions imply the existence
of a unique di¬erentiable y : R ’ R such that
y (t) = f (t, y(t)), y(0) = y0 . (B)
Explain why y is twice di¬erentiable and express y (t) in terms of f (t, y(t)),
f,1 (t, y(t)) and f,2 (t, y(t)). By using the 2nd mean value theorem (Exer-
cise K.49), or otherwise, show that
|y (n + 1)h) ’ y(nh) ’ f (nh, y(nh))h| ¤ .
Use this result to show that
|y (n + 1)h) ’ yn+1 | ¤ (1 + Kh)|y(nh) ’ yn | + .

Deduce that
((1 + Kh)N +1 ’ 1).
|y(N h) ’ yN | ¤
In order to emphasise the dependence on h, let us write yn = yn . Show
that, if the positive number a is ¬xed and we take hN = a/N , then

[h ]
((1 + KhN )N +1 ’ 1).
|y(a) ’ yN N | ¤
Observe (or recall) that that, if x ≥ 0, then
1 m1
x m
xr ≥ 0,
e ’ (1 + x) ≥ ’
r mr

and deduce that
LhN aK
[h ]
|y(a) ’ yN N | ¤ (e ’ 1) (C)
[h ]
and, in particular, yN N ’ y(a) as N ’ ∞.

Exercise K.267. [12.3, T, ‘ ] We continue with the discussion of Exer-
cise K.266. Informally, we may interpret the inequality (C) in Exercise K.266
as saying that that ˜our error estimate for Euler™s method is roughly propor-
tional to the step length™. nequality (C) is, however, only an upper estimate
for the error. Can we get a substantially better estimate? Consider the spe-
cial case f (t, u) = u, y0 = 0 and a = 1. Show that y(t) = et and yn = (1+y)n .
Show that
[h ]
y(1) ’ yN N = e ’ (1 + N ’1 )N
1 N1 1 hN
≥ ’ ≥ = .
r Nr
r! 2N 2

Informally, we may say ˜in this case, the error for Euler™s method decreases
no faster than the step length™.
We see that (roughly speaking) halving the step length in Euler™s method
will double the amount of calculation and only halve the error. Thus Euler™s
method is a reasonable one if we want to solve one di¬erential equation to
a reasonable degree of accuracy but unattractive if we want to solve many
di¬erential equations to a high degree of accuracy.
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.268. [12.3, T, ‘ ] We continue with the discussion of Exer-
cises K.266 and K.267. So far we have ignored the fact that computers only
work to a certain degree of accuracy. As a simple model to take account of
this, we replace equation (A) of Exercise K.266 by

yr+1 = yr + f (xr , yr )h +
˜ ˜ ˜ (D)

where the ˜error™ r satis¬es the condition | r | ¤ for some ¬xed > 0. As
before, we impose the initial condition y0 = 0.
(i) As in Exercise K.266, we take yn = yn , ¬x a positive number a and
take hN = a/N . Show that

[h ]

<< . .

. 65
( : 70)

. . >>