#### Vol. 14, No. 4, 2021

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Shotgun identification on groups

### Jacob Raymond, Robert Bland and Kevin McGoff

Vol. 14 (2021), No. 4, 631–682
##### Abstract

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,K\subset G$ and a finite alphabet $\mathsc{𝒜}$. In such problems, there is a “global” pattern $w\in {\mathsc{𝒜}}^{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 1, and our second general result establishes sufficient conditions under which the random pattern $w$ is nonidentifiable with probability tending to 1. Additionally, we illustrate our main results by applying them to several families of examples.

However, your active subscription may be available on Project Euclid at
https://projecteuclid.org/involve

We have not been able to recognize your IP address 54.80.252.84 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

or by using our contact form.

##### Keywords
identifiability, shotgun identification
Primary: 60C05
Secondary: 94A15