Random walks

An easy mistake to make in this problem is to find the average value of ${A}_{100}$ . This is 0, since for any case with a value of $n$ there's equally many cases with a value of $-n$ . This approach is not correct, because while it finds the average the $-n$ cases would actually count as a positive distance and they would not cancel.

Let's find the average value of the distance to 0 squared, ${{A}_{i}}^{2}$ . Suppose the amount we add for step $n$ is ${B}_{n}$ , which becomes $0$ if it's past $i$ . The overlines represent average values. $\overline { {{ A }_{ i }}^{2} } = \overline{{\left({B}_{1}+{B}_{2}...+{B}_{i}\right)}^{2}}$ $\overline { {{ A }_{ i }}^{2} } = \left(\overline{{{B}_{1}}^{2}}+\overline{{{B}_{2}}^{2}}...+\overline{{{B}_{i}}^{2}}\right)+\sum _{m\neq n }^{ \quad }{ \overline{{ B }_{ m }B_{ n }} }$

We know for each $m, n$ that $\overline{{ B }_{ m }B_{ n }}=0$ since it's equally probable for their product to be $-1$ or $1$ . We're left with

$\overline { {{ A }_{ i }}^{2} } = \left(\overline{{{B}_{1}}^{2}}+\overline{{{B}_{2}}^{2}}...+\overline{{{B}_{i}}^{2}}\right) = i$

From this $\left|{A}_{i}\right|$ can be expected to be about $\sqrt{i}$ .

Let's conisider the walk as a vector $W=(x_1,x_2,...,x_{100})$ , such that $x_i \in \{1,-1\}$ for $1 \leq i \leq 100$ . The displacement after $100$ steps is $\displaystyle A_{100}=\bigg|\sum_{k=1}^{100} x_i\bigg|$ . Since $100$ is even, the possible value of the final displacement are $A_i=2n$ , $0\leq n \leq 50$ , $n \in \mathbb{N}$ . Hence,

$\displaystyle \mathbb{P}(A_{100}=0)=2 \cdot \frac{1}{2^{100}} \binom{100}{50} \\ \displaystyle \mathbb{P}(A_{100}=2)=2 \cdot \frac{1}{2^{100}} \binom{100}{49} \\ \hspace{60pt} \vdots \\ \displaystyle \mathbb{P}(A_{100}=2n)=2 \cdot \frac{1}{2^{100}} \binom{100}{50-n}$

So, the expected value of the random variable $A_{100}^2$ is

$\displaystyle \mathbb{E}(A_{100}^2=4n^2)=\frac{1}{2^{99}} \sum_{n=0}^{50} 4n^2 \binom{100}{50-n}=100=K^2$

Eventually

$\displaystyle \sqrt{K}=\boxed{10}$