I'm trying to find a set of uniform measure 1/2 over $ \{ -1,1 \} ^n \times \{-1,1\}^n$ such that the inner product of $(x,y)\in\{ -1,1 \} ^n \times \{-1,1\}^n$ will hold $|\langle x,y\rangle|< \frac{\sqrt(n)}{c}$ for some constant $c$.


I believe that a better way to look at it is saying I have a simple random walk. How do I find $r$ such that after $n$ steps the random walk will land in $(-r,r)$ w.p. 1/2 ?
(Hopefully, for my needs and as I suspect, in fact $r$ will be $\Theta (\sqrt(n))$).


Formally, take independent random variables $Z\_1, Z\_2,\dots$, where each variable is either $1$ or $-1$, with a 50% probability for either value, and set $S\_0 = 0$ and $S\_n =\sum\_{j=1}^nZ\_j$. for what $r$ holds $$Pr[|\sum\_{j=1}^nZ\_j| \leq r] = 0.5$$



Radius of random walk on Z
By simple counting argument one has
$$P(X\_1+\cdots+X\_n=r)=\frac{1}{2^n}\binom{n}{\frac{n-r}{2}}$$
ignoring parity conditions. Stirling approximation implies that if $r=o(n)$ we have
$$\binom{n}{\frac{n-r}{2}}=O\left(n^{-\frac{1}{2}}2^n\right).$$
So that
$$P(|X\_1+\cdots+X\_n|\le r)=\sum\_{k=-r}^r \frac{1}{2^n}\binom{n}{\frac{n-k}{2}}=O(rn^{-\frac{1}{2}}).$$
In particular if $r$ is so that $P(|X\_1+\cdots+X\_n|\le r)=0.5$, then $r=\Theta(\sqrt{n})$.


