3
$\begingroup$

Consider linear $N$-dimensional space $F_2^N$. Consider its $K$ dimensional subspace $V \subset F_2^N$. Let us calculate $w(k,V,N)$ number of vectors in $V$ of Hamming weight $k$ in $V$.

Since there is finite number of subspaces we can calculate average: $\sum_{V} w(k,V,N)$.

Question is there something known about it ?

Coding theory motivation - is to understand how good/bad is a random linear code ? I.e. error-correcting code is precisely $V$ in $F_2^N$. Code is bad if we have many vectors of small Hamming weight.

http://en.wikipedia.org/wiki/Hamming_weight

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

You can compute the average very explicitly. For $v\in F_2^N$, let $||v||$ denote the Hamming weight of $v$. Changing the order of summation, your sum can be re-written as $$ \sum_{v\colon\ ||v||=k} T(v), $$ where $T(v)$ is the number of $K$-dimensional subspaces of $F_2^N$, containing $v$. Now, if $k>0$, then $v\ne 0$, and the number of subspaces in question does not depend on $v$ and is equal to the number of $(K-1)$-dimensional subspaces of $F_2^{N-1}$, which is $$ \frac{(2^{N-1}-1)(2^{N-1}-2))(2^{N-1}-4)\cdots(2^{N-1}-2^{K-2})}{(2^{K-1}-1)(2^{K-1}-2)(2^{K-1}-4)\cdots(2^{K-1}-2^{K-2})}. $$ The sum under consideration is therefore equal to the product of this fraction and the binomial coefficient $\binom Nk$ (the number of vectors $v$ of weight $k$), and the average is obtained by dividing this sum by the total number of all $K$-dimensional subspaces of $F_2^N$, which is $$ \frac{(2^N-1)(2^N-2)(2^N-4)\cdots(2^N-2^{K-1})}{(2^K-1)(2^K-2)(2^K-4)\cdots(2^K-2^{K-1})}. $$ After cancellations, the average is equal to $$ \frac{2^K-1}{2^N-1}\,\binom Nk = 2^{K-N}\binom Nk \, (1+o(1)),\ K\to\infty. $$

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Seva WOW !!! Can we understand what distribution we get when K,N are "large" ? It might be just something simple related to binomial distribution tending to normal distribution ... $\endgroup$
    – Alexander Chervov
    Commented Feb 24, 2012 at 18:09
  • $\begingroup$ I appended two lines to my answer to address this. $\endgroup$
    – Seva
    Commented Feb 24, 2012 at 19:13
  • $\begingroup$ if sum k=1...N I expect to get 1+O(1), but we get 2^K... is it correct ? $\endgroup$
    – Alexander Chervov
    Commented Feb 24, 2012 at 19:21
  • $\begingroup$ What we computed is the average (=expected) number of vectors of weight $k$ in a randomly chosen $K$-dimensional subspace. Summing over $k$, we get the total number of vectors in a random $K$-dimensional subspace, which is $2^K$. Makes sense? $\endgroup$
    – Seva
    Commented Feb 24, 2012 at 19:57
  • $\begingroup$ One more comment to interpret the result. We have shown that the proportion of vectors of weight $k$ among all vectors of a random $K$-dimensional subset is about $2^{-N}\binom Nk$, which is the proportion of vectors of weight $k$ among all vectors of $F_2^K$. In other words, lying in a $K$-dimensional subspace is independent from having weight $k$. Pretty expectable! $\endgroup$
    – Seva
    Commented Feb 24, 2012 at 20:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .