Erratum: LOWER BOUNDS FOR TRACE RECONSTRUCTION (Ann. Appl. Probab. (2020) 30 (503-525) DOI: 10.1214/19-AAP1506)

Lemma 3.1 asserts that Eyn [Z(yn)]. Exn [Z(xn)] = Θ(n-1/2) and Eyn [Z(yn)] > Exn [Z(xn)] for all sufficiently large n. Our proof was not correct: As Benjamin Gunby and Xiaoyu He pointed out to us, we missed four terms in the computation of equation (3.3). Those terms contribute a negative amount, so the proof is more delicate. Here is a correct proof. The intuition behind the result is that a string with a defect of the type we consider, namely, a 10 in a string of 01's, is likely to cause more 11's in the trace than a string without the defect. Since the defect in yn is shifted to the right as compared to the defect in xn, the defect of yn is slightly more likely to "fall into"the test window {⌈2np + 1⌉, ⋯, ⌊2np + √npq⌋} of the trace than is the defect of xn. More precisely, the difference in probability is of order n-1/2. In the proof below, we make this intuition rigorous. PROOF. We assume throughout the proof that k ∈ {⌈2np + 1⌉, ⋯, ⌊2np + √npq⌋}. Let E(m, k) denote the event that bit m in the input string is copied to position k in the trace. First observe that 'Equation Presented' and 'Equation Presented'. Note that the string xn centered at m is identical to the string yn centered at m + 2, except for two bits at the ends. Therefore, for every m ∈ {k, ⋯, 3n}, we have 'Equation Presented' where o∞ (n) denotes something nonnegative that decays at least exponentially fast in n. Combining this with Pxn [E(m, k)] = o∞ (n) for m < k + 2 or m > 3n yields 'Equation Presented' Setting am: = qp/(1 - q2) = q/(1 +q) if m is even and am: = 0 otherwise, we see that 'Equation Presented' Subtracting this from the previous display gives 'Equation Presented' The second factor in the above summand, modulo an additive error of o∞ (n), represents the difference in probability of the event xk = xk+1 = 1 given E(m, k) for the string xk as compared to a string without any defect. It takes the following explicit form: 'Equation Presented' where ≈ means that we incur an additive error of ±o∞ (n). Now let j0 be a sufficiently large positive integer that 'Equation Presented' Note that j0 depends on q but can be chosen so that it does not depend on n. We suppose in the rest of the proof that n > j0. By (E.1) and (E.2), 'Equation Presented' For m ∈ {2n - 2j0, ⋯, 2n + 2} and with ξ: = k - 2np, we have 'Equation Presented' because for m ∈ {2n - 2j0, ⋯, 2n}, 'Equation Presented' the same result holds for m ∈ {2n + 1, 2n + 2} by a similar estimate. Combining (E.2) and (E.5), we get that the right-hand side of (E.4) is equal to (E.6) 'Equation Presented' Summing the left-hand side of (E.4) over k ∈ {⌈2np + 1⌉, ⋯, ⌊2np + √npq⌋} and using the last display along with Pxn [E(2n, k)] = Θ(n-1/2) and (E.3), we get the lower bounds in the lemma, namely, Eyn [Z(yn)] - Exn [Z(xn)] = Ω(n-1/2) and Eyn [Z(yn)] > Exn [Z(xn)]. It remains to prove the upper bound, namely, Eyn [Z(yn)] - Exn [Z(xn)] = O(n-1/2). Let bm,n denote the absolute value of the right-hand side of (E.2). By (E.1) and (E.2), we have 'Equation Presented'. Now sum over k; (2.7) of Lemma 2.2 yields Σk| Pxn [E(m + 2, k)] - Pxn [E(m, k)]| = O(m-1/2) = O(n-1/2). In addition, Σm bm,n = O(1). Combining these bounds, we arrive at the upper bound of the lemma. □We remark that one can get a more precise bound in (E.6) that gives something positive for all q ∈ (0, 1) simultaneously by not truncating the sum on the right-hand side of (E.1) and by using a more precise version of (E.5). The result, in fact, gives lower and upper bounds for the left-hand side of (E.4) of the form 'Equation Presented'. Finally, we note that in the proof of Proposition 1.4 on page 519, the definitions of X and Y should be slightly modified: c should be √c both times.