PaperlayerView exact revision on arXiv

Source-linked AI summary

When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions

Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh

arXiv:2610.30001v1cs.ITmath.IT

TL;DR

Binary sequence reconstruction asks how to recover a sequence from multiple noisy outputs; this paper studies the worst-case exact-t substitution setting and whether majority-vote remains sufficient. It establishes a lower worst-case threshold for an optimal decoder, gives an early-termination condition, and evaluates a weighted-majority alternative.

  • Problem

    The paper asks what worst-case observation guarantee enables unique reconstruction when each binary output has exactly t substitution errors, and whether majority-vote remains optimal in that setting.

    Source: §I · p. 1

  • Method

    The paper characterizes the exact-t worst-case threshold, derives an error-detection condition for early termination, and proposes weighted majority-vote using error correlations.

    Source: §III · p. 3, B. Error detection and termination of… · p. 4, §V · p. 9

  • Results

    N_wc is strictly below N_maj, and weighted majority-vote numerically outperforms bit-wise majority-vote, supporting—but not proving—the conjecture that it lowers the required observations.

    Source: §III · p. 3, §V · p. 9

  • Takeaways & Limitations

    The early-termination rule can certify majority-vote success with fewer than the worst-case required observations.

    Source: §III · p. 3, B. Error detection and termination of… · p. 4, §V · p. 9

    The reconstruction guarantees studied concern binary sequences under the exact-t substitution channel.

    Source: §III · p. 3

Abstract

from arXiv · show

We consider the problem of binary sequence reconstruction where a sequence is transmitted multiple times over a channel, and each undergoes substitution errors by an arbitrary error vector of Hamming weight exactly $t$. We determine $N_{\mathrm{wc}}$, the minimum number of distinct channel output observations guaranteeing unique reconstruction by an optimal decoder, and show that the bit-wise majority-vote decoder, which was proved by Levenshtein (2001) to be optimal for channels corrupting up to $t$ bits, is in fact suboptimal here. Despite this suboptimality, we prove a condition that admits a practical early-termination rule, necessary for every decoder at any number of outputs $N$, and sufficient for bit-wise majority-vote even below $N_{\mathrm{wc}}$. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below $N_{\mathrm{wc}}$ when the block-length $k>2t+1$. Finally, we propose an alternative algorithm aimed at guaranteeing unique reconstruction with fewer observations than bit-wise majority-vote, and demonstrate through exhaustive enumeration that it successfully decodes channel output-sets where bit-wise majority-vote fails.

I. INTRODUCTION

The paper studies worst-case reconstruction under an exact-t substitution channel, motivated by fixed corruption budgets, and finds that bit-wise majority-vote is suboptimal. It introduces the channel setting and situates it within sequence-reconstruction research.

I. INTRODUCTION

  • The introduction places worst-case combinatorial guarantees alongside probabilistic reconstruction and distance-based sufficient conditions that can use fewer observations.It also notes extensions to insertion, deletion, mixed errors, coded settings, and list decoding.Source: §I · p. 1
  • The exact-t channel models settings where each transmission uses a fixed corruption budget, including adversarial jammers using all available resources.Earlier work studied average-case performance under uniformly random constant-weight errors.Source: §I · p. 1
  • The paper characterizes worst-case reconstruction for exact-t errors and shows that bit-wise majority-vote is suboptimal, motivating alternative algorithms.The classical up-to-t setting had established majority-vote as optimal.Source: §I · p. 1

B. System Setup and Channel Model

  • The channel outputs N distinct binary sequences, each at Hamming distance exactly t from the input; the paper focuses on t<k/2 and excludes k=2t, where reconstruction is impossible.For k=2t, the exact-t spheres around a sequence and its complement coincide.Source: B. System Setup and Channel Model · p. 2

C. Majority-Vote Decoder and Known Results

For the exact-t channel, the paper distinguishes the minimum observation threshold for any decoder from the majority-vote threshold and establishes that majority-vote is not worst-case optimal. It also reviews the decoder’s bitwise rule and its optimality in the classical up-to-t setting.

C. Majority-Vote Decoder and Known Results

  • Bit-wise majority-vote decodes each position from its most frequent observed value, with ties treated as erasures; the paper assumes odd N≥3.Position j is correct when its error-column sum c_j is less than N/2.Source: C. Majority-Vote Decoder and Known… · p. 2
  • In the classical up-to-t binary setting, Levenshtein showed that majority-vote achieves the minimum observation bound, so no decoder can guarantee reconstruction with fewer observations.The cited work derives the bound for a q-ary alphabet, whose expression simplifies for binary sequences.Source: C. Majority-Vote Decoder and Known… · p. 2
  • For exact-t errors, N_maj denotes the majority-vote worst-case threshold, distinct from N_wc, which is reserved for the best possible decoder.The exact-t threshold for majority-vote does not exceed the classical up-to-t threshold, and is strictly lower when t≥2.Source: C. Majority-Vote Decoder and Known… · p. 2

