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

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

• 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. Apr 7, 2023 at 3:44
• I think you're right. Thanks! Apr 7, 2023 at 15:40

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