On the Expected Number of Views Required for Fixed-Error Sequence Reconstruction

We analyze noisy binary sequence reconstruction subject to exactly <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t$</tex> distinct substitution errors, where a fixed number of distinct noisy output sequences (or views) are available at the decoder. The error sequences are assumed to be drawn uniformly at random, without replacement, from the Hamming sphere of radius <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t-\mathbf{a}$</tex> natural extension of the adversarial error model considered in the classical work of Levenshtein (2001). In this paper, we fix the decoder to be the majority-vote decoder, which was proved in Levenshtein (2001) to be capable of reconstructing any sequence in the “worst-case,” subject to the presence of at least a certain number of views <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N_{\mathbf{wc}}$</tex>. Such a decoder is “optimal in the worst-case” in that when the number of views is smaller than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N_{\mathbf{wc}}$</tex>, there exists a sequence that cannot be reconstructed by any decoder. Via a correspondence with a counting problem in the space of binary matrices, we first provide a simple Monte-Carlo method for estimating the probability <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P_{\mathbf{Maj}}$</tex> of successful decoding, using the majority-vote decoder. Next, via the same correspondence, we present an analytical lower bound on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P_{\mathbf{Maj}}$</tex>, which is derived using a recursive procedure. These results then allow us to bound the expected number of views required for reconstruction.