Skip to main content
1 of 13
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Large-deviation inequalities for a class of simple random multivariate polynomial

Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. Let $\{0,1\}^N$ be the collection of all subsets of $[N]$ and 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 $$ z_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 $A_t(F) := \sum_{A \in F}z_A$, where $z_A := \prod_{i \in A} z_i$. Note that $A_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 $A_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\, A_t(F) = \sum_{A \in F}t^{|A|}$ and

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

Question. In the case where $F=\{0,1\}^N$ and $F=K_{N,k}$, are there an analytic formulae for $M_t(F)$ ?

As an 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}(A_t(F)) = M_t(F) - E_t(F)^2 = N+N(N-1)t^2 - N^2 t^2 = N(1-t^2)$. Chebychev's inequality then gives

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


Related: Concentration of a certain simple / well-structured random multilinear polynomial with growing degree

dohmatob
  • 6.9k
  • 1
  • 18
  • 76