5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 1, 2011 at 14:59

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$". $\endgroup$
    – ilyaraz
    Commented Mar 1, 2011 at 15:25
  • $\begingroup$ what do you mean by "asymptotically close"? The ratio is close to 1? The ratio is bounded from both sides? $\endgroup$ Commented Mar 1, 2011 at 15:29
  • $\begingroup$ The ratio $E[\ldots] / (1 - 2 \varepsilon)^{\alpha n}$ can be upper-bounded with $2^{o(n)}$, I think. $\endgroup$
    – ilyaraz
    Commented Mar 1, 2011 at 15:41
  • $\begingroup$ I edited the answer. $\endgroup$ Commented Mar 1, 2011 at 23:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .