On the Average List Size of VT Codes under Two Insertions or Two Deletions

Levenshtein’s classical theorem shows that any code that can uniquely decode from $t$ deletions can also uniquely decode from $t$ insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece’s \emph{average list size problem}. More precisely, given a binary code $\mathcal{C}$ of length $n$ that uniquely corrects $t^{\mathrm{\prime }}$ insertions (or deletions), we are interested in the average number of codewords returned by a $t$-insertion (or deletion) list decoder, where $t^{\mathrm{\prime }}<t$. Focusing on the case of $t^{\mathrm{\prime }}=1$ and $t=2$, we find that under two insertions, this quantity is at most $(n+12)\mathrm{/}4$ for any VT code of length $n$, whereas under two deletions it is at least $n\mathrm{/}2-10$ when averaged over all length-$n$ VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.