Probability of existence of a base in the span of sparse vectors in GF(2)

Question

For $i=1,2,\dots,l$, let $\mathbf{v}_i =(v_{i1},v_{i2},\dots,v_{in}) \in \mathbb{F}_2^n$ be a sparse vector in GF(2) such that all $v_{ij}$'s are independent for all $1 \le i \le l, 1 \le j \le n$ and $$\mathrm{Pr}[v_{ij}=1] = \frac{\log(n)}{n}, \qquad 1 \le i \le l, 1 \le j \le n \\\mathrm{Pr}[v_{ij}=0] = 1-\frac{\log(n)}{n}, \quad 1 \le i \le l, 1 \le j \le n$$ Let $\mathbf{e}_1 = (1,0,0,\dots,0) \in \mathbb{F}^n_2$ be a base vector in GF(2) in which the only non-zero element is the first element. What can we say about the probability that this base exists in the span of the vectors $\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_l$? $$\mathrm{Pr}[~\mathbf{e}_1 \in \mathrm{Span}\{\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_l\}~] = ~?$$ This probability quickly approaches 1 as $l$ approaches $n$ but is it possible to find a closed form for this probability in terms of $l$ and $n$? If not, can we find good upper and/or lower bounds for this probability in terms of $l$ and $n$?

Answer 1

Let $V$ be the $n \times l$ matrix whose columns are your vectors. For a given vector $x \in \mathbb F_2^l$ with $k$ $1$'s, and $1 \le i \le n$, the number of $j$ for which $x_j = 1$ and $v_{ij} = 1$ is a binomial random variable $W_i(x)$ with parameters $(k,p)$, with $W_i(x)$ for different $i$ independent. Thus $$\mathbb P((Vx)_i = 1) = \mathbb P(W_i(x) \ \text{odd}) = \dfrac{1}{2} (1 - (1-2p)^k)$$ so that $$ \mathbb P(V x = e_1) = 2^{-n} (1 - (1-2p)^k) (1 + (1-2p)^k)^{n-1}$$ The expected number of $x$ for which $V x = e_1$ is then $$ E(p,n,l) = \sum_{k=0}^l {l \choose k} 2^{-n}(1 - (1-2p)^k) (1 + (1-2p)^k)^{n-1} $$ Now if $n \ge l$, $\ker V$ has dimension $\ge n-l$, so if there are any such $x$ there are at least $2^{n-l}$ of them. Thus we can get an upper bound $$\mathbb P(e_1 \in \text{Span}(v_1, \ldots, v_l)) \le 2^{l-n} E(p,n,l)$$