In a random integer walk along a number line (each step 0.5 probability of moving right and 0.5 probability of moving left), what is the average distance from the origin during the walk?

Other questions on here ask something that sounds like this, but I'm not sure if they are talking about the average during the walk, or just your expected distance at the end of the walk.

Follow-up question: if you have the answer for the end of a walk of length $n$ (call it $w(n)$), could you get the during walk average by doing the average $\sum_1^n{w(i)}/n$, or would that not work because the distance at each step is not independent of the distance of the previous steps?


Assume without loss of generality that the random walk starts at 0. Let $X_i$ be a random variable with $P(X_i = 1) = P(X_i = -1) = 1/2$, so that the random walk is represented by the random variable $S_n = X_1 + \cdots + X_n$. At time $m$, the distance from the origin is $|S_m|$. Let us compute $E[|S_{2m}|] = E[|X_1 + \cdots + X_{2m}|]$.

The random walk can only be at an even position, so $P(|S_{2m}| = j) = 0$ for $j$ odd. Now let $2k$ be an even integer in $[0,2m]$. By symmetry, $$P(X_1 + \cdots + X_{2m} = 2k) = P(X_1 + \cdots X_{2m} = -2k)$$ Let us compute the probability that the walker is at $2k$. If the walker moves $j$ steps forward and $2m - j$ steps backwards, he is at $2j - 2m = 2k$. Thus we require $k+m$ many $+1$'s. The sum of the $X_i$ is a binomial distribution with parameters $p = 1/2$ and $n = 2m$, so that $$P(S_{2m} = 2k) = \binom{2m}{m+k} \left(\frac12\right)^{2m}$$ and $$P(|S_{2m}| = 2k) = \binom{2m}{m+k} \left(\frac12\right)^{2m-1}.$$ Computing the expectation, \begin{align*} E[|S_{2m}|] &= \sum_{k=0}^{2m} k P(|S_{2m}| = k) \\ &= \sum_{k=0}^{m} 2k P(|S_{2m}| = 2k) \\ &= \sum_{k=0}^{m} k \left(\frac12\right)^{2m-2}\binom{2m}{k+m} \\ &= \frac{m+1}{2^{2m-1}}\binom{2 m}{m+1} \\ &= \frac{m+1}{2^{2m-1}} \cdot \frac{(2m)!}{(m+1)!(m-1)!} \\ &= \frac{m+1}{2^{2m-1}} \cdot \frac{(2m)!}{m!m!} \cdot \frac{m}{m+1} \\ &= \frac{2m}{2^{2m}} \binom{2m}{m}. \end{align*} Similarly, one can show that $$E[|S_{2m+1}|] = \frac{2m+1}{2^{2m}} \binom{2m}{m}.$$ Now we can compute the average distance. \begin{align*} E\left[\frac{|S_1| + \cdots + |S_{2n}|}{2n} \right] &= \frac{1}{2n}(E[|S_1|] + \cdots + E[|S_{2n}|]) \\ &= \frac{1}{2n}\left(\sum_{k=0}^{n-1} E[|S_{2k+1}|] + \sum_{k=1}^n E[|S_{2k}|]\right) \end{align*}

  • $\begingroup$ But isn't $E[|S_{2m}|]$ the expected distance at the end of the walk, and not during the walk? $\endgroup$ – tscizzle Dec 21 '15 at 0:23
  • $\begingroup$ @tscizzle do you mind writing the random variable you're interested in? The wording of the question is unclear $\endgroup$ – user217285 Dec 23 '15 at 23:27
  • $\begingroup$ I think it would be $\frac{(S_1+...+S_n)}{n}$, using your definition of $S$, since $S$ is the distance from the origin, and I want the expected average distance from the origin of all the positions along the walk. $\endgroup$ – tscizzle Dec 24 '15 at 0:05
  • 1
    $\begingroup$ @tscizzle $S_i$ is the position of the walk; the distance is $|S_i|$. For example, the random walk could be at position -5, and the distance would be 5. Unless you actually want to take into account it being at a negative location... $\endgroup$ – user217285 Dec 24 '15 at 1:15
  • $\begingroup$ you're 100% right, my bad. there should be absolute-value in there, as you say. $\endgroup$ – tscizzle Dec 24 '15 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.