0
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Useful keywords are "central limit theorem" and "normal distribution". By the central limit theorem, $S_n/\sqrt{n}$ converges in distribution to the standard normal distribution as $n\to\infty$. So if $r_n$ is defined by $P(S_n\in(-r_n, r_n))=1/2$ for all $n$, then by the symmetry around 0 of the standard normal distribution, $r_n/\sqrt{n}\to x$ as $n\to\infty$ where $x$ is given by $\Phi(x)=3/4$, $\Phi(-x)=1/4$ (here $\Phi$ is the standard normal distribution function). $\endgroup$ – James Martin Sep 2 '11 at 15:36
1
$\begingroup$

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})$.

$\endgroup$
  • $\begingroup$ "Stirling approximation" is better known to probabilists as "the central limit theorem". :-) $\endgroup$ – Nate Eldredge Sep 2 '11 at 12:50
  • $\begingroup$ Many thanks ! Is it simple to find the exact value of r ? $\endgroup$ – user17253 Sep 3 '11 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy