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} $$ Observe that the $y_i$'s are iid with distribution $\mathbb P(y_1 = 1) = (1+t)/2$ and $\mathbb P(y_1=-1) = (1-t)/2$. In particular, their mean is $\mathbb E\, y_1 = t$.
For non-empty collection $F=F_N$ 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$.
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$ ?
I'm fine with a weak law of large numbers (LLN), i.e a result of the form $$ \dfrac{S_t(F)}{E_t(F)} \overset{p}{\to} 1, $$ where $E_t(F) := \mathbb E\, S_t(F) = \sum_{A \in F}t^{|A|}$ is the mean of $S_t(F)$.
A crude idea via Chebyshev's inequality
It is clear
$$ 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$. Chebyshev'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}{N\delta^2} = O_{\delta}(1/N) = o_{\delta}(1). $$
In particular, we deduce that $S_t(K_{N,1})/(Nt) \overset{p}{\to} 1$ in the limit $N \to \infty$.
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 $\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} = (6N/t^2)^{k-1} = o({N \choose k})$ since $k=o(\log N)$. We deduce that
$$ \begin{split} M_t(F) &\le {N \choose k}^2 t^{2k}(1 + o(1)), \end{split} $$ and so $\mathrm{var}(S_t(F)) \le o({N \choose k}^2) = o(E_t(F)^2)$ in the above regime.
Chebyshev'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}). $$
In particular, we deduce that in the asymptotic regime above, one has $\dfrac{S_t(K_{N,k})}{{N \choose k} t^k} \overset{p}{\to} 1$.
Example 3. Let us generalize the previous example. First note that $S_t(F)$ is a random polynomial in $z_1,\ldots,z_N$, of total degree $q$ given by $$ q:=\max_{A \in F}|A|. $$ For any $i \in \{0,1,\ldots,q\}$, define $\mu_i = \mu_i(F)$ by $$ \mu_i := \sup_{B \subseteq [N],\, |B| = i}|\{A \in F \mid B \subseteq A\}|. $$ Note that $\mu_i/|F|$ upper-bounds the fraction of elements of $F$ which contain a subset of size $i$. In particular, one has $\mu_0 = |F|$.
A result of Schudy and Sviridenko (2011) tells us that
Proposition. For any $\lambda \gt 0$, \begin{eqnarray} \mathbb P\left(|S_t(F) - E_t(F)| \ge \delta(\lambda) \right) \le e^2 e^{-\lambda}, \end{eqnarray} where $\delta(\lambda):= \max_{1 \le i \le q}\max(\sqrt{\lambda |F| \mu_i C^q},\lambda^i \mu_i C^q)$ and $C \gt 1$ is an absolute constant.
Assume that the $\mu_i$'s verify the following smoothness condition $$ \frac{\mu_i}{|F|} = \sup_{B \subseteq [N],\, |B|=i}\frac{1}{|F|}|\{A \in F \mid B \subseteq A\}| \le c N_1^{-i},\text{ for all }1 \le i \le q, $$ for some absolute constant $c$ and $N_1=N_1(N)$ to be prescribed. Note
Then, one easily computes $$ \max_{1 \le i \le q} \lambda^i \mu_i C^q \le cC^q |F| \max_{1 \le i \le q}(\lambda/N_1)^i = cC^q |F| \begin{cases} \lambda/N_1,&\mbox{ if }\lambda \le N_1,\\ (\lambda/N_1)^q,&\mbox{ otherwise.} \end{cases} $$ On the other hand, one has $$ \max_{1 \le i \le q}\sqrt{\lambda |F| \mu_i C^q} \le \max_{1 \le i \le q}\sqrt{\lambda |F|^2 c N_1^{-i} C^q} = |F|\sqrt{cC^q \lambda /N_1}. $$ We deduce that if $\lambda \le N_1$, then $$ \delta(\lambda) \le |F| \max(\sqrt{cC^q \lambda /N_1},cC^q\lambda /N_1) = \max(u,u^2)|F|, $$ where $u := \sqrt{cC^q \lambda /N_1}$. We get \begin{eqnarray} \mathbb P\left(|S_t(F)- E_t(F)| \ge \max(u,u^2) |F|\right) \lesssim e^{-\lambda} = e^{-u^2 N_1 / (cC^q)} = e^{-u^2 N_1^{1-o(1)}}. \end{eqnarray}
Taking $u \in (0,1)$ gives \begin{eqnarray} \mathbb P\left(|S_t(F)- E_t(F)| \ge u |F|\right) \lesssim e^{-u^2 N_1^{1-o(1)}}, \end{eqnarray} in the regime where $$ N_1 \to \infty\text{ with }q = o(\log N_1). $$ For example, when $F = K_{N,k}$ and we take $N_1=N$, $q=k$, then we are in the setting of the previous example.
Now, observe that $E_t(F) = \sum_{A \in F}t^{|A|} \ge |F|t^q$. We deduce that \begin{eqnarray} \mathbb P\left(\left|\frac{S_t(F)}{E_t(F)}- 1\right| \ge u\right) \lesssim e^{-u^2 t^{2q}N_1^{1-o(1)}}, \end{eqnarray} which is much stronger than the LDI obtained in the previous example (with $N_1=N$ and $F=K_{N,k}$).
to be continued...
