Exam

Compute

u_{n}

for the simple random walk on

Z_{2 p}

for

A = {p}

and

p = 3

Deleting both the row and the column corresponding to state

p

we get the transition matrix of a random walk

Y_{n}

Z_{2 p - 1} = {- (p - 1), \dots, p - 1}

. Hence

\frac{1}{2} (\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array}) .

The eigen values are:

1 / 2, 0, - 1 / 2, - \sqrt{3} / 2, \sqrt{3} / 2

and an orthonormal set of eigen vectors is:

\begin{array}{rcl} v_{1} & = & \frac{1}{2} (1, 1, 0, - 1, - 1) \\ v_{2} & = & \frac{1}{2} (1, 0, - 1, 0, 1) \\ v_{3} & = & \frac{1}{2} (1, - 1, 0, 1, - 1) \\ v_{4} & = & \frac{1}{\sqrt{12}} (1, - \sqrt{3}, 2, - \sqrt{3}, 1) \\ v_{5} & = & \frac{1}{\sqrt{12}} (1, \sqrt{3}, 2, \sqrt{3}, 1) \end{array}

Now

u_{1} = ⟨ u_{1}, v_{2} ⟩ v_{2} + ⟨ u_{1}, v_{4} ⟩ v_{4} + ⟨ u_{1}, e_{v} ⟩ v_{5} = \frac{1}{4} v_{2} + \frac{1}{\sqrt{12}} v_{4} + \frac{1}{\sqrt{12}} v_{5}

and thus

u_{n + 1} = Q^{n} u_{1} = \frac{1}{\sqrt{12}} ((- \sqrt{3} / 2)^{n} v_{4} + (\sqrt{3} / 2)^{n} v_{5}) = \frac{1}{12} ((- \sqrt{3} / 2)^{n} (1, - \sqrt{3}, 2, - \sqrt{3}, 1) + (\sqrt{3} / 2)^{n} (1, \sqrt{3}, 2, \sqrt{3}, 1)) .

in particular

u_{2 m + 1} (0) = \frac{1}{3} (3 / 4)^{m}

.
For arbitrary

p

an eigen vector

v = (v_{1}, \dots, v_{2 p - 1})

is of the form:

v_{k} = A e^{i t k} + B e^{- i t k} .

The recursion:

v_{k - 1} + v_{k + 1} = λ v_{k}

gives:

λ = 2 \cos (t)

. The boundary conditions

v_{2} = λ v_{1}

and

v_{2 p - 2} = λ v_{2 p - 1}

imply that

A e^{2 i t} + B e^{- 2 i t} = (e^{i t} + e^{- i t}) (A e^{i t} + B e^{- i t})

i.e.

B = - A

and

e^{i t (2 p - 1) - i t} - e^{- i t (2 p - 1) + i t} = (e^{i t} + e^{- i t}) (e^{i t (2 p - 1)} - e^{- i t (2 p - 1)})

i.e.

\sin (2 p t) = 0

t = k π / (2 p)

k = 1, \dots, 2 p - 1

. Thus the eigen values are

2 \cos \frac{j π}{2 p}, j = 1, \dots, 2 p - 1 .

and the eigen vectors

v_{j} : = (\sin \frac{j π}{2 p}, \sin \frac{2 j π}{2 p}, \dots, \sin \frac{(2 p - 1) j π}{2 p}) .