Trace reconstruction with varying deletion probabilities
Trace reconstruction with varying deletion probabilities
复制标题
具有不同删除概率的迹线重建
DOI：
10.1137/1.9781611975062.6
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Y. Peres
中科院分区：
文献类型：
--
作者：
Lisa Hartung;N. Holden;Y. Peres
在迹重构问题中，未知字符串${\bf x}=（x_0，\dots，x_{n-1}）\in\{0，1，...，m-1\}^n$是通过删除通道观察到的，它以一定的概率删除每个$x_k$，产生一个收缩的字符串$\widetilde{\bf X}$。早期的工作已经证明，如果每个$x_k$以相同的概率$q\in[0，1）$被删除，则压缩字符串$\widetilde{\bf X}$的$\exp（O（n^{1/3}））$独立副本足以以高概率重建$\bf x$。假设某些规律性条件，我们将此上限扩展到删除概率变化的设置。首先，我们考虑的情况下，$x_k$被删除，以某种已知的概率$q_k$。然后我们考虑每个字母$\zeta\在\{0，1，.，m-1与某个可能未知的删除概率q\zeta$相关联。
In the trace reconstruction problem an unknown string ${\bf x}=(x_0,\dots,x_{n-1})\in\{0,1,...,m-1\}^n$ is observed through the deletion channel, which deletes each $x_k$ with a certain probability, yielding a contracted string $\widetilde{\bf X}$. Earlier works have proved that if each $x_k$ is deleted with the same probability $q\in[0,1)$, then $\exp(O(n^{1/3}))$ independent copies of the contracted string $\widetilde{\bf X}$ suffice to reconstruct $\bf 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 $q_k$. Then we consider the case where each letter $\zeta\in \{0,1,...,m-1\}$ is associated with some possibly unknown deletion probability $q_\zeta$.