Distribution of the Minimum Distance of Random Linear Codes

Let $q\geq 2$ be a prime power. In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension $k$ in $\mathbb {F}_{q}^{n}$ . We provide quantitative estimates showing that the distribution function of the minimum 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 $\frac {1}{q}$ and $n$ . The latter, in turn, converges to a Gumbel distribution at integer points when $\frac {k}{n}$ converges to a fixed number in (0, 1). Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an improvement of the Gilbert–Varshamov bound for $2< q< 49$ .