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 $\{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}} \frac{1}{{n \choose |S|}}\sum_{i=1}^p 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. The difficulty here is that: indexed by $(S,i)$, the $f_S(x_i)f_S(y)$'s are not independent, and as can be seen in the case $d=2$.

Solution for the case $d=1$
---
Here, $S_{n,d}$ consists of all the singletons of $[n]$. Thus,
$$
Z = \frac{1}{n}\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/n$. Thus, $Z$ concentrates around $0$ if $n \gg p$.