New Proofs and Theorems in the Realm of Supersequences and Subsequences

We present and prove a theorem related to maximal initial deletion masks in the realm of supersequences, from which we derive a new proof for a Hamming weight clustering scheme as a corollary: in the context of deletion channels, a codeword y of length n can be subject to s random deletions that lead to a received s-deleted codeword x of length k, which is a subsequence of the originally intended codeword by the sender. The supersequences that could have led to the received subsequence are clustered into r=n-k+1 groups according to r=h(y)-h(x) and it turns out that the size of each such cluster is independent of the exact form of the subsequence and that it is purely a function of n, k, r and h(x). We derive a new proof for this theorem that gives more insight into the structure of this space and we also give a simple closed form expression for computing the size of each cluster.

Moreover, we present a recursion based approach for computing the size of a cluster, which provides yet another proof for the theorem. Time permitting, we will also discuss potential lines of attack based on the said clustering for proving minimal entropy in the context of leaked subsequences, a study rooted in an analysis of quantum key establishment protocols.