42 1. Random Walk and Discrete Heat Equation

• (Monotone Convergence Theorem) Show that if 0 ≤ X1 ≤

X2 ≤ · · · , then

E lim

n→∞

Xn = lim

n→∞

E[Xn].

In both parts, the limits and the expectations are allowed to take on

the value infinity.

Exercise 1.7. Prove Theorem 1.6.

Exercise 1.8. Suppose X1,X2,... are independent random variables

each of whose distribution is symmetric about 0. Show that for every

a 0,

P max

1≤j≤n

X1 + · · · + Xj ≥ a ≤ 2 P{X1 + · · · + Xn ≥ a}.

(Hint: Let K be the smallest j with X1 + · · · + Xj ≥ a and consider

P{X1 + · · · + Xn ≥ a | K = j}. )

Exercise 1.9. Suppose X is a random variable taking values in Z.

Let

φ(t) =

E[eitX

] = E[cos(tX)] + i E[sin(tX)] =

x∈Z

eitx

P{X = x},

be its characteristic function. Prove the following facts:

• φ(0) = 1 , |φ(t)| ≤ 1 for all t and φ(t + 2π) = φ(t).

• If the distribution of X is symmetric about the origin, then

φ(t) ∈ R for all t.

• For all integers x,

P{X = x} =

1

2π

π

−π

φ(t)

e−ixt

dt.

• Let k be the greatest common divisor of the set of integers

n with P{|X| = n} 0. Show that φ(t + (2π/k)) = φ(t)

and |φ(t)| 1 for 0 t (2π/k).

• Show that φ is a continuous (in fact, uniformly continuous)

function of t.

Exercise 1.10. Suppose X1,X2,... are independent, identically dis-

tributed random variables taking values in the integers with char-

acteristic function φ. Let Sn = X1 + · · · + Xn. Suppose that the