Timeline for How many vectors of Hamming weight L in "random" K dimensional subspace of F_2^N ? Or how good/bad is random linear block code ?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2012 at 18:01 | comment | added | Alexander Chervov | To comment just above --- if "K" is very big e.g. extreme case K=N - so there is only one "subspace" which is space itself, then of course number of weight "k" vectors is C_n^k, so if "K" is something near it we may expect similar result... | |
| Feb 25, 2012 at 17:54 | vote | accept | Alexander Chervov | ||
| Feb 24, 2012 at 20:21 | comment | added | Seva | 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! | |
| Feb 24, 2012 at 19:57 | comment | added | Seva | 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? | |
| Feb 24, 2012 at 19:21 | comment | added | Alexander Chervov | if sum k=1...N I expect to get 1+O(1), but we get 2^K... is it correct ? | |
| Feb 24, 2012 at 19:13 | comment | added | Seva | I appended two lines to my answer to address this. | |
| Feb 24, 2012 at 19:11 | history | edited | Seva | CC BY-SA 3.0 |
added 130 characters in body; added 3 characters in body
|
| Feb 24, 2012 at 18:09 | comment | added | Alexander Chervov | @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 ... | |
| Feb 24, 2012 at 15:39 | history | edited | Seva | CC BY-SA 3.0 |
more typos and corrections
|
| Feb 24, 2012 at 15:16 | history | answered | Seva | CC BY-SA 3.0 |