On the size distribution of Levenshtein balls with radius one

arXiv2204.02201MaRDI QIDQ6505696FDOQ6505696

Authors: Geyang Wang, Qi Wang 

Abstract: The fixed length Levenshtein (FLL) distance between two words $mathbfx,yinmathbb{Z}_m^n$ is the smallest integer $t$ such that $mathbfx$ can be transformed to $mathbfy$ by $t$ insertions and $t$ deletions. The size of a ball in FLL metric is a fundamental but challenging problem. Very recently, Bar-Lev, Etzion, and Yaakobi explicitly determined the minimum, maximum and average sizes of the FLL balls with radius one. In this paper, based on these results, we further prove that the size of the FLL balls with radius one is highly concentrated around its mean by Azuma's inequality.

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Synchronization error-correcting codes (94B50)

This page was built for publication: On the size distribution of Levenshtein balls with radius one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505696)