Distribution of the Minimum Distance of Random Linear Codes
Jing Hao, Han Huang, Galyna V. Livshyts, Konstantin Evgenjevich Tikhomirov · 2020
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 (qk-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). 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 minimum code weight. As a corollary of the main result, we obtain an asymptotic improvement of the Gilbert-Varshamov bound for 2 < q < 49.