III. MAJORITY-VOTE DECODING: GUARANTEES AND LIMITATIONS

  • For t≥2, the exact-t worst-case reconstruction threshold N_wc is strictly below the majority-vote guarantee N_maj.The section identifies N_wc as the minimum number of observations required by any decoder for guaranteed reconstruction.Source: C. Majority-Vote Decoder and Known… · pp. 2–3, §III · p. 3, Table I · p. 3
  • The section also derives an error-detection property that can verify correct reconstruction without knowing the transmitted sequence.This property supplies a sufficient condition for confirming reconstruction.Source: §III · p. 3

A. Worst-case reconstruction guarantee threshold

The worst-case reconstruction threshold is governed by the largest set of outputs consistent with two distinct candidate sequences. Between that threshold and the majority-vote guarantee, unique reconstruction is possible for an optimal decoder even though majority vote may fail.

A. Worst-case reconstruction guarantee threshold

  • Unique reconstruction is guaranteed exactly when the number of observations exceeds the largest ambiguity-set size over all pairs of distinct candidates.If every observation belongs to an ambiguity set for a candidate pair, those candidates cannot be distinguished; exceeding the largest such set rules out that ambiguity.Source: A. Worst-case reconstruction guarantee… · p. 3
  • An ambiguity set contains outputs at distance t from both candidates; for candidates differing in 2d coordinates, each such output differs from each candidate in d coordinates there and t−d elsewhere.The supplied proof states that no such output exists when d > t.Source: A. Worst-case reconstruction guarantee… · p. 3
  • For Nwc ≤ N < Nmaj, an optimal decoder guarantees unique reconstruction, but majority vote may fail; the gap exists only for t ≥ 2.For t = 1, Nwc = Nmaj = 3.Source: A. Worst-case reconstruction guarantee… · p. 4
  • The Nmaj−Nwc gap grows with t and, for large k, approaches Nwc as t approaches k/2.The supplied excerpt identifies fixed k = 20 as an example setting for the gap but does not provide its table values.Source: A. Worst-case reconstruction guarantee… · p. 4, Table II · p. 4

B. Error detection and termination of bit-wise majority-vote decoding

A majority-vote output can be checked against the exact-t channel constraint: if it is at distance t from every observation, it is the transmitted sequence. This test can permit early termination below Nwc, while Nmin and Nmaj delimit when success is possible and guaranteed.

B. Error detection and termination of bit-wise majority-vote decoding

  • If the majority output is at distance t from every observation, it equals the transmitted sequence, even for odd 1 < N < Nmaj.The distance test is necessary for every decoder; the theorem makes it sufficient for majority vote, including when N < Nwc.Source: B. Error detection and termination of… · pp. 4–5
  • As t approaches k/2, Nmin grows, so more observations are needed before majority-vote success is possible.The paper also reports Monte Carlo estimation of the first output count N* at which the early-termination rule is triggered.Source: B. Error detection and termination of… · p. 5, Figure 1 · p. 5
  • For k = 10 and t = 2, Nmin = 2, while for k = 10 and t = 4, Nmin = 5; thus three observations may suffice in the first case but cannot suffice in the second.The cited examples give Nwc = 17 and Nmaj = 19 for t = 2, and Nwc = 113 and Nmaj = 169 for t = 4.Source: B. Error detection and termination of… · p. 5
  • For Nmin ≤ N < Nmaj, success is possible but not guaranteed; below Nmin it is impossible, and at or above Nmaj majority-vote success is guaranteed.The early-termination condition detects success in the intermediate regime.Source: B. Error detection and termination of… · p. 5

C. Counting majority-vote failures at t = 2, N = Nwc

For t = 2 at N = Nwc, this section counts the output-sets where bit-wise majority-vote fails. It derives a closed-form count and extends the analysis toward t > 2.

C. Counting majority-vote failures at t = 2, N = Nwc

IV. WEIGHTED MAJORITY-VOTE DECODERS

The section proposes a low-complexity weighted majority-vote decoder to exploit the exact-t structure. It aims to reduce the observations needed relative to bit-wise majority-vote, with a modest increase in complexity.

IV. WEIGHTED MAJORITY-VOTE DECODERS

  • The weighted majority-vote decoder aims to reconstruct with fewer observations than bit-wise majority-vote by exploiting the exact-t structure.The proposed reduction is an aim, not a stated guarantee of achieving Nwc.Source: §IV · p. 7
  • The decoder processes bits in an order chosen by reliability and carries information from previously decoded positions.The paper analyzes the correctness of its first decision before presenting the ordering and construction.Source: §IV · p. 7
  • The decoder’s performance against bit-wise majority decoding is evaluated by exhaustive search where feasible.The evaluation is numerical.Source: §IV · p. 7

A. Error Budget Tracking and Weights

