»ã±¨±êÌâ (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.