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