Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{R}^n$ denote the set of $k$-partite, $k$-sparse binary vectors, in the sense that $v \in S$ if for all $i \in [0, k-1] \cap \mathbb{Z}$, there is a unique $j \in [1,n/k] \cap \mathbb{Z}$ such that $v_{i\cdot n/k + j} = 1$, and all other entries of $v$ are $0$. In particular, $|S| = (n/k)^k$.
Let $\delta > 0$ be a parameter where $\delta \ll 1$. For any $v \in S$, let $p := \Pr_{A}\left[ \|Av\|_2 \leq \delta \right]$. Note that $p$ is the same for all $v \in S$ and can be computed by using the CDF of a $\chi^2_m$ distribution. Roughly, $$p = \left( \frac{\delta}{\sqrt{mk}} \right)^{m(1 \pm o(1))}.$$
For $v \in S$, let $X_v$ be the indicator random variable $\mathbb{1}\left[\|Av\|_2 \leq \delta \right]$ (with $\mathbb{E}[X_v]= p$).
Let $X = \sum_{v \in S} X_v$. By linearity of expectation, one has $\mathbb{E}[X] = \left( \frac{n}{k} \right)^k p$. Suppose $\delta$ and $p$ are set so that this expectation is exponentially large in $n/k$, e.g., $p = (n/k)^{-k/10}$. Is there any way to convert this into a high probability statement that $X$ is large, or even not $0$, with noticeable probability? Of course, one has trivial bounds like $\Pr[X = 0] \leq 1-p$ using the fact that $\Pr[X \leq (n/k)^k] = 1$, but is there anything stronger one can say? (One can say $\Pr[X = 0] \leq (1-p)^{n/k}$ using the fact that there are $n/k$ jointly independent random variables in the sum, but this is still much weaker than what I'm hoping for.)
One idea I'm considering is using Chebyshev's inequality to bound $\Pr[X = 0]$ if one can compute (an upper bound on) $\mathrm{Var}(X)$, but as far as I can tell, this quickly gets messy when digging into the Marcum Q-function as the CDF for the non-central $\chi^2_m$ distribution. For Chebyshev's bound to be useful here, it seems that we need $$ \frac{1}{(n/k)^{2k}} \sum_{v_1, v_2 \in S} \Pr[X_{v_1} = 1 \land X_{v_2} = 1] = O(p^2),$$ which I'm not sure is even true. Any insight or suggestions would be appreciated, thanks!
