Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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). –  James Martin Sep 2 '11 at 15:36

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
"Stirling approximation" is better known to probabilists as "the central limit theorem". :-) –  Nate Eldredge Sep 2 '11 at 12:50
    
Many thanks ! Is it simple to find the exact value of r ? –  Tom Gur Sep 3 '11 at 8:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.