对随机游走问题期望距离的估计
由于是估计，所以我们只讨论一个界。于是对于更高维度的问题暂不做讨论。
将问题简单的抽象成一个计数器，有 \(\frac{1}{2}\) 的概率 \(+1\)，\(\frac{1}{2}\) 的概率 \(-1\)。进行 \(n\) 步求最后的期望值。
稍微列一下式子，大概是这样：
\[\frac{\sum\limits_{k=0}^{n}\binom{n}{k}|2k-n|}{2^n}
\]
通过一些推导\(^1\)，可以得到分子不大于 \(2n\binom{n-1}{\lfloor\frac{n}{2}\rfloor}\)。
那么上式显然不会超过 \(\sqrt{n}\)，于是我们得到一个很松的界。
\([1]\)
\[\sum_{k=0}^{n}\binom{n}{k}|2k-n|=2\sum_{k=0}^{\frac{n}{2}}\binom{n}{k}(n-2k)=2n(\sum_{k=1}^{\frac{n}{2}}\binom{n-1}{k}-\sum_{k=1}^{\frac{n}{2}}\binom{n-1}{k-1})=2n(\binom{n-1}{\frac{n}{2}}-1)
\]