论文标题
shot弹枪标识
Shotgun identification on groups
论文作者
论文摘要
我们考虑了shot弹枪在组上识别模式的问题，这扩展了先前在shot弹枪识别DNA序列和标记图的工作。组$ G $上的shot弹枪标识问题由两个有限的子集$ c \ subset g $和$ k \ subset g $和一个有限的字母$ \ mathcal {a} $指定。在此类问题中，在\ Mathcal {a}^{ck} $中有一个``全局''模式$ w \，并且一个人希望仅基于``$ k $ w $'$ k $ w $的$ k $形式的$ w $ nefly of $ c $ c $ c $ c $ c $ c $ copters n o local``本地''local'$ k $ w $的观察而能够识别这种模式（到翻译）。我们认为是渐近制度，其中$ w $倾向于无穷大，$ w $的符号是在i.i.d中绘制的。时尚。我们的第一个总体结果建立了足够的条件，在该条件下，随机模式$ W $可以从其读取中识别为概率，而我们的第二个一般结果则建立了足够的条件，在该条件下，随机模式$ W $不可识别，并且概率趋向于一个。此外，我们通过将它们应用于几个示例家庭来说明我们的主要结果。
We consider the problem of shotgun identification of patterns on groups, which extends previous work on shotgun identification of DNA sequences and labeled graphs. A shotgun identification problem on a group $G$ is specified by two finite subsets $C \subset G$ and $K \subset G$ and a finite alphabet $\mathcal{A}$. In such problems, there is a ``global" pattern $w \in \mathcal{A}^{CK}$, and one would like to be able to identify this pattern (up to translation) based only on observation of the ``local" $K$-shaped subpatterns of $w$, called reads, centered at the elements of $C$. We consider an asymptotic regime in which the size of $w$ tends to infinity and the symbols of $w$ are drawn in an i.i.d. fashion. Our first general result establishes sufficient conditions under which the random pattern $w$ is identifiable from its reads with probability tending to one, and our second general result establishes sufficient conditions under which the random pattern $w$ is non-identifiable with probability tending to one. Additionally, we illustrate our main results by applying them to several families of examples.
