Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of our vectors will be linearly independent (over $\mathbb{F}_2$) too.

The question is as follows: how large $d - n$ should be if we want this probability to be, say, $1 - 1 / \mathrm{poly}(n)$?

  • $\begingroup$ Ilya, is this your homework in probability? Sounds like an advanced problem for serious students at MSU. $\endgroup$ – Wadim Zudilin May 4 '10 at 13:17
  • $\begingroup$ No. This fact would be useful for my research. Our course in probability is not that advanced. $\endgroup$ – ilyaraz May 4 '10 at 13:22
  • $\begingroup$ Then please clarify whether all objects (vectors, random $d$-dimensional subspaces) are with respect to ground field $\mathbb F_2$, or the 2-element field is needed to express the independence property. Even the latter option sounds strange, a better formulation of the problem would be helpful. $\endgroup$ – Wadim Zudilin May 4 '10 at 13:41
  • $\begingroup$ We consider linear dependence over $F_2$ of course. $\endgroup$ – ilyaraz May 4 '10 at 13:54
  • $\begingroup$ This is clear. Are the vectors from $\mathbb F_2^{2n}$? Is the subspace viewed as a subspace of $\mathbb F_2^{2n}$? $\endgroup$ – Wadim Zudilin May 4 '10 at 14:14

Suppose the vectors are $e_1,\dots,e_n$. The kernel of projection onto a random subspace of dimension $n+r$ is a random subspace of dimension $n-r$, so you want the probability that such a subspace has trivial intersection with the span of $e_1,\dots, e_n$. Now just count the number of choices for a basis $v_1,\dots, v_{n-r}$ of such a space: $2^{2n} - 2^n$ for the first vector, then $2^{2n} - 2^{n+1}$ for the second, and so on. This is to be compared with $2^{2n} - 1$ choices for the first vector if one doesn't have an restriction, $2^{2n}-2$ for the second and so on.

So the probability of this happening is the ratio of these two quantities, which you need to find a good approximation for; a very brief back-of-an-envelope calculation suggested it's about $1 - c2^{-r}$, at least if $r$ is largeish. For your specific needs, then, $d - n$ should be about $C\log n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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