 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ia/paper-2/11f/iv/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Only even times contribute, and at time

2 k

the walk is at zero exactly when it has made

k

steps in each direction. By linearity of expectation,

E (V_{2 n}) = \sum_{j = 0}^{2 n} P (S_{j} = 0) = \sum_{k = 0}^{n} \frac{( k 2 k )}{4 ^{k}} .

The Stirling formula implies that

\frac{( k 2 k )}{4 ^{k}} \sim \frac{1}{πk} .

Hence there is a constant

c_{0} > 0

such that this term is at least

c_{0} / k

for every

k \geq 1

, after decreasing

c_{0}

to cover the finitely many small values. Therefore

E (V_{2 n}) \geq c_{0} \sum_{k = 1}^{n} \frac{1}{k} \geq c_{0} \int_{1}^{n + 1} x^{- 1/2} d x .

The final expression is

2 c_{0} (n + 1 - 1)

, so, after another adjustment for small

n

, there is a constant

c > 0

with

E (V_{2 n}) \geq c n

for every

n

 New to topics? Read the docs here!