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

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 Chebychev's inequality gives $$ \mathbb P(|Z-\mathbb EZ| \ge (1/2) \mathbb E Z) \le 4R(Z) = o(1). $$

We deduce that

Proposition. 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 using a Chernoff-type bound.