On the size distribution of Levenshtein balls with radius one
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913240397643776 |
|---|---|
| author | Wang, Geyang Wang, Qi |
| author_facet | Wang, Geyang Wang, Qi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_02201 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the size distribution of Levenshtein balls with radius one Wang, Geyang Wang, Qi Information Theory Combinatorics 94B50, 05D40 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. |
| title | On the size distribution of Levenshtein balls with radius one |
| topic | Information Theory Combinatorics 94B50, 05D40 |
| url | https://arxiv.org/abs/2204.02201 |