Trace reconstruction with varying deletion probabilities

In the trace reconstruction problem an unknown string x = (x₀, . . ., x_n−₁) ∈ {0, 1, ..., m − 1}ⁿ is observed through the deletion channel, which deletes each x_k with a certain probability, yielding a contracted string X . Earlier works have proved that if each x_k is deleted with the same probability q ∈ [0, 1), then exp(O(n¹/³)) independent copies of the contracted string X suffice to reconstruct x with high probability. We extend this upper bound to the setting where the deletion probabilities vary, assuming certain regularity conditions. First we consider the case where x_k is deleted with some known probability qk. Then we consider the case where each letter ζ ∈ {0, 1, ..., m − 1} is associated with some possibly unknown deletion probability qζ.