# lowerbounding the expectation of maximum of $K$ random walking

Let $$X_{i,j}$$ be $$K \times N$$ i.i.d. random variables such that $$P(X_{i,j} = 1) = P(X_{i,j} = -1) = \frac{1}{2}$$, and $$S_p = \sum_{q=1}^{N} X_{p,q}$$ be $$K$$ i.i.d. random variables, each of which is an $$N$$ step random walking.

How to prove $$E[\max_{p \in [K]} S_p] \ge \Omega(\sqrt{N\log K})$$?