Let $X=(x_1,\ldots,x_p)$ be an $p \times n$ random matrix with iid entries from $\{\pm 1\}$, distributed so that $\mathbb P(x_{ij} = 1) \equiv 1/2$, where $x_i=(x_{i1},\ldots,x_{in})$. Let $y$ be a random vector in $\mathbb R^n$ independent of $X$, with iid entries with same distribution as the $x_{ij}$'s. For any subset $S$ of $[n]:=\{1,\ldots,n\}$, define $f_S(y) = \prod_{s \in S} y_s \in \mathbb R$. Fix $d \in [n]$, and let $\mathcal S_{n,d}$ be the collection of nonempty subsets of $d$ with cardinality at most $d$, and define a random variable $Z$ by
$$
Z := \sum_{S \in \mathcal S_{n,d}} Z_S,\text{ where } Z_S := \sum_{i=1}^p Z_{S,i},\text{ and }Z_{S,i} := f_S(x_i) f_S(y).
$$

It is clear that $Z$ and $-Z$ have are equal in distribution (in particular, this means $Z$ has zero mean).

>**Question.** What is a good upper-bound for the variance of $Z$ ?

I'm interested in concentration inequalities (tail bounds) for $Z$. I figured out it suffices to obtain good upper-bounds for the variance of $Z$, and then use Chebychev's inequality.

**Bottleneck.** Note that for each fixed $S$, the random variable $Z_S$ is a sum of random $p$ iid random variables $Z_{S,1},\ldots,Z_{S,p}$, each with zero mean and unit variance. The difficulty here is that $Z_{S_1,i}$ and $Z_{S_2,i}$ are correlated if $S_1 \cap S_2 \ne \emptyset$.

Solution for the case $d=1$
---
Here, $S_{n,d}$ consists of all the singletons of $[n]$. Thus,
$$
Z = \sum_{j=1}^n \sum_{i=1}^p x_{ij} y_j.
$$

Now, for the $x_{ij}y_j$ are a sequence of iid random variables indexed by $(i,j)$, with zero mean and unit variance. Therefore $\mbox{var}(Z) = p$.