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

Let us consider a boolean hypercube $C = \{-1, 1\}^n$. Let $S = \{x \in C \mid |\{i \mid x_i = -1\}| = \varepsilon n\}$ be a Hamming sphere in $C$ (here $\varepsilon$ stands for the fixed parameter from $(0, 1/2)$). Let us sample $X \in S$ uniformly at random. And we are interested in estimating $\mathrm{E}[X_1 X_2 \ldots X_{\alpha n}]$, where $\alpha$ is a sufficiently small constant.

We would like to argue that this expectation is somewhat close to $(1 - 2\varepsilon)^{\alpha n}$ (that could have been the case if $X_i$'s were independent).

Is there any way to avoid tedious computations here? It is tempting to say that $X_i$'s are "almost independent" and use some "limit theorem".

Or is it possible to replace $X_i$'s by properly correlated gaussians and argue that expectation doesn't change much?

After all, I feel that this question must be considered somewhere, so it would be nice to find an appropriate reference.

share|improve this question
1  
I don't think there's any hope of using limit theorems in your case, where you take a constant proportion of coordinates; hard computations may be necessary. –  Mark Meckes Mar 1 '11 at 14:59
add comment

1 Answer

up vote 5 down vote accepted

If I am not mistaken, this expectation equals the coefficient of $x^{\varepsilon n}$ in $(1-x)^{\alpha n}(1+x)^{(1-\alpha) n}$ divided by the corresponding coefficient in $(1+x)^n$ (which equals, of course, $\binom{n}{\varepsilon n}$). Such coefficient may be represented as integrals over unit circle (and so over $[0,2\pi]$) and their asymptotics may be calculated by some standard machinery. I do not write down more, because I do not understand, what exactly do you want (say, which small constant is more, $\alpha$ or $\varepsilon$? Is $n$ chosen large after these constants are already fixed, or $n$ tends to infinity simultaneously with constants tending to zero?).

Update.

Such statement seems to be true. Call two values log-equivalent, if their logarithms are equivalemt. We choose $x_0:=\varepsilon/(1-\varepsilon)$, then $\binom{n}{\varepsilon n}$ is log-equivalent to $x_0^{-\varepsilon n} (1+x_0)^n$. Then interpret our coefficient as $(2\pi i)^{-1}\int f(z)dz/z$ for $f(z)=z^{-\varepsilon n} (1-z)^{\alpha n}(1+z)^{(1-\alpha)n}$, and integral is taken over the circuit around 0. Choose the circuit $|z|=x_0$ and note that for small $\alpha$ we will have $|f(z)|\leq f(x_0)$ (this is less or more clear: $|1+z|\leq 1+x_0$ and for $\alpha$ close to 0 this is most important, we have to be careful with neighborhood of $x_0$, but it is ok too). Then just apply this estimate for estimating integral.

share|improve this answer
    
I need the following statement: for all sufficiently small $\varepsilon > 0$ there exists sufficiently small $\alpha > 0$, such that "expectation is asymptotically close to $(1 - 2 \varepsilon)^{\alpha n}$". –  ilyaraz Mar 1 '11 at 15:25
    
what do you mean by "asymptotically close"? The ratio is close to 1? The ratio is bounded from both sides? –  Fedor Petrov Mar 1 '11 at 15:29
    
The ratio $E[\ldots] / (1 - 2 \varepsilon)^{\alpha n}$ can be upper-bounded with $2^{o(n)}$, I think. –  ilyaraz Mar 1 '11 at 15:41
    
I edited the answer. –  Fedor Petrov Mar 1 '11 at 23:45
    
Thank you for your invaluable help! –  ilyaraz Mar 2 '11 at 5:02
add comment

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.