The decoder tracks each output’s remaining error budget as it processes columns, using that estimate to weight later votes. It checks the final estimate against the exact-t channel constraint.

A. Error Budget Tracking and Weights

  • The decoder processes columns in an order and carries information from previously decided positions into weighted votes on later columns.The first step uses identical weights, so weighting takes effect from the second step onward.Source: A. Error Budget Tracking and Weights · p. 7
  • After each decision, the remaining error budget estimates how many errors an output must still contain among the undecoded columns.If previous decisions are correct, this estimate equals the true number of remaining errors.Source: A. Error Budget Tracking and Weights · p. 7
  • Outputs with smaller remaining budgets are treated as more reliable, and the decoder assigns weights based on the difference between correct and erroneous entries.The weight is positive when correct entries outnumber errors, negative when errors outnumber correct entries, and zero when they are balanced.Source: A. Error Budget Tracking and Weights · p. 7
  • The decoder accepts its estimate only if every output is at Hamming distance t from it; that condition is necessary for any correct decoder and sufficient when N ≥ Nwc.The condition supports checking a reconstruction without knowing the transmitted sequence.Source: A. Error Budget Tracking and Weights · p. 7

B. The First Decision

The first decision uses ordinary majority-vote because all weights initially match. The section analyzes when this decision is correct and reports empirical support for the designed algorithm’s sufficiency.

B. The First Decision

  • Lemma 5 gives a condition under which the first position, selected for decoding, is decoded correctly by majority-vote.The supplied statement of the condition is incomplete, so its threshold is not reported here.Source: B. The First Decision · p. 8
  • For t = 2 and N = Nwc = 2k − 3, the highest-reliability column is decoded correctly by majority-vote.This is stated for t < k/2.Source: B. The First Decision · p. 8
  • Whether Lemma 5’s inequality suffices for the designed algorithm to decode all positions remains unresolved, though Table III offers empirical support.The table also gives limited evidence that the inequality is tight: at N = Nwmaj − 1, some output-sets defeat the proposed algorithm.Source: B. The First Decision · p. 8

C. Decoding order

The decoder orders columns by decreasing reliability, using the absolute vote as the reliability measure, so more confident decisions update error budgets before less reliable ones. Reliability ties can affect decoding, motivating backtracking; the resulting decoder's broader guarantees remain conjectural.

C. Decoding order

  • Decreasing reliability order decodes the most confident columns first, so their decisions update error budgets before less reliable columns are processed.Reliability is quantified by the absolute value of each undecoded position's vote.Source: C. Decoding order · p. 8
  • When reliabilities tie, column order can change whether the decoder makes a correct decision, as the k = 5, t = 2 example demonstrates.With the same reliability-degenerate group, decoding column 1 next yields an incorrect decision, while choosing columns 2, 3, or 4 yields a correct one.Source: C. Decoding order · pp. 8–9
  • Backtracking revisits reliability-degenerate tie choices after specified failures and declares failure only when no unspent ties remain.The listed triggers include budget-constraint violations, termination that violates Remark 1, and a zero vote.Source: C. Decoding order · p. 9
  • The authors conjecture that Algorithm 1 decodes uniquely when N ≥ max{Nwc, Nwmaj} and whenever bit-wise majority decodes uniquely.These claims arise from exhaustive evaluation of admissible inputs for k ∈ {5, 6, 7, 8, 9} and t ∈ {2, 3}, where feasible; they remain unproved.Source: C. Decoding order · p. 9
  • Whether any efficient decoder guarantees unique reconstruction with Nwc outputs remains open.The section delimits where the weighted approach reaches the threshold and where it does not.Source: C. Decoding order · p. 9

V. CONCLUSION

For the exact-t channel, the paper characterizes the worst-case unique-reconstruction guarantee and finds bit-wise majority vote suboptimal. It also gives an early-termination rule and a weighted-majority decoder whose numerical results support, but do not prove, a lower observation requirement.

V. CONCLUSION

  • The paper characterizes the exact-t channel's worst-case unique-reconstruction guarantee and shows bit-wise majority vote is suboptimal in this setting.The paper also devises an early-termination rule for majority vote, including when fewer than the worst-case required observations are available.Source: §V · p. 9
  • The weighted-majority decoder exploits error correlations to try to improve the unique-reconstruction threshold, with a modest complexity increase.Its numerical performance supports the conjecture that it lowers the number of observations required for worst-case reconstruction, but the claim is presented as a conjecture.Source: §V · p. 9

AI STATEMENT

The authors used Claude to assist with code efficiencies for exhaustive enumerations in Table III and the Monte Carlo simulation for Fig. 1.

AI STATEMENT

  • Claude assisted in finding code efficiencies for Table III's exhaustive enumerations and the Monte Carlo simulation used to generate Fig. 1.This assistance is reported in the paper's AI statement.Source: AI STATEMENT · p. 9
Loading 2610.30001v1…