Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. For any $k$, let $K_{N,k}$ denote the collection of $k$-element subsets of $[N]$. Let $x=(x_1,\ldots,x_N)$ be a uniformly random vector on the hyper-cube $\{\pm 1\}^N$. That is, the $x_i$'s are iid Rademacher random variables. Fix $t \in (0,1)$, and construct $z=z(t) = (z_1,\ldots,z_N) \in \{\pm 1\}^N$ from $x$ by setting
$$
y_i = \begin{cases}
1,&\mbox{ w.p }t,\\
x_i,&\mbox{ w.p }1-t
\end{cases}
$$

For non-empty collection $F$ of subsets of $[N]$, define a random variable $A(F)$ by $S_t(F) := \sum_{A \in F}z_A$, where $z_A := \prod_{i \in A} z_i$. Note that $S_t(F)$ is a random polynomial in $z_1,\ldots,z_N$, of total degree $\max_{A \in F}|A| \le N$.


**Question.** Are there generic large-deviation inequalities for $S_t(F)$, for a broad class of choices of $F$ with a definable limit when $N \to \infty$ ?

A crude idea via Chebychev's inequality
---
It is clear that $E_t(F) := \mathbb E\, S_t(F) = \sum_{A \in F}t^{|A|}$ and

$$
M_t(F) := \mathbb E\, S_t(F)^2 = \sum_{A,B \in F}z_A z_B = \sum_{A,B \in F} t^{|A \Delta B|} = \sum_{A,B}z_A z_B = \sum_{A,B} t^{|A|+|B|-2|A \cap B|},
$$
where $A \Delta B := (A \setminus B) \cup (B \setminus A)$ is the *symmetric difference* of $A$ and $B$.

**Example 1.** As a first example, note that when $F=K_{N,1}$, one has $E_t(F) = Nt$ and
$$
M_t(F) = \sum_{i,j \in [N]} t^{2\delta_{i\ne j}} = \sum_{i \in [N]} 1 + \sum_{i \in [N]}\sum_{j \in [N]\setminus\{i\}} t^2) = N + N(N-1)t^2.
$$
Thus, $\mathrm{var}(S_t(F)) = M_t(F) - E_t(F)^2 = N+N(N-1)t^2 - N^2 t^2 = N(1-t^2) \le N$. Chebychev's inequality then gives

$$
\mathbb P\left(\left|\frac{S_t(F)}{Nt} - 1\right| \ge \delta\right) \le \frac{N}{(\delta N t)^2} = \frac{1}{Nt^2\delta^2} = O_{t,\delta}(1/N) = o_{t,\delta}(1).
$$

**Example 2.** As a generalization of the previous example, consider $F= K_{N,k}$, for some positive integer $k \le N$. It is clear that $E_t(F) = {N \choose k} t^k$. On the other hand
$$
M_t(F) = \sum_{A,B \in F}t^{2k-|A \cap B|} = t^{2k}\sum_{A,B \in F}t^{-2|A \cap B|}.
$$
Now, in the above some there are ${N \choose k}$ choices for $A$. Once this is fixed, there are ${k \choose j}\times {N - (k-j)}{k-j}$ choices for $B \in F$ such that $|A \cap B| = j$. We deduce that
$$
\begin{split}
M_t(F) &= {N \choose k}t^{2k}\sum_{j=0}^k {k \choose j}{N-(k-j) \choose k-j}t^{-2j}\\
&= {N \choose k}t^{2k}\left({N-k \choose k} + \sum_{j=1}^k {k \choose j}{N-(k-j) \choose k-j}t^{-2j}\right)\\
&\le {N \choose k}t^{2k}\left({N-k \choose k} + \sum_{j=1}^k {k \choose j}(3N)^{k-j}t^{-2j}\right)\\
&\le {N \choose k}t^{2k}\left({N \choose k} + \sum_{j=1}^k {k \choose j}(3N)^{k-j}t^{-2j}\right),
\end{split}
$$
where we've used the fact. Now, in the regime where
$$
N \to \infty\text{ s.t } k = o(\log N),
$$
we have further have $\sum_{j=1}^k {k \choose j}(3N)^{k-j}t^{-2j} \le t^{-2k} (2^k-1) (3N)^{k-1} \le t^{-2k}(6N)^{k-1} = t^{-2k}o({N \choose k})$. We deduce that

$$
\begin{split}
M_t(F) &\le {N \choose k}^2 (t^{2k} + o(1)),
\end{split}
$$
and so $\mathrm{var}(S_t(F)) \le o({N \choose k}^2) = o(E_t(F)^2/t^{2k})$ in the above regime.

Chebychev's inequality then gives

$$
\mathbb P\left(\left|\frac{S_t(F)}{{N \choose k}t^k} - 1\right| \ge \delta\right) \le \frac{\mathrm{var}(S_t(F))}{\delta^2 E_t(F)^2} = o(\frac{1}{\delta^2 t^2}) =  o_{t,\delta}(1).
$$

----

**Related:** https://mathoverflow.net/q/444090/78539