论文标题
关于Levenshtein球的大小分布，半径为
On the size distribution of Levenshtein balls with radius one
论文作者
论文摘要
The fixed length Levenshtein (FLL) distance between two words $\mathbf{x,y} \in \mathbb{Z}_m^n$ is the smallest integer $t$ such that $\mathbf{x}$ can be transformed to $\mathbf{y}$ by $t$ insertions and $t$ deletions.在FLL度量标准中，球的大小是一个基本但具有挑战性的问题。最近，Bar-Lev，Etzion和Yaakobi明确确定了半径为1的FLL球的最小，最大和平均大小。在本文中，基于这些结果，我们进一步证明了半径的FLL球的大小高度集中在Azuma的不等式周围。
The fixed length Levenshtein (FLL) distance between two words $\mathbf{x,y} \in \mathbb{Z}_m^n$ is the smallest integer $t$ such that $\mathbf{x}$ can be transformed to $\mathbf{y}$ 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.
