1
$\begingroup$

Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of the $G_i$'s, i.e the collection of subsets of $[N]$ which contain exactly one element from each $G_i$. Note that $\mathcal T$ is isormophic to $G_1 \times \ldots \times G_k$ in an obvious way, and thus $|\mathcal T| = N_1^k$.

Let $x \in \{\pm 1\}^N$ be a random vector vector with iid Rademacher components. Fix $\theta \in [0,1)$, and define a random vector $y=(y_1,\ldots,y_N) \in \{\pm 1\}^N$ as follows:

  • Let $I_\theta$ a uniformly random subset of $[N]$ of size $\theta N$, drawn independently of $x$.
  • For any $n \in [N]$, set $$ y_n = \begin{cases}-1,&\mbox{ if }n \in I_\theta,\\ x_n,&\mbox{ else.} \end{cases} $$ Finally, let $z = x \odot y \in \{\pm 1\}^N$ be the component-wise product of $x$ and $y$, and define a random variable $Z$ by $$ Z := \sum_{T \in \mathcal T} z_T, $$ where $z_T := \prod_{t \in T} z_t$. Note that $Z$ is a random multilinear polynomial of total degree $k$.

My objective is to design $N_1$ and $k$ (as a function of $N$) such that $Z$ is as large as possible (and positive !) w.p $1-o(1)$ in the limit $N \to \infty$.

Now, it is clear that we can alternately write $$ Z = \prod_{1 \le i \le k} S_i, $$

