Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as $\{0,1,2,\ldots,q-1\}$. Each vector consists of exactly $m$ nonzero elements uniformly randomly chosen from $\{1,2,\ldots,q-1\}$, $m\ll N$. The nonzero coordinates of each vector are randomly located.

Now the question is, given a new such random $N$-dimensional vector $\mathbf{v}_{i+1}$, what is the probability that it is linearly independent with the previous $i$ vectors?

Best Regards.

share|improve this question

1 Answer 1

These are some preliminary thoughts that are too long for a comment.

An equivalent question is: How many vectors with exactly $m$ nonzero entries are in the subspace generated by the first $i$ vectors? Then one just divides by $(q-1)^m\left(\begin{array}{c}N \\ m \end{array}\right)$ to get the probability. A naive guess is $\frac{(q-1)^m}{q^{N-i}} \left(\begin{array}{c}N \\ m \end{array}\right)$. A trivial lower bound is $i (q-1)$. A trivial upper bound is $q^i-1$.

I would guess that, as long as $m$ is reasonably large, for small $i$ the trivial lower bound is approximately correct, and for larger $i$ the naive guess is correct. All in all, the problem behaves very differently depending on the relative sizes of $i$, $m$, $N$, and, to a lesser extent, $q$. What regimes are you most interested in?

When $m$ is very small, we get some interesting behavior. For $m=1$, we can exactly compute the probability of linear independence - it is $(1-1/N)^{i}$. For $m=2$, we can see the $N$ elements as vertices of a graph and the $i$ vectors as edges. Then our new vector can be linearly dependent only if the two nonzero coordinates are connected to each other, or both connected to cycles. I think one can get accurate formulas without too much difficulty this way.

When the probability of a linear dependence among the $i$ vectors is sufficiently small, a good upper bound is provided by counting the expected number of ways to write a new vector as the sum of old vectors. One can write this a a sum over different ways to write a new vector as a sum of old ones, and try to find the largest terms. In particular for small $i$ I think only a couple of ways of writing a new vector as a sum of old ones will be dominant - most vectors of length $m$ that are sums of vectors of length $m$ will be sums of only $1$ or $2$ or $3$ vectors of length $m$. Then you would get a sequence of increasingly exact formulas.

The most important question is really how $i,m,$ and $N$ relate to each other. The problem is really very different for different values of that.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.