Assume x1, x2, x3, ..., xn are independent arbitrary signs such that Pr(xi=-1)=Pr(xi=1)=1/2.
Show a positive constant K exists s.t. for m ≥ 1 and y1, . . . , yn ∈ ℝ, the following is true:
$$\begin{equation*} Pr\left(|\sum_{i=1}^m y_i x_i | > \frac 1 2 \sqrt {\sum_{i=1}^m {y_i}^2}\right) \ge K \end{equation*}$$
I think this has looks familiar with the Payley-Zygmund which states that:
$$Pr(X>θEX) \ge {(1 − θ)}^2 \frac {{E(X)}^2} {E(X^2)}$$
Do I have to replace θEX with $\frac 1 2 \sqrt {\sum_{i=1}^m {y_i}^2}$? I am a little confused as in how to do the transformation. Thanks in advance.
Lemma
There exist a positive constant $c$ such that $E|\sum_{i=1}^{m} y_ix_i| \leq c \sqrt {\sum_{i=1}^{m} y_i^{2}}$ for all choices of $m$ and $y_i$'s.
Assuming this for the moment take $X= \frac {|\sum_{i=1}^{m} y_ix_i|} {\sqrt {\sum_{i=1}^{m} y_i^{2}}}$ and $\theta =\frac 1 {c}$ in Payley - Zygmund to get the desired inequality. [ Just note that $X>1/2$ implies $X>(1/2)\theta EX$. I will leave the details here but feel free to ask for the details if necesssary].
To prove the lemma we need Uniform Boundedness Principle. Define linear maps $T_m:l^{2} \to L^{1}(P)$ by $T_m(\{y_n\})=\sum_{i=1}^{m} y_ix_i$. It is clear that these are continuous linear maps. We claim that for any fixed $\{y_n\} \in l^{2}$ $\sup_m ( E|\sum_{i=1}^{m} y_ix_i|)<\infty$. To prove this just note that the second moments of $\sum_{i=1}^{m} y_ix_i$ are bounded.Hence the first moments are also bounded.
Now we apply Uniform Boundedness Principle to conclude that $\sup \{( E|\sum_{i=1}^{m} y_ix_i|):m\geq 1 ,\sqrt {\sum_{i=1}^{m} y_i^{2}} \leq 1 \}<\infty$. This proves the lemma.