Skip to main content
MathOverflow

Return to Question

added 75 characters in body
Source Link
mhsnk
mhsnk
  • 307
  • 2
  • 13

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$?

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 $$\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$?

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$?

Source Link
mhsnk
mhsnk
  • 307
  • 2
  • 13

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

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 $$\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$?