Concentration of a certain simple / well-structured random multilinear polynomial with growing degree

Question

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

Answer 1

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$