How far from home after n random steps?

Question

A walker starts at 0 and takes n steps, each +1 or -1 with probability 	frac12, independently. Let Sn be his final position. What is the expected distance from the origin, E\lvert Snvert, and how does it grow with n? (Note: E[Sn] = 0 by symmetry, we want the expected absolute distance.)

Accepted Answer

The average signed position is 0: he is equally likely to drift either way. But he is rarely sitting exactly at 0, so the average distance is positive and grows. A quick handle comes from the variance. Each step has mean 0 and variance 1, and steps are independent, so \operatorname{Var}(Sn) = n, \qquad E[Sn^2] = n. The typical distance is therefore of order \sqrt{n}, the walker spreads out like the square root of time, the signature of diffusion. (Doubling the number of steps only multiplies the typical distance by \sqrt{2}, not 2.) The exact expected absolute distance, for an even number of …

How far from home after n random steps?

Your answer

More Probability questions