40 1. Random Walk and Discrete Heat Equation

To do this, assume #(Zd\A) = K, let

˜

T

A

= min{n ≥ 1 : Sn ∈ A},

and for x, y ∈ Zd \ A, we define

J(x, y) = P{

˜

T

A

∞,S

˜A

T

= y | S0 = x}.

Then J is a K × K matrix. In fact (Exercise 1.25),

(1.31) (J − I) G = −I.

In particular, G is invertible.

1.6. Exercises

Exercise 1.1. Suppose that X1,X2,... are independent, identically

distributed random variables such that

E[Xj] = 0, P{|Xj| K} = 0,

for some K ∞.

• Let M(t) =

E[etXj

] denote the moment generating function

of Xj. Show that for every t 0, 0,

P{X1 + · · · + Xn ≥ n} ≤ [M(t)

e−t]n.

• Show that for each 0, there is a t 0 such that

M(t) e−t 1. Conclude the following: for every 0,

there is a ρ = ρ( ) 1 such that for all n,

P{|X1 + · · · + Xn| ≥ n} ≤ 2

ρn.

• Show that we can prove the last result with the boundedness

assumption replaced by the following: there exists a δ 0

such that for all |t| δ,

E[etXj

] ∞.

Exercise 1.2. Prove the following: there is a constant γ (called

Euler’s constant) and a c ∞ such that for all positive integers n,

⎛

⎝

n

j=1

1

j

⎞

⎠

− γ − log n ≤

c

n

.