where $S_i := \sum_{t \in G_i} z_t$. It is clear that

  • The $S_i$'s are iid.
  • Each $S_i$ is itself a sum of iid random variables which take values $\pm 1$, with $\mathbb P(z_t = 1) = 1-\theta/2$ and $\mathbb E\, z_t = 1-\theta/2 - \theta/2 = a := 1-\theta \in [0,1]$. Also, $\mathbb E S_i = a N_1$ and $$ \begin{split} \mathbb E S_i^2 &= \sum_{t \in G_i} \sum_{t' \in G_i} \mathbb E z_{t} \mathbb E z_{t'} = N_1 + \sum_{t' \ne t} a^2 N_1 + N_1(N_1-1)(1-\theta)^2\\ & = N_1(1-a^2) + a^2 N_1^2 = N_1(1-(1-\theta)^2) + (\mathbb E S_i)^2. \end{split} $$

It follows that $\mathbb E Z = (a N_1)^k$, and $$ \begin{split} \mathrm{var}(Z) &= \prod_{i=1}^k \mathbb E S_i^2 - \prod_{i=1}^k (\mathbb E S_i)^2 = ((aN_1)^2 + N_1(1-a^2))^k - ((a N_1)^2)^k\\ & = ((aN_1)^2)^{k}\left(\left(1 + \frac{1/a^2-1}{N_1}\right)^k - 1\right) = (\mathbb E Z)^2 R(Z), \end{split} $$ where $R(Z) := \mathrm{var}(Z) / (\mathbb E Z)^2 = \left(1 + \dfrac{c}{N_1}\right)^k - 1$, with $c := 1/a^2 - 1 \ge 0$. Now, one computes

$$ 0 \le \left(1 + \frac{c}{N_1}\right)^k - 1= \left(\left(1 + \frac{c}{N_1}\right)^{N_1}\right)^{k/N_1} - 1 \le e^{ck/N_1} - 1. $$

Thus, if $N_1 \to \infty$ such that $k = o(N_1)$ (i.e $k/N_1 \to 0$), then $R(Z) = o(1)$, and Chebyshev's inequality gives $$ \mathbb P(|Z-\mathbb EZ| \ge (1/2) \mathbb E Z) \le 4R(Z) = o(1). $$

We deduce that

Proposition 1. If $N_1 \to \infty$ such that $k=o(N_1)$, then $Z \asymp \mathbb E Z = (aN_1)^k$ w.p $1-o(1)$.

Question. Is there a concentration inequality for $Z$ which doesn't requiring that $k=o(N_1)$ ? In fact, is it possible to concentrate $Z$ in the regime $N_1 = o(k)$ ?

My hope is that it would be possible to go beyond the "$k=o(N_1)$" barrier by computing higher moments of $Z$, and then using a Chernoff-type bound, but I don't know how to go about this (the combinatorics seem to be quite involved).

Update: An idea

We can further write $z_t = 2 b_t - 1$, where $b_t$ is Bernoulli with parameter $p=1-\theta/2 \in [1/2,1]$. Thus, $S_i = \sum_{t \in G_i} (2b_t - 1) = 2 B_i - N_1$, where $B_i := \sum_{t \in G_i} b_t \sim \mathrm{Bin}(N_1,p)$. By well-known concentration results,

$$ \begin{split} \mathbb P(B_i \ge (1+t)N_1 p) &\le e^{-\frac{t^2p^2N_1}{2+t}},\text{ for all }t \gt 0,\\ \mathbb P(B_i \le (1-t)N_1 p) &\le e^{-\frac{t^2p^2N_1}{2}},\text{ for all }0 \lt t \lt 1. \end{split} $$

We deduce that, $$ \begin{split} \mathbb P(S_i \ge (2p(1+t) - 1)N_1) &\le e^{-\frac{t^2p^2N_1}{2+t}},\text{ for all }t \gt 0,\\ \mathbb P(S_i \le (2p(1-t)-1)N_1) &\le e^{-\frac{t^2p^2N_1}{2}},\text{ for all }0 \lt t \lt 1. \end{split} $$

Taking $t = q / \phi(N_1)$ with $q := \sqrt 2 / p$, we obtain for any $i$, it holds w.p $1-e^{-N_1/\phi(N_1)}$ that $S_i \ge ((2p-1)-q/\phi(N_1)) N_1 = (a-q/\phi(N_1))N_1$. A union bound then gives: w.p $1-\delta(N_1) = 1 - ke^{-N_1/\phi(N_1)}$ it holds that $$ \frac{Z}{(aN_1)^k} \ge \left(1-\frac{q/a}{\phi(N_1)}\right)^k = \left(\left(1-\frac{q/a}{\phi(N_1)}\right)^{\phi(N_1)}\right)^{k/\phi(N_1)} =: R(N_1) $$

Now, we want $k$ to be as large as possible, and for the RHS of the above to be as large as possible too. We can achieve this by designing the function $\phi:\mathbb R_+ \to \mathbb R_+$ such that in the limit $N_1 \to \infty$,

  • $\delta(N_1) = e^{-N_1/\phi(N_1) + \log k} \to 0$, and
  • $\phi(N_1) \to \infty$ as fast as possible
  • $k = \phi(N_1)$.

To satisfy the above constraints it suffices to take

$$ \phi(N_1) = N_1/\sqrt{C\log N_1}, $$

This gives $Z \gtrsim (aN_1)^k b^{k\sqrt{\log N_1}/N_1} = (aN_1e^{-(q/a)\sqrt{\log N_1}/N_1})^k$, with $b := e^{-(q/a)\sqrt C} \in (0,1)$. Take $C \gt 1$ and $k = N_1^{C-1}$. This gives $$ N_1^2 / \phi(N_1)^2 + \log k = C\log N_1 - (C-1)\log N_1 = \log N_1, $$ and so $\delta(N_1) = 1/N_1$, and $$ Z \ge (a N_1)^ke^{-q/a}\text{ w.p } 1 - O(1/N_1) = 1-o(1). $$

Now, take $N_1 = N^{\alpha}$, $k = N^{1-\alpha}$ (for some $\alpha \in (0,1/2)$), to get $C=(1-\alpha)/\alpha=1/\alpha-1 \gt 1$. This gives $$ Z \gtrsim (a N^\alpha \cdot b^{\sqrt{\alpha \log N}/N^\alpha})^{N^{1-\alpha}} \asymp (a N^\alpha)^{N^{1-\alpha}} \gg e^{N^{1-\alpha}}. $$ We have thus established the following result.

Proposition 2. For any $\alpha \in (0,1/2)$, and set $N_1 = N_1(N)$ and $k=k(N)$ as above. In the limit $N \to \infty$, it hold w.p $1-1/N^\alpha =1-o(1)$ that $$ Z \gg e^{N^{1-\alpha}}. $$

Note that Proposition 2 is a net improvement on Proposition 1: the latter only gave a lower bound of order $e^{\sqrt N}$, while the former gives a lower-bound of order $e^{N^{1-\alpha}}$, which is infinitely larger since $\alpha \in (0,1/2)$. However, this bound is still not good enough: ideally, I'd like to have a lower-bound of the form $Z \gtrsim e^{N/\log(N)^c}$ w.p $1-o(1)$.

$\endgroup$
2
  • 1
    $\begingroup$ I can't really follow all the notation, but why doesn't the last idea give a bound like $e^{N\log\log N/C\log N}$? If $N_1=C\log N$ for large enough $C=C(\theta)$, each $S_i$ should be at least $\log N$ with probability at least $1-1/N^2$ from Chernoff bounds, and there are $N/C\log N$ of them. This is probably tight because if $N_1=c\log N$ for small enough $c>0$, the probability a given $S_i$ is even positive is far enough away from $1$ that the overall expression won't even be positive with high probability. $\endgroup$ Apr 7, 2023 at 3:44
  • $\begingroup$ I think you're right. Thanks! $\endgroup$
    – dohmatob
    Apr 7, 2023 at 15:40

1 Answer 1

1
$\begingroup$

Disclaimer. It turns out that as pointed out by user @Jason Gaitonde, the idea I presented at the end of my question eventually solves my problem with the right choise of $N_1$, namely $N_1 = C \log N$ for sufficiently large positive constant $C$. In this post, I'll fill in the details. I'd be grateful if someone could kindly check the math. Thanks in advance.


Claim. Take $N_1 = 2C \log N$, $k = N/N_1$, where $C$ is a sufficiently large positive constant. For large $N$, it holds w.p $1-1/N^{2C-1} =1-o(1)$ that $$ Z(\mathcal T) \gtrsim ((1-\theta)C \log N)^{N/(2C\log N)}, $$

Proof. First observe that, in the definision of $S_i$, we can further write $z_t = 2 b_t - 1$, where $b_t$ is Bernoulli with parameter $p=1-\theta/2 \in [1/2,1]$. Thus, $S_i = \sum_{t \in G_i} (2b_t - 1) = 2 B_i - N_1$, where $B_i := \sum_{t \in G_i} b_t \sim \mathrm{Bin}(N_1,p)$. By well-known concentration results, \begin{eqnarray} \begin{split} \mathbb P(B_i \ge (1+t)N_1 p) &\le e^{-\frac{t^2pN_1}{2+t}},\text{ for all }t > 0,\\ \mathbb P(B_i \le (1-t)N_1 p) &\le e^{-\frac{t^2p N_1}{2}},\text{ for all }0 < t < 1. \end{split} \end{eqnarray} We deduce that, \begin{eqnarray} \begin{split} \mathbb P(S_i \ge (2p(1+t) - 1)N_1) &\le e^{-\frac{t^2p N_1}{2+t}},\text{ for all }t > 0,\\ \mathbb P(S_i \le (2p(1-t)-1)N_1) &\le e^{-\frac{t^2p N_1}{2}},\text{ for all }0 < t < 1. \end{split} \end{eqnarray} Thus, for $t \in (0,a)$, we obtain for any $i$, it holds w.p $1-e^{-t^2 p N_1/2}$ that $$ S_i \ge ((2p-1)-t) N_1 = (a-t)N_1, $$ where $a := 2p-1 = 1-\theta \in (1/2,1]$ as before. A union bound then over $i \in [k]$ then gives: w.p $1-\delta(N_1) = 1 - ke^{-t^2 p N_1/2}$ it holds that \begin{eqnarray} \frac{Z(\mathcal T)}{(aN_1)^k} \ge \left(1-t/a\right)^k = \left(\left(1-t/a\right)^{a}\right)^{k/a} \ge e^{-tk/a}. \end{eqnarray}

Now, we want $k$ to be as large as possible, and the RHS of the above to be as large as possible too. We can achieve this by ensuring that

  • $\delta(N_1) = e^{-t^2 p N_1/2 + \log k} = e^{-t^2 p N_1/2 + \log N - \log N_1} \to 0$, and

To satisfy the above constraint (perhaps non-optimally!) it suffices to take \begin{eqnarray} N_1 \ge C\log N,\,k=N/N_1 = N/(C\log N), \end{eqnarray} where $C$ is sufficiently larger and might depend on $N$. Then, taking $t \in \min(a,(0,\sqrt{2/C}/p)))$, we have $\delta(N_1) = e^{-(t^2 p C/2) \log N + \log N - \log\log N - \log C} = 1/N^{t^2 p C/2-1}$, and so w.p $1-\delta(N_1)$, it holds that $$ Z(\mathcal T)/(aN_1)^k \gtrsim b(t)^k $$ where $b(t) := e^{-t/a} \in (0,1/e)$. In particular, taking $C = 1/(a^2 p^2)$, $N_1 = C \log N$, and $t = a/2$, we deduce that \begin{eqnarray} \begin{split} Z(\mathcal T) &\gtrsim (a N_1)^k e^{-k/2} = (aCe^{-1/2} \log N)^{N/(C\log N)} \gtrsim 2^{cN\log^2 N / \log N}, \end{split} \end{eqnarray} w.p $1-o(1)$, which proves the claim. $\quad\quad \Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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