The Intersection of Insertion and Deletion Balls

Preprint. Paper

Abstract

This paper studies the intersections of insertion and deletion balls. The t-insertion, t-deletion ball of a sequence x is the set of all sequences received by t insertions, deletions to x, respectively. While the intersection of either deletion balls or insertion balls has been rigorously studied before, the intersection of an insertion ball and a deletion ball has not been addressed so far. We find the maximum intersection size of any two insertion and deletion balls in the binary case. For the special case of one-insertion and one-deletion balls we find the intersection size for all pair of sequences. Then, we derive the largest and average values of this intersection size. Lastly, we present an algorithm that efficiently computes the intersection of any t1-insertion ball and t2-deletion ball. This paper was submitted to IEEE Information Theory Workshop (ITW), 2021.