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

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

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
@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 ... –  Alexander Chervov Feb 24 '12 at 18:09
    
I appended two lines to my answer to address this. –  Seva Feb 24 '12 at 19:13
    
if sum k=1...N I expect to get 1+O(1), but we get 2^K... is it correct ? –  Alexander Chervov Feb 24 '12 at 19:21
    
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? –  Seva Feb 24 '12 at 19:57
    
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! –  Seva Feb 24 '12 at 20:21

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.