Distribution of the minimal distance of random linear codes
share
We study the distribution of the minimal distance (in the Hamming metric) of a random linear code of dimension k in F_q^n. We provide quantitative estimates showing that the distribution function of the minimal distance is close (superpolynomially in n) to the cumulative distribution function of the minimum of (q^k-1)/(q-1) independent binomial random variables with parameters 1/q and n. The latter, in turn, converges to a Gumbel distribution at integer points when k/n converges to a fixed number in (0,1). In a sense, our result shows that apart from identification of the weights of parallel codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimal code weight. As a corollary of the main result, we obtain an asymptotic improvement of the Gilbert–Varshamov bound for 2<q<49.
READ FULL TEXT