Edit: I couldn’t point this out earlier because I was on my phone, but the maximum attained by a random walk is not actually O(√N), it’s O(√NloglogN). It really doesn’t affect your argument, but strictly speaking the claim is otherwise not true.
Interesting. You were correct and I was wrong here. I was unaware that the expected maximum was enough larger than the expected final value that it ended up asymptotically different.
Interesting. You were correct and I was wrong here. I was unaware that the expected maximum was enough larger than the expected final value that it ended up asymptotically different.