How Far Does a Random Walk Wander?

Level 4●●●○○ Medium~5 min

Problem

Let

S_n=\sum_{i=1}^n X_i

be a symmetric simple random walk,

X_i=\pm1

with probability

1/2

each, independent. Find

E[S_n]

and

\mathrm{Var}(S_n)

. Roughly how far from the origin is the walk after

n

steps — i.e. estimate

E[|S_n|]

for large

n

3 / 36