报告题目 (Title)：Levenshtein球的大小分布问题（On the size distribution of the fixed-length Levenshtein balls with radius one）

报告人 (Speaker)： 王琦 教授（南方科技大学）

报告时间 (Time)：2023年11月18日(周六) 14:00

报告地点 (Place)：校本部 F309

邀请人(Inviter)：丁洋

主办部门：理学院数学系

报告摘要：The fixed-length Levenshtein (FLL) distance between two words x,y∈Z_m^n is the smallest integer t such that x can be transformed to y by t insertions and t deletions. The size of a ball in the FLL metric is a fundamental yet challenging problem. Very recently, Bar-Lev, Etzion, and Yaakobi explicitly determined the minimum, maximum and average sizes of the FLL balls with radius one, respectively. In this talk, I will further prove that the size of the FLL balls with radius one is highly concentrated around its mean by Azuma’s inequality.