1.1. Simple random walk 11

1.1.5. Several dimensions. We now consider a random walker on

the d-dimensional integer grid

Zd

= {(x1,...,xd) : xj integers} .

At each time step, the random walker chooses one of its 2d nearest

neighbors, each with probability 1/2d, and moves to that site. Again,

we let

Sn = x + X1 + · · · + Xn

denote the position of the particle. Here x, X1,...,Xn,Sn represent

points in

Zd,

i.e., they are d-dimensional vectors with integer compo-

nents. The increments X1,X2,... are unit vectors with one compo-

nent of absolute value 1. Note that Xj

· Xj = 1 and if j = k, then

Xj · Xk equals 1 with probability 1/(2d); equals −1 with probability

1/(2d); and otherwise equals zero. In particular, E[Xj · Xj] = 1 and

E[Xj · Xk] = 0 if j = k. Suppose S0 = 0. Then E[Sn] = 0, and a

calculation as in the one-dimensional case gives

E[|Sn|2]

= E[Sn · Sn] = E

⎡⎛

⎣⎝

n

j=1

Xj⎠

⎞

·

⎛

⎝

n

j=1

Xj⎠⎦

⎞⎤

= n.

o

Figure 2. The integer lattice Z2