I am trying to sharpen my intuition on some random-walk style results.
Suppose we are looking at a random walk on $\mathbb{Z}$ starting at $0$. At the $k$th step, we either walk to the left $k$ steps or to the right $k$ steps, each equally likely. What is the expected absolute distance from the origin after $n$ steps?
Equivalently,
What is the expected absolute value of the sum $$ \sum_{k = 1}^n \hat k \tag{1}$$ where $\hat k$ is a random variable that takes the value $k$ or $-k$, each with probability $1/2$?
I am familiar with the idea that adding $\sum_{k = 1}^n \widehat{ 1}$, by which I mean adding $n$ random variables that are either $1$ or $-1$ with probability $1/2$, results in expected magnitude about $\sqrt n$ (ignoring factors of $2\pi$). This sort of square root cancellation comes up in my work frequently.
More recently, randomly-signed sums of nonconstant terms have become prevalent in my work, and I'm trying to get an intuitive grasp on how they behave. With respect to $(1)$ above, if they were all positive we would get something like $n^2$. If we had mere square root cancellation, we would get something like $n^{3/2}$. But I suspect (without too much foundation; a gut instinct, I suppose) we should have more than square-root cancellation, although I do not quite know what to really